狗狗12/11实习面经

原帖地址:一亩三分地

今天等了不耐烦了,心想跪就跪吧, 就发了一份催一下, 结果半小时后收到hr说过了。现在才敢贴面试题。 因为问题简单了一点怕被鄙视。。。两轮都是google research的人面的所以算法问的可能简单点。

第一轮, 国人大哥, 并且认识我phd导师(心中窃喜, 原来我导师那么有名)。 随便聊聊后,开始问第一题, tree的 in-order traversal 你会嘛? (再喜 ,认识我导师也不用那么放水吧)。 答: recursive 和 iterative 都可以你要哪个? recursive就行, 好瞬间结束。 warm-up结束, 然后问如果两棵树你怎么判断是不是有一样的中序遍历,答:分别扫一遍然后compare一次。 再问,如果一颗很大一颗很小会有神马问题。 答:浪费时间。 追问, 你该怎么办? 然后我突然就傻了, 死活写不好。大哥给hint说, 两颗一起recursive行不行。 行, 写完。 然后大哥让我跑个最简单例子,发现我的算法不对, 心想跪了。。。,已经半个小时过去了,这都答不出来。 大哥鼓励说恩这题不简单你再修改修改你recursive试试看。 死活还是失败。 最后还有10分钟不到了, 我脑抽终于好了, 说我们不写recursive了吧, 写iterative对应一一比较就好了。其实写完还超时了,大哥,让我快速跑下case和说下复杂度就结束了。

第二轮, 反正不是国人和烙印。 上来啥也么有聊开做题。 crossproduct: 就是给 {“ab”,“c”} {“de”}{“eg”, “f”} 返回出{“abdeeg”,”abdef”,”cdeeg”,”cdef”}就是把每个set的元素练到后面所有set的element前面。具体点假设有3个set分别有M,N,K个元素那么最终就返回MNK个元素的一个set. 两两一做加for loop 搞定。 第二题, 问给一排不等关系式比如 a>b, f>c, b>e这样的, 然后给你两个元素 比如 a,e问他们是否存在 不等关系。 建立graph, 然后BFS/DFS即可。 其中问了很多假设比如会不会存在a>b, b>a情况, 给的元素会不会没有出现过神马的。 假设都不回的话, 就是一个有向无回路图。 然后我自作聪明说, 哈因为无回路不需要再来一个set或者变量来记录有没有访问过,因为算法一定会结束。 面试官想了想说, 恩对的, 但算法复杂度会怎么样。 O(V) 或O(E)? 看用BFS还是DFS。 面试官想了想说 I don’t think so。心想完了又要跪了。面试官耐心给了一个例子,才反应出来即使无环还是会exponential的复杂度出现的。结束后问我有问题吗?我就随口问了一句你们工业届做deep learning东西啊, 目前数学理论保证那么差,你们care嘛?然后他突然说话停不下来了,超了10多分钟说。其实我英文不好没有听懂太多,反正大意就是 good question, 我们非常需要数学。

大概就这样吧,反正面试我犯了很多错误,也算是运气比较好才过了。 可能当中的交流也是非常重要的。犯错不怕, 能体现出你能从错误中快速更正和学习还是能弥补回来的。

求team match!!!