一亩三分地论坛

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

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

[找工就业] Amazon电面, 跪穿

[复制链接] |试试Instant~ |关注本帖
ykwwind 发表于 2016-5-8 13:34:29 | 显示全部楼层 |阅读模式

2016(4-6月)-[]EE硕士+fresh grad 无实习/全职 - 网上海投| 码农类全职@Amazonfresh grad应届毕业生

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

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

x
烙印上来介绍了自己, 让我介绍了下,问了问对前端和后端的感受(个人喜好感受之类的)
上题了...先来了个模糊不清的版本. 一个Array, non-negative integer,让我找一个length = 3的subarray, 满足maximum product.
模糊不清啊,得问要不要维持原先的order啊...答曰“不知道,你怎么想?”, 那我说咱先不考虑吧......
那么就sort下,选个最大的三个呗....烙印表示可以,继续...

问我,如果里面有negative怎么办........我直接懵逼了, 开始想思路, leetcode上有个求不限长度的subarray max product...但是这限了长度了,我陷入了思考....试着和他交流下,要下hint....

烙印一言不合直接就说,那我们换下吧........不要negative了,你给我找一个满足了原先order的长度3的subarray出来...我就搞了三个candidate num, 扫过去...

烙印又发问了, 找个ascending的, 满足原先order, 长度3的,max product的subarray.......(我TM....), 这时候时间快没了,他让我讲思路,我就说DFS ,recursion....(压根没时间想优化了....直接爆破了)
他问我,time/space complexity......我傻逼一样的问它,recursion stack的space要算进去嘛,他说算啊...然后又补了句,不是constant的解法啊?我整个人都不好了..................

-google 1point3acres


一言不合就改,我做题的思路全程支离破碎.........基友边上帮着Google, 还是没帮上...刚给搜到了一个看着能用的,他换题了..................................
ccrjohn8787 发表于 2016-5-13 18:53:49 | 显示全部楼层
ykwwind 发表于 2016-5-13 11:23
不是求和,是求那个sub array.....

如果求subarray 记一下最大值时的index就行。
  1. public int[] maxProductLength3(int[] nums) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2. {
  3.     if (nums.length < 3)
  4.         return null; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.     int current = 1;
  6.     int resultIndex = -1;
  7.     int result = Integer.MIN_VALUE;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.     for (int i = 0; i < nums.length; i++)
  9.     {
  10.         current *= nums[i];
  11.         if (i > 2)
  12.         {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.             current /= nums[i-3];
  14.         }
  15.         if (i >= 2 && current >= result) {result = current; resultIndex = i;}
  16.     }
  17.     return new int[] {resultIndex-2, resultIndex-1, resultIndex};
  18. }

复制代码
回复 支持 1 反对 1

使用道具 举报

