刚跪的电面 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

刚跪的电面

刚跪的电面# JobHunting - 待字闺中

I*a2015-08-24 07:08

1 楼

1. strstr
2. find first K most frequent number
都是老题，但第二题事先准备时看面经，都是问Kth most frequent number.　解法就
是的HashMap建好，然后quickselect。　O(n).
这里要求first K，　想了半天我说那就整个maxheap,　pop前Ｋ个freq, 再去HashMap
里找，而且考虑到重复频率的可能，还要一个HashSet避免重复频率只找到其中一个元
素。　Code写完，说复杂度太高，让优化，吭哧了半天也没想出咋优化，跪了。。
求大神指点，谢谢！

j*72015-08-24 07:08

2 楼

2.) partial quicksort

J*a2015-08-24 07:08

3 楼

这第二题，keep一个k 大小的min heap也可以吧，扫完以后，把heap里面的元素pop打
印。

p*e2015-08-24 07:08

4 楼

知道了第K个，前K个自然知道了啊

HashMap

【在 I**********a 的大作中提到】

: 1. strstr
: 2. find first K most frequent number
: 都是老题，但第二题事先准备时看面经，都是问Kth most frequent number.　解法就
: 是的HashMap建好，然后quickselect。　O(n).
: 这里要求first K，　想了半天我说那就整个maxheap,　pop前Ｋ个freq, 再去HashMap
: 里找，而且考虑到重复频率的可能，还要一个HashSet避免重复频率只找到其中一个元
: 素。　Code写完，说复杂度太高，让优化，吭哧了半天也没想出咋优化，跪了。。
: 求大神指点，谢谢！

I*a2015-08-24 07:08

5 楼

学习了，谢谢！

【在 j**7 的大作中提到】

: 2.) partial quicksort

I*a2015-08-24 07:08

6 楼

我写的就是这样的，o(nlgk)吧应该是？刚楼上给的解法好像是o(n)+o(klgk）
再问下，找到了freq,回hashmap里找对应元素有什么好办法？

【在 J*********a 的大作中提到】

: 这第二题，keep一个k 大小的min heap也可以吧，扫完以后，把heap里面的元素pop打
: 印。

J*a2015-08-24 07:08

7 楼

lz，这题应该用minheap而不是maxheap吧，

J*a2015-08-24 07:08

8 楼

quicksort返回前K，是不是可以用个pair（freq，num）进行sort，对比freq，最后返
回pair的num。

h*p2015-08-24 07:08

9 楼

返回第k个跟第前k个数是一样的
同样的写法，就是返回值不一样。第k个返回的是一个数，第前k个返回的就是一个数组
如果是quick select，既然你已经找到第k个了，那在array里之前的都已经是小于第k
个的，一起返回就好了。复杂度应该还是线性
LZ这是哪家的题？感觉难度跟类型像是FB的？strstr需要写kmp吗？

HashMap

【在 I**********a 的大作中提到】

f*e2015-08-24 07:08

10 楼

请问，是哪家得？

I*a2015-08-24 07:08

11 楼

我可能名词说的不对吧，我之前准备的找第Ｋ个的算法是只保证前Ｋ－１个是小于第Ｋ
个，后面的都大于第Ｋ个，但是前Ｋ－１个并不见得有序。　所以the Kth != first K
PocketGems
不要求ＫＭＰ

k

【在 h**p 的大作中提到】

: 返回第k个跟第前k个数是一样的
: 同样的写法，就是返回值不一样。第k个返回的是一个数，第前k个返回的就是一个数组
: 如果是quick select，既然你已经找到第k个了，那在array里之前的都已经是小于第k
: 个的，一起返回就好了。复杂度应该还是线性
: LZ这是哪家的题？感觉难度跟类型像是FB的？strstr需要写kmp吗？
:
: HashMap

j*32015-08-24 07:08

12 楼

能站内短我什么公司么？

s*g2015-08-24 07:08

13 楼

第二题用minheap O(nlogk)速度没问题的让你优化的其实是内存面试人如果没有跟你
说输入是sort过的stream 那估计是黑你了 move on吧

HashMap

【在 I**********a 的大作中提到】

x*62015-08-24 07:08

14 楼

首先，如果用Max heap，time complexity最好是nlogn；但如果用min heap, 就可以改
善到nlogk。
其次，没必要pop之后再去map里找，可以建一个包含num和freq的class，然后heap里存
这个class的object，这样pop的时候可以轻易print number
[在 ItachiUchiha (仙人掌) 的大作中提到：]
：1. strstr
：2. find first K most frequent number
：...........

s*a2015-08-24 07:08

15 楼

不理解为什么总面这种毫无实用价值的题。。。你一辈子也用不到这种算法。。。

f*y2015-08-24 07:08

16 楼

第二题应该用Moore Voting algorithm, 时间复杂度O(n), 空间复杂度O(1)

1. strstr2. find first K most frequent number都是老题，但第二题事先准备时看
面经，都是问Kth most frequent numb........

【在 I**********a 的大作中提到】

: 我可能名词说的不对吧，我之前准备的找第Ｋ个的算法是只保证前Ｋ－１个是小于第Ｋ
: 个，后面的都大于第Ｋ个，但是前Ｋ－１个并不见得有序。　所以the Kth != first K
: PocketGems
: 不要求ＫＭＰ
:
: k