g********d 发帖数: 43 | 1 在Google, M$面试被我糟践之后,终于在Amazon电面中发挥稍微正常点了,两轮面试,
感觉还行, 和面试官都挺聊得来。希望能有好结果。
第一轮面试:
上来就问我有啥问题没,以前面试没有碰到上来就让我提问的,有点懵,既然让提好就
不客气了.问了一个,他回答了之后问我还有问题么,我心想难道今天就是让我问问题
么,这倒不错,就又问了几个。后来面试管急了,说“好了,让我问你几个问题吧”。
我心想,要出题了。果不其然。
给一个数组和一个random number generator,写一个函数,返回这个数组的一个
permutation, 要求任何可能的permutation都被等概率返回。
设计一个aircraft traffic control系统。 这个答的一般,说了一些class,method什
么的。
然后就聊我的research,最后就开始瞎侃了,问我去过seattle没有,介绍seattle,说
附近有山,适合hiking, blahblah,问我课余喜欢啥活动,我说soccer,然后就又侃了
一通。。。
第二轮面试
先介绍Research,然后追着research里的一些 |
f****4 发帖数: 1359 | |
l***r 发帖数: 241 | |
b******v 发帖数: 1493 | |
g********d 发帖数: 43 | 5 Relational Database
【在 f****4 的大作中提到】 : RDB 是啥?
|
r****o 发帖数: 1950 | 6 Bless,
BTW,请问什么是RDB啊?
【在 g********d 的大作中提到】 : 在Google, M$面试被我糟践之后,终于在Amazon电面中发挥稍微正常点了,两轮面试, : 感觉还行, 和面试官都挺聊得来。希望能有好结果。 : 第一轮面试: : 上来就问我有啥问题没,以前面试没有碰到上来就让我提问的,有点懵,既然让提好就 : 不客气了.问了一个,他回答了之后问我还有问题么,我心想难道今天就是让我问问题 : 么,这倒不错,就又问了几个。后来面试管急了,说“好了,让我问你几个问题吧”。 : 我心想,要出题了。果不其然。 : 给一个数组和一个random number generator,写一个函数,返回这个数组的一个 : permutation, 要求任何可能的permutation都被等概率返回。 : 设计一个aircraft traffic control系统。 这个答的一般,说了一些class,method什
|
w******1 发帖数: 520 | 7 后来出了道题,给一个数
组和一个数K,找到所有的pairs,每个pair里两个数的和等于K。我就问数组有序么,他
就说有序怎么处理、无序又怎么处理。我就blahblah。
===========
这个怎么答?给个提示行么 |
g********d 发帖数: 43 | 8 如果数组有序,用头尾两个指针, 计算这两个指针所指的数之和P,根据P和K的关系决定
哪个指针移动,直到这两个指针相遇. O(n).
或者对每一个元素i, 用binary search在a[i+1 .. n]子数组搜索K-a[i],O(n*logn)
如果无序,先排序,再用上述算法。 不知道到有没有更快的算法。
【在 w******1 的大作中提到】 : 后来出了道题,给一个数 : 组和一个数K,找到所有的pairs,每个pair里两个数的和等于K。我就问数组有序么,他 : 就说有序怎么处理、无序又怎么处理。我就blahblah。 : =========== : 这个怎么答?给个提示行么
|
r****o 发帖数: 1950 | 9 无序的话,就用hash table就可以了把,不用排序。O(n)。
【在 g********d 的大作中提到】 : 如果数组有序,用头尾两个指针, 计算这两个指针所指的数之和P,根据P和K的关系决定 : 哪个指针移动,直到这两个指针相遇. O(n). : 或者对每一个元素i, 用binary search在a[i+1 .. n]子数组搜索K-a[i],O(n*logn) : 如果无序,先排序,再用上述算法。 不知道到有没有更快的算法。
|
s******t 发帖数: 2374 | 10 恩。有序的话也可以用任何一种search方法,比如binary search可以达到 log n
【在 r****o 的大作中提到】 : 无序的话,就用hash table就可以了把,不用排序。O(n)。
|
|
|
g********d 发帖数: 43 | 11 忘提了,空间代价必须是constant.
我当时比较了一下,如果用hash table,空间需求会比较大,如果大小固定,当数组很
大时,性能会degrade。
排序的空间代价小,但查询慢。
我说了hash之后,他就追问hash table的细节了,开散列、闭散列等等
后来他又问如果这个数组实在太大,放不到内存里,我就有比较了一下hash table, B/
B+ tree,不过这里有点心虚,以前没考虑过hash table很大的情况下,磁盘I/O,key
clustering会造成的性能影响。
【在 r****o 的大作中提到】 : 无序的话,就用hash table就可以了把,不用排序。O(n)。
|
b******v 发帖数: 1493 | 12 有序的话,对每个元素a[i],用binary search找K-a[i],代价是log n
那么一共是 O(nlog(n))吧?
【在 s******t 的大作中提到】 : 恩。有序的话也可以用任何一种search方法,比如binary search可以达到 log n
|
d*******8 发帖数: 785 | 13 Bless,应该能拿到Onsite了
【在 g********d 的大作中提到】 : 在Google, M$面试被我糟践之后,终于在Amazon电面中发挥稍微正常点了,两轮面试, : 感觉还行, 和面试官都挺聊得来。希望能有好结果。 : 第一轮面试: : 上来就问我有啥问题没,以前面试没有碰到上来就让我提问的,有点懵,既然让提好就 : 不客气了.问了一个,他回答了之后问我还有问题么,我心想难道今天就是让我问问题 : 么,这倒不错,就又问了几个。后来面试管急了,说“好了,让我问你几个问题吧”。 : 我心想,要出题了。果不其然。 : 给一个数组和一个random number generator,写一个函数,返回这个数组的一个 : permutation, 要求任何可能的permutation都被等概率返回。 : 设计一个aircraft traffic control系统。 这个答的一般,说了一些class,method什
|
g********d 发帖数: 43 | 14 借你吉言,希望如此
设计类题目是短板阿。。。回头得补补
【在 d*******8 的大作中提到】 : Bless,应该能拿到Onsite了
|
m*****k 发帖数: 64 | 15 这道题怎么做的?
给一个数组和一个random number generator,写一个函数,返回这个数组的一个
permutation, 要求任何可能的permutation都被等概率返回。
【在 g********d 的大作中提到】 : 在Google, M$面试被我糟践之后,终于在Amazon电面中发挥稍微正常点了,两轮面试, : 感觉还行, 和面试官都挺聊得来。希望能有好结果。 : 第一轮面试: : 上来就问我有啥问题没,以前面试没有碰到上来就让我提问的,有点懵,既然让提好就 : 不客气了.问了一个,他回答了之后问我还有问题么,我心想难道今天就是让我问问题 : 么,这倒不错,就又问了几个。后来面试管急了,说“好了,让我问你几个问题吧”。 : 我心想,要出题了。果不其然。 : 给一个数组和一个random number generator,写一个函数,返回这个数组的一个 : permutation, 要求任何可能的permutation都被等概率返回。 : 设计一个aircraft traffic control系统。 这个答的一般,说了一些class,method什
|
d*******8 发帖数: 785 | 16 1/setsize概率随机 Pick一个数,然后Remove这个数,在剩余子集里再
这么Pick。
vector array; //as input
vector result;
vector::iterator it = array.begin();
while(array.size()!=0)
{
int picker = random(array.size());
result.push_back(array[picker]);
array.erase(it+picker);
}
【在 m*****k 的大作中提到】 : 这道题怎么做的? : 给一个数组和一个random number generator,写一个函数,返回这个数组的一个 : permutation, 要求任何可能的permutation都被等概率返回。
|