微软Office印度面试经验| 170套（2年经验）

第一轮： 验证中缀算术表达式字符串（大括号和大括号类似于括号）：（1+2）*{[90*3]-[67+8-9]}

拟建Ans：Djikstra的调车场

面试官的Ans：解析器树

第二轮：

给定一个书架上的书，根据书的任何特定属性对这些书进行分类，例如按字母顺序递增的作者姓名、类别、出版日期等。书的属性的价值必须从外部服务获取，而且调用成本很高。

约束条件：O（1）空间，获取书籍优先级的调用应该尽可能地最小化。

建议的Ans：使用与书的属性相关联的优先级映射进行快速排序，这是一种改进的分区方案，其中每个元素的优先级只提取一次，总共是nlogn调用。

约束变量：最小互换。

提议的Ans：

1.使用O（n^2）时间和O（1）空间进行选择排序n交换

2.具有O（n）空间和时间的桶式分拣0掉期

第三轮：

给定一个很长的字符串和一个变换映射，用它们的结果变换替换所有出现的针字符串，例如。

建议的Ans：一个字符一个字符地处理，如果后缀与任何一根针匹配，则替换后缀，这是一个天真的解决方案。