推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 6287|回复: 46
收起左侧

Google电面面经

[复制链接] |试试Instant~ |关注本帖
melody_qyao 发表于 2015-4-16 13:17:33 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
昨天面了google,已挂。。来地里发面经攒人品,顺便问问大家这道题有没有什么好的思路,我想了半天没想到什么好的方法。
given a full binary tree, please write a function to encode the shape of the tree. Using the result that you get from part I to reconstruct the tree. You should use as little space as you can to reconstrcut it.
就是说自己选个data structure来存这棵树的形状,尽量少用space,然后用你存的result来重建这棵树。
注意的地方:1. 这是一棵full binary tree,不是普通的二叉树,也就是说对于每个node,要么没有child,要么是两个child。2. 只需要存树的形状,不需要存节点的val。
我一开始想复杂了,分别用arraylist preorder和inorder一遍,然后根据leetcode上那种方法用两次遍历得到的list reconstruct,被面试官否决了。说空间用太多,而且没必要存节点值。完后我就想用个string来存(她提示我的),就像leetcode上那样存二叉树,例如n1,n2,n3,#,#,n4,n5这样,然后她问我这样存有啥缺点,我说了之后她让我写代码重建tree,时间太紧我没想到什么好方法,可能太紧张了然后面试官说超时间了要结束了,我最后大概就说了个思路。
想问问大家有没有什么好的解法?或者不用这种data structure也行。

评分

2

查看全部评分

lancelot981 发表于 2016-1-25 05:05:49 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
关于那个full tree的问题我觉得有一个更compact的办法:.1point3acres缃
因为每个node只会有两种可能:有0个child或有2个children,所以一个bit就可以表示。那么我们可以记录这棵树inorder traversal sequence每个node的children number。比如
          1
   2            3
. visit 1point3acres.com for more.             4       5            就可以表示为    1011000,1 个byte搞定. visit 1point3acres.com for more.
           6  7
回复 支持 1 反对 0

使用道具 举报

chunyung 发表于 2015-4-17 11:17:44 | 显示全部楼层
关注一亩三分地微博:
Warald
既然是full binary tree,表示一個node只會有0會2個node,題目又要求不需要存node的值
所以我覺得只需記錄每個node有幾個child node(即0或2)即可. For example:
      2
    /    \
  1      3
上面這個Full binary tree, 依據preorder的順序來serlize,則可用字串"2 0 0"來記錄其形狀
要deserialize的話,則根據字串的值即可以決定其下面有幾個child node而恢復其形狀
回复 支持 1 反对 0

使用道具 举报

johnnywsd 发表于 2015-4-20 09:48:55 | 显示全部楼层
  1. '''
  2. My solution: compress it to an integer. Level traverse. if the node has two child put 1, else put 0
  3. '''

  4. import Queue
  5. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  6. . From 1point 3acres bbs
  7. class Node():
  8.     def __init__(self, val):
  9.         self.val = val. 鍥磋鎴戜滑@1point 3 acres
  10.         self.left = None
  11.         self.right = None. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12. . visit 1point3acres.com for more.

  13. class Solution():
  14. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.     def __init__(self):
  16.         pass

  17.     # [url=home.php?mod=space&uid=160137]@return[/url] a integer.鏈枃鍘熷垱鑷1point3acres璁哄潧
  18.     def compress(self, node):. 鍥磋鎴戜滑@1point 3 acres
  19.         que = Queue.Queue()
  20.         res = 0
  21.         que.put(node)
  22.         while not que.empty():
  23.             cur = que.get()
  24.             res = res << 1
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  25.             if cur.left is not None and cur.right is not None:
  26.                 res |= 1. From 1point 3acres bbs
  27.                 que.put(cur.left). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  28.                 que.put(cur.right)
  29.             elif cur.left is None and cur.right is None:
  30.                 pass
  31.             else:. 1point 3acres 璁哄潧
  32.                 raise Exception(). visit 1point3acres.com for more.
  33.         return res.1point3acres缃

  34. . From 1point 3acres bbs
  35.     def decompress(self, compressed):
  36.         bits = []. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  37.         while compressed: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  38.             last_bit_zero = compressed >> 1 << 1
  39.             last_bit = compressed ^ last_bit_zero
  40.             compressed = compressed >> 1
  41.             bits.append(last_bit)
  42.         bits.reverse()

  43.         root = Node(0)
  44.         que = Queue.Queue()
  45.         que.put(root)
  46.         for bit in bits:
  47.             if bit == 1:
  48.                 node = que.get().1point3acres缃
  49.                 left = Node(0). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  50.                 right = Node(0)
  51.                 node.left = left
  52.                 node.right = right
  53.                 que.put(left). 1point3acres.com/bbs
  54.                 que.put(right). From 1point 3acres bbs
  55.             else:
  56.                 node = que.get()

  57.         return root
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| melody_qyao 发表于 2015-4-19 11:21:18 | 显示全部楼层
neomiracle 发表于 2015-4-18 07:47
楼主可不可以解释下存树的形状,不存节点value是怎么存呢,实在想不明白不存value的话怎么样还能把tree给建 ...

你看10楼说的,就是对于每个node只存它有多少个child node就可以了,然后根据这一行child node的多少得知下一行对应的位置有没有node,以此类推。
回复 支持 1 反对 0

使用道具 举报

