h**o
发帖数: 548 | 1 以及Find Median Of Two Sorted Arrays。 复杂度是logM+logN还是logK?我觉得是
logM+logN，为什么有人说logK?
这道题一直不想看。但据说是高频。终于在2013末看懂了。 |
|
|
|
A*********c
发帖数: 430 | 4 这样考虑，既然是top K, 无论数组多长，两个数组K后面的全部可以一刀切掉，所以看
算法本身有没有这步功能，没有这步也可以加上，所以算法复杂度和M，N无关。
就像两个班级求前5名，必然在两个班级的前5名里出现，跟两个班级分别多大没关系。
在加上二分查找，所以是top K。 |
|
W*********y
发帖数: 481 | 5 O(log(M*N)) 和 O(log(M+N)) 不一样吧？
as |
|
A*********c
发帖数: 430 | 6 O(log(M*N)) = O (log(M) + log(N))
log(M) <= log(M+N)
log(N) <= log(M+N)
O(log(M+N)) <= O(2*log(M+N)) = O(log(M+N));
right? |
|
h**o
发帖数: 548 | 7 喔是这样。所以就是：
int findKthSmallest(int A[], int m, int B[], int n, int k) {
if ((m == 0 && n==0) || k >m+n) return INT_MIN;
int min_m = min(m, k);
int min_n = min(n, k);
return findKthSmallest_recur(A, min_m, B, min_n, k);
}
findKthSmallest_recur()就沿用leetcode讲的算法。 |
|
s********x
发帖数: 914 | 8 那我写一下吧
public static int findKthSmallestElementInTwoSortedArrays(int[] a, int i
, int m, int[] b, int j,
int n, int k) {
validate(a, b)；
if ( m > n) {
return findKthSmallestElementInTwoSortedArrays(b, j, n, a, i, m
,k);
} // now m <= n
// Boundary check
if (k > m + n) {
throw new IllegalArgumentException("k is too big");
} else if (k <= m) {
// cut two arrays to be both of size k b... 阅读全帖 |
|
s**x
发帖数: 7506 | 9 跟我用的差不多， 这种算法是 log(min(k, m, n)).
code 简答些的貌似 logm+logn.
i
m |
|
|
s**x
发帖数: 7506 | 11 should be around 5 lines. log(min(n, m, k)) needs about 20. |
|
|
q*******d
发帖数: 49 | 13 总共三轮
第一轮俩人technical
1. tweet has topics, find top 10 topics of tweets send in last 30 minutes
2. leetcode 积水问题
3. there are different kind of databases; given a query, system will tell
you which database you should connect(system gives you a string like "Oracle
" or "MySQL"). Design a class that could handle any query.
第二轮俩人technical
1. java questions
2. make car; given “bus” return object bus; given "truck" return object
truck...etc
3. many linked lists meet together. find the first node that a... 阅读全帖 |
|
q*******d
发帖数: 49 | 14 总共三轮
第一轮俩人technical
1. tweet has topics, find top 10 topics of tweets send in last 30 minutes
2. leetcode 积水问题
3. there are different kind of databases; given a query, system will tell
you which database you should connect(system gives you a string like "Oracle
" or "MySQL"). Design a class that could handle any query.
第二轮俩人technical
1. java questions
2. make car; given “bus” return object bus; given "truck" return object
truck...etc
3. many linked lists meet together. find the first node that a... 阅读全帖 |
|
m****v
发帖数: 88 | 15 背景：国内最好的技校+美本公立普通学校CS+东海岸比较好的学校CS MS
Amazon和一个湾区大公司的实习 有大量内推
CC150 leetcode过了一遍，题刷的不是很好，不过由于海投，面试经验比较多
Onsite round: Google(内推直接onsite, rej), Facebook(内推，rej), LinkedIn(内
推，offer), Oracle(Target school, offer), Amazon(内推直接onsite，drop),
Microsoft(一轮Campus之后onsite, offer)
Phone/Campus: Dropbox(rej), Pinterest(2nd round rej, 很可惜), TwoSigma(rej,
大师兄内推, 可惜), Goldman Sachs core Strats(rej), Citadel tech(rej), SIG(
drop), TGS(rej), AppNexus(rej, 莫名其妙), Airbnb(drop), EA Games(drop)
Code test: Twitter(re... 阅读全帖 |
|
m****v
发帖数: 88 | 16 Dropbox:
2sum, 3sum both with duplicates
30分钟写出来了 然后挂了 可能bar比较高
Pinterest:
Map/reduce top 10 ip address
java iterator wrapper (more functions 忘了 反正挺难写的). input is a
original queue iterator
symmetric tree
get the kth element uniformly (swap by 1/k possibiliy) |
|
m****v
发帖数: 88 | 17 背景：国内最好的技校+美本公立普通学校CS+东海岸比较好的学校CS MS
Amazon和一个湾区大公司的实习 有大量内推
CC150 leetcode过了一遍，题刷的不是很好，不过由于海投，面试经验比较多
Onsite round: Google(内推直接onsite, rej), Facebook(内推，rej), LinkedIn(内
推，offer), Oracle(Target school, offer), Amazon(内推直接onsite，drop),
Microsoft(一轮Campus之后onsite, offer)
Phone/Campus: Dropbox(rej), Pinterest(2nd round rej, 很可惜), TwoSigma(rej,
大师兄内推, 可惜), Goldman Sachs core Strats(rej), Citadel tech(rej), SIG(
drop), TGS(rej), AppNexus(rej, 莫名其妙), Airbnb(drop), EA Games(drop)
Code test: Twitter(re... 阅读全帖 |
|
m****v
发帖数: 88 | 18 Dropbox:
2sum, 3sum both with duplicates
30分钟写出来了 然后挂了 可能bar比较高
Pinterest:
Map/reduce top 10 ip address
java iterator wrapper (more functions 忘了 反正挺难写的). input is a
original queue iterator
symmetric tree
get the kth element uniformly (swap by 1/k possibiliy) |
|
y*******x
发帖数: 40 | 19 早上刚第一轮PS（偶在国内），core storage职位，供参考
1. 聊简历
2. Java相关，比较深入，包含OOD，并发相关，例如java memory model，lock-free，
dead lock等
3. coding：N个list求kth largest |
|
y*******x
发帖数: 40 | 20 LZ在国内，春节期间面了L和T，附上面经，攒RP。
Linkedin, system&infra team。版上好人推荐的general hiring，没选上，后来自己
在linkedin投的这个职位
PS1:
senior staff engineer，老美，70年代大学毕业。
1. 聊简历和技术背景
2. 子数组最大和，我说见过，说了O(n)的方案，没coding
3. Search in rotated sorted array。开始没考虑重复元素，后来修正了。但面试官
似乎不知道重复元素的影响，举了几个例子验证后，说OK
最后，我问了一些linkedin infra的问题，解答很详细，并推荐了rest.li，后来和同
事研究了下，在服务发现这块设计的很赞
PS2:
国人主面，老外shadow
1. 聊项目经验，问的很仔细，英文水平有限，又没法画图，解释的不太好
2. Java和OS相关概念
3. coding，序列化和反序列二叉树。用了leetcode的表示法。春节期间没练习，手生
，结果有逻辑bug，当时感觉完全没信心了，提问阶段只问了一个就不想说了。
2天后接到fee... 阅读全帖 |
|
t********o
发帖数: 10 | 21 来自主题: JobHunting版 - 多家的面经 具体哪些公司就不提了，反正就是版上的那些大公司，把能记住的电面onsite题就混在
一块儿了。
1. anagram
2. OO design: candy bar
3. sort color
4. 给一个小写的string，例如“abcd” 输出所有大小写混合的组合
5. string to double
6. given a string words, find the shortest substring including all the given
key words
7. what is little/big endian, how to tell if one machine is little or big
endian machine？
8. power set
9. smart pointer
10. given a set of weighted intervals, find the set non-overlap weighted
intervals that has the biggest weight
11. two sum变形
12. serialize... 阅读全帖 |
|
t********o
发帖数: 10 | 22 来自主题: JobHunting版 - 多家的面经 具体哪些公司就不提了，反正就是版上的那些大公司，把能记住的电面onsite题就混在
一块儿了。
1. anagram
2. OO design: candy bar
3. sort color
4. 给一个小写的string，例如“abcd” 输出所有大小写混合的组合
5. string to double
6. given a string words, find the shortest substring including all the given
key words
7. what is little/big endian, how to tell if one machine is little or big
endian machine？
8. power set
9. smart pointer
10. given a set of weighted intervals, find the set non-overlap weighted
intervals that has the biggest weight
11. two sum变形
12. serialize... 阅读全帖 |
|
j****l
发帖数: 85 | 23 selection找kth smallest element那种方法，可以O(n)。记得cc上
面有讲到这个方法，忘了具体在哪儿了。
对的发现leetcode原题了，自觉还是算法积累不够多，得多看题才行，谢谢啊！ |
|
h*********r
发帖数: 14 | 24 TOP K无法用O(n)解的，这个算法只能是第Kth个。。 |
|
|
f*******w
发帖数: 1243 | 26 背景：EE 非名校PhD 无线通信方向，预计夏天毕业，两次实习经历（12年Broadcom，
13年Amazon）
2月的时候发现时间紧迫，开始锁定SDE的目标狂投简历……真正意义上的海投，大大小
小有近百家吧，基本没有找人refer。偶尔在版上看到有人帮忙refer的时候也会问一下
，不过好像都被简历拒了- -
所有面经放上……
Bloomberg:
02/21 电面阿三，没有写具体code，都是说思路
Why bloomberg?
Mention and describe one of your projects. What is your role on this project?
Polymorphism in C++, how to implement virtual functions (vtable), different
types of polymorphisms (dynamic/static).
Two sum (with or without extra memory)
Kth node to the last (Linked List)
Implement m... 阅读全帖 |
|
g******y
发帖数: 143 | 27 Interviewed with Kinect group
Phone interview
1.implement an image convolution and optimize it
2. find the intersection of two rectangles
Onsite
Round1
1. Implement strstr() and optimize it
2. Implement histogram equalization algorithm
3. Bayes conditional probability
Round2
1. Implement a fixed floating point class
2. Square root of a number (the number can be less than 1)
Round3
1. Find subarray which has max sum
2. Find the kth element in two sorted arrays
Round4
1. Im... 阅读全帖 |
|
G******n
发帖数: 572 | 28 娃满月了，看着他对这个世界的好奇，我无法入睡。
物理phd最后一年，早已对学术界失望，对学术生涯失去热情。老板很supportive，今
年之内完成论文。之前三天打鱼准备了一会儿编程，面了几个，都没有结果。可能是之
前太多事情让自己分心，而且比较迷茫，没有一个准确的目标。（现在也不确定。。。）
现在生活慢慢稳定下来，虽然赶不上summer intern了，还是希望能在毕业之前找到工
作。
地点：大波士顿地区（至少暂时不能离开），纽约地区也可以试试
目标：entry-level 大公司码工，quant，data scientist （支持H1b和opt extension
的）
背景：top20 Physics phd，本科国内top3，成绩和学习能力没问题，数学和解题能力
不错，但没有实习经历。phd方向实验和理论，显微镜成像图像处理，数据分析，MC数
值模拟
技能：C++很熟练，Matlab。其他的都会一些，core java/j2ee, machine learning,
sql都有听过公开课和做作业，数据结构和算法会的有限。leetcode做（看）过20%，没
有认真去刷
差不多... 阅读全帖 |
|
d**k
发帖数: 797 | 29 不是让你算联系
算联系的function是给定的，直接调用就行
主要还是输出kth elements |
|
b*****c
发帖数: 1103 | 30 sorted matrix = each row/column is sorted
remember k=O(n^2)
write code to solve in n*lg n
----------------------
O(n^2) is simple and stupid --- QuickSelect |
|
|
T*******e
发帖数: 4928 | 32 啊，最近面世我刚遇到这题。一个印度面世官出的， 你不会和我面得同一家吧?
cupertino的. |
|
|
l******a
发帖数: 14 | 34 Divid the matrix to 2 by 2. Each are n/2 X n/2
If k<=n*n/4, restrain search to only the top left square
Else if k =>n*n*3/4 restrain search to only the right bottom square
Else restrain search to top right and bottom left square
This way you cut it at least to half size each time
T(n) = 2T(n/2) O(1)
So T(n) = O(nlogn)
O(n) is doable. But I need O(n lgn) and the code.O(n) algorithmhttp://www.cse.yorku.ca/~........ |
|
T*******e
发帖数: 4928 | 35 Are you sure it's working? For example,
Find the 4th element in 6x6 matrix.
matrix:
1 20 30 40 50 60
2 21 31 41 51 61
3 22 32 42 52 62
4 23 33 43 53 63
5 24 34 44 54 64
6 25 35 45 55 65 |
|
b*****c
发帖数: 1103 | 36 樓上的，
1 1 1 1
1 2 2 2
1 2 2 2
1 2 2 2
找k=4，你的算法錯了，不能只看topleft |
|
b*****c
发帖数: 1103 | 37 1) O(k*log(min(k,n)) , just look at my original thread, k=O(n^2) !!!!
Quickselect = O(n^2). O(k*log(min(k,n)) will be "Stupider"
2) O((n+n)*log(range of values in matrix)
tell me how do you solve
1 2 3 99999
1 2 3 99999
1 2 3 99999
1 2 3 99999
k=5
of
the |
|
T*******e
发帖数: 4928 | 38 I didn't say they were better than O(n^2). I just say they
are two methods that I can think of. |
|
b*****c
发帖数: 1103 | 39 good job. running simulation to verify
that
mid |
|
b*****c
发帖数: 1103 | 40 lol.
1 2 4
2 3 4
2 4 4
k=5就错了 |
|
b*****c
发帖数: 1103 | 41 是每行每列分别有序，不是将matrix视作array的有序，
前者是sorted matrix的数学定义，后者是不知出处的定义 |
|
T*******e
发帖数: 4928 | 42
you can verify it yourself or just lol. What do I care. |
|
|
|
D*********d
发帖数: 125 | 45 每次把矩阵划成4份，每次至少能够扔掉1/4，也就是说如果k>左上角的最大值，那么扔
掉左上角，如果k<右下角的最小值，那么扔掉右下角，这样不知道是不是
T(n) = 3*T(1/4n)+a?然后复杂度是多少？有点蒙。。 |
|
j********8
发帖数: 10 | 46 //Best first search, time complexity O(klog(n)). The size of heap is at most
2*n. Every time an element is popped from the heap or inserted to the heap,
O(log(n)). We need to do the pop and insert operations k times. So the time
complexity is O(klog(n)).
//Space complexity O(n), because there are at most 2*n nodes in the priority
queue.
struct node
{
int index;
int val;
node(int index_, int val_): index(index_), val(val_){}
bool operator > (const node& other) const
{
... 阅读全帖 |
|
W*********y
发帖数: 481 | 47 从右上开始找，
若大于input，move down
若小于input，move left,
若等于input, return
一直找到左壁或者下壁。ruturn false.
这样扫 2*n个元素必能找到， |
|
b******g
发帖数: 3616 | 48 哪里有input?.....这是看成leetcode上那道了?.... |
|
|
b*****c
发帖数: 1103 | 50 sorted matrix = each row/column is sorted
e.g.,
1 6 6
2 7 7
2 8 9
k=7
remember k=O(n^2)
write code to solve in n*lg n
----------------------
O(n^2) is simple and stupid --- QuickSelect!!!!!!!! |
|
