$4 AMC Theatres® Movie Ticket# Fashion - 美丽时尚
w*a
1 楼
10分钟面经系列,这次是T家。
上次FB二面终于如期收到拒信,move on了。T家的一面希望大家bless啊。
刚开始给我一分钟时间问了我两个behavior问题,一个是我现在在做什么,一个是why
T家。
然后就开collabedit了,就写了一道题。题很简单,板上的XDJM们相信都能秒杀。
给一个多叉树和一个节点,求出这个节点所有path下来的数字的和。比如给出树和节点
4
4
/ \
2 1
\
3
答案就是413+42 = 455。
这个题倒没什么,拿到就问了他需不需要考虑big int的问题,他说不需要,int肯定够
用。那就放心写了。写完之后我怕有bug在纸上反复写各种test验证。他问我干啥,我
就说我在做“单元测试”。他就让我别在纸上画了直接在collabedit上写。我就把他给
的sample用函数流程走了一遍。。
随后就是一系列的follow up。我一开始给的解不是最优解(犯2了,啥也没想上来先用
了vector存所有路径下的数字,最后我逐个相加)。他也没说什么,因为代码本身没问
题,就是跟我说让我说出时间复杂度和空间复杂度。说空间复杂度的时候他就问我能不
能不用vector的,我当时心小凉了一把,立即改掉了,我加了个引用参数来存的sum,
每次sum+=xxx。在C++里用引用用惯了(后面才知道不是好习惯)。他没说什么,问我
现在的空间复杂度是多少,我说O(1),他说真的是O(1)么?我说是O(1)啊。他说如
果考虑递归的stack损耗呢?我说考虑堆栈消耗那就不是O(1)了,如果考虑这点,当这
个树很大的时候,还会stack overflow。他说提到stack overflow,你能说说函数调用
的栈空间耗费在哪里?我说参数压栈需要空间,局部变量要栈空间,栈指针也是。他说
那么如果现在我们考虑堆栈损耗,空间复杂度是多少。我说那就是O(n)了,n取决于递
归深度。然后又追着问我如何测量递归深度。我说在这个程序中递归深度就是当前节点
到最深叶子节点的depth。他说OK,又问了最后一个问题(我上面埋下的祸根)。他说
在并行开发情况下,用引用是会出问题的,让我把引用改掉。我只得立即改成传返回值
回去了。最后他终于说了句“现在看上去很不错了”。
面试题确实很简单,还好也没出bug,除了被他指出有两点需要improve的地方。关于引
用在并行环境下有问题这个真没想到。下次是要注意一下了。平时都是在单线程下编程
,这些地方很少注意到。希望能够拿到二面,求bless。
他最后还问我对概率熟不熟悉,我说我基本不熟悉。他说好那我就不问你了,这个也不
是必要的。当时松了口气哈哈。
PS.这次是打电话的,他说话我听得断断续续的,所以我说了很多sorry,有些关键问题
我让他写下来了。应该不影响吧。我跟他说了是电话线路问题。
上次FB二面终于如期收到拒信,move on了。T家的一面希望大家bless啊。
刚开始给我一分钟时间问了我两个behavior问题,一个是我现在在做什么,一个是why
T家。
然后就开collabedit了,就写了一道题。题很简单,板上的XDJM们相信都能秒杀。
给一个多叉树和一个节点,求出这个节点所有path下来的数字的和。比如给出树和节点
4
4
/ \
2 1
\
3
答案就是413+42 = 455。
这个题倒没什么,拿到就问了他需不需要考虑big int的问题,他说不需要,int肯定够
用。那就放心写了。写完之后我怕有bug在纸上反复写各种test验证。他问我干啥,我
就说我在做“单元测试”。他就让我别在纸上画了直接在collabedit上写。我就把他给
的sample用函数流程走了一遍。。
随后就是一系列的follow up。我一开始给的解不是最优解(犯2了,啥也没想上来先用
了vector存所有路径下的数字,最后我逐个相加)。他也没说什么,因为代码本身没问
题,就是跟我说让我说出时间复杂度和空间复杂度。说空间复杂度的时候他就问我能不
能不用vector的,我当时心小凉了一把,立即改掉了,我加了个引用参数来存的sum,
每次sum+=xxx。在C++里用引用用惯了(后面才知道不是好习惯)。他没说什么,问我
现在的空间复杂度是多少,我说O(1),他说真的是O(1)么?我说是O(1)啊。他说如
果考虑递归的stack损耗呢?我说考虑堆栈消耗那就不是O(1)了,如果考虑这点,当这
个树很大的时候,还会stack overflow。他说提到stack overflow,你能说说函数调用
的栈空间耗费在哪里?我说参数压栈需要空间,局部变量要栈空间,栈指针也是。他说
那么如果现在我们考虑堆栈损耗,空间复杂度是多少。我说那就是O(n)了,n取决于递
归深度。然后又追着问我如何测量递归深度。我说在这个程序中递归深度就是当前节点
到最深叶子节点的depth。他说OK,又问了最后一个问题(我上面埋下的祸根)。他说
在并行开发情况下,用引用是会出问题的,让我把引用改掉。我只得立即改成传返回值
回去了。最后他终于说了句“现在看上去很不错了”。
面试题确实很简单,还好也没出bug,除了被他指出有两点需要improve的地方。关于引
用在并行环境下有问题这个真没想到。下次是要注意一下了。平时都是在单线程下编程
,这些地方很少注意到。希望能够拿到二面,求bless。
他最后还问我对概率熟不熟悉,我说我基本不熟悉。他说好那我就不问你了,这个也不
是必要的。当时松了口气哈哈。
PS.这次是打电话的,他说话我听得断断续续的,所以我说了很多sorry,有些关键问题
我让他写下来了。应该不影响吧。我跟他说了是电话线路问题。