shinichish 发表于 2015-4-16 13:22:20 | 显示全部楼层
这是binary tree serialization吗?
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-4-16 13:27:54 | 显示全部楼层
shinichish 发表于 2015-4-16 13:22
这是binary tree serialization吗?

我后来查了一下,是serialization的问题。就是用n1, n2, n3, #, #, n4, n5那种数据结构存,然后reserialize一下。但是觉得是full binary tree,会不会有简便一点的方法。
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-4-17 01:18:20 | 显示全部楼层
melody_qyao 发表于 2015-4-15 21:27. 鍥磋鎴戜滑@1point 3 acres
我后来查了一下,是serialization的问题。就是用n1, n2, n3, #, #, n4, n5那种数据结构存,然后reseriali ...

恩恩,full binary tree会简单一点,可以用bfs来序列化,这样就没有#了
回复 支持 反对

使用道具 举报

wild_ricky_0221 发表于 2015-4-17 01:24:19 | 显示全部楼层
回复 支持 反对

使用道具 举报

adaromu 发表于 2015-4-17 07:13:18 | 显示全部楼层
shinichish 发表于 2015-4-17 01:18
恩恩,full binary tree会简单一点,可以用bfs来序列化,这样就没有#了

为什么bfs以后就没有#了呢?
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-4-17 10:21:58 | 显示全部楼层
adaromu 发表于 2015-4-16 15:13. more info on 1point3acres.com
为什么bfs以后就没有#了呢?
. 鍥磋鎴戜滑@1point 3 acres
因为#都会在最后,你就不存下来就好了
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-4-17 10:43:07 | 显示全部楼层
shinichish 发表于 2015-4-17 10:21
因为#都会在最后,你就不存下来就好了

我想了一下bfs貌似不行啊
你考虑一下这个case
    *
*       *
     *      *
         *       *
这个case 你用bfs下来是不能保存形状的,因为第二行的那个node它的左子树没有,但是在你的遍历里面看不出来。
回复 支持 反对

使用道具 举报

liushen 发表于 2015-4-17 11:08:20 | 显示全部楼层
这个是不是serialize 和deserialize tree 啊?啥叫做存树的形状啊?
我贴个serialize  deserialize的代码吧:
//Serialize and Deserialize tree, assume value stored in treenode is integer.. from: 1point3acres.com/bbs
public String serialize(TreeNode root){
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
}
private void serialize(TreeNode node, StringBuilder sb){
        if(node==null){sb.append("#");}
        else{
                sb.append(node.val+" ");
                serialize(node.left, sb);
                serialize(node.right, sb);
        }. From 1point 3acres bbs
}
public TreeNode deserialize(String s){.鐣欏璁哄潧-涓浜-涓夊垎鍦
        if(s==null || s.length()==0){
                return null;
        }. 1point 3acres 璁哄潧
        StringTokenizer st = new StringTokenizer(s, " ");
        return deserialize(st);
}
private TreeNode deserialize(StringTokenizer st){. visit 1point3acres.com for more.
        if(!st.hasMoreTokens()){return null;}
        String val = st.nextToken();
        if(val.equals("#")){
                return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(val));
        root.left = deserialize(st);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        root.right = deserialize(st);
        return root;
}
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-4-17 11:50:38 | 显示全部楼层
melody_qyao 发表于 2015-4-16 18:43
我想了一下bfs貌似不行啊. From 1point 3acres bbs
你考虑一下这个case
    *

这个貌似不是full binary tree。。。
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-4-17 11:54:17 | 显示全部楼层
shinichish 发表于 2015-4-17 11:50.1point3acres缃
这个貌似不是full binary tree。。。

是的,你可能把full binary tree和complete binary tree搞混了。。。。
回复 支持 反对

使用道具 举报

shou3301 发表于 2015-4-17 12:02:32 | 显示全部楼层
因为每个node要么有两个children,要么没有,我觉得可以在serialize的时候存2或者0,2代表当前节点有2个孩子,否则没有。这样就省去了存#的空间。经过初步验证应该可行。
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-4-17 12:11:45 | 显示全部楼层
shou3301 发表于 2015-4-17 12:02
因为每个node要么有两个children,要么没有,我觉得可以在serialize的时候存2或者0,2代表当前节点有2个孩 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
恩,就是每个node存有几个child node,跟9楼的想法一样,我觉得可以试一下,谢谢啦
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-4-17 12:20:59 | 显示全部楼层
melody_qyao 发表于 2015-4-16 19:54
是的,你可能把full binary tree和complete binary tree搞混了。。。。
-google 1point3acres
哦哦。。sorry。。
回复 支持 反对

使用道具 举报

neomiracle 发表于 2015-4-18 07:47:46 | 显示全部楼层
楼主可不可以解释下存树的形状,不存节点value是怎么存呢,实在想不明白不存value的话怎么样还能把tree给建回去呢
回复 支持 反对

使用道具 举报

tracywade 发表于 2015-4-20 05:44:30 | 显示全部楼层
adaromu 发表于 2015-4-17 07:13
为什么bfs以后就没有#了呢?

因为每层node多少你都知道  只需要逗号来分开每个树就好了
回复 支持 反对

使用道具 举报

adaromu 发表于 2015-4-20 09:23:00 | 显示全部楼层
tracywade 发表于 2015-4-20 05:44
因为每层node多少你都知道  只需要逗号来分开每个树就好了

哦哦是这个意思
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-25 23:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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