查看: 862|回复: 11
收起左侧

亚麻社招OA1

|只看干货
匿名用户-A3F  发表于 2021-10-17 03:17:46 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎

2021(10-12月) 码农类General 硕士 全职@Amazon - 网上海投 - 在线笔试  | 😐 Neutral 😐 AverageOther | 其他
前两天刚做的OA1,遇到了新题
第一道是类似于compare version number写个比较器就行
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
问题。 图片在附件里


本帖子中包含更多资源

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

评分

参与人数 4大米 +5 收起 理由
ruoyi.rrr + 2
qitidash + 1 给你点个赞!
Flore20 + 1 给你点个赞!
mierdalol + 1 给你点个赞!

查看全部评分


上一篇:图森电面挂经验顺便吐槽下面试官
下一篇:数学能行 - OA (求大米)
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (124)
 
 
1% (2)    👎
ciacia7621 发表于 2021-10-17 12:54
主要是它要打印所有组合,这样如果存在大量重复元素不可避免worst case都是O(mn),即使查找过程是nlogn ...

  1. import heapq
  2. import bisect
  3. def optimals(deviceCapacity, foregroundAppList, backgroundAppList):
  4.     nums1 = sorted(foregroundAppList, key = lambda x: x[1], reverse = True)
  5.     nums2 = sorted(backgroundAppList, key = lambda x: x[1], reverse = True)
  6.     # result and the most optimal sum of memeory
  7.     res, current = [], 0
  8.     # heap
  9.     pq, visited = [(-nums1[0][1]-nums2[0][1], (0,0))], {(0, 0)}
  10.     while pq:
  11.         w, (i, j) = heapq.heappop(pq)
  12.         if j + 1 < len(nums2) and (i, j + 1) not in visited:
  13.             heapq.heappush(pq, ( - nums1[i][1] - nums2[j + 1][1], (i, j + 1)))
  14.             visited.add((i, j + 1))
  15.         if i + 1 < len(nums1) and (i + 1, j) not in visited:
  16.             heapq.heappush(pq, ( - nums1[i + 1] - nums2[j], (i + 1, j)))
  17.             visited.add((i + 1, j))
  18.         # skip sums greater than device capacity
  19.         if -w > deviceCapacity:
  20.             continue
  21.         # if we see a sum smaller than optimal sum, no need to continue
  22.         if -w < current:
  23.             break
  24.         if abs(-w-deviceCapacity) < abs(current-deviceCapacity):
  25.             res = [[nums1[i][0], nums2[j][0]]]
  26.             current = -w
  27.         elif -w == current:
  28.             res.append([nums1[i][0], nums2[j][0]])
  29.     return res

  30. def optimalsBisect(deviceCapacity, foregroundAppList, backgroundAppList):
  31.     nums1 = sorted([(memory, idx) for idx, memory in foregroundAppList])
  32.     nums2 = sorted([(memory, idx) for idx, memory in backgroundAppList])
  33.     res, current = [], 0
  34.     for m, i in nums1:
  35.         pos = bisect.bisect_right(nums2, (deviceCapacity - m, float("inf")))
  36.         # find the closest one
  37.         if pos == 0:
  38.             w = m + nums2[pos][0]
  39.         elif pos == len(nums2):
  40.             pos = pos - 1
  41.             w = m + nums2[pos][0]
  42.         elif pos >= len(nums2) - 1:
  43.             w = m + nums2[pos][0]
  44.         else:
  45.             if abs(m+nums2[pos-1][0]-deviceCapacity) < abs(m+nums2[pos][0]-deviceCapacity):
  46.                 pos = pos - 1
  47.             w = m + nums2[pos][0]
  48.         # update the optimal memory sum
  49.         if w > deviceCapacity:
  50.             continue
  51.         if abs(w-deviceCapacity) < abs(current-deviceCapacity):
  52.             res = []
  53.             current = w
  54.         # add every pair sum up to current optimal sum
  55.         while pos >= 0 and m + nums2[pos][0] == current:
  56.             res.append([i, nums2[pos][1]])
  57.             pos -= 1
  58.     return res

  59. c = 7
  60. f = [[1, 2], [2, 4], [3, 6]]
  61. b = [[1, 2]]
  62. print(optimalsBisect(c, f, b))


  63. c1 = 10
  64. f1 = [[1, 3], [2, 5], [3, 7], [4, 10]]
  65. b1 = [[1, 2], [2, 3], [3, 4], [4, 5]]
  66. print(optimalsBisect(c1, f1, b1))

  67. c2 = 16
  68. f2 = [[2, 7], [3, 14]]
  69. b2 = [[2, 10], [3, 14]]
  70. print(optimalsBisect(c2, f2, b2))

