g**u
发帖数: 583 | 1 攒RP, 发第二轮Amazon面经
一开始是 interviewer自我介绍3分钟，对方介绍自己组的project,讲的巨快。 自己手
机信号不好，没听明白， 就不时“hum”表示依然在听，没掉线。
接着开始做题，题目是非常经典的:
在一个数组中，有的数字出现基数次，有的出现偶数次，写程序找出出现基数次的方法.
脑袋不知为何短路， 没有说 xor 的方法，直接就上了hash_map,
， 然后设置sum=0,通过sum的值来确定出现基数次的元素； 然后讨论如果输入里面所
有的元素都出现偶数次怎么办， 接着讨论hash table 的设计考虑的因素，然后被要求设计一个 差的hash function, 肯定没听错，的确是设计一个差的hash function, 自己一顿瞎侃.....然后被要求电话里面读code实现......
接着是OOD, 就是经典的设计card的问题， 说了一通，基本上和career cup查不多； 被要求实现shuffle cards的算法；
然后interviwer开始变要求, 如果要支持不同的游戏规则怎么办，答strategy
pattern，谈了如何实现和结构； 接着被问，如果card的点数不是A-13，而是A-10如何办
， 答曰factory pattern,再说一通
接着是我提问的环节，脑袋这时候开始苏醒，说了寻找基数次的题目可以先排序，然后
再遍历即可找到，说了一通时间和空间的trade-off。
收到 on site邀请 | l*********r
发帖数: 674 | 2 设计一个差的hash function，能说说你怎么回答的么？ | g**u
发帖数: 583 | 3
这个， 老实说我也不知道怎么回答好。 我当时说的是 collision取决于hash
function， table size和load factor。 如果要找一个差的hash function的话，要取
决于输入的数据的特征，比如说如果你的table size是 power of 2的话，然后再通过
取模的方式获得index，那么collision的概率就很大了（隐约记的table size是2^k-1
，比如说7，15）
等大牛解答
【在 l*********r 的大作中提到】
: 设计一个差的hash function，能说说你怎么回答的么？
| k***o
发帖数: 125 | | g*********s
发帖数: 1782 | 5 xor doesn't work if two numbers appear odd times.
法.
求设计一个
差的hash function, 肯定没听错，的确是设计一个差的hash function, 自己一顿瞎侃
.....然
后被要求电话里面读code实现......
被要求实
现shuffle cards的算法；
【在 g**u 的大作中提到】
: 攒RP, 发第二轮Amazon面经
: 一开始是 interviewer自我介绍3分钟，对方介绍自己组的project,讲的巨快。 自己手
: 机信号不好，没听明白， 就不时“hum”表示依然在听，没掉线。
: 接着开始做题，题目是非常经典的:
: 在一个数组中，有的数字出现基数次，有的出现偶数次，写程序找出出现基数次的方法.
: 脑袋不知为何短路， 没有说 xor 的方法，直接就上了hash_map,
: ， 然后设置sum=0,通过sum的值来确定出现基数次的元素； 然后讨论如果输入里面所
: 有的元素都出现偶数次怎么办， 接着讨论hash table 的设计考虑的因素，然后被要求设计一个 差的hash function, 肯定没听错，的确是设计一个差的hash function, 自己一顿瞎侃.....然后被要求电话里面读code实现......
: 接着是OOD, 就是经典的设计card的问题， 说了一通，基本上和career cup查不多； 被要求实现shuffle cards的算法；
: 然后interviwer开始变要求, 如果要支持不同的游戏规则怎么办，答strategy
| i***e
发帖数: 452 | 6
still work. scan the array twice, and do xor twice. time complexity and
space complexity doesn't change.
【在 g*********s 的大作中提到】
: xor doesn't work if two numbers appear odd times.
:
: 法.
: 求设计一个
: 差的hash function, 肯定没听错，的确是设计一个差的hash function, 自己一顿瞎侃
: .....然
: 后被要求电话里面读code实现......
: 被要求实
: 现shuffle cards的算法；
| g**u
发帖数: 583 | 7
第二天就收到了。
但是第一次店面过了1周才收到第二次店面的邀请。 估计得看interviewer提交
feedback的快慢。。。
【在 k***o 的大作中提到】
: 请问电面多久后收到onsite邀请？多谢
| g*********s
发帖数: 1782 | 8 1 2 3 3. how does xor work?
【在 i***e 的大作中提到】
:
: still work. scan the array twice, and do xor twice. time complexity and
: space complexity doesn't change.
| g**u
发帖数: 583 | 9
In fact, I think xor can still work if we have 2 number appearing odd times.
after xor the entire array, we will find the first non zero bit of the
result, then we will partition the original array into 2 groups with the
first group with that bit to be 0, the second group with that bit to be 1,
we then do xor trick within each group, the left over is the number appears
odd times....
not sure for multiple(>2) number missing though....
【在 g*********s 的大作中提到】
: 1 2 3 3. how does xor work?
| g*********s
发帖数: 1782 | 10 but your question has nothing to do with missing nums.
times.
1,
appears
【在 g**u 的大作中提到】
:
: In fact, I think xor can still work if we have 2 number appearing odd times.
: after xor the entire array, we will find the first non zero bit of the
: result, then we will partition the original array into 2 groups with the
: first group with that bit to be 0, the second group with that bit to be 1,
: we then do xor trick within each group, the left over is the number appears
: odd times....
: not sure for multiple(>2) number missing though....
| k***o
发帖数: 125 | 11 嗯，知道了，祝你ONSITE好运
【在 g**u 的大作中提到】
:
: In fact, I think xor can still work if we have 2 number appearing odd times.
: after xor the entire array, we will find the first non zero bit of the
: result, then we will partition the original array into 2 groups with the
: first group with that bit to be 0, the second group with that bit to be 1,
: we then do xor trick within each group, the left over is the number appears
: odd times....
: not sure for multiple(>2) number missing though....
|
|
