发信人: repeat112 (windfantasy), 信区: JobHunting
标 题: 微软onsite面试悲剧，附面经并求分析，多谢~
发信站: BBS 未名空间站 (Thu May 8 18:31:09 2014, 美东)
一周之内面了微软两个组，刚刚收到结果双双悲剧，一个组的HR说It's a tough call
，另一个组的HR说very close，不知道是不是套话，总之很沮丧……来版上求问一下大
家问题可能出在哪，并且附上大概的面试过程和coding题目。
第一组：
第1轮：是一个SDE II，看名字像是中东人。coding题目是给定2棵树，判定是否其中一
棵是另一棵的subtree，同时用了DFS和BFS，写完code讨论了几个testcases和复杂度就
结束了。
第2轮：一个白哥Senior Lead，问的题目是一个maze（用2D matrix表示，有的坐标上
有障碍），给定起点和终点，找出从起点到终点的path，还是用的常规的DFS解法，搜
索过程排除有障碍的和访问过的坐标。
第3轮：一个小黑Lead II带去一起lunch，午饭之后问了大概半小时设计题，设计当软
件窗口（比如Word窗口）大小变化的时候每个子图标栏的大小如何变化，大概定义了一
下各个class，挑了其中一个function写了code。
第4轮：一个三哥Principle Lead，先问了一个ASCII和Kanji字符混合的数组，问how
to do a backspace，就是给一个index，如何找到上一个字符的起始index，因为ASCII
字符是1byte，Kanji字符是2bytes，要确定往回跳一步还是两步。这题之前面过知道答
案，跟三哥分析了一通也没要求写代码就算过了。又问了一题spiral matrix是
Leetcode原题，直接写完code试了几个testcase搞定。
第5轮：没在schedule上，跟老大见面。主要是聊天，就问了一个小游戏的设计。
总结：基本上都算顺利，写code过程中有一两个小bug，自己发现了改过来了。答白哥
的题因为code排版有些乱，一开始没看明白，解释了之后白哥表示this should work。
最后和老大谈的时候因为紧张犯了点小错误，老大指出之后很快改过来了。HR一直跟我
说hard decision，tough call，说了半天也没弄明白到底被拒的原因是什么……
第二组：
第1轮：中国人Senior Lead，问了2个题都没见过，面试官说是他自己临时想的……一
道题考树，给定一个结点，怎样不修改parent-child relationship让给定结点在most-
left path上，总之就是自底向上依次把给定结点放到最左边吧。第二题有点像十字链
表，要求遍历所有的结点形成一个单链表，搞了半天没明白题意，写了半天code面试官
看不下去了，提醒了我之后才做出来。
第2轮：一个俄国人SDE II，问的题目差不多算是Leetcode原题，就是Binary Tree
Maximum Path Sum做了点变形，The path may start and end at any node。但是要求
的不是path上的数值之和，而是path长度（也就是path上结点个数减去1），把所有结
点的值看成1就可以等价过去。
第3轮：Senior SDE，看名字像是香港人。问了binary tree（满二叉树）的遍历，按顺
序打印：从上到下每一层的最左结点，从左到右所有的leaf结点，从下到上每一层的最
右结点。先问能否用extra space，面试官说可以，于是就用BFS存下来每一层的结点（
参考Leetcode原题Binary Tree Level Order Traversal），然后按要求打印。又问不
用extra space如何，我用preorder traversal加checking可以打印出第一步和第二步
，第三步好像preorder解决不了。时间到了就没再继续。
第4轮：Senior SDE，一个国人姐姐。人很nice，题目也不难。一道Leetcode原题
Construct Binary Tree from Preorder and Inorder Traversal，另一道面经上有过
，就是找出两个Linked Lists Converge的node。
第5轮：三哥Senior Lead，上来还是先问那道ASCII和Kanji字符的题，因为在版上听说
过因为重复题目没跟面试官说被拒的，就告诉三哥说已经问过，第二题问树结点的
common ancestor，这题电面时候的三哥就问过，真不知道是不是故意重复问的。告诉
他之后又问了一题，稍微有点复杂：假设一个电话键盘，按键是1, 2, 3, 4, 5, 6, 7,
8, 9, *, 0, #，要求返回所有valid电话号码的个数。条件是：1. 只能从1-9里选一
个数开始，2. 每选择一个数，下一个数只能像国际象棋里的knight那样跳（听三哥的
解释应该是和中国象棋的马一个跳法）。没什么好方法，只能DFS统计valid号码个数，
过程很复杂。好不容易写完了，三哥问有简单方法不，我说暂时只能想到常规方法，三
哥说可以用DP，我说这么一会推出transition方程有点难，时间到了三哥也没继续问。
第6轮：还是见老大，schedule上没有的。纯聊天，没考题目。
总结：没被问到设计题，算法题都解出来了，虽然有些题给的不是最优解法但至少得到
面试官的肯定是work的。HR的说法是very close，feedback也是nothing bad，就是认
为我design方面lack experience。我就郁闷了，一个设计题都没问，怎么评判我缺少
design经验的，猜想是被三哥黑了吧……
面试情况就是这样，请大家看看是哪里出了问题。本来听微软的朋友说基本上最后老大
出面了就说明有戏，还挺憧憬能有个offer的，没想到却是全跪的结果，实在是太沮丧
了……
---------------------------UPDATE------------------------------
把我的解题过程贴过来。Leetcode原题就忽略了。
第一组：
第1轮：判断subtree。假设两棵树T1和T2，先用DFS在T1里找到和T2的root一样的结点
，然后从找到的结点开始和T2进行比较，我用了BFS，就是用queue，一边一个queue，
同时push/pop进行比较，如果碰到不一样的就return false。做完了想起来其实就是
Leetcode上的Same Tree，直接还用DFS递归比queue省事。
第2轮：找出maze中的path。开一个matrix标记maze的每一个点是否访问过，然后DFS搜
索，从起点开始，查找它的上下左右邻居，如果没有访问过也没有obstacle，就作为一
个选择进行下一步搜索，一直递归下去直到找到终点为止。
第3轮：设计题。
第4轮：ASCII和Kanji字符的题以前面过，当时没做出来，答案就是回来网上搜的（参
考这个网址http://discuss.joelonsoftware.com/default.asp?interview.11.334807.4）。Spiral Matrix是Leetcode原题就不说了。
第二组：
第1轮：移动树结点的题说过了，就是自下往上依次把结点移到最左边，因为面试官给
了parent指针，就是一个while循环一层一层往上。链表题我说明一下，就是链表其实
是一个2D矩阵，每个结点有right和down两个指针，就是简单的先向右遍历，然后把最
右结点链接到下一层的最左结点上，这样完成遍历所有结点。
第2轮：Leetcode原题。
第3轮：我给的解法是参考Leetcode原题的，面试官说这样解也可以。
第4轮：preoder和inorder创建树是Leetcode原题。链表converge就是先统计两个链表
分别的长度，对于长的链表，长几步就把指针前移几步，然后两个指针同时往前走，一
直到两个指针相等就是converge的点。
第5轮：找出valid号码个数，就是正常DFS，从一个数开始，写一个函数用来统计下一
步可以往哪跳才valid，然后再从valid的地方继续DFS下去。DP解法没来得及想出。
--
※ 修改:·repeat112 於 May 8 23:54:04 2014 修改本文·[FROM: 71.]
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 71.]
Monday, June 9, 2014
微软onsite面试悲剧，附面经并求分析，多谢~
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment