微软面试 | 书脊

微软面试 | 书脊

1. 中年烙印, 一路微笑, 结果找不到面试房间, 上来聊简历, 然后开始做题, Search in Rotated Sorted Array 开始的不得了, 准备开始演戏, 各种聊做法, 各种聊思路, 顺利秒掉, follow up: Search in Rotated Sorted Array II 问run time, 让举例 worst case….这轮感觉不错.
2. 中年烙印, 光头那种..上来不聊简历, 聊项目, 问了一些mysql的基础问题, 比如怎么同步, 怎么rollback. 还问了序列化好像…然后开始做题: max sum subtree 秒了, 然后问path, bfs秒了, 然后问如果是product呢…这个…我想了十分钟, 聊了思路 时间到了…感觉不好, 不过这不是最不好的.
3. 年轻烙印,. 这轮最不好, 上来各种聊简历, 然后看我在做TA, 跟我说,他是普度的算法TA. 然后问我个特别简单的sort singly link list…上来merge sort 解决. 然后follow up, 你会不会用quicksort.. 挂就挂在quicksort了. 也是我没练习到的愿意, 那个partition各种bug..好不容易写完, 最后问复杂度, 还说错了, 因为link list最后的swap pivot的时候, 也要走一遍list….算了..反正就挂这轮了
4. 老年烙印, 看着像老大, 带我屋子一言不发, 我怀疑是不是和前面的面试人吵架了…上来reverse link list.. 然后隔一个reverse一个..都是lc原题…没有开心的聊天, 一直让我问他问题..我从西雅图的天气聊到吃的..最后板着脸走了…
5. 最奇葩的是,我刚出门就进门, 白人manager… 我以为我前几轮早挂了, 加上前一天很晚才到, 困的要死了…结果白人manager拉住, 上来就说我是manager…我靠…我还想上个厕所…都不好意思…..进屋, 直接问我怎么valid bst…秒掉后, 问我能不能不用递归做..能啊..都看到manager了, 还不能…秒了后,说, 我问你一个难点的问题..: 一个lru cache 大小为n, 做PRAM CREW. 就是多线程, 多读单写, 读写双互斥锁.  我老师搞这个的….上来就准备写code..被拉住, 聊思路, 毁了..聊了两个设计都不满意, 反正到最后我也不知道怎么设计好:
   1. 因为lru大小n, n肯定不会很大..所以我第一方案是写时锁整体,读时不锁..这个最naive的思路, 立刻被嘲讽说 太慢.
   2. 第二个方案是多加range 参数, 比如write(x,1,5) 就是写x 锁1-5 block.. 结果被嘲讽说worst case会线程饥渴….

回头问朋友, 朋友说面试被问到了mirror travel…好吧….

Read full article from 微软面试 | 书脊