由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - MS intern 电面被拒,附上面试过程
相关主题
O(N) sort integer array我花了一个小时才调通过这个程序
大公司算法题问一道排序题
subset一个google面试题
微软onsite电面不好,求bless。这题怎么答?
算法题:两列找共同元素有O(n)的算法吗?一道twitter的题
A家新鲜面经--都是经典题考古到一道题
Amazon 电面归来AMAZON PHONE SCREEN 1 基本死掉。
amazon背靠背电面书上关于search和sorting的部分 应该不用全看吧?
相关话题的讨论汇总
话题: bitmap话题: usage话题: ms话题: 4gb话题: yahoo
进入JobHunting版参与讨论
1 (共1页)
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
2
bloom filter
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?

相关主题
A家新鲜面经--都是经典题我花了一个小时才调通过这个程序
Amazon 电面归来问一道排序题
amazon背靠背电面一个google面试题
进入JobHunting版参与讨论
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
13
看来算法也要多知道些
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
17
trie
s*********i
发帖数: 66
18
bitmap是如何实现的?
n**********w
发帖数: 1082
19
pm面的不是ALGORITHM,而是。。。
c*******d
发帖数: 255
20
是啥?

【在 n**********w 的大作中提到】
: pm面的不是ALGORITHM,而是。。。
相关主题
电面不好,求bless。这题怎么答?AMAZON PHONE SCREEN 1 基本死掉。
一道twitter的题书上关于search和sorting的部分 应该不用全看吧?
考古到一道题amazon 电面问题 求解答, 在线等
进入JobHunting版参与讨论
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
相关主题
F家电面:group Anagrams大公司算法题
一道Bloomberg 面试题subset
O(N) sort integer array微软onsite
进入JobHunting版参与讨论
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?
1 (共1页)
进入JobHunting版参与讨论
相关主题
书上关于search和sorting的部分 应该不用全看吧?算法题:两列找共同元素有O(n)的算法吗?
amazon 电面问题 求解答, 在线等A家新鲜面经--都是经典题
F家电面:group AnagramsAmazon 电面归来
一道Bloomberg 面试题amazon背靠背电面
O(N) sort integer array我花了一个小时才调通过这个程序
大公司算法题问一道排序题
subset一个google面试题
微软onsite电面不好,求bless。这题怎么答?
相关话题的讨论汇总
话题: bitmap话题: usage话题: ms话题: 4gb话题: yahoo