车版热帖:大家对买豪车怎么看

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 4874|回复: 28
收起左侧

亚麻社招online test

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

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

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

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

x
120min hackerrank 的 OA, 就一道题:
命令行输入一个int list (5,6,3,4,2)
再输入两个int A and B(2,5)
根据输入的list 构建一个BST. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
输出是BST中,A到B的距离。. from: 1point3acres.com/bbs

比如构建的BST可以是:
       5
     /    \
   3      6
/   \
2     4

那么2到5的距离就是2. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

评分

1

查看全部评分

xli147 发表于 2016-3-3 08:59:57 | 显示全部楼层
楼主是kindle team的hiring event吗?
回复 支持 反对

使用道具 举报

 楼主| beforelost 发表于 2016-3-3 09:02:13 | 显示全部楼层
xli147 发表于 2016-3-3 08:59
楼主是kindle team的hiring event吗?
. 1point3acres.com/bbs
是啊,你也是吗?
回复 支持 反对

使用道具 举报

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

使用道具 举报

xli147 发表于 2016-3-3 09:21:14 | 显示全部楼层
你是哪天面试啊?跟我一起面的还有一个中国女生
回复 支持 反对

使用道具 举报

 楼主| 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时有顺序吗?是随便构建吗?那输出的距离可能会不同怎么办?比如. 鍥磋鎴戜滑@1point 3 acres
       4
     /    \. From 1point 3acres bbs
   3      5
/           \
2            6
这样,A和B距离就会是3了。
能不能稍微详细讲讲?谢谢~~祝楼主拿到offer:)
回复 支持 反对

使用道具 举报

 楼主| beforelost 发表于 2016-3-3 11:36:54 | 显示全部楼层
QueenYoYo 发表于 2016-3-3 11:31
lz你好~~你的int list构建BST时有顺序吗?是随便构建吗?那输出的距离可能会不同怎么办?比如. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
       4
  ...

我是根据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
如果不加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。
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
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-4-23 19:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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