一亩三分地论坛

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

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

Amazon三月社招 Hankerrank 120m 在线笔试面经

[复制链接] |试试Instant~ |关注本帖
UnemotionalJohn 发表于 2016-4-4 11:40:06 | 显示全部楼层 |阅读模式

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

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

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

x
周末交了amazon的hackerrank的OA。 题目是tree distance。
给了一组unique的整数。要求构造一个BST。再给出两个在tree上的节点,计算出两个节点之tree distance. "tree distance" 的定义是number of edges on the path(traversing each edge only once) between two nodes.如果任何一个节点在tree中不存在,报错。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
举个例子
input:
2 //节点A. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
5 //节点B
4 //整数的个数
4 1 5 2 //整数数组
   4
/  \
1    5.1point3acres缃
  \
   2. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
output: 3
解法:先构造BST,然后找到A和B节点的lowest common ancestor: C, 然后分别找到C到A和C到B的距离再相加。也许有更优的解法,没有想太多。


评分

2

查看全部评分

kemeng1314 发表于 2016-4-4 12:01:17 | 显示全部楼层
请问楼主投的什么组拿到oa的呢,谢谢!
回复 支持 反对

使用道具 举报

 楼主| UnemotionalJohn 发表于 2016-4-5 10:08:33 | 显示全部楼层
kemeng1314 发表于 2016-4-4 12:01
请问楼主投的什么组拿到oa的呢,谢谢!
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
recruiter介绍说是做www.amazon.com/echo的组。
回复 支持 反对

使用道具 举报

小魏Stenica 发表于 2016-7-27 17:35:32 | 显示全部楼层
楼主我想请问一下,你例子中给的这个数组,构造成BST的话也可以是这样啊:
           4
         /    \
       2       5
      /
    1
这样的话距离就是2对吧。。。。
我该怎么构造BST呢。。。。如果BST可以构造成很多种的话。。。
回复 支持 反对

使用道具 举报

blueorange 发表于 2016-9-25 21:00:58 | 显示全部楼层
小魏Stenica 发表于 2016-7-27 17:35
楼主我想请问一下,你例子中给的这个数组,构造成BST的话也可以是这样啊:
           4
         /    \ ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
如果按照数组顺序扫描创建BST,应该不会出现这种构造。
回复 支持 反对

使用道具 举报

小魏Stenica 发表于 2016-9-30 07:02:13 | 显示全部楼层
blueorange 发表于 2016-9-25 06:00.鏈枃鍘熷垱鑷1point3acres璁哄潧
如果按照数组顺序扫描创建BST,应该不会出现这种构造。

谢谢,后来我也想通了,确实是这样
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 17:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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