聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2513|回复: 9
收起左侧

[算法题] 问一道google电面题

[复制链接] |试试Instant~ |关注本帖
又见紫风铃 发表于 2015-11-5 07:51:46 | 显示全部楼层 |阅读模式

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

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

x
求问下各位大神,怎么判断一个按照Preorder traversal serialized的binary tree的序列是否正确呢?不能deserialize成树比如
A) 9 3 4 # # 1 # # 2 # 6 # #是对的,因为表示
           9
         /   \
       3      2
      /  \      \
    4    1      6   
B ) 9 3 4 # # 1 # #就是错的,因为无法反构造回一棵树
robinyqiu 发表于 2015-11-7 14:46:48 | 显示全部楼层
我觉得可以在字符串里找"n##"这种结构(对应tree里两个children都是Null的叶节点),找到之后就把"n##"改写成"#",也就是把找到的那个末端的子树想想成null,最后字符串变成"#"的就是valid,否则就invalid
比如 A) 9 3 "4 # #" "1 # #" 2 # "6 # #" ---> 9 3 # # 2 # # ---> 9 "3 # #" "2 # #" ---> 9 # # ---> "9 # #" ---> "#"
       B) 9 3 "4 # #" "1 # #" ---> 9 3 # # ---> 9 "3 # #" ---> 9 # (没有"n##"结构了,return false)
不知道说清楚了没有

评分

2

查看全部评分

回复 支持 3 反对 0

使用道具 举报

全球28万学生4.7分推荐
dietpepsi 发表于 2016-1-16 11:04:30 | 显示全部楼层
本帖最后由 dietpepsi 于 2016-1-16 14:32 编辑

更好的做法是完全不用stack只需要一个计数,代表当前(总出度-总入度)的差值。
然后每一个node不论是不是null,都增加一个入度。区别在于如果不是null,则又需要两个子,即增加两个出度。
任何时刻这个计数不能小于0,否则return false; 并且最后此计数必须为0。
  1. public boolean isValidSerialization(String preorder) {
  2.     String[] nodes = preorder.split(",");
  3.     int diff = 1;
  4.     for (String node: nodes) {
  5.         if (--diff < 0) return false;
  6.         if (!node.equals("#")) diff += 2;
  7.     }
  8.     return diff == 0;
  9. }
复制代码

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

2006reload 发表于 2015-11-6 13:08:47 | 显示全部楼层
leetcode 255 verify-preorder-sequence-in-binary-search-tree/
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-11-7 06:06:06 | 显示全部楼层
2006reload 发表于 2015-11-6 13:08
leetcode 255 verify-preorder-sequence-in-binary-search-tree/

不太一样吧,不是BST而且是带mark的sequence,不知道思路会不会是类似的,表示木有想到
回复 支持 反对

使用道具 举报

2006reload 发表于 2015-11-13 14:51:49 | 显示全部楼层
嗯 我看错了
回复 支持 反对

使用道具 举报

programmingnerd 发表于 2016-1-5 14:22:41 | 显示全部楼层
try to reconstruct the tree from the preorder sequence, if cannot reconstruct a tree. then not correct. keep an counter (initial 0), if can correctly reconstruct, the final counter value will be the length of the original sequence. if counter is larger or smaller, the sequence is wrong.
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-5 21:28:47 | 显示全部楼层
programmingnerd 发表于 2016-1-5 14:22
try to reconstruct the tree from the preorder sequence, if cannot reconstruct a tree. then not corre ...

It is required not to try to reconstruct the tree
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-16 04:47:34 | 显示全部楼层
本帖最后由 dietpepsi 于 2016-1-16 14:33 编辑

2 楼正解。
实现的话,可以用一个stack。贴一个我的实现。
这里假设字符串是逗号分隔,null一样是用'#'。
用了数组来模拟stack感觉好写一点儿,用Deque也是可以滴。复杂度是线性。
  1. public boolean isValidSerialization(String preorder) {
  2.         String[] values = preorder.split(",");
  3.         int n = values.length;
  4.         boolean[] isNull = new boolean[n]; // the stack
  5.         int end = 0; // end index
  6.         for (String value : values) {
  7.             if (end == 1 && isNull[0]) return false;
  8.             isNull[end++] = value.equals("#");
  9.             while (end >= 3 && !isNull[end - 3] && isNull[end - 2] && isNull[end - 1]) {
  10.                 isNull[end - 3] = true;
  11.                 end -= 2;
  12.             }
  13.         }
  14.         return end == 1 && isNull[0];
  15.     }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 01:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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