k*****5
发帖数: 25 | 1 我前段时间和Microsoft 三轮电话面试，没有拿到on site，把电话面试中遇到的一些
题说一下，希望对未来的面试者有用。
第一轮: 把binary tree 每一个level的所有节点用linked lists连起来。这道题
leetcode上有，当时还没做过leetcode, 花了挺长时间想算法，剩下的时间不多，写的
code有bugs。
In hindsight, 最后没拿到onsite可能和这一轮的表现有关系。
第二轮: Question 1: 在一个unsorted数组中，如何找到最长连续递增数列， 比如9,2
,5,10,3,7,4，应该返回2,3,4,5, 要求不能够用排序。我回答了一个用hash table的解
法.
Question 2: X台机器，每台机器有Y个数，如何找这些数的median, 要求不能用extra
storage space. 我回答了一个类似quicksort 的partition operation的解法。
第三轮: Question 1: 如何确定一个linked list有circle. 如何reverse一个linked
list.
Question 2: 如果一个linked list 有circle, 如何找到circle的开始节
点。这两道题career cup 150题里面出现过。
Question 3：设计一个自动售货机。 | h********o
发帖数: 2316 | 2 “Question 3：设计一个自动售货机。”这怎么弄？ | m********e
发帖数: 118 | 3 就是实现个dfa
【在 h********o 的大作中提到】
: “Question 3：设计一个自动售货机。”这怎么弄？
| b****u
发帖数: 37 | 4 Question 2: X台机器，每台机器有Y个数，如何找这些数的median, 要求不能用extra
storage space. 我回答了一个类似quicksort 的partition operation的解法。
能讲下怎么用partition operation吗？
,2
extra
【在 k*****5 的大作中提到】
: 我前段时间和Microsoft 三轮电话面试，没有拿到on site，把电话面试中遇到的一些
: 题说一下，希望对未来的面试者有用。
: 第一轮: 把binary tree 每一个level的所有节点用linked lists连起来。这道题
: leetcode上有，当时还没做过leetcode, 花了挺长时间想算法，剩下的时间不多，写的
: code有bugs。
: In hindsight, 最后没拿到onsite可能和这一轮的表现有关系。
: 第二轮: Question 1: 在一个unsorted数组中，如何找到最长连续递增数列， 比如9,2
: ,5,10,3,7,4，应该返回2,3,4,5, 要求不能够用排序。我回答了一个用hash table的解
: 法.
: Question 2: X台机器，每台机器有Y个数，如何找这些数的median, 要求不能用extra
| h********o
发帖数: 2316 | 5 谢谢，查了google没看懂，毕竟不是cs的，呵呵
【在 m********e 的大作中提到】
: 就是实现个dfa
| I*********7
发帖数: 125 | 6 除了设计题，其他都巨简单。。。。为毛我就是碰不到这种面试呢！ | d********r
发帖数: 38 | 7 第二轮: Question 1: 在一个unsorted数组中，如何找到最长连续递增数列， 比如9,2
,5,10,3,7,4，应该返回2,3,4,5, 要求不能够用排序。我回答了一个用hash table的解
法.
这个不排序怎么做？？
,2
extra
【在 k*****5 的大作中提到】
: 我前段时间和Microsoft 三轮电话面试，没有拿到on site，把电话面试中遇到的一些
: 题说一下，希望对未来的面试者有用。
: 第一轮: 把binary tree 每一个level的所有节点用linked lists连起来。这道题
: leetcode上有，当时还没做过leetcode, 花了挺长时间想算法，剩下的时间不多，写的
: code有bugs。
: In hindsight, 最后没拿到onsite可能和这一轮的表现有关系。
: 第二轮: Question 1: 在一个unsorted数组中，如何找到最长连续递增数列， 比如9,2
: ,5,10,3,7,4，应该返回2,3,4,5, 要求不能够用排序。我回答了一个用hash table的解
: 法.
: Question 2: X台机器，每台机器有Y个数，如何找这些数的median, 要求不能用extra
| k*****5
发帖数: 25 | 8 思路类似于寻找Kth smallest element in an array, median of X*Y个数也是寻找X*Y
/2th smallest element. 选一个数，把它叫做pivot, 用pivot 来partition 所有机器
上的数，并统计有多少个数小于等于pivot， 根据这个信息缩小查找的范围 (divide
and conquer)。
extra
【在 b****u 的大作中提到】
: Question 2: X台机器，每台机器有Y个数，如何找这些数的median, 要求不能用extra
: storage space. 我回答了一个类似quicksort 的partition operation的解法。
: 能讲下怎么用partition operation吗？
:
: ,2
: extra
| t******f
发帖数: 79 | |
|
