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都被等概率返回。
|
