一亩三分地论坛

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

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

AMAZON新OA,还是挺有难度的

[复制链接] |试试Instant~ |关注本帖
老妖zm 发表于 2015-8-30 06:30:34 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Amazon - 猎头 - HR筛选 在线笔试 |Other在职跳槽

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

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

x
前段时间收到AMAZON家HR邮件,问我是否对一个安卓职位感兴趣。

我说毕业之后就没再搞安卓了,有没有其他职位。 她说可以,就约了个OA 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

13年毕业的时候投过亚马逊,当时也是做的OA, 那会题都挺简单,一个比较复杂的就是求最近的100个点, 用heap就行了。 这次我以为也差不多,

然后上版上看了其他人的OA面经,coding都挺简单 。所以一直没咋好好准备。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
没想到今天收到的OA还是挺有难度的。

具体题目不说了,就是给了一个场景和一个类,以及一个方程接口。

这个题其实是求最近父节点, 但不是二叉树。 所以感觉还是挺难的,最后想到了转化RMQ求解。 时间复杂度O(N), 空间也大概是O(N)。 . Waral 鍗氬鏈夋洿澶氭枃绔,

本来一看题目还以为是二叉树,还高兴了一下,没想到仔细一看不是二叉树。
时间一个小时,想来35分钟, 写了20分钟, 最后过了本地的编译就交了。


吐槽一下,现在亚马逊的第一面都这么难了。。如果都是这个难度, 感觉ONSITE要跪啊。 希望到时候能多问一些system design的题吧。


评分

1

查看全部评分

 楼主| 老妖zm 发表于 2015-8-30 06:47:44 | 显示全部楼层
题目就是 给一个 树, 求任意两点的 lowest common ancestor 树不是二叉树。.鐣欏璁哄潧-涓浜-涓夊垎鍦

回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-30 21:21:36 | 显示全部楼层
楼主啥时候做的?
回复 支持 反对

使用道具 举报

 楼主| 老妖zm 发表于 2015-8-31 05:14:37 | 显示全部楼层
jiebour 发表于 2015-8-30 21:21
楼主啥时候做的?

周六做的吧。看来是个code challenge,不算oa.
hr还是挺迅速的, 周四联系到, 周六就做题了
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-8-31 05:47:26 | 显示全部楼层
我觉得这题按链接中的方法2稍微改变下就可以做啊,和在二叉树上找的思路基本一样。
http://www.geeksforgeeks.org/low ... -binary-tree-set-1/
回复 支持 反对

使用道具 举报

 楼主| 老妖zm 发表于 2015-8-31 06:16:43 | 显示全部楼层
glaciersilent 发表于 2015-8-31 05:47
我觉得这题按链接中的方法2稍微改变下就可以做啊,和在二叉树上找的思路基本一样。
http://www.geeksforge ...

这个如果用递归, 每个node 有多个子节点的话, 时间复杂度太高了吧
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-8-31 07:02:21 | 显示全部楼层
老妖zm 发表于 2015-8-31 06:16
这个如果用递归, 每个node 有多个子节点的话, 时间复杂度太高了吧

复杂度O(n)啊 这题递归的解法也只是遍历所有树节点一次因为每次递归中直接返回了之前递归LCA的结果而不是重新算子节点树的LCA
回复 支持 反对

使用道具 举报

 楼主| 老妖zm 发表于 2015-8-31 07:26:12 | 显示全部楼层
glaciersilent 发表于 2015-8-31 07:02
复杂度O(n)啊 这题递归的解法也只是遍历所有树节点一次因为每次递归中直接返回了之前递归LCA的结果而不 ...

如果是二叉树的话, 逻辑简单,因为要么两个点在root 两侧,要么在同一侧。 如果在两侧的话lca就是root. 如果在一侧的话, 对那一侧递归。

如果不是二叉树,我仔细想了一下,这样递归也可以。不过是不太支持多次查询。 每次查询都需要O(N).
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
原题应该是要考虑多次查询的。

-google 1point3acres

我最开始也是想参照二叉树做的, 但发现逻辑不太一样。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-31 08:12:28 | 显示全部楼层
老妖zm 发表于 2015-8-31 07:26. 鍥磋鎴戜滑@1point 3 acres
如果是二叉树的话, 逻辑简单,因为要么两个点在root 两侧,要么在同一侧。 如果在两侧的话lca就是root.  ...

然后呢?用RMQ思想?可以把多次查询的复杂度降低?
求楼主解释。。。。
回复 支持 反对

使用道具 举报

 楼主| 老妖zm 发表于 2015-8-31 08:21:15 | 显示全部楼层
jiebour 发表于 2015-8-31 08:12
然后呢?用RMQ思想?可以把多次查询的复杂度降低?
求楼主解释。。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我也不知道自己给的是不是最佳答案。

我的做法是先建立2个数组depth[], val[]一个map< TreeNode*, int> first, 并对tree 做一次preproder DFS。 depth记录DFS路径上每一个点的dep, val记录路径上每个点的指针。 first记录每个NODE在DFS第一次出现的位置。. from: 1point3acres.com/bbs
初始化只需要做一次就够。
这样 LCA(Node1,Node2) = val[RMQ(depth[], first[Node1], first[Node2])]. . 1point 3acres 璁哄潧

要找LCA,只要每次进行一次RMQ 查询就行了。.1point3acres缃
.1point3acres缃
回复 支持 反对

使用道具 举报

ffjjcclxxx 发表于 2015-9-3 16:00:24 | 显示全部楼层
问下楼主 这个oa1 有给due date吗 我也收到了 但是没写due date 还是说这个due date 不是Email里的 是要打开链接才能看到的?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-4 01:47:43 | 显示全部楼层
老妖zm 发表于 2015-8-31 08:21
我也不知道自己给的是不是最佳答案。

我的做法是先建立2个数组depth[], val[]一个map< TreeNode*, int ...

楼主,你说的我貌似懂了点。
不过你的思路突然让我想到是cc150里面某个题目的思路。
那可不可以这样:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
两次遍历tree,第一次找到root到node1的路径(O(N)),第二次找到root到node2的路径(O(N)),然后路径比如说可以用LinkedList存储,然后这俩LinkedList肯定是前面一段相同,然后接下来就是找这俩LinkedList的最后一个相同的node了呗?
回复 支持 反对

使用道具 举报

dwl1222 发表于 2015-9-5 06:10:57 | 显示全部楼层
楼主。这题跟二叉树又没什么区别。
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-9-9 08:43:14 | 显示全部楼层
老妖zm 发表于 2015-8-31 07:26
如果是二叉树的话, 逻辑简单,因为要么两个点在root 两侧,要么在同一侧。 如果在两侧的话lca就是root.  ...

楼主你好,我想问一下你提到说每个node的child nodes不一定是2个,是不是他给的TreeNode类的成员变量中,child nodes是用一个类似ArrayList<TreeNode>的变量来表示的呢?另外如楼上几位朋友所说,感觉做法跟二叉树上的做法应该是一样的,复杂度仍然也是On, 因为每个节点就访问了一次。你觉得呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 06:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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