一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1655|回复: 27
收起左侧

2014-04-18 Amazon on-site

[复制链接] |试试Instant~ |关注本帖
johnnywsd 发表于 2014-4-21 10:05:44 | 显示全部楼层 |阅读模式

2014(4-6月) 码农类 硕士 全职@Amazon - 网上海投 - Onsite |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

一轮:.鏈枃鍘熷垱鑷1point3acres璁哄潧
1. 判断两个linked list 是否有交叉,有则返回True,没有返回False。follow-up: 有环怎么办。. more info on 1point3acres.com
2. 写一个BestSeller类, 实现其中的三个方法. getTop50Itesm(), SellItem(String id, int num), getItemRank(String id)

二轮:.1point3acres缃
1. 一个游戏。有一个数组,每次从头或者尾取一个数(然后这个数就从数组里删除了)。你和对手轮流取数。你最大取的所有数之和是多少?

三轮:
1. leetcode 原题,maxmium subarray http://oj.leetcode.com/problems/maximum-subarray/
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
四轮:
1.  一个矩形棋盘,有写格子不能走,找到一条从A格到B格的路线。. more info on 1point3acres.com
( 这个题烙印竟然要求必须使用Java,楼主最近两年来基本都在写Python,Java在白板上写实在困难。恨死烙印)

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

评分

2

查看全部评分

 楼主| johnnywsd 发表于 2014-4-21 10:34:36 | 显示全部楼层
一轮,1
  1. class ListNode(object):
  2.     def __init__(self, val=None):
  3.         self.val = val
  4.         self.next = None. from: 1point3acres.com/bbs


  5. class Solution(object):

  6.     def __init__(self):
  7.         self._visited = dict()

  8.     def is_interset(self, A, B):. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.         p1 = A
  10.         p2 = B
  11.         while p1:. 1point 3acres 璁哄潧
  12.             if p1 not in self._visited:
  13.                 self._visited[p1] = 1
  14.             else:
  15.                 break
  16.             p1 = p1.next

  17.         while p2:. from: 1point3acres.com/bbs
  18.             tmp = self._visited.get(p2, '0')
  19.             if tmp == 1:
  20.                 return True
  21.             elif tmp == 2:
  22.                 break. more info on 1point3acres.com
  23.             else:
  24.                 # tmp == 0
  25.                 self._visited[p2] = 2
  26.             p2 = p2.next
  27.         return False
复制代码
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-21 10:36:37 | 显示全部楼层
一轮,2
  1. # Amazon need to keep a record about the best seller items.. 1point3acres.com/bbs
  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.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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. class Item(object):
  17.     def __init__(self, id=None, val=None):
  18.         self.id = id
  19.         self.val = val
    . visit 1point3acres.com for more.

  20. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  21. class BestSellerRanks(object):
  22.     def __init__(self, items):
  23.         """
  24.         Time complecity O(nlogn)
  25.         """. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.         self._items = sorted(items, key=lambda x: x.val, reverse=True)
  27.         self._dict_id_to_idx = {}. 1point 3acres 璁哄潧
  28.         for idx, item in enumerate(self._items):
  29.             self._dict_id_to_idx[item.id] = idx

  30.     def get_top_50_Ranks(self):. from: 1point3acres.com/bbs
  31.         """
  32.         Time complecity O(1)
  33.         """
  34.         return self._items[:50]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  35.     def sell_item(self, id, num):
  36.         """
  37.         Time complecity O(n)
  38.         """
  39.         idx = self._dict_id_to_idx[id]
  40.         self._items[idx].val += num
  41.         for i in range(idx, 0, -1): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  42.             if self._items[i].val > self._items[i - 1].val:
  43.                 self._dict_id_to_idx[self._items[i].id] -= 1
  44.                 self._dict_id_to_idx[self._items[i - 1].id] -= 1
  45.                 self._items[i], self._items[i - 1] = \
  46.                     self._items[i - 1], self._items[i]
  47.             else:
  48.                 break

  49.         return self._items[:50]
