一亩三分地论坛

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

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

Google电面面经

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

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

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

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

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来重建这棵树。.鏈枃鍘熷垱鑷1point3acres璁哄潧
注意的地方: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 | 显示全部楼层
既然是full binary tree,表示一個node只會有0會2個node,題目又要求不需要存node的值. more info on 1point3acres.com
所以我覺得只需記錄每個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. class Node():
  6.     def __init__(self, val):
  7.         self.val = val
  8.         self.left = None
  9.         self.right = None
  10. . from: 1point3acres.com/bbs

  11. class Solution():
  12. .1point3acres缃
  13.     def __init__(self):
  14.         pass. 鍥磋鎴戜滑@1point 3 acres

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


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

  40.         root = Node(0)
  41.         que = Queue.Queue().鏈枃鍘熷垱鑷1point3acres璁哄潧
  42.         que.put(root)
  43.         for bit in bits:. 鍥磋鎴戜滑@1point 3 acres
  44.             if bit == 1:
  45.                 node = que.get().鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.                 left = Node(0)
  47.                 right = Node(0)
  48.                 node.left = left
  49.                 node.right = right
  50.                 que.put(left).鐣欏璁哄潧-涓浜-涓夊垎鍦
  51.                 que.put(right)
  52.             else:. 1point 3acres 璁哄潧
  53.                 node = que.get()

  54.         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
我后来查了一下,是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
为什么bfs以后就没有#了呢?

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

使用道具 举报

 楼主| 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 啊?啥叫做存树的形状啊?. 1point3acres.com/bbs
我贴个serialize  deserialize的代码吧:
//Serialize and Deserialize tree, assume value stored in treenode is integer.
public String serialize(TreeNode root){
        StringBuilder sb = new StringBuilder();. 1point3acres.com/bbs
        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){. visit 1point3acres.com for more.
                return null;
        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        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;
        }
        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貌似不行啊
你考虑一下这个case
    *
. From 1point 3acres bbs
这个貌似不是full binary tree。。。
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-4-17 11:54:17 | 显示全部楼层
shinichish 发表于 2015-4-17 11:50. 1point3acres.com/bbs
这个貌似不是full binary tree。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
是的,你可能把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搞混了。。。。
. visit 1point3acres.com for more.
哦哦。。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. from: 1point3acres.com/bbs
因为每层node多少你都知道  只需要逗号来分开每个树就好了

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 20:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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