一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2303|回复: 28
收起左侧

亚麻社招online test

[复制链接] |试试Instant~ |关注本帖
beforelost 发表于 2016-3-3 08:18:47 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Amazon - 猎头 - 在线笔试 |Pass在职跳槽

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

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

x
120min hackerrank 的 OA, 就一道题:
命令行输入一个int list (5,6,3,4,2)
再输入两个int A and B(2,5)
根据输入的list 构建一个BST
输出是BST中,A到B的距离。

比如构建的BST可以是:
       5
     /    \. more info on 1point3acres.com
   3      6
/   \
2     4

那么2到5的距离就是2

题目不难,提前40min就写完提交了,第二题接到onsite通知

评分

1

查看全部评分

xli147 发表于 2016-3-3 08:59:57 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
楼主是kindle team的hiring event吗?
回复 支持 反对

使用道具 举报

 楼主| beforelost 发表于 2016-3-3 09:02:13 | 显示全部楼层
关注一亩三分地微博:
Warald
xli147 发表于 2016-3-3 08:59. 鍥磋鎴戜滑@1point 3 acres
楼主是kindle team的hiring event吗?

是啊,你也是吗?
回复 支持 反对

使用道具 举报

xli147 发表于 2016-3-3 09:05:05 | 显示全部楼层
是啊...baltimore那个吗?私聊?
回复 支持 反对

使用道具 举报

xli147 发表于 2016-3-3 09:21:14 | 显示全部楼层
你是哪天面试啊?跟我一起面的还有一个中国女生
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| beforelost 发表于 2016-3-3 09:24:45 | 显示全部楼层
xli147 发表于 2016-3-3 09:21
你是哪天面试啊?跟我一起面的还有一个中国女生

1号呀,不是event只有一天吗?我是早上面的
回复 支持 反对

使用道具 举报

 楼主| beforelost 发表于 2016-3-3 09:27:58 | 显示全部楼层
xli147 发表于 2016-3-3 09:05
是啊...baltimore那个吗?私聊?

私信你了
回复 支持 反对

使用道具 举报

QueenYoYo 发表于 2016-3-3 11:31:30 | 显示全部楼层
lz你好~~你的int list构建BST时有顺序吗?是随便构建吗?那输出的距离可能会不同怎么办?比如
       4. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
     /    \
   3      5. visit 1point3acres.com for more.
/           \
2            6
这样,A和B距离就会是3了。
能不能稍微详细讲讲?谢谢~~祝楼主拿到offer:)
回复 支持 反对

使用道具 举报

 楼主| beforelost 发表于 2016-3-3 11:36:54 | 显示全部楼层
QueenYoYo 发表于 2016-3-3 11:31
lz你好~~你的int list构建BST时有顺序吗?是随便构建吗?那输出的距离可能会不同怎么办?比如
       4
  ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
我是根据list的输入顺序,第一个数字就是root,然后一个一个的insert
回复 支持 反对

使用道具 举报

xli147 发表于 2016-3-3 11:37:45 | 显示全部楼层
QueenYoYo 发表于 2016-3-3 11:31
lz你好~~你的int list构建BST时有顺序吗?是随便构建吗?那输出的距离可能会不同怎么办?比如
       4
  ...

按输入顺序insert的
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2016-3-3 11:37:56 | 显示全部楼层
构建bst可以自定义节点吗?可以给每个节点加parent吗
回复 支持 反对

使用道具 举报

 楼主| beforelost 发表于 2016-3-3 11:40:27 | 显示全部楼层
AndrewFish 发表于 2016-3-3 11:37
构建bst可以自定义节点吗?可以给每个节点加parent吗

没说不可以好像,不过我没有加parent节点。当时想的是120分钟就给这一道题,我就老老实实做吧。
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2016-3-3 11:44:39 | 显示全部楼层
beforelost 发表于 2016-3-2 20:40. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
没说不可以好像,不过我没有加parent节点。当时想的是120分钟就给这一道题,我就老老实实做吧。

加了parent只要找到第一个节点然后dfs或者bfs就行了复杂度n  楼主有logn的解法吗
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2016-3-3 11:49:20 | 显示全部楼层
如果不加parent得先找nearest neighbor然后查两个节点离那个neighbor的距离,貌似时间复杂度只有logn了
回复 支持 反对

使用道具 举报

 楼主| beforelost 发表于 2016-3-3 12:42:59 | 显示全部楼层
AndrewFish 发表于 2016-3-3 11:49. from: 1point3acres.com/bbs
如果不加parent得先找nearest neighbor然后查两个节点离那个neighbor的距离,貌似时间复杂度只有logn了

对,我是先找lowest common parent,然后求到左右距离的和。因为BST 所以是logN
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-3-3 13:07:10 | 显示全部楼层
这题怎么做啊?自己建bst吗?
回复 支持 反对

使用道具 举报

xli147 发表于 2016-3-3 13:33:47 | 显示全部楼层
先建bst,找lowest common ancestor, 然后找lca,node1,node2的level。-google 1point3acres
distance=(level of node1 - level of lca) +(level of node2 - level of lca)
回复 支持 反对

使用道具 举报

chuyahui 发表于 2016-3-7 09:21:18 | 显示全部楼层
大家好,还有没有面亚麻kindle的,大家可以认识下?
我私信楼主还有xli147了。。。。
回复 支持 反对

使用道具 举报

Jolli9 发表于 2016-3-9 03:56:40 | 显示全部楼层
楼主或者地里的朋友,有没有kin*dle组on site的问题分享下?多谢。。。。。
回复 支持 反对

使用道具 举报

 楼主| beforelost 发表于 2016-3-10 11:17:33 | 显示全部楼层
onsite 看这里 http://www.1point3acres.com/bbs/thread-177399-1-1.html
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-29 04:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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