j****l
发帖数: 85 | 1 才第一轮，感觉面的不太好。leetcode刷了这么多，发现还是不够呀。
面试官感觉是非老美非烙印非老中的外国人，口语很好，略有口音，但是电话音质太差
，整个过程听起来很累。
先让自我介绍，问了最喜欢的project，希望在技术方面讲细一点，但是我的那个
project可讲的细节太多了要讲好久，讲了一会儿感觉他没什么反应，就问说如果感兴
趣我可以更深入讲，他说不用了，挺好，然后开始code题目。
第一道是经典题给很多（millions以上）个点，以（x，y）坐标表示，找出离原点最近
的k个点。k 远小于 n。
开始还想了一会儿，后来想到用priority queue来做，问了时间复杂度是nlogn。面完
后问了一下别人，发现是可以用selection做的，更快。
第二道比较tricky给是一个string和一个alphabet，找出包含所有alphabet的最短的
substring。我的方法是用hashset保存alphabet，读string，每遇到一个字母，就从
hashset里面移除对应字母，最后如果hashset为空则string包含所有字母。在面试官提
示下发现可以试着缩短这个string，再check是否包含所有字母这样子做，code写完了
没有多余时间优化，大致讲了一下思路，就结束了。这道题stackOverflow上面有人讨
论，感兴趣的可以搜一下。
另外求leetcode 和CC150之外，如何找到这种题练？感觉这个难度还是比leetcode平均
难度高一些啊。 |
s******7
发帖数: 1758 | 2 第一道你用priority queue就是heap找前k个，应该是 nlogk, 应该够快了，
selection能更快？
第二道leetcode有吧，Minimum Window Substring，双指针一前一后一夹O(n) |
g****s
发帖数: 1755 | 3 UP楼上， ：）
第一题算是KMP/heap sort; 建一个容纳K个数的Heap，遍历数组，遇到某个值小于Heap
目前最大值的和时候update heap;一次遍历就可以了。
第二题Leetcode原题：两个hashMap 一个toFind() 一个alreadyFound; 再建个Queue存
储string里每个在alphabet里的字符对应的index; alreadyFound找到满足每个
alphabet出现次数的时候，从queue里poll()出此次subString的超始点。时间上一次遍
历就结束了O(n)。 |
j****l
发帖数: 85 | 4 selection找kth smallest element那种方法，可以O(n)。记得cc上
面有讲到这个方法，忘了具体在哪儿了。
对的发现leetcode原题了，自觉还是算法积累不够多，得多看题才行，谢谢啊！
【在 s******7 的大作中提到】
: 第一道你用priority queue就是heap找前k个，应该是 nlogk, 应该够快了，
: selection能更快？
: 第二道leetcode有吧，Minimum Window Substring，双指针一前一后一夹O(n)
|
l*********8
发帖数: 4642 | 5 leetcode 中等难度的题目吧。
【在 j****l 的大作中提到】
: 才第一轮，感觉面的不太好。leetcode刷了这么多，发现还是不够呀。
: 面试官感觉是非老美非烙印非老中的外国人，口语很好，略有口音，但是电话音质太差
: ，整个过程听起来很累。
: 先让自我介绍，问了最喜欢的project，希望在技术方面讲细一点，但是我的那个
: project可讲的细节太多了要讲好久，讲了一会儿感觉他没什么反应，就问说如果感兴
: 趣我可以更深入讲，他说不用了，挺好，然后开始code题目。
: 第一道是经典题给很多（millions以上）个点，以（x，y）坐标表示，找出离原点最近
: 的k个点。k 远小于 n。
: 开始还想了一会儿，后来想到用priority queue来做，问了时间复杂度是nlogn。面完
: 后问了一下别人，发现是可以用selection做的，更快。
|
j****l
发帖数: 85 | 6 有一点不明白，这个方法是如何找到最短substring的？
Heap
【在 g****s 的大作中提到】
: UP楼上， ：）
: 第一题算是KMP/heap sort; 建一个容纳K个数的Heap，遍历数组，遇到某个值小于Heap
: 目前最大值的和时候update heap;一次遍历就可以了。
: 第二题Leetcode原题：两个hashMap 一个toFind() 一个alreadyFound; 再建个Queue存
: 储string里每个在alphabet里的字符对应的index; alreadyFound找到满足每个
: alphabet出现次数的时候，从queue里poll()出此次subString的超始点。时间上一次遍
: 历就结束了O(n)。
|
j****l
发帖数: 85 | 7 呜呜我咋觉得比我刷过的题难，目前刷了大半还没刷完，高频题倒是写了两遍了，希望
刷完以后也有你这感觉。。。
【在 l*********8 的大作中提到】
: leetcode 中等难度的题目吧。
|
w********s
发帖数: 1570 | 8 第一题不是heap么？klogn, k << n
【在 j****l 的大作中提到】
: 才第一轮，感觉面的不太好。leetcode刷了这么多，发现还是不够呀。
: 面试官感觉是非老美非烙印非老中的外国人，口语很好，略有口音，但是电话音质太差
: ，整个过程听起来很累。
: 先让自我介绍，问了最喜欢的project，希望在技术方面讲细一点，但是我的那个
: project可讲的细节太多了要讲好久，讲了一会儿感觉他没什么反应，就问说如果感兴
: 趣我可以更深入讲，他说不用了，挺好，然后开始code题目。
: 第一道是经典题给很多（millions以上）个点，以（x，y）坐标表示，找出离原点最近
: 的k个点。k 远小于 n。
: 开始还想了一会儿，后来想到用priority queue来做，问了时间复杂度是nlogn。面完
: 后问了一下别人，发现是可以用selection做的，更快。
|
w********s
发帖数: 1570 | 9 第二题，不是扫一遍之后记录所有的字母的位置
比如str=abcdbacebd, set=abcd
a:0,5
b:1,4,8
c:2,6
d:3,9
pos = 0:
abcd={0,1,2,4}, length = 4, pop 0
pos = 1:
abcd={5,1,2,4}, length = 5, pop 1
pos = 2:
abcd={5,4,2,4}, length = 4, pop 2
...
【在 j****l 的大作中提到】
: 才第一轮，感觉面的不太好。leetcode刷了这么多，发现还是不够呀。
: 面试官感觉是非老美非烙印非老中的外国人，口语很好，略有口音，但是电话音质太差
: ，整个过程听起来很累。
: 先让自我介绍，问了最喜欢的project，希望在技术方面讲细一点，但是我的那个
: project可讲的细节太多了要讲好久，讲了一会儿感觉他没什么反应，就问说如果感兴
: 趣我可以更深入讲，他说不用了，挺好，然后开始code题目。
: 第一道是经典题给很多（millions以上）个点，以（x，y）坐标表示，找出离原点最近
: 的k个点。k 远小于 n。
: 开始还想了一会儿，后来想到用priority queue来做，问了时间复杂度是nlogn。面完
: 后问了一下别人，发现是可以用selection做的，更快。
|
P**********k
发帖数: 1629 | 10 是nlogk吧
【在 w********s 的大作中提到】
: 第一题不是heap么？klogn, k << n
|
|
|
w******g
发帖数: 189 | 11 请问楼主，2题都要写出代码来吗？45分钟2题再加上讲project够么？ |
s******d
发帖数: 424 | 12 top K问题真有O(N)啊，看这里
http://stackoverflow.com/questions/4956593/optimal-algorithm-fo
假设K比N小很多 N=100， K=5，前N-K+2个元素按照锦标赛方法两两比较，大的胜出
（N-K+2）
（N-K+2）/2
（N-K+2）/4
...
1 |
s******d
发帖数: 424 | 13 能在面试的几十分钟里面想出来选择算法就太牛了，考官肯定以为你见过 |
x*****0
发帖数: 452 | |
h*********r
发帖数: 14 | 15 TOP K无法用O(n)解的，这个算法只能是第Kth个。。
【在 s******d 的大作中提到】
: top K问题真有O(N)啊，看这里
: http://stackoverflow.com/questions/4956593/optimal-algorithm-fo
: 假设K比N小很多 N=100， K=5，前N-K+2个元素按照锦标赛方法两两比较，大的胜出
: （N-K+2）
: （N-K+2）/2
: （N-K+2）/4
: ...
: 1
|
m*****l
发帖数: 95 | 16 快选的问题是要把所有的节点都load到内存里，space是O(n). Heap的方法Space是O(k)
【在 j****l 的大作中提到】
: selection找kth smallest element那种方法，可以O(n)。记得cc上
: 面有讲到这个方法，忘了具体在哪儿了。
: 对的发现leetcode原题了，自觉还是算法积累不够多，得多看题才行，谢谢啊！
|
l****i
发帖数: 2772 | 17 quickselect是O（n）
【在 h*********r 的大作中提到】
: TOP K无法用O(n)解的，这个算法只能是第Kth个。。
|
s*****B
发帖数: 32 | |
r****7
发帖数: 2282 | 19 我觉得你可能太执着于刷题然后就不太动脑子了
其实这两个题从0开始想都不是很困难。
【在 j****l 的大作中提到】
: 才第一轮，感觉面的不太好。leetcode刷了这么多，发现还是不够呀。
: 面试官感觉是非老美非烙印非老中的外国人，口语很好，略有口音，但是电话音质太差
: ，整个过程听起来很累。
: 先让自我介绍，问了最喜欢的project，希望在技术方面讲细一点，但是我的那个
: project可讲的细节太多了要讲好久，讲了一会儿感觉他没什么反应，就问说如果感兴
: 趣我可以更深入讲，他说不用了，挺好，然后开始code题目。
: 第一道是经典题给很多（millions以上）个点，以（x，y）坐标表示，找出离原点最近
: 的k个点。k 远小于 n。
: 开始还想了一会儿，后来想到用priority queue来做，问了时间复杂度是nlogn。面完
: 后问了一下别人，发现是可以用selection做的，更快。
|
