讨论一道Amazon OA题目

刚刚结束了一个OA test，我是在职跳槽，找朋友内推的。为什么这种情况也要做OA啊。。。
Anyway，上题

Given a list of unique integers, construct the binary treeby given order without rebalancing, then find out the distance between twonodes.

public static int bstDistance(int[] values, int n, intnode1, int node2)

for example,

values= [

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

font style="color:rgb(102, 102, 102)">最后有三个case没有过，可能是超时，感觉逻辑应该对的，geeksforgeeks也有同样的解法。
是不是可以不用构建树，然后算出来距离呢？求大神解答。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

自己顶。。。我看别人的思路也是这样的，还是需要构建这个BST的。另外一道题是推荐movie的，给一个movie，返回N个rating最后的movie。其实就是graph 的遍历，BFS或者DFS都可以，再加一个priorityqueue。我用的BFS，12个case都通过了，不知道dfs会不会超时

弱弱地问一下BST怎么建立呀？每读array里一个数，把那个数插入BST里面？NlogN的复杂度？看见另外一个帖子说中序遍历，怎么建bst呀?
第一题至少可以只从LCA(node1,node2)那个数开始建立BST，两个node都读到了，就停止建bst了。

楼主也是内推社招OA? 是不是75min CODING+15MIN cultural survey?  cultural survey是什么鬼？方便发一下具体情况么？祝楼主好运连连！

楼主面哪个组？

lfzh123 发表于 2017-1-20 07:59
自己顶。。。我看别人的思路也是这样的，还是需要构建这个BST的。另外一道题是推荐movie的，给一个movie， ...

请问这题输入是怎么样的啊？怎么会跟graph联系起来？

tinadu 发表于 2017-1-21 15:26
楼主也是内推社招OA? 是不是75min CODING+15MIN cultural survey?  cultural survey是什么鬼？方便发一下具 ...

就是behavior question

veryblues 发表于 2017-1-23 12:26
请问这题输入是怎么样的啊？怎么会跟graph联系起来？

面的是AWS。因为每个movie都一个similar movie list，所以就是一个graph

lfzh123 发表于 2017-1-24 00:51
面的是AWS。因为每个movie都一个similar movie list，所以就是一个graph

哦哦，所以你说题目是不是想问rating最相近的movie？而不是最后？

不是，就是graph里ranking最高的