amazon offer+面经， facebook面经(下周二还有电面)

为啥感觉amazon一直比其他家多

恭喜LZ啦！我得了CMU INI 和MISM的2012Fall的AD，正在犹豫去哪个呢。LZ知道哪个就业好些，能给点儿建议么？还有MISM有个背景调查是吧，INI也有么? 祝LZ多拿Offer!

哈哈，来看题了。感谢分享面经。Facebook真心bug啊~

谢谢lz的面经哇！lz说的on campus面试是在pitts还是SV校区呀？？

求三个数和为零的那题转化成两个数和为指定值的方法？给跪了
ilovexiao77 发表于 2012-3-12 12:38

只知道n^2的做法

1. 
   
2. 首先对数组A排序,从小到大
   
3. for i = 0 to n-1
   
4.   sum = -a[i]
   
5.   start = 0, end = n -1;
   
6.   while （start < end）
   
7.     if a[start] + a[end] == -a[i]  and start != i and end !=i 则找到
   
8.     if a[start] + a[end] > -a[i] --end;
   
9.     else ++start
   

复制代码

低音兄我来顶顶你的帖子。。。才看见。。才发现

回复 9# newlxnewlx

薄熙来刚出事，你就换头像了。还挺迅速

danielgao 发表于 2012-3-21 14:40
只知道n^2的做法

输出一个数组里所有的和为0的三个数

如果能用额外空间的话，好像可以用hash table做：

====================================
1. use a double-loop to traverse the whole array, enumerate each possible pair of numbers, build up a hash table, use the sum values of the two numbers as the key, and the positions of the two numbers as the values. O(n^2) time, O(n) space

2. traverse the whole array once again, for each value, try to retrieve the positons from the hash table by the key of [current value minus by zero]... done! O(n)

total time complexity: O(n^2), w/ additional O(n) space.

====================================

similarily, sum two numbers into a certain value,

1. create a hash table, use each value of the numbers in the array as a key, then their positions as values. O(n) time w/ O(n) space
2. traverse the whole array once again, for each value, try to retrieve the positions from the hash table by the key of [certain value minus current value]... done. O(n) time

total: O(n) time w/ O(n) additional space..

======================================

路过看看

小弱拜读大作。