复制代码
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-21 10:38:56 | 显示全部楼层
二轮,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. class Solution(object):
  6.     """
  7.     DP, without cach. O(2^n)
  8.     """
  9.     def get_max_sum(self, A):
  10.         return self._get_max_sum_aux(A, 0, len(A) - 1)

  11.     def _get_max_sum_aux(self, A, left, right):
  12.         if left > right:
  13.             return 0
  14.         elif left == right:
  15.             return A[left]
  16.         else:
  17.             tmp_sum = sum(A[left:right + 1])
  18.             chose_left = tmp_sum - self._get_max_sum_aux(A, left + 1, right)
  19.             chose_right = tmp_sum - self._get_max_sum_aux(A, left, right - 1)
  20.             res = max(chose_left, chose_right)
  21.             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. class Solution(object):
  6.     """
  7.     DP, cache. O(n^2). because there are n * n keys in self._cache. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.     """
  9.     def __init__(self):
  10.         self._cache = {}

  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:. visit 1point3acres.com for more.
  18.             return A[left]
  19.         else:
  20.             if (left, right) in self._cache:
    . 鍥磋鎴戜滑@1point 3 acres
  21.                 return self._cache[(left, right)]
  22.             tmp_sum = sum(A[left:right + 1])
  23.             chose_left = tmp_sum - self._get_max_sum_aux(A, left + 1, right)
  24.             chose_right = tmp_sum - self._get_max_sum_aux(A, left, right - 1)
  25.             res = max(chose_left, chose_right)
  26.             self._cache[(left, right)] = res. 鍥磋鎴戜滑@1point 3 acres
  27.             return res
    .1point3acres缃
复制代码
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.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4. # Question: What the maxmium sum of numbers you can get.

  5. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  6. class Solution(object):
  7.     """
  8.     DP, cache. O(n^2). because there are n * n keys in self._cache
  9.     decrease the time of cacluate the sume in the recursions
  10.     """
  11.     def __init__(self):
  12.         self._cache = {}

  13.     def get_max_sum(self, A):
  14.         curr_sum = sum(A)
  15.         return self._get_max_sum_aux(A, 0, len(A) - 1, curr_sum)

  16.     def _get_max_sum_aux(self, A, left, right, curr_sum):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  17.         if left > right:
  18.             return 0
  19.         elif left == right:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20.             return A[left]
  21.         else:. Waral 鍗氬鏈夋洿澶氭枃绔,
  22.             if (left, right) in self._cache:
  23.                 return self._cache[(left, right)]
  24.             tmp_sum = curr_sum 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.             chose_left = tmp_sum - self._get_max_sum_aux(A, left + 1, right,
  26.                                                          curr_sum - A[left])
  27.             chose_right = tmp_sum - self._get_max_sum_aux(A, left, right - 1,
  28.                                                           curr_sum - A[right])
  29.             res = max(chose_left, chose_right)
  30.             self._cache[(left, right)] = res
  31.             return res
复制代码
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-21 10:52:12 | 显示全部楼层
三轮,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). From 1point 3acres bbs
  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.         . From 1point 3acres bbs
  18.         return max(f)
复制代码
.1point3acres缃
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.     }. from: 1point3acres.com/bbs
  16. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-21 10:53:19 | 显示全部楼层
四轮,1
烙印要求使用Java,楼主Java好久没使用过了,各位同学给补充下答案吧。
回复 支持 反对

使用道具 举报

discoveryi 发表于 2014-4-21 11:26:52 | 显示全部楼层
楼主maxmium subarray用DP做不至于用了45分钟吧?  能到面试官有什么特别要求吗?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2014-4-21 11:27):
难道面试官要求DP和Divide and conquer两个solution?
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-21 11:31:21 | 显示全部楼层

这个题是第三轮。楼主让第二轮的亚裔小哥整惨了。这个题就犯蒙了。亚裔小哥实在是态度特别不好。具体就不说了。。。
回复 支持 反对

使用道具 举报

Soviet 发表于 2014-4-21 11:36:10 | 显示全部楼层
请问第四个题是求Unique Paths 的数量呢?还是每个格子上有些值求最小或最大path value sum?
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-21 11:48:24 | 显示全部楼层
Soviet 发表于 2014-4-21 11:36
请问第四个题是求Unique Paths 的数量呢?还是每个格子上有些值求最小或最大path value sum?

任意条就可以了。
回复 支持 反对

使用道具 举报

discoveryi 发表于 2014-4-21 12:15:07 | 显示全部楼层
johnnywsd 发表于 2014-4-21 11:31
这个题是第三轮。楼主让第二轮的亚裔小哥整惨了。这个题就犯蒙了。亚裔小哥实在是态度特别不好。具体就不 ...

谢谢楼主,希望你拿到offer。.鐣欏璁哄潧-涓浜-涓夊垎鍦
那人请教下面试官要求DP还是Divide and conquer?
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-21 13:14:36 | 显示全部楼层
discoveryi 发表于 2014-4-21 12:15
谢谢楼主,希望你拿到offer。. 1point3acres.com/bbs
那人请教下面试官要求DP还是Divide and conquer?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
谢谢。
这两个算法有区别吗?不太懂。按说应该是要求DP。小哥头两个问题问我喜欢什么数据结构,喜欢什么算法。我说的DP,它就给我找了个DP的题。 我的代码是按照他的提示写出来的。你可以参考以下。
回复 支持 反对

使用道具 举报

