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


一亩三分地论坛

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

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

Google电面面经

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

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

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

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

x
昨天面了google,已挂。。来地里发面经攒人品,顺便问问大家这道题有没有什么好的思路,我想了半天没想到什么好的方法。. more info on 1point3acres.com
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

查看全部评分

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

使用道具 举报

lancelot981 发表于 2016-1-25 05:05:49 | 显示全部楼层
关注一亩三分地微博:
Warald
关于那个full tree的问题我觉得有一个更compact的办法:
因为每个node只会有两种可能:有0个child或有2个children,所以一个bit就可以表示。那么我们可以记录这棵树inorder traversal sequence每个node的children number。比如
          1
   2            3
             4       5            就可以表示为    1011000,1 个byte搞定
           6  7
回复 支持 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. class Node():
  6.     def __init__(self, val):. 鍥磋鎴戜滑@1point 3 acres
  7.         self.val = val
  8.         self.left = None
  9.         self.right = None


  10. class Solution():
  11. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.     def __init__(self):
  13.         pass

  14.     # [url=home.php?mod=space&uid=160137]@return[/url] a integer
  15.     def compress(self, node):
  16.         que = Queue.Queue()
  17.         res = 0
  18.         que.put(node)
  19.         while not que.empty():
  20.             cur = que.get()
  21.             res = res << 1
  22.             if cur.left is not None and cur.right is not None:
  23.                 res |= 1
  24.                 que.put(cur.left)
  25.                 que.put(cur.right)
  26.             elif cur.left is None and cur.right is None:
  27.                 pass
  28.             else:
  29.                 raise Exception()
  30.         return res 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


  31.     def decompress(self, compressed):
  32.         bits = []
  33.         while compressed:. from: 1point3acres.com/bbs
  34.             last_bit_zero = compressed >> 1 << 1
  35.             last_bit = compressed ^ last_bit_zero
  36.             compressed = compressed >> 1. 1point3acres.com/bbs
  37.             bits.append(last_bit)
  38.         bits.reverse()

  39.         root = Node(0)
  40.         que = Queue.Queue()
  41.         que.put(root). 1point3acres.com/bbs
  42.         for bit in bits:
  43.             if bit == 1:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  44.                 node = que.get()
  45.                 left = Node(0)
  46.                 right = Node(0)
  47.                 node.left = left
  48.                 node.right = right
  49.                 que.put(left)-google 1point3acres
  50.                 que.put(right).鐣欏璁哄潧-涓浜-涓夊垎鍦
  51.             else:
  52.                 node = que.get()
  53. . 鍥磋鎴戜滑@1point 3 acres
  54.         return root. 鍥磋鎴戜滑@1point 3 acres
复制代码
回复 支持 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. From 1point 3acres bbs
我后来查了一下,是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. Waral 鍗氬鏈夋洿澶氭枃绔,
为什么bfs以后就没有#了呢?

因为#都会在最后,你就不存下来就好了
回复 支持 反对

使用道具 举报

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

我想了一下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.
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);
        }
}
public TreeNode deserialize(String s){
        if(s==null || s.length()==0){
                return null;. more info on 1point3acres.com
        }
        StringTokenizer st = new StringTokenizer(s, " ");
        return deserialize(st);
}
private TreeNode deserialize(StringTokenizer st){
        if(!st.hasMoreTokens()){return null;}
        String val = st.nextToken();
        if(val.equals("#")){
                return null;
        }. From 1point 3acres bbs
        TreeNode root = new TreeNode(Integer.valueOf(val));
        root.left = deserialize(st);
        root.right = deserialize(st);. Waral 鍗氬鏈夋洿澶氭枃绔,
        return root;
}
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| melody_qyao 发表于 2015-4-17 11:54:17 | 显示全部楼层
shinichish 发表于 2015-4-17 11:50
这个貌似不是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. 鍥磋鎴戜滑@1point 3 acres
因为每个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搞混了。。。。

哦哦。。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-8-17 12:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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