一亩三分地论坛

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

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

Amazon Intern面经

[复制链接] |试试Instant~ |关注本帖
yhfyhf 发表于 2015-12-18 04:07:50 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Amazon - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完的的Amazon Intern, 题目不难,感觉是跪了,发个面经。
电话接起来,先让我自我介绍一下,然后就开始coding。这时我才听出来是个三哥。

先是写binary search, 脑子有点短路,最后跳出left <= right的loop后还加了个if条件判断是否找到,被三哥指出来,直接return -1就好了。然后给他描述一下是怎么运行的。

follow up是有duplicates的情况,返回任意index怎么做,返回最左边的index怎么做,这里又写了一个bug。。。

再follow up是[9, 8, 7, 1, 2, 3, 4] binary search. 这个和Search in Rotated Sorted Array不太一样,这里是先递减后递增,一紧张什么都写不出了。赶紧先把上一题的前半部分先复制了一遍,然后开始模仿Search in Rotated Sorted Array,比较mid的值和两边的值,写了两行就卡住了。三哥说你先别急着写,你先跟我讨论一下,好看看你的思路对不对。我说我想用mid跟两边的值比较。三哥说,你这样有用吗?我:没用。。那我先写找pivot吧。我写了三行,三哥那边说一直看不到我写了什么,我说你刷新一下?他说刷新也没用。。然后我刷新了一下,发现我刚写的三行代码没了。。三哥重新开一个页面,我开始重写。然后找到pivot后,我说然后再分别在左半边和右半边查找。他说行了,应该对了。


再follow up,有duplicates。我。。。。碰到duplicates得用linear search?他说,这样就O(n)了。。。我:可是这里跟上一题的duplicates不一样,blablabla... 他:对了,跟上一题不一样。。。然后他说没时间了,问了两个问题结束。


总的来说,感觉三哥人超级好,口音也还好(虽然有好几次让他重复),会一直引导我写,可是我写出了各种bug。。。肯定是跪了。。心塞。. 鍥磋鎴戜滑@1point 3 acres
-google 1point3acres

-google 1point3acres补充内容 (2016-1-9 07:14):.鏈枃鍘熷垱鑷1point3acres璁哄潧
12/30 offer get.

本帖被以下淘专辑推荐:

lpx1989 发表于 2015-12-18 04:16:37 | 显示全部楼层
这样就可以了,binary search。。。。。。。希望我的电面也这样
回复 支持 反对

使用道具 举报

ljdsoft 发表于 2016-1-6 05:21:37 | 显示全部楼层
楼主有消息了么,过了吗?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 07:08:35 | 显示全部楼层
follow up是[9, 8, 7, 1, 2, 3, 4]

是找一个input的数字,还是最大,或者最小。
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-1-9 07:14:08 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-9 07:08
follow up是[9, 8, 7, 1, 2, 3, 4]

. 鍥磋鎴戜滑@1point 3 acres是找一个input的数字,还是最大,或者最小。

找一个给定的数字。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 07:19:47 | 显示全部楼层
yhfyhf 发表于 2016-1-9 07:14
找一个给定的数字。
. 鍥磋鎴戜滑@1point 3 acres
这是个好问题,以前还真没考虑过。
{1, 3, 50, 10, 9, 7, 6}

这个数组,怎么搜?比如要找7
第一遍pivot = 10,然后发现10的左面比他大,右边比他小。然后呢?因为小数可能出现在10个左边,也可能出现在右边。难道还要在加个dfs?

补充内容 (2016-1-9 07:20):
求龟哥给个解法
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-1-9 07:25:20 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-9 07:19
这是个好问题,以前还真没考虑过。
{1, 3, 50, 10, 9, 7, 6}

找pivot时比较的是相邻的两个元素。
回复 支持 反对

使用道具 举报

lpx1989 发表于 2016-1-9 07:28:12 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-8 19:19
这是个好问题,以前还真没考虑过。
{1, 3, 50, 10, 9, 7, 6}
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我想到一个方法,第一遍logN找到最小点,然后分两边各搜一下,其实还是logN。就找到了
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-1-9 07:29:17 | 显示全部楼层
lpx1989 发表于 2016-1-9 07:28
我想到一个方法,第一遍logN找到最小点,然后分两边各搜一下,其实还是logN。就找到了

对,我写的就是这种方法。所以其实是两遍或三遍binary search。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 07:29:17 | 显示全部楼层
yhfyhf 发表于 2016-1-9 07:25
找pivot时比较的是相邻的两个元素。

我比较了啊, 10的左边比他大,右边比他小,但是因为不是sorted,所以左边右边都可能出现比他小的数
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-1-9 07:31:50 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-9 07:29
我比较了啊, 10的左边比他大,右边比他小,但是因为不是sorted,所以左边右边都可能出现比他小的数
.鏈枃鍘熷垱鑷1point3acres璁哄潧
对呀,那就在左边找到pivot为止呀。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 07:34:01 | 显示全部楼层
lpx1989 发表于 2016-1-9 07:28
我想到一个方法,第一遍logN找到最小点,然后分两边各搜一下,其实还是logN。就找到了

{1, 3, 50, 10, 9, 7, 6}
这种数组的最小点一定是最左,或者最又。
. more info on 1point3acres.com
可行方法是,找到最大点,然后把array parition成2部分,然后每部分都会是单一上升,或者下降。
然后在写2个binary search一个是上升的,一个是下降的。
所以这题需要写3个binary search
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-1-9 07:34:43 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-9 07:34
{1, 3, 50, 10, 9, 7, 6}
这种数组的最小点一定是最左,或者最又。

对,但是有可能在第二个binary search就找到了,直接return了。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 07:35:57 | 显示全部楼层
yhfyhf 发表于 2016-1-9 07:31
对呀,那就在左边找到pivot为止呀。
. 鍥磋鎴戜滑@1point 3 acres
{1, 3, 50, 10, 9, 7, 6}

把这个array看成这样
1,x, 50, 10, 9, x, 6

比如我要找7, 然后7可以出现在这2个 x 的任何一个位置。
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-1-9 07:37:01 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-9 07:35
{1, 3, 50, 10, 9, 7, 6}

把这个array看成这样

哦哦 我忘了是返回true/false还是index。反正算法对了就行了,这个不重要哈哈哈哈
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 07:40:23 | 显示全部楼层
yhfyhf 发表于 2016-1-9 07:37
哦哦 我忘了是返回true/false还是index。反正算法对了就行了,这个不重要哈哈哈哈

不是返回index的问题。。.1point3acres缃
是一个binary search没发做啊。
{1, 3, 50, 10, 9, 7, 6}
binary search第一部找pivot, 10是pivot,但是下一部呢?怎么判断是向左走还是向又走呢?
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-1-9 07:41:34 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-9 07:40.鏈枃鍘熷垱鑷1point3acres璁哄潧
不是返回index的问题。。
是一个binary search没发做啊。
{1, 3, 50, 10, 9, 7, 6}

你这例子,50才是pivot呀。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 07:43:43 | 显示全部楼层
yhfyhf 发表于 2016-1-9 07:41
你这例子,50才是pivot呀。。

我读书特别少,你千万别骗我。。。-google 1point3acres
0 + ( 6-0)/2 = 3
arr[3] = 10...
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 07:44:20 | 显示全部楼层
yhfyhf 发表于 2016-1-9 07:41
你这例子,50才是pivot呀。。

pivot是50,存在相同问题,,该左该又。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 10:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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