一亩三分地论坛

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

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

Amazon新鲜面经

[复制链接] |试试Instant~ |关注本帖
aliyucun 发表于 2016-1-8 04:16:51 | 显示全部楼层 |阅读模式

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

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

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

x
刚刚面试完Amazon,面试官估计是个印度人。开始问了下所做的projects,然后问了下linkedlist和arraylist区别,quicksort和mergesort的区别。. 1point3acres.com/bbs

coding部分题目就是:Find paths in a binary search tree summing to a target value
在binary tree中,从给定节点Node出发,节点值相加等于给定值K的所有可能路径。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
听完题目就直接跪了,硬着头皮直接一顿说,最后面试官看我实在也是coding不出来,就结束了。然后让我问了他几个问题。
. 鍥磋鎴戜滑@1point 3 acres
不知道结果会怎么样,挂的可能性超级高,到时候及时回来update

本帖被以下淘专辑推荐:

徐小桃 发表于 2016-1-8 04:31:03 | 显示全部楼层
咱俩应该是同一个面试官,我也觉得应该是个印度人,不过英语还算标准的,祝好运
回复 支持 反对

使用道具 举报

liujunlovecs 发表于 2016-1-8 05:37:35 | 显示全部楼层
是以指定的node为root, 还是说只要有Path经过这个node就可以?
回复 支持 反对

使用道具 举报

liujunlovecs 发表于 2016-1-8 05:38:13 | 显示全部楼层
还有,面试有没有问OO Design。我下周面试,这块不清楚怎么准备。
回复 支持 反对

使用道具 举报

liujunlovecs 发表于 2016-1-8 05:38:37 | 显示全部楼层
徐小桃 发表于 2016-1-8 04:31
咱俩应该是同一个面试官,我也觉得应该是个印度人,不过英语还算标准的,祝好运

你面试的时候有没有问一些OO Design 的问题?
回复 支持 反对

使用道具 举报

徐小桃 发表于 2016-1-8 05:42:05 | 显示全部楼层
liujunlovecs 发表于 2016-1-8 05:38
你面试的时候有没有问一些OO Design 的问题?

没有问到,但还是尽量准备吧,毕竟他发的邮件里说会包括ood的问题的
回复 支持 反对

使用道具 举报

liujunlovecs 发表于 2016-1-8 05:50:48 | 显示全部楼层
徐小桃 发表于 2016-1-8 05:42
没有问到,但还是尽量准备吧,毕竟他发的邮件里说会包括ood的问题的

你今天面试问了什么题呢?能不能透露下,我下周就要店面了~~~
回复 支持 反对

使用道具 举报

zhexuany 发表于 2016-1-8 05:55:50 | 显示全部楼层
这个用red order traversal 应该就行了。leetcode上有类似的题。

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴补充内容 (2016-1-8 05:56):
pre order 抱歉,typo
回复 支持 反对

使用道具 举报

Toby 发表于 2016-1-8 06:03:15 | 显示全部楼层
祝好运,字数字数
回复 支持 反对

使用道具 举报

nintendodog 发表于 2016-1-8 07:24:54 | 显示全部楼层
lz 还有下家吗
回复 支持 反对

使用道具 举报

LouisT 发表于 2016-1-8 08:51:45 | 显示全部楼层
貌似是这个题阿. from: 1point3acres.com/bbs
https://leetcode.com/problems/path-sum-ii/
回复 支持 反对

使用道具 举报

Liuology 发表于 2016-1-8 11:47:22 | 显示全部楼层
楼主coding 题目给定节点不一定是root对吗, path 可以是任意长度 不一定要到达叶子节点对吗?
回复 支持 反对

使用道具 举报

zhexuany 发表于 2016-1-8 12:23:43 | 显示全部楼层
Liuology 发表于 2016-1-8 11:47
楼主coding 题目给定节点不一定是root对吗, path 可以是任意长度 不一定要到达叶子节点对吗?

即使这样,也还是可以用recursion的方法来做。 每次传值的时候,减去root的val。在程序中检测,传进去的值是否为零,是就返回。
回复 支持 反对

使用道具 举报

Liuology 发表于 2016-1-8 21:25:48 | 显示全部楼层
zhexuany 发表于 2016-1-8 12:23
即使这样,也还是可以用recursion的方法来做。 每次传值的时候,减去root的val。在程序中检测,传进去的 ...

但是你如何考虑path跨过root经过左右子树的情况呢?
回复 支持 反对

使用道具 举报

nintendodog 发表于 2016-1-8 21:37:52 | 显示全部楼层
Liuology 发表于 2016-1-8 21:25
但是你如何考虑path跨过root经过左右子树的情况呢?

我提供一种思路,先找到这个两个点的最近公共祖先再往下搜就可以了
回复 支持 反对

使用道具 举报

nintendodog 发表于 2016-1-8 23:16:44 | 显示全部楼层
Liuology 发表于 2016-1-8 21:25
但是你如何考虑path跨过root经过左右子树的情况呢?

我SB 了看错题目了,别介意啊= =
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-1-9 01:06:52 | 显示全部楼层
Liuology 发表于 2016-1-8 21:25
但是你如何考虑path跨过root经过左右子树的情况呢?

这种情况不需要考虑吧?我觉得Tree是单向性的,只能从上到下,所以横跨root不算一条连通的path
回复 支持 反对

使用道具 举报

ben_viv 发表于 2016-1-9 02:59:09 | 显示全部楼层
CC150 的原题吗? 先假设所有路径都从root开始找sum等于target的path,然后generalize到从任何node开始沿着path到root往回加,traverse一遍tree就能找到所有路径。时间复杂度是nlogn。
回复 支持 反对

使用道具 举报

zhexuany 发表于 2016-1-9 05:36:18 | 显示全部楼层
Liuology 发表于 2016-1-8 21:25
但是你如何考虑path跨过root经过左右子树的情况呢?

题目说的是find paths in a binary search tree。 你说的这种情况,不再考虑范围内。
回复 支持 反对

使用道具 举报

iamwds 发表于 2016-1-9 17:04:25 | 显示全部楼层
complexity: merge sort: average and worst case o(nlogn); quick sort: average O(nlogn), worst case O(n^2); .鏈枃鍘熷垱鑷1point3acres璁哄潧
Space: merge sort: extra space; quick sort: in place
Stability: merge sort: stable; quick sort: not stable

Best fit: merge sort: slow seqential media; quick sort: general purpose.
这个总结的全吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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