📣 VIP通行证夏日特惠 限时立减$68
回复: 10
跳转到指定楼层
上一主题 下一主题
收起左侧

TripAdvisor电面面经,目测已杯具

全局:

2013(10-12月) 码农类General 本科 全职@TripAdvisor - 网上海投 - 技术电面  | | Fail |

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
目测是要杯具的节奏,来报个面经败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);
        }
}


上一篇:Morgan Stanley On Campus 面试
下一篇:写一个TI电话面试经验

本帖被以下淘专辑推荐:

  • · TA|主题: 9, 订阅: 0
🔗
zzpanda 2013-10-11 00:06:56 | 只看该作者
全局:
他是不是想让你用hashset啊。。。而且你这个code一直return都是0,recursion也有问题,只是parent一直和left,right比,建议run个例子看看。个人认为不可能两个pointer traverse tree除非改变tree的形状

评分

参与人数 1大米 +3 收起 理由
bryanjhy + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
 楼主| 金妮韦崽 2013-10-11 00:16:06 | 只看该作者
全局:
zzpanda 发表于 2013-10-10 11:06
他是不是想让你用hashset啊。。。而且你这个code一直return都是0,recursion也有问题,只是parent一直和lef ...

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

使用道具 举报

🔗
zzpanda 2013-10-11 04:45:55 | 只看该作者
全局:
金妮韦崽 发表于 2013-10-11 00:16
肯定不是想用hash吧。。。那个比array还费空间嘛

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

评分

参与人数 1大米 +3 收起 理由
bryanjhy + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
xperzy 2013-10-11 05:06:37 | 只看该作者
全局:
题没明白,是只有两个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;
}
回复

使用道具 举报

🔗
 楼主| 金妮韦崽 2013-10-11 05:19:59 | 只看该作者
全局:
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一遍完事儿,不费其他时间空间。不过确实写起来有一定困难的样子= =(好吧鄙人递归不行就不要给自己找借口了!)
回复

使用道具 举报

🔗
 楼主| 金妮韦崽 2013-10-11 05:24:18 | 只看该作者
全局:
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());
回复

使用道具 举报

🔗
adlxk 2013-10-11 06:23:29 | 只看该作者
全局:
金妮韦崽 发表于 2013-10-11 05:19
嗯,谢谢~
话说我后来再改进了一下我那个优化解法的代码,然后还在网上找了一下。似乎还是蛮可行的~

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

使用道具 举报

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

使用道具 举报

🔗
 楼主| 金妮韦崽 2013-10-11 11:15:07 | 只看该作者
全局:
adlxk 发表于 2013-10-10 17:23
楼主的思路很好,但是这个递归貌似有问题,prev没有正确更新? 感觉这个检查的过程和check valid BST一样 ...

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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