一亩三分地论坛

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

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

今年面得差不多了,热乎乎的palantir面筋送给大家

[复制链接] |试试Instant~ |关注本帖
lazysheep 发表于 2014-12-19 05:27:09 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Palantir - 校园招聘会 - 技术电面 |Other

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

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

x
面之前就觉着会比较难了。. more info on 1point3acres.com
有个tree,tree里面node的结构包含一个char和左右指针。同一个node的左右指针可以指向同一个child节点,不同node也可以指向相同child节点。保证这个tree里面没有环。
例如: A            A           A
          /  \          ()           /  \
         B   C,        B  ,      C    B
                                    \    /
                                     D
都是可以的。
让implement一个函数,输入Node* root和int k,返回这个tree在中序遍历下的第k个节点的存的char。考察点在于由于中序遍历时会有重复节点,如何才能节省时间找到第k个。楼主比较挫,不会做,大家可以讨论哈~
xlhdh 发表于 2014-12-19 05:55:14 | 显示全部楼层
如果有一个队伍 1, 2, 。。。 k, k+1, 。。。。 n, 第二次遇到某节点,就不再把它加入队伍中?

简单想的话就把每个节点涂上色,分别代表已遍历全部子树,已开始遍历子树,和从未遇到过这个节点,recurse的时候如果遇到见过的节点,就不recurse它了。。。Intro to Algorithms 有的。。
回复 支持 反对

使用道具 举报

xlhdh 发表于 2014-12-19 05:55:33 | 显示全部楼层
如果有一个队伍 1, 2, 。。。 k, k+1, 。。。。 n, 第二次遇到某节点,就不再把它加入队伍中?

简单想的话就把每个节点涂上色,分别代表已遍历全部子树,已开始遍历子树,和从未遇到过这个节点,recurse的时候如果遇到见过的节点,就不recurse它了。。。Intro to Algorithms 有的。。
回复 支持 反对

使用道具 举报

xlhdh 发表于 2014-12-19 05:55:47 | 显示全部楼层
如果有一个队伍 1, 2, 。。。 k, k+1, 。。。。 n, 第二次遇到某节点,就不再把它加入队伍中?
. 1point3acres.com/bbs
简单想的话就把每个节点涂上色,分别代表已遍历全部子树,已开始遍历子树,和从未遇到过这个节点,recurse的时候如果遇到见过的节点,就不recurse它了。。。Intro to Algorithms 有的。。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-12-19 05:57:44 | 显示全部楼层
加size域, 二分。 O(log n)
回复 支持 反对

使用道具 举报

zhongneu 发表于 2014-12-19 12:55:23 | 显示全部楼层
北美农民 发表于 2014-12-19 05:57.鏈枃鍘熷垱鑷1point3acres璁哄潧
加size域, 二分。 O(log n)
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
能说具体一点吗?O(logn)是总的time complexity?
回复 支持 反对

使用道具 举报

shire1989 发表于 2015-1-29 06:26:03 | 显示全部楼层
北美农民 发表于 2014-12-19 05:57
加size域, 二分。 O(log n)
. From 1point 3acres bbs
size域值得什么?
回复 支持 反对

使用道具 举报

liuzhe1218 发表于 2015-2-2 04:10:04 | 显示全部楼层
北美农民 发表于 2014-12-19 05:57
加size域, 二分。 O(log n)

你好,求教size域的具体解法。。
回复 支持 反对

使用道具 举报

liuzhe1218 发表于 2015-2-2 04:17:35 | 显示全部楼层
顺便贴上我的解法。。求各位大牛指正!
  1. public TreeNode getNodeK(TreeNode root, int k){
  2.                 if (root == null || k <= 0){
  3.                         return null;
  4.                 }
  5.                 Stack<TreeNode> s = new Stack<TreeNode>();. from: 1point3acres.com/bbs
  6.                 Set<TreeNode> visited = new HashSet<TreeNode>();
  7.                 TreeNode rst = null;. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.                 TreeNode p = root;.1point3acres缃
  9.                 int counter = 0;
  10.                
  11.                 while (s.size() > 0 || p != null){.1point3acres缃
  12.                         if (p != null && !visited.contains(p)){
  13.                                 s.push(p);
  14.                                 p = p.left;. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.                         else{
  17.                                 p = s.pop();
  18.                                 visited.add(p);
  19.                                 counter++;
  20.                                 if (counter == k){
  21.                                         rst = p;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.                                         break;. from: 1point3acres.com/bbs
  23.                                 }
  24.                                 p = visited.contains(p.right) ? null : p.right;
  25.                         }
  26.                 }
  27.                 return rst;
  28.         }
复制代码
回复 支持 反对

使用道具 举报

头像被屏蔽
whuwangyi 发表于 2015-2-5 15:02:42 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-15 11:42:13 | 显示全部楼层
北美农民 发表于 2014-12-18 16:57
加size域, 二分。 O(log n)

求二分的做法!size是以当前节点为root的subtree size?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 08:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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