TripAdvisor电面面经，目测已杯具

目测是要杯具的节奏，来报个面经败RP

就是个第一轮技术电面啦，半个小时。面试官白人男，似乎时间略紧的样子。
问题：二叉树找duplicates

这边先提供了一个infix traversal解法，按顺序全排到arraylist里面再for loop轮一遍（最后居然忘记写return= =）。然后他问我那个for loop能不能用个别的玩意儿替换，我说用递归应该可以吧，或者用while loop或者for

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

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

data == last_visited)){
                        count++;
                }
                last_visited = root.data;
                countDuplesHelper(root.right, last_visited, count);
        }
}

他是不是想让你用hashset啊。。。而且你这个code一直return都是0，recursion也有问题，只是parent一直和left，right比，建议run个例子看看。个人认为不可能两个pointer traverse tree除非改变tree的形状

zzpanda 发表于 2013-10-10 11:06
他是不是想让你用hashset啊。。。而且你这个code一直return都是0，recursion也有问题，只是parent一直和lef ...

肯定不是想用hash吧。。。那个比array还费空间嘛

金妮韦崽 发表于 2013-10-11 00:16
肯定不是想用hash吧。。。那个比array还费空间嘛

我假设你说的是int tree，arraylist你把整个tree都加进去了，万一tree特别大怎么办？hashset最后还不用再loop一遍，一边traverse一边判断，其实array是最好的，但是你要确定出这个tree的最大值和最小值

题没明白，是只有两个node duplicate 还是什么啊？

traversal 一遍同时用 hashmap判断不行么？


补充内容 (2013-10-11 05:08):
//for each node in your traversal
if (hmap[current_node->val]==true){
  //found duplicate
  //store or output
}else{
  hmap[current_node->val]=true;
}

zzpanda 发表于 2013-10-10 15:45
我假设你说的是int tree，arraylist你把整个tree都加进去了，万一tree特别大怎么办？hashset最后还不用再 ...

嗯，谢谢~
话说我后来再改进了一下我那个优化解法的代码，然后还在网上找了一下。似乎还是蛮可行的~

public int countDupes(Node root, Node prev) {

int duplicates = 0;

if ( root == null ) {
return duplicates;
}

duplicates += countDupes(root.getLeft(), prev);
if ( root != prev && root.getValue() == prev.getValue() ) {
duplicates += 1;
}
duplicates += countDupes(root.getRight(), root);

return duplicates;
}

个人是觉得这个解法还是最优的，因为就是traverse一遍完事儿，不费其他时间空间。不过确实写起来有一定困难的样子= =（好吧鄙人递归不行就不要给自己找借口了！）

xperzy 发表于 2013-10-10 16:06
题没明白，是只有两个node duplicate 还是什么啊？

traversal 一遍同时用 hashmap判断不行么？

肯定可以啊，不过个人嫌hashmap太大。。。当时那人问我还有没有更优解的时候我就说，时间上是O(nlogn)就还凑合，不过需要多用一条数组有点悲剧

完整题目在这里：
// Assume there are duplicate values in a BST tree containing Integers; please write countDupes() and return an int for the count of duplicate values in the tree (the number of nodes to remove to make the tree contain unique values only).
//     5
//  2     9
// 1 3   8 9
//      7
//     6 7
//    5   7

// AssertTrue("There are 4 dupes", 4 == countDupes());

金妮韦崽 发表于 2013-10-11 05:19
嗯，谢谢~
话说我后来再改进了一下我那个优化解法的代码，然后还在网上找了一下。似乎还是蛮可行的~

楼主的思路很好，但是这个递归貌似有问题，prev没有正确更新？ 感觉这个检查的过程和check valid BST一样，CTCI上有用了一个全局变量来保存prevVisited node。如果是我的话，会直接用非递归的in order traversal，比较方便

如果用C++可以传引用Node&，这样遍历底层时的修改可以在上层生效，但是Java里这种情况下有点不方便，只能设全局变量，或者专门define一个Node的wrapper class，anyway我还是喜欢非递归。。。另外想问下楼主，电面就是在网上海投得到的吗

adlxk 发表于 2013-10-10 17:23
楼主的思路很好，但是这个递归貌似有问题，prev没有正确更新？ 感觉这个检查的过程和check valid BST一样 ...

嗯，也许。所以我觉得最好的方法估计还是也把prev给弄成全局变量= =我也喜欢非递归的in order traversal，但毕竟我已经说了非递归的解法了，然后人家叫我说最优解我咋好意思说对不起没有了╮(╯▽╰)╭