2014-04-18 Amazon on-site

除了第四轮烙印要求必须使用Java外，楼主都是用Python写的。

一轮：
1. 判断两个linked list 是否有交叉，有则返回True,没有返回False。follow-up： 有环怎么办。
2. 写一个BestSeller类， 实现其中的三

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

a，楼主最近两年来基本都在写Python，Java在白板上写实在困难。恨死烙印）

楼主会在楼下发自己的答案。希望大家批评指正。

我感觉LZ的第3题这么做是对的。。。我们是不是有一个assumption，看不到除了两头以外里面的数字？所以取当前最大。另外有没有一个assumption没有重复数字？

发现亚麻收了好多nyu的

lz就是个jb

一轮，1

1. class ListNode(object):
   
2.     def __init__(self, val=None):
   
3.         self.val = val
   
4.         self.next = None
   
5. 
   
6. 
   
7. class Solution(object):
   
8. 
   
9.     def __init__(self):
   
10.         self._visited = dict()
    
11. 
    
12.     def is_interset(self, A, B):
    
13.         p1 = A
    
14.         p2 = B
    
15.         while p1:
    
16.             if p1 not in self._visited:
    
17.                 self._visited[p1] = 1
    
18.             else:
    
19.                 break
    
20.             p1 = p1.next
    
21. 
    
22.         while p2:
    
23.             tmp = self._visited.get(p2, '0')
    
24.             if tmp == 1:
    
25.                 return True
    
26.             elif tmp == 2:
    
27.                 break
    
28.             else:
    
29.                 # tmp == 0
    
30.                 self._visited[p2] = 2
    
31.             p2 = p2.next
    
32.         return False
    

复制代码

一轮，2

1. # Amazon need to keep a record about the best seller items.
   
2. # We need this class
   
3. # class BestSellerRanks{
   
4. #     public List<Item> getTop50Ranks(); // get top 50 ranked Items
   
5. #     public getItemRank(String id) // get the rank of the item whoes id is id.
   
6. #     public sellItem(String id, int num) // sell more num items whose id is id
   
7. # }
   
8. # We need to make these three method run as fast as possible.
   
9. # FYI the Item class may like this
   
10. # class Item{
    
11. #     String id; // Unique id for each item
    
12. #     String name;
    
13. #     int val; // number of this item sold.
    
14. #     .....
    
15. # }
    
16. 
    
17. 
    
18. class Item(object):
    
19.     def __init__(self, id=None, val=None):
    
20.         self.id = id
    
21.         self.val = val
    
22. 
    
23. 
    
24. class BestSellerRanks(object):
    
25.     def __init__(self, items):
    
26.         """
    
27.         Time complecity O(nlogn)
    
28.         """
    
29.         self._items = sorted(items, key=lambda x: x.val, reverse=True)
    
30.         self._dict_id_to_idx = {}
    
31.         for idx, item in enumerate(self._items):
    
32.             self._dict_id_to_idx[item.id] = idx
    
33. 
    
34.     def get_top_50_Ranks(self):
    
35.         """
    
36.         Time complecity O(1)
    
37.         """
    
38.         return self._items[:50]
    
39. 
    
40.     def sell_item(self, id, num):
    
41.         """
    
42.         Time complecity O(n)
    
43.         """
    
44.         idx = self._dict_id_to_idx[id]
    
45.         self._items[idx].val += num
    
46.         for i in range(idx, 0, -1):
    
47.             if self._items[i].val > self._items[i - 1].val:
    
48.                 self._dict_id_to_idx[self._items[i].id] -= 1
    
49.                 self._dict_id_to_idx[self._items[i - 1].id] -= 1
    
50.                 self._items[i], self._items[i - 1] = \
    
51.                     self._items[i - 1], self._items[i]
    
52.             else:
    
53.                 break
    
54. 
    
55.         return self._items[:50]
    

复制代码

二轮，1

以下三个Solutions是逐步优化的。

Solution1

1. # You and your friend are playing a game
   
2. # There is an list of numbers, you pick up one from either
   
3. # the front or the rare. Then your friend pick up one
   
4. # Question: What the maxmium sum of numbers you can get.
   
5. 
   
6. 
   
7. class Solution(object):
   
8.     """
   
9.     DP, without cach. O(2^n)
   
10.     """
    
11.     def get_max_sum(self, A):
    
12.         return self._get_max_sum_aux(A, 0, len(A) - 1)
    
13. 
    
14.     def _get_max_sum_aux(self, A, left, right):
    
15.         if left > right:
    
16.             return 0
    
17.         elif left == right:
    
18.             return A[left]
    
19.         else:
    
20.             tmp_sum = sum(A[left:right + 1])
    
21.             chose_left = tmp_sum - self._get_max_sum_aux(A, left + 1, right)
    
