groupon新鲜面经啊[楼主已悲剧]

molotov 发表于 2012-11-8 11:19
是不是第一题没考虑circle啊

他说了没circle。我也没太听清。难道他说的是有circle?

北美农民 发表于 2012-11-8 08:17
第四题方法3（改进）是啥？ 似乎能想到的就是枚举搜索DP了

都太经典了。。。

见到了这种，面试的时候内心都忍不住得偷着笑。。。然后骂一句，考官你这小样，这也想难倒我。。。

2sum如果枚举就是n^2，排序了再找是n lgn，允许用额外空间hash就是n。

经典题不一定能过

nooneknow 发表于 2012-11-8 11:53
都太经典了。。。

见到了这种，面试的时候内心都忍不住得偷着笑。。。然后骂一句，考官你这小样，这也 ...

严格来说， 只有1对1映射的hash， 也就是查找时间严格的O（1）才能做到O（n）。

这题要做出这样的hash还得看元素大小了。

其实面试的时候， 遇到这种题还是得提高警惕啊， 楼主答了3个方法都没过。。

nooneknow 发表于 2012-11-8 11:53
都太经典了。。。

见到了这种，面试的时候内心都忍不住得偷着笑。。。然后骂一句，考官你这小样，这也 ...

我就是这么答的啊。。。还举例讲解了。。他听的也挺明白的。。。看来还得细心。加多想想测试用例。

同跪了

1、比较好想的一种方案就是先求链表长度，然后在求第（n-k）个结点；不过可以用两个指针。先让前面的指针走到正向第k个结点，这样前后两个指针的距离差是k-1，之后前后两个指针一起向前走，前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点。
2、...
3、...
4、其实最初的想法是排序，然后前后同时夹逼进行计算；不过这个题同样可以设计一个hash来解决

链表问题特别考边界条件的判断。

北美农民 发表于 2012-11-8 14:37
严格来说， 只有1对1映射的hash， 也就是查找时间严格的O（1）才能做到O（n）。

这题要做出这样的hash ...

要是interviewer这么问你，你可以说，theoretically可以证明，hash表的大小合适，也就是负载因子选取得当，hash方法能保证O(1)的存取时间。

面试过程中有很多运气的因素，lz没拿到也不一定是题本身没做好吧。没关系，再接再厉吧。但是经典题肯定是要滚瓜烂熟的。