ccrjohn8787 发表于 2016-5-13 11:16:23 | 显示全部楼层
  1. public int maxProductLength3(int[] nums)
  2. {
  3.     if (nums.length < 3)
  4.         return Integer.MIN_VALUE;
  5.     int current = 1;
  6.     int result = Integer.MIN_VALUE;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.     for (int i = 0; i < nums.length; i++)
  8.     {
  9.         current *= nums[i];
  10.         if (i > 2)
  11.         {
  12.             current /= nums[i-3];
  13.         }
  14.         if (i >= 2) {result = Math.max(result, current);}
  15.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.     return result;
  17. }
复制代码

这样行不?
回复 支持 0 反对 1

使用道具 举报

alex8937 发表于 2016-5-12 21:42:42 | 显示全部楼层
ykwwind 发表于 2016-5-10 01:01
我当时的考虑是,烙印肯定是瞅准了要一个原先array order的subarray....我用了排序最后还是要推倒重来.  ...

subarray啊 又不是subset 怎么能排序
回复 支持 1 反对 0

使用道具 举报

Hualiang 发表于 2016-5-9 03:24:28 | 显示全部楼层
你电面还有基友帮。。。也是醉了
回复 支持 反对

使用道具 举报

fanttfw 发表于 2016-5-10 00:29:14 | 显示全部楼层
这个不是很简单么,你排序完了小的自然在最后啊,那么你就比较一下最大三个,跟最大的乘以两个最小的不就出来了么,为什么要全部重新推翻呢
回复 支持 反对

使用道具 举报

碇真嗣 发表于 2016-5-10 00:36:34 | 显示全部楼层
有人在旁边google反而会影响你的思路。。
回复 支持 反对

使用道具 举报

 楼主| ykwwind 发表于 2016-5-10 01:01:30 | 显示全部楼层
fanttfw 发表于 2016-5-10 00:29
这个不是很简单么,你排序完了小的自然在最后啊,那么你就比较一下最大三个,跟最大的乘以两个最小的不就出 ...

我当时的考虑是,烙印肯定是瞅准了要一个原先array order的subarray....我用了排序最后还是要推倒重来. 就想试着写slidling windown.
回复 支持 反对

使用道具 举报

treebug 发表于 2016-5-13 10:09:39 | 显示全部楼层
fanttfw 发表于 2016-5-10 00:29
这个不是很简单么,你排序完了小的自然在最后啊,那么你就比较一下最大三个,跟最大的乘以两个最小的不就出 ...

subarray啊,怎么能排序呢,肯定要按照原来的顺序啊。
回复 支持 反对

使用道具 举报

treebug 发表于 2016-5-13 10:50:25 | 显示全部楼层
这道题用个queue就能做出来了~我以前也是有人坐旁边帮忙,我现在发现还不如自己想,旁边的人太打扰你了~
回复 支持 反对

使用道具 举报

 楼主| ykwwind 发表于 2016-5-13 11:23:10 | 显示全部楼层
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不是求和,是求那个sub array.....
回复 支持 反对

使用道具 举报

justin 发表于 2016-5-13 11:36:22 | 显示全部楼层
个人一直觉得电面的时候搜google不是什么好事情。-google 1point3acres
一来是作弊,连电面的难度都需要作弊,onsite基本不用想过了。.1point3acres缃
二来我反而觉得搜google影响思路。很多题其实自己细心想想是能想通的,但是搜google的话,一边要回复面试官的问话,一边还要理解google出的答案。如果直接把答案抄上去但是思路描述不清的话,但凡有点经验的面试官都会发现你在作弊的。面试官估计就是感觉出你在搜google,所以才频繁修改题目描述的。
回复 支持 反对

使用道具 举报

 楼主| ykwwind 发表于 2016-5-13 12:07:46 | 显示全部楼层
justin 发表于 2016-5-13 11:36
个人一直觉得电面的时候搜google不是什么好事情。
一来是作弊,连电面的难度都需要作弊,onsite基本不用想 ...

哎,我这答,室友隔壁听着Google上个双保险......
这题按照他的要求我事后搜了一天答案也没找到个靠谱的.

至于改题么,我给你描述下,我刚“额”或者思考30秒,那边就准备改条件了...........................
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-5-13 23:36:59 | 显示全部楼层
只找三个最大的好像不用sort,直接扫一遍就可以了。。
回复 支持 反对

使用道具 举报

vae371 发表于 2016-5-31 07:57:56 | 显示全部楼层
Mark6 发表于 2016-5-13 23:36
只找三个最大的好像不用sort,直接扫一遍就可以了。。

为什么啊?
回复 支持 反对

使用道具 举报

ericzou 发表于 2016-5-31 08:24:52 | 显示全部楼层
碰到烙印还是 祈祷吧
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-5-31 08:33:15 | 显示全部楼层
. 1point3acres.com/bbs
用三个变量保存当前最大的三个值?
回复 支持 反对

使用道具 举报

xietao0221 发表于 2016-5-31 08:53:45 | 显示全部楼层
用一个窗口保存当前三个值,然后去一个加一个扫一遍就好了
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-31 10:40:41 | 显示全部楼层
想了个O(n)解法,大家看看对不:

1. 扫一遍array, 记录最大的三个值a, b, c和最小的两个值c, d。
2. return max(a*b*c, a*c*d)

这样顺序也保留了

补充内容 (2016-5-31 10:42):
记录两个最小值是为了处理有两个负数相乘得出了很大的正数的情况。
回复 支持 反对

使用道具 举报

Gwennie 发表于 2016-6-9 05:32:49 | 显示全部楼层
烙印。。。不说了呵呵
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 18:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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