MSRA Intern面经

拿到offer了，感觉还是蛮轻松的hhh~这样大四上选课和实习都搞定了，暂时不用联系企业啦，现在就看保研的事情了。一共两面，能跟大家分享的有价值信息不多，我想主要还是我的背景比较适合这个项目吧，所以过程比较顺利。

一面先做了一道题，检查一棵二叉树是否是平衡二叉树。这种经典老题大家一定要记优化到极致的方法，不要只贪图OJ过了就过了，我当时就改了好几次才让老师满意。。。不过老师人特别好，这样也放我过了...然后聊了聊项目，最后整体感觉他挺满意的，我也挺意外的（

二面是学长，也比较轻松，先聊了聊项目，然后问了B+树的好处。然后提了一个问题，回答这个问题的过程也是我重点想和大家分享的内容：假设现在有一棵红黑树需要持久化到某个SSD上，SSD的特点是把0写为1容易，把1擦除为0难。这样我们在插入删除时，节点之间可能会发生旋转。每个节点中有一块区域存了parent的地址和child1、2的地址，修改起来不是很容易，问怎么办。一开始我说，每次旋转应该涉及的节点不多，旋转的情况也可以枚举，有无可能设计一种编码方式使得旋转成为可能，他说不可能。然后我愣了一会，他提示我COW，我反应过来可以搞个dirty bit，然后把新块插入到后面，每个dirty块留一个更新后版本的指针。但这样查询可能会变成线性复杂度O（查询次数），然后他又问我怎么办，其实当时我想那就把它所有的祖先都改了，就不要那个后版本指针了，虽然这样可以变为log，但我当时说了马上自我否定了，觉得每次修改都要复制所有的祖先有点离谱...后来答案就是这个。。但还没完，还有一个问题是这样标记为dirty有什么坏处，我说可能会造成内存碎片，他说怎么解决，我当时就蒙了，那可能像OS一样搞个碎片队列集中管理？？或者写个合并算法，定期扫描。最后这个问题就聊到这里，学长说这个其实跟科研的过程有点相似，这个问题我肯定不了解也没想过，但实际上这个问题的做法和改进也是一步步想出来的，然后他说也不要经常自我否定，很多想法一开始看上去其实也很直观、平庸，但其实都是不错的想法。面完以后感觉遇到这种没遇见过的比较有思维含量的问题，我还是有点慌的，可能想到dirty bit的操作比较关键，但也花了一段时间才反应过来。希望大家可以冷静思考，以一种跟老师讨论的心态去思考和交流。大概一个小时后老师就给我打电话说过了~

整体面试体验非常不错，两位老师也很守时，循循善诱，是特别nice的老师。我的另一位同学被问到的算法题是设计LRU，就是双向链表+hash的那个问题，是他先过了然后发给我的招聘信息。很期待在MSRA的工作，然后可能大四毕业或者研究生毕业再回来写面经了hhh~