复制代码
binary search的写完了,但我不确定是否漏掉了什么edge case。如果大部分组合都是Optimal的确会出现你说这种情况,所以如果一个O(MN)的for loop可以AC的话我不会折腾这些的.
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (124)
 
 
1% (2)    👎
本帖最后由 SoWhat0309 于 2021-10-16 22:49 编辑
ciacia7621 发表于 2021-10-16 22:25
第二题暴力能过吗?除非没有重复数字,要不双指针会漏掉结果

貌似可以过。。。不过其实可以先sort两个list,二分法查找或者参考https://leetcode.com/problems/find-k-pairs-with-smallest-sums/ (二者之和从大到小,只看比Capacity 小的第一个和), 这样可以O(NlogN) 防止N很大的时候TLE(楼主没截数据范围是有点遗憾)
  1. import heapq
  2. def optimals(deviceCapacity, foregroundAppList, backgroundAppList):
  3.     nums1 = sorted(foregroundAppList, key = lambda x: x[1], reverse = True)
  4.     nums2 = sorted(backgroundAppList, key = lambda x: x[1], reverse = True)
  5.     # result and the most optimal sum of memeory
  6.     res, current = [], 0
  7.     # heap
  8.     pq, visited = [(-nums1[0][1]-nums2[0][1], (0,0))], {(0, 0)}
  9.     while pq:
  10.         w, (i, j) = heapq.heappop(pq)
  11.         if j + 1 < len(nums2) and (i, j + 1) not in visited:
  12.             heapq.heappush(pq, ( - nums1[i][1] - nums2[j + 1][1], (i, j + 1)))
  13.             visited.add((i, j + 1))
  14.         if i + 1 < len(nums1) and (i + 1, j) not in visited:
  15.             heapq.heappush(pq, ( - nums1[i + 1] - nums2[j], (i + 1, j)))
  16.             visited.add((i + 1, j))
  17.         # skip sums greater than device capacity
  18.         if -w > deviceCapacity:
  19.             continue
  20.         # if we see a sum smaller than optimal sum, no need to continue
  21.         if -w < current:
  22.             break
  23.         if abs(-w-deviceCapacity) < abs(current-deviceCapacity):
  24.             res = [[nums[1][0], nums[2][0]]]
  25.         elif -w == current:
  26.             res.append([nums[1][0], nums[2][0]])
  27.     return res
复制代码
现改的,binary search的懒的写了


补充内容 (2021-10-18 01:18 +8:00):
heap复杂度最坏是mnlog(mn),基本就指望stop early,binary search的有空补。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (124)
 
 
1% (2)    👎
ciacia7621 发表于 2021-10-17 11:44
可能我理解有误,但看起来这样用heapq最坏的时间复杂度应该是mnlog(mn),比如说capcity非常小的话,几 ...

是的heap是(mn)log(mn)最坏情况 (我回头改一下),是否更好全看device Capacity卡在哪,是否能stop early... 本来是想sort之后对每一个foreground app,在background app里bisect一下deviceCapacity - foregroundMemory,更新最优方案的内存使用+ result list, 但edge case没想清楚就拿现成的改了下。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (143)
 
 
0% (1)    👎
双指针会漏掉一些pair吧,双循环brutal force过不了?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (107)
 
 
16% (21)    👎
第二题暴力能过吗?除非没有重复数字,要不双指针会漏掉结果
回复

使用道具 举报

rw802 2021-10-17 15:10:48 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎
sort + two ptrs?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (107)
 
 
16% (21)    👎
SoWhat0309 发表于 2021-10-16 22:36
貌似可以过。。。不过其实可以先sort两个list,二分法查找或者参考https://leetcode.com/problems/find-k ...

可能我理解有误,但看起来这样用heapq最坏的时间复杂度应该是mnlog(mn),比如说capcity非常小的话,几乎所有的组合都会入堆,然后挨个pop
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (107)
 
 
16% (21)    👎
SoWhat0309 发表于 2021-10-17 12:17
是的heap是(mn)log(mn)最坏情况 (我回头改一下),是否更好全看device Capacity卡在哪,是否能stop earl ...

主要是它要打印所有组合,这样如果存在大量重复元素不可避免worst case都是O(mn),即使查找过程是nlogn,到collect或者打印结果的时候,还是会变成mn,
回复

使用道具 举报

地里的匿名用户
匿名用户-DF8  发表于 2021-10-18 12:19:12
本楼: 👍   0% (0)
 
 
0% (0)   👎
楼主方便直接贴图吗?下载zip文件好像还要用大米。。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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