hedvig电面 至今不知怎么解。。

原帖地址:一亩三分地

上来就问题目,一道简单的秒过。然后问了一道到现在我都没想到解法的。。

题目:有n+1个1到n的数字,找出重复的字符。
可能有多个字符重复,找出其中任意一个就可以。每个字符可能重复2遍以上。
read only,O(1) extra space.

我回答了O(n^2)的brute force解法。然后实在想不到更快的方法了。
要hint他问最快解法是多少,我说O(n),他说中间的呢,我说O(n log n), 他说那就找个O(n log n) 的解法出来。。。

当时想到的解法:
sort,不行,因为是read onlyhash,不行,因为O(1) space用linked list find cycle的方式,也不行,可以找到有重复,可是不知道怎么找具体重复的数值。O(n log n) 就想到了mergesort,每次分一半,然后分别找重复,如果两边都没有重复,merge一步不知道怎么做。
开始怀疑自己智商了。。

面试期间还能听到对面有人在讲话在笑,面试官还离开了一会>.< 现在想到电面都腿抽筋=。=