v****s 发帖数: 1112 | 1 刚刚收到拒信,周二面的,ms还是很有效率的。。。
interviewer 是个 DATA center的pm, 感觉比较随和但是也很tough,也比较喜欢笑。
先是电话迟来了5min,然后信号不好又折腾了10min,重新打过来,这样就浪费了15min。
我以为直接来考programming,结果那哥们先跟我聊了10min的research, 完了直接问,
如果你明天就来intern,你的research能马上对你要去的组有什么贡献?我没料到会问
这种问题,瞎说一气。。。估计影响分直接被扣完了,ft....
然后就是简单的概念题和在netmeeting 上coding,
接下来算法题,
given 1 billion integers, how do u efficiently find the duplicates?
我说用bitmap, blablabla, 结果这哥们说,这个算法不错,你还能想到其他的么?我
说hash,他说这个本质和bitmap是一样的,我又想了一分钟,把知道的data structure
穷举了一遍,还是死活想不出来。
最后剩下几分钟,他问我有什么问题要问他的, |
p******y 发帖数: 708 | |
m****u 发帖数: 3915 | 3 概念和coding是问啥了?
感觉楼主答的不错阿
15min。
【在 v****s 的大作中提到】 : 刚刚收到拒信,周二面的,ms还是很有效率的。。。 : interviewer 是个 DATA center的pm, 感觉比较随和但是也很tough,也比较喜欢笑。 : 先是电话迟来了5min,然后信号不好又折腾了10min,重新打过来,这样就浪费了15min。 : 我以为直接来考programming,结果那哥们先跟我聊了10min的research, 完了直接问, : 如果你明天就来intern,你的research能马上对你要去的组有什么贡献?我没料到会问 : 这种问题,瞎说一气。。。估计影响分直接被扣完了,ft.... : 然后就是简单的概念题和在netmeeting 上coding, : 接下来算法题, : given 1 billion integers, how do u efficiently find the duplicates? : 我说用bitmap, blablabla, 结果这哥们说,这个算法不错,你还能想到其他的么?我
|
m*****g 发帖数: 226 | 4 那个1billion的问题,我也被问的
难道是一个人?
当时我就先说hash, 然后再说的bitmap |
v****s 发帖数: 1112 | 5 difference between passing by value and passing by ref.
i still don't know in which part i screwed up.... sigh...
but i wasn't feeling that well after the interview
【在 m****u 的大作中提到】 : 概念和coding是问啥了? : 感觉楼主答的不错阿 : : 15min。
|
v****s 发帖数: 1112 | 6 然后他还有让你说别的算法么?他给了什么comments?
【在 m*****g 的大作中提到】 : 那个1billion的问题,我也被问的 : 难道是一个人? : 当时我就先说hash, 然后再说的bitmap
|
v****s 发帖数: 1112 | 7 i actually thought of this , but i guessed it would not help so i didn't
said it. and it's kind of related to the "hash" idea
besides, bloom filter can be used to detect whether that int is in your list, but with false alarm, like, if your int is hashed into 102, 77, 125 position, another int can possibly be hashed into these spots as well.
so i don't BF is the one he was seeking for.
【在 p******y 的大作中提到】 : bloom filter
|
S******n 发帖数: 1009 | 8 is there a range for this 1 billion integers?
If you use hash, how do you define a hash function so that different
number has different mapping?
【在 m*****g 的大作中提到】 : 那个1billion的问题,我也被问的 : 难道是一个人? : 当时我就先说hash, 然后再说的bitmap
|
S******n 发帖数: 1009 | 9 问下你是怎样拿到ms面试的,直接在网上投还是找人内部投的?
我网投了google, facebook, amazon,yahoo, ms,目前只拿到了前两个面试
amazon, yahoo,ms网投就是没消息
【在 m*****g 的大作中提到】 : 那个1billion的问题,我也被问的 : 难道是一个人? : 当时我就先说hash, 然后再说的bitmap
|
v****s 发帖数: 1112 | 10 i asked the inviewer whether we know some statistics of the int, he say no
stat. so i guess it's uniform distributed 32 bit or 64 bit int.
【在 S******n 的大作中提到】 : is there a range for this 1 billion integers? : If you use hash, how do you define a hash function so that different : number has different mapping?
|
|
|
v****s 发帖数: 1112 | 11 i submitted my app on website, then 1 month later the campus recruiter sent
me emails for interview.
【在 S******n 的大作中提到】 : 问下你是怎样拿到ms面试的,直接在网上投还是找人内部投的? : 我网投了google, facebook, amazon,yahoo, ms,目前只拿到了前两个面试 : amazon, yahoo,ms网投就是没消息
|
w*********l 发帖数: 1337 | 12 bloom filter跟hashing没有本质区别啊
【在 p******y 的大作中提到】 : bloom filter
|
c******f 发帖数: 2144 | |
l*f 发帖数: 218 | 14 radix sort,O(n*k)
你用hash map,当map增大时insert key的时间不是常数 |
S******n 发帖数: 1009 | 15 yes, this is good
【在 l*f 的大作中提到】 : radix sort,O(n*k) : 你用hash map,当map增大时insert key的时间不是常数
|
v****s 发帖数: 1112 | 16 恩,那天我们组的老美也说了radix sort, o(nk). 但是我觉得我说的bitmap也是o(n),
interview也太tough了吧。。。
【在 l*f 的大作中提到】 : radix sort,O(n*k) : 你用hash map,当map增大时insert key的时间不是常数
|
s**********o 发帖数: 105 | |
s*********i 发帖数: 66 | |
n**********w 发帖数: 1082 | |
c*******d 发帖数: 255 | 20 是啥?
【在 n**********w 的大作中提到】 : pm面的不是ALGORITHM,而是。。。
|
|
|
v****s 发帖数: 1112 | 21 ???
【在 n**********w 的大作中提到】 : pm面的不是ALGORITHM,而是。。。
|
n****e 发帖数: 2401 | 22 是寂寞
【在 n**********w 的大作中提到】 : pm面的不是ALGORITHM,而是。。。
|
m*****r 发帖数: 280 | 23 1 billion integer is 4GB. He was testing you about data structure + memory usage + cache usage.
Buy the book - "programming pearls" if you want to go to MS, Google, Amazon, Yahoo...
Those interviewers are so lazy, and still use the same question 5 years ago to test people. |
m*****g 发帖数: 226 | 24 如果把cache之类的考虑上来的话,还是bitmap最好阿
有没有牛人说说这题
usage + cache usage.
Amazon, Yahoo...
ago to test people.
【在 m*****r 的大作中提到】 : 1 billion integer is 4GB. He was testing you about data structure + memory usage + cache usage. : Buy the book - "programming pearls" if you want to go to MS, Google, Amazon, Yahoo... : Those interviewers are so lazy, and still use the same question 5 years ago to test people.
|
m*****g 发帖数: 226 | 25 如果把cache之类的考虑上来的话,还是bitmap最好阿
有没有牛人说说这题
usage + cache usage.
Amazon, Yahoo...
ago to test people.
【在 m*****r 的大作中提到】 : 1 billion integer is 4GB. He was testing you about data structure + memory usage + cache usage. : Buy the book - "programming pearls" if you want to go to MS, Google, Amazon, Yahoo... : Those interviewers are so lazy, and still use the same question 5 years ago to test people.
|
v****s 发帖数: 1112 | 26 i've done this calculation during the interview, and told him i could finish
this using bitmap in a 32bit machine.
usage + cache usage.
Amazon, Yahoo...
ago to test people.
【在 m*****r 的大作中提到】 : 1 billion integer is 4GB. He was testing you about data structure + memory usage + cache usage. : Buy the book - "programming pearls" if you want to go to MS, Google, Amazon, Yahoo... : Those interviewers are so lazy, and still use the same question 5 years ago to test people.
|
m*****r 发帖数: 280 | 27 Then your answer was incorrect.
32bit win only allows each application using maximum 2GB(more than that, app
crash). You have to split, sort, then merge if you use 32bit.
Anyway, find correct answer in programming pearl.
finish
【在 v****s 的大作中提到】 : i've done this calculation during the interview, and told him i could finish : this using bitmap in a 32bit machine. : : usage + cache usage. : Amazon, Yahoo... : ago to test people.
|
l*****a 发帖数: 14598 | 28 1 billion =1000 million=10 pow 9
which need (10 pow 9)/8 =125*( 10 power 6)=125M memory
to use bitmap
usage + cache usage.
Amazon, Yahoo...
ago to test people.
【在 m*****r 的大作中提到】 : 1 billion integer is 4GB. He was testing you about data structure + memory usage + cache usage. : Buy the book - "programming pearls" if you want to go to MS, Google, Amazon, Yahoo... : Those interviewers are so lazy, and still use the same question 5 years ago to test people.
|
v****s 发帖数: 1112 | 29 where did u get this "2GB"?
i think a 32 bit machine has 2^32 ~~ 4GB, though a bit less than exactly 4GB
, which is about 3.4GB.
besides, bitmap deal with "bit" , so it's significantly less than 3.4GB .
app
【在 m*****r 的大作中提到】 : Then your answer was incorrect. : 32bit win only allows each application using maximum 2GB(more than that, app : crash). You have to split, sort, then merge if you use 32bit. : Anyway, find correct answer in programming pearl. : : finish
|
c**********n 发帖数: 516 | 30 re
【在 p******y 的大作中提到】 : bloom filter
|
|
|
m*****r 发帖数: 280 | 31 google it. http://www.microsoft.com/whdc/system/platform/server/PAE/PAEmem.mspx
4GB is for all applications, for each app is 2GB. Don't ask me
why, ask MS.
4GB
【在 v****s 的大作中提到】 : where did u get this "2GB"? : i think a 32 bit machine has 2^32 ~~ 4GB, though a bit less than exactly 4GB : , which is about 3.4GB. : besides, bitmap deal with "bit" , so it's significantly less than 3.4GB . : : app
|
H*X 发帖数: 281 | 32 why do you need 4GB in the first place? why do you want to use 1 Byte per
integer? He was suggesting the bitmap method...not the "bytemap method".
【在 m*****r 的大作中提到】 : google it. http://www.microsoft.com/whdc/system/platform/server/PAE/PAEmem.mspx : 4GB is for all applications, for each app is 2GB. Don't ask me : why, ask MS. : : 4GB
|
r********g 发帖数: 1351 | 33 我记得programming pearls上有关于大数组的讨论,但要是想找出所有的duplicate,
还是bitmap
最好吧...如果只需要找出一个duplicate,估计有更好的办法(怎么我的印象还是跟
binary
search有关的)....
usage +
cache usage.
Amazon,
Yahoo...
ago to test
people.
【在 m*****r 的大作中提到】 : 1 billion integer is 4GB. He was testing you about data structure + memory usage + cache usage. : Buy the book - "programming pearls" if you want to go to MS, Google, Amazon, Yahoo... : Those interviewers are so lazy, and still use the same question 5 years ago to test people.
|
c**********r 发帖数: 472 | 34 不知楼主解释清楚题目了没有,是要求找出说有的duplicate还是找出一个就可以。 |
m*****r 发帖数: 280 | 35 I assume 4 bytes for an integer. Bitmap may use no memory in
case of all zeros. But should your program consider the worst case? |