狗家MTV 11/19昂塞

第一轮

上来先问给两个sorted list,按照所有大小顺序顺序做一个iterator, 2 pointers秒。
然后follow up问里面有很多duplicate但是只允许return一个怎么办, 把pointer的update rule改了一下。
第三问又问如果有多个包含重复的sorted list呢。我提了可以用heap存所有list然后平均每次next要log(k)时间, 或者把他们merge到一起(蠡口儿时三),但楼主一直在想iterator所以说给heap的做法。还因为时间不够没写完。

另外提一句现在谷歌会给每一个面试者一个表记录每一轮面了什么,然后第二轮面试官一上来看了表就问“啊你上一轮问的merge sorted list是吧?”我才知道可能他真的是想问蠡口儿时三原题 。这一轮没发挥好,一开始时间有点浪费太多了,也没有好好把握面试官给的hint。

第二轮

蠡口遗留尔变形,binary search秒了。然后问了binary tree traversal的方式和stack上要求的时间空间复杂度。面试官是做计算机视觉的,后面剩的时间不少聊了很多他的project。

午饭。一个ABC姐姐带我在面试旁边一栋楼吃的,狗家东西是真的难吃,但当时特别饿也特别累了所以还是吃了不少(真香! )。吃完在面试房间外面椅子上休息了十来分钟回血。

第三轮

面试官没来,开hangout远程。汇率变种BFS做。讨论了一下各种edge case花了不少时间,最后写完test完就没其他时间了。不知道这个算不算太慢了(捂脸)。

晚上睡到床上才想起来写了个bug,在加visited的时候顺序不对,不影响正确性但有些情况可能会慢,做的时候面试官没有提醒我只让我跑test,希望面试官网开一面

第四轮

把一个list里面的dirty number去掉,dirty number由另一个给的method判定。先用两个pointer一般遍历一边swap最后return index的传统做法,面试官不太满意。然后在加了一步得到index后删掉后面的所有数,面试官满意。

后面的题都没写代码。先是问一个array需要从1-15中间generate五个不重复random number怎么做最好,我说用一个array然后遍历每一位与array里任意随机位做swap然后取前五位。. 1point3acres

然后问现在define一张卡片为5*5的matrix然后每一个column都需要做五个不重复random number但他们的取值域不重合(1-15, 16-30, 31-45, etc),现在要generate N张卡片所有column不能重复,该怎么做。我先说了一个沿用蠡口流失(或者next permutation?)的思路,说可以把十五个数选五个的所有permutation编号(比如 1,2,3,4,5 就是第0个permutation,1, 2, 3, 4,7 是第2个)然后根据编号的值域随机选五个(可重复)然后根据每个column对应的值域放数上去,他说这个解法没见过,但中间数学太多了,换一个想法。

在他引导下我们得出结论,直接每张都用老办法generate五个column然后check duplicate不i行就重新generate(在N远小于所有combination总数的情况下这个不会太慢),然后关键点在于缩短check的时间。我提出了用trie来check duplicate (将column里面的数字就像一个string里面的char一样插入trie) 这样的话check duplicate永远O(1)时间。面试官将信将疑看了半天最后还是决定这个是对的。我试探性的问他脑中的最优解是啥,他说规定不能说,但我的解法是个好解法。

关于这题还有什么好的办法欢迎大家讨论!

总体说来第一轮不太满意,第三轮有小bug, 希望能有hc!自己的问题还是代码量稍微大一点写白板速度就跟不上,然后有的时候没有好好考虑面试官的建议,这些以后都要注意一下。

然后扯一点感(ji)想(tang),onsite面试,尤其带travel的,最重要的事还是吃好饭睡好觉。楼主失眠很严重,长期处于晚上睡不着白天没精神只能靠食物和药物调节的恶性循环,经常在面试前紧张睡不好,又不敢用药物害怕影响第二天专注度,于是睁眼到天亮面试。拿到昂塞之后觉得还是要调节自己的状态,强行戒掉了一切助眠药物和咖啡因饮料,改变了饮食作息习惯,这些远比刷题痛苦。最终成功在面试前一晚在MTV的森林灰中安稳地睡了一觉

祝大家面试顺利

请问第四轮的check为什么不能直接用hashset?

楼主说得太详细了,好评已!祝好运哈

对的应该用hash的当时想的太复杂了居然连这个都没想到

不慌,我觉得你面的挺好的