22.             chose_right = tmp_sum - self._get_max_sum_aux(A, left, right - 1)
    
23.             res = max(chose_left, chose_right)
    
24.             return res
    

复制代码

Solution2

1. # You and your friend are playing a game
   
2. # There is an list of numbers, you pick up one from either
   
3. # the front or the rare. Then your friend pick up one
   
4. # Question: What the maxmium sum of numbers you can get.
   
5. 
   
6. 
   
7. class Solution(object):
   
8.     """
   
9.     DP, cache. O(n^2). because there are n * n keys in self._cache
   
10.     """
    
11.     def __init__(self):
    
12.         self._cache = {}
    
13. 
    
14.     def get_max_sum(self, A):
    
15.         return self._get_max_sum_aux(A, 0, len(A) - 1)
    
16. 
    
17.     def _get_max_sum_aux(self, A, left, right):
    
18.         if left > right:
    
19.             return 0
    
20.         elif left == right:
    
21.             return A[left]
    
22.         else:
    
23.             if (left, right) in self._cache:
    
24.                 return self._cache[(left, right)]
    
25.             tmp_sum = sum(A[left:right + 1])
    
26.             chose_left = tmp_sum - self._get_max_sum_aux(A, left + 1, right)
    
27.             chose_right = tmp_sum - self._get_max_sum_aux(A, left, right - 1)
    
28.             res = max(chose_left, chose_right)
    
29.             self._cache[(left, right)] = res
    
30.             return res
    

复制代码

Solution3

1. # You and your friend are playing a game
   
2. # There is an list of numbers, you pick up one from either
   
3. # the front or the rare. Then your friend pick up one
   
4. # Question: What the maxmium sum of numbers you can get.
   
5. 
   
6. 
   
7. class Solution(object):
   
8.     """
   
9.     DP, cache. O(n^2). because there are n * n keys in self._cache
   
10.     decrease the time of cacluate the sume in the recursions
    
11.     """
    
12.     def __init__(self):
    
13.         self._cache = {}
    
14. 
    
15.     def get_max_sum(self, A):
    
16.         curr_sum = sum(A)
    
17.         return self._get_max_sum_aux(A, 0, len(A) - 1, curr_sum)
    
18. 
    
19.     def _get_max_sum_aux(self, A, left, right, curr_sum):
    
20.         if left > right:
    
21.             return 0
    
22.         elif left == right:
    
23.             return A[left]
    
24.         else:
    
25.             if (left, right) in self._cache:
    
26.                 return self._cache[(left, right)]
    
27.             tmp_sum = curr_sum
    
28.             chose_left = tmp_sum - self._get_max_sum_aux(A, left + 1, right,
    
29.                                                          curr_sum - A[left])
    
30.             chose_right = tmp_sum - self._get_max_sum_aux(A, left, right - 1,
    
31.                                                           curr_sum - A[right])
    
32.             res = max(chose_left, chose_right)
    
33.             self._cache[(left, right)] = res
    
34.             return res
    

复制代码

三轮，1

Solution1

1. class Solution:
   
2.     # @param A, a list of integers
   
3.     # @return an integer
   
4.     def maxSubArray(self, A):
   
5.         num = len(A)
   
6.         f = [None] * num
   
7.         if not A:
   
8.             return 0
   
9.         if num == 1:
   
10.             return A[0]
    
11.         f[0] = A[0]
    
12.         mymax = A[0]
    
13.         #We should ignore the sum of the
    
14.         #previous n-1 elements if nth element is greater than the sum.
    
15.         for i in xrange(1, num):
    
16.             f[i] = max(A[i], f[i-1] + A[i])
    
17.         
    
18.         return max(f)

复制代码

Solution2

1. public class Solution {
   
2.     public int maxSubArray(int[] A) {
   
3.         if (A == null){
   
4.             return 0;
   
5.         }
   
6.         int curr_max = A[0];
   
7.         int max = A[0];
   
8.         for(int i=1; i<A.length; i++){
   
9.             curr_max = Math.max(curr_max + A[i], A[i]);
   
10.             if (curr_max > max){
    
11.                 max = curr_max;
    
12.             }
    
13.         }
    
14.         return max;
    
15.     }
    
16. }

复制代码

四轮，1
烙印要求使用Java，楼主Java好久没使用过了，各位同学给补充下答案吧。

楼主maxmium subarray用DP做不至于用了45分钟吧？  能到面试官有什么特别要求吗？

补充内容 (2014-4-21 11:27):
难道面试官要求DP和Divide and conquer两个solution?

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请问第四个题是求Unique Paths 的数量呢？还是每个格子上有些值求最小或最大path value sum？

Soviet 发表于 2014-4-21 11:36
请问第四个题是求Unique Paths 的数量呢？还是每个格子上有些值求最小或最大path value sum？

任意条就可以了。