qthong 发表于 2014-4-21 21:10:59 | 显示全部楼层
楼主第二轮好像做的不对,如果是search的话,应该是minmax search,假设你和对手都是用最优策略。你应该分别维护你和对手的最大值,而这里你只维护了一个最大值。如果用DP的话,我觉得你应该加一个额外纬度,表示当前数组是你轮到你取数还是对手取数。
回复 支持 反对

使用道具 举报

qthong 发表于 2014-4-21 21:28:19 | 显示全部楼层
第一题第二问用数组实现比较简单,但是效率比较差。应该有一种红黑树的实现方式。不过,估计半小时内一般人写不出来。
回复 支持 反对

使用道具 举报

nathanwong 发表于 2014-4-22 01:20:26 | 显示全部楼层
lz,你好!  第三轮游戏那个,我有点不懂。我的理解是the max sum i could get finally 是max(对手最后得到的sum,我最后得到的总和)的最大值,因为游戏没有规定谁先开始取数。
第二,我没想到怎么用dp? 我的navie方法是我想的是无论对手是谁
每次都是max(left, right)取最大的. from: 1point3acres.com/bbs
前后指针往中间 move。 两个对手各自维护一个max。  描述的比较乱,请问可否会的同学各个指点? 谢谢了。。。。
回复 支持 反对

使用道具 举报

neomiracle 发表于 2014-4-22 07:02:05 | 显示全部楼层
nathanwong 发表于 2014-4-21 12:20
lz,你好!  第三轮游戏那个,我有点不懂。我的理解是the max sum i could get finally 是max(对手最后得到 ...

LZ拿到了amazon的offer,估计没时间回贴了 我来替他说下这道题吧。题目的意思是两个人轮流取数,而且两个人都会在当前情况下取到最大的数字之和。其实是如果该数组确定以后,两个人所取的结果已经是一个定值了,因为两人的策略相同。
例如数组为[4, 7, 2, 9],A先取 取到的数一定[9,7] B一定是[4, 2]。因为如果只有[4,7,2]时, B先取,B可以取4或2,剩下[7,2]或[7,4]时,A一定会取7,这样B能取到[4,2]A能取到[9,7]
所以说解题的思路是利用DFS找到所有的可能性,一个search tree 然后在回溯找到从最后到当前的所取到的数列,这样时间复杂度为2^n (确切为 2^(n - 1))。
然后就是为了提高时间复杂度,采用DP的思路。假设数组为D,我们用两个二维DP数组A B, A[j] 表示先取者取 i-j之间数的所取最大值。B[j]表示后取者在i-j之前所取的值,这样的话有以下动态转移方程:
A[j] = A + B[i + 1][j]; B[j] = A[j - 1];
A[j] = A[j][j] + B[j - 1]; B[j] = A[i + 1][j];

补充内容 (2014-4-21 18:08):
A[j] = A + B[i + 1][j]; B[j] = A[i + 1][j];
A[j] = A[j][j] + B[j - 1]; B[j] = A[j - 1];

补充内容 (2014-4-21 18:10):
二维数组居然打不出来。。。。
A(i,j) = A(j,j) + B(i, j-1); B(i,j) = A(i,j-1)
A(i,j) = A(i,i) + B(i+1,j); B(i,j) = A(i+1,j);
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-22 08:33:30 | 显示全部楼层
nathanwong 发表于 2014-4-22 01:20
lz,你好!  第三轮游戏那个,我有点不懂。我的理解是the max sum i could get finally 是max(对手最后得到 ...

规定我先取数,对手后取。
我想你的navie方法是不对的。例如:1,1,9,5 四个数,你一定回先取1而不是5.
回复 支持 反对

使用道具 举报

lhn9021 发表于 2014-4-22 09:40:02 | 显示全部楼层
我的解法跟neomiracle比较像 不过我是bottom up
A B 的策略是一样的
当还剩0个时 A(B)什么都取不了
当还剩1个时 A(B)只能取那一个
当还剩2个时 A(B)取两个的最大值. 鍥磋鎴戜滑@1point 3 acres
当还剩3个时 A(B)取两边最大值 中间的还归A(B)
当还剩4个时 A(B)取 max(取最左边+右边三个的和减去B(A)取右边三个的最大值,取最右边+左边三个的和减去B(A)取左边三个的最大值)
以此类推用DP解
回复 支持 反对

使用道具 举报

nathanwong 发表于 2014-4-22 10:07:44 | 显示全部楼层
正解!!!!!!厉害 lz
回复 支持 反对

使用道具 举报

nathanwong 发表于 2014-4-22 10:16:30 | 显示全部楼层
neomiracle 发表于 2014-4-22 07:02
LZ拿到了amazon的offer,估计没时间回贴了 我来替他说下这道题吧。题目的意思是两个人轮流取数, ...

朋友?你nyu的?如果是的话,我们可以有机会再library 碰面的。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 18:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表