amazonLocal 组 面经# JobHunting - 待字闺中
m*k
1 楼
amazonLocal 组，
上上周3面的，本周2收到据信，攒人品，上面经。
印女，PM，
1. copy linked list with random link in each node. 我给的答案不是回家后
google到的那个big linklist then separate， 我让原node的random link point to
its clone。
这样也能达到要求但改变了原始link,她也没反对。
2. code IsBST,
我写了个递归，还需要看root结点是否大于left child's subtree max, 以及是否小于
right child's subtree min, 被她问到复杂度， 指出非最优，重新想了一会， 说那
就inorder traversal , 每次和前一个值比一下，先给一个Prev=-infinity, 在白板上
纠结了一阵写出了和http://www.mitbbs.com/article/JobHunting/31990685_3.html相似的code.不过我是把prev传入IsBST,而且用
prev = +infinity 来表示false; 还是Kramnik (克拉姆尼克)的更graceful, 兄弟你咋
不早点贴出来啊，hehe！
3. customers want to buy some products but the products are out of stock,
design a system to notify them when those products are again available.
我回答说这就是个小功能，建立一个 wishList table with 2 columns, prodId 和
customerIDs 每次货物到库重新录入系统时 retrieve wishList table by productId
, 然后给粗customer 发信。但她好像不满意，强调说要设计一个
系统来实现。我傻了一会，又说可以在数据库中加一个trigger，一旦product 数目从0
update 到正值就给信. 她好像还是不满意。 后来想，难道她想听JMS?
白男，自报是director，
spend quite some time talking about my background and his team.
1.implement priority queue, 我回答用hashmap, key is priority level, value
is a normal queue, 这个非主流自创和上网看到的post（http://www.java-forums.org/java-lang/7449-how-implement-priority-queue-java.html）简直大相庭径， 表砸我，hoho!
2.design, display a customer's friends list who also bought the product he
is curently looking at.
小白男，
1. storeLocator, 100 stores, find the closest k=5 to customer's location. max-heap.
2. based on 1, given MaxHeap interface, implement
specified methods.
3. design deck, card classes.
小印男,
1. implement LRU cache , 我说可以用java的LinkedHashMap, 或者自己用 hashMap +
double linked list.
2. how to improve a web app. 我先draw a graph from browser to App server and DB, 然后每个环节侃了一通。
3. stock history data int stock[n], find the best sell and buy time.
O(n) ，
int maxgain =0, best_buytime = 0, best_selltime =0; current_buytime=0;
current_selltime =0;
for( i = 1 to stock.length-1)
{
if (stock[i] > stock[current_selltime])
{
current_selltime = i ;
//update maxgain if possible
int current_gain = stock[current_selltime] - stock[current_buytime];
if(current_gain > maxgain)
{
maxgain = current_gain ;
best_selltime = current_selltime;
best_buytime = current_buytime;
}
}
if (stock[i] < stock[current_buytime])
{
current_selltime = i;
current_buytime = i;
}
}
也可以在stock array 尾部加一个dummy end node, stock[n+1] = -1,
这样就只需要在if (stock[i] < stock[current_buytime]) block 中 update
maxgain 和 best_*time.
总结，这些经典题应该烂熟于心，对于我这样的非牛人现场纠结地想和写基本等于死菜
。 ：（
anyway, 谨以此文纪念又一次搞砸的面试。
上上周3面的，本周2收到据信，攒人品，上面经。
印女，PM，
1. copy linked list with random link in each node. 我给的答案不是回家后
google到的那个big linklist then separate， 我让原node的random link point to
its clone。
这样也能达到要求但改变了原始link,她也没反对。
2. code IsBST,
我写了个递归，还需要看root结点是否大于left child's subtree max, 以及是否小于
right child's subtree min, 被她问到复杂度， 指出非最优，重新想了一会， 说那
就inorder traversal , 每次和前一个值比一下，先给一个Prev=-infinity, 在白板上
纠结了一阵写出了和http://www.mitbbs.com/article/JobHunting/31990685_3.html相似的code.不过我是把prev传入IsBST,而且用
prev = +infinity 来表示false; 还是Kramnik (克拉姆尼克)的更graceful, 兄弟你咋
不早点贴出来啊，hehe！
3. customers want to buy some products but the products are out of stock,
design a system to notify them when those products are again available.
我回答说这就是个小功能，建立一个 wishList table with 2 columns, prodId 和
customerIDs 每次货物到库重新录入系统时 retrieve wishList table by productId
, 然后给粗customer 发信。但她好像不满意，强调说要设计一个
系统来实现。我傻了一会，又说可以在数据库中加一个trigger，一旦product 数目从0
update 到正值就给信. 她好像还是不满意。 后来想，难道她想听JMS?
白男，自报是director，
spend quite some time talking about my background and his team.
1.implement priority queue, 我回答用hashmap, key is priority level, value
is a normal queue, 这个非主流自创和上网看到的post（http://www.java-forums.org/java-lang/7449-how-implement-priority-queue-java.html）简直大相庭径， 表砸我，hoho!
2.design, display a customer's friends list who also bought the product he
is curently looking at.
小白男，
1. storeLocator, 100 stores, find the closest k=5 to customer's location. max-heap.
2. based on 1, given MaxHeap
specified methods.
3. design deck, card classes.
小印男,
1. implement LRU cache , 我说可以用java的LinkedHashMap, 或者自己用 hashMap +
double linked list.
2. how to improve a web app. 我先draw a graph from browser to App server and DB, 然后每个环节侃了一通。
3. stock history data int stock[n], find the best sell and buy time.
O(n) ，
int maxgain =0, best_buytime = 0, best_selltime =0; current_buytime=0;
current_selltime =0;
for( i = 1 to stock.length-1)
{
if (stock[i] > stock[current_selltime])
{
current_selltime = i ;
//update maxgain if possible
int current_gain = stock[current_selltime] - stock[current_buytime];
if(current_gain > maxgain)
{
maxgain = current_gain ;
best_selltime = current_selltime;
best_buytime = current_buytime;
}
}
if (stock[i] < stock[current_buytime])
{
current_selltime = i;
current_buytime = i;
}
}
也可以在stock array 尾部加一个dummy end node, stock[n+1] = -1,
这样就只需要在if (stock[i] < stock[current_buytime]) block 中 update
maxgain 和 best_*time.
总结，这些经典题应该烂熟于心，对于我这样的非牛人现场纠结地想和写基本等于死菜
。 ：（
anyway, 谨以此文纪念又一次搞砸的面试。
