Google Phone Interview

今天刚面完Google的Phone Interview，第一个面试碰到三姐，就是在Google，命啊。。。
第一题，有一个size为N+1的array，其中的数大小在1和N之间，找其中的Duplicate Number。
我一开始提的方法是用hash map记录，时间复杂度和空间复杂度都是O（N），然后问我能不能优化，我给了个先sort再和前一个element比较的方法，空间复杂度可以降成O（1），但时间复杂度为O（N^2），再问有没有方法能让两者都为O（1）。然后又提了一个Bucket Array的方法，说用0和1记录，但这方法实际其实还是O（N）和O（N）。然后她说可以做下一题。。。（其实之后想了想可以用bits代替。。没办法了。。）

第二题，通过一个URL寻找这个网站所有的URL，这题感觉非常的open。就所有其他信息都没有，就花了很多时间confirm。然后我大概说的是像爬虫那样去做。但最后没有时间完全解释完她就说时间到了。
.
快毕业了，在大学4年里，Google之前一直是我的Dream company，但感觉有点凉。。。Google梦碎了。。。

如果我没理解错的话，第一题array里的abs(数字)-1作为index，然后将该index对应的值变成负的，每一次映射之前都检查是不是负的，是就是dup，这不是LC上的原题么？还是我看漏了东西？

补充内容 (2019-5-21 04:59):
不过时间复杂度O(1)是认真的？

radix_dog 发表于 2019-5-21 00:28
用长数据类型把所有数加一起， 再减去（1+2+3+。。。+N）， 也就是（1+N）*N/2， 得到的数就是那个冗余数？ ...

不是所有1到N的数都要有的，只是说数都在1和N之间（包括），这地方我一开始也理解错了，浪费了一些时间才confirm清楚

最佳应该是时间复杂度O（n）和空间复杂度O（1），当时问的是有没有办法减少两个复杂度

加油楼主，祝你好运！zszszszszszszszszszszszszs

sort 时间复杂度为什么是 n方呢？nlogn 吧? 而且楼主Google可以每年都面呀，没必要觉得梦碎了

不好意思，打错了，是nlogn

ripxdanni 发表于 2019-5-20 17:57
加油楼主，祝你好运！zszszszszszszszszszszszszs

谢谢！

JimLuo 发表于 2019-5-20 18:14
sort 时间复杂度为什么是 n方呢？nlogn 吧? 而且楼主Google可以每年都面呀，没必要觉得梦碎了

不好意思打错了，是nlogn。Google挂了会冻一年吧。。挂了只能看社招有没机会了

冻一年是什么意思

“通过一个URL寻找这个网站所有的URL”，是指已知一個網站的url，然後找這個網頁上顯示的所有url？

O(1) O(1)怎么说？感觉不可能啊