首页 > MSRA Intern面经
头像
dogfar
编辑于 2020-08-08 17:40
+ 关注

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~

更多模拟面试

全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