一亩三分地论坛

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

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

1102 Google 实习电面

[复制链接] |试试Instant~ |关注本帖
ywmaggie 发表于 2015-11-3 09:36:09 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完两轮45min电面,跪的妥妥的。面试官跟我说 There is no short path. Practice more. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

两轮都是中国小哥,人都非常nice,无奈自己实在太弱了,刚跟男朋友哭完,平复一下心情,在地里看了这么多面经,来回馈一下。

第一轮
Tree Longest consecutive sequence. Leetcode有差不多原题,是binary tree。这个面试官说就是正常的树。我用的recursion, 问时间复杂度,O(n).
我用了global variable, 问我可能有什么问题,他说是thread unsafe,问我能不能不用global variable.
Follow up是如果是DAG,不是tree,怎么做。

第二轮
给一个删除树节点的函数,和root,怎么遍历删除整棵树。用了postorder recursion。
问这个程序可能会crash,为什么。  因为recursion太多可能会memory overflow。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
问怎么避免,用level order,空间复杂度O(n).
如果还是太大,怎么办,我就不会了,他提示说serialize,我想到了线索化二叉树,但是太难了,不会,postorder iteration也太难了,不会。
这些复习的时候都看到过,觉得肯定不会考,所以也怨不得别人。

自己就这样吧,再多投一投其他公司吧,觉得今年实习好难找:(
祝大家好运。

评分

5

查看全部评分

小柯西 发表于 2015-11-3 14:28:32 | 显示全部楼层
代码再贴一遍
def deleteTree(root):
     while root:
         next_root = root.left
         if not next_root:
             next_root = root.right.鐣欏璁哄潧-涓浜-涓夊垎鍦
             deleteNode(root). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
         else:
             predecessor = root.left
             while predecessor.right: predecessor = predecessor.right
             predecessor.right = root
         root = next_root
回复 支持 3 反对 0

使用道具 举报

xin_gator 发表于 2015-11-5 02:45:59 | 显示全部楼层
小柯西 发表于 2015-11-3 14:28
代码再贴一遍
def deleteTree(root):. 1point 3acres 璁哄潧
     while root:

好牛的算法!
回复 支持 1 反对 0

使用道具 举报

latioswang 发表于 2015-11-3 21:02:49 | 显示全部楼层
小柯西 发表于 2015-11-3 14:28
代码再贴一遍
def deleteTree(root):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
     while root:

Hello, I rewrite your python code to C++ code :
void deleteTree(TreeNode *root) {
    TreeNode *cur = root;
    while (cur) {
        TreeNode *next = cur->left;
        if (next == NULL) {
            next = cur->right;. 鍥磋鎴戜滑@1point 3 acres
            delete cur;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        } else {
            TreeNode *pre = cur->left;
            while (pre->right) {
                pre = pre->right;
            }
            pre->right = cur;
        }
        cur = next;
    }
}
please feel free to check it and give some suggestions ! Thanks !
回复 支持 1 反对 0

使用道具 举报

aliyucun 发表于 2015-11-3 14:03:11 | 显示全部楼层
right rotate the tree, once the root does not have any left node, we can delete the root and move to right node
回复 支持 1 反对 0

使用道具 举报

abcd1992719g 发表于 2015-11-3 11:13:29 | 显示全部楼层
遍历删除整颗树的话,可以用stack来做inorder的遍历,空间最多只需要log(n).不知道可不可行.代码在这里 github.com/gzc/oops/blob/master/Google/deleteTree.cpp
回复 支持 反对

使用道具 举报

abcd1992719g 发表于 2015-11-3 11:25:18 | 显示全部楼层
线索化二叉树貌似也需要至少logn的空间才能完成吧?不知道面试官啥意思...
回复 支持 反对

使用道具 举报

 楼主| ywmaggie 发表于 2015-11-3 12:14:06 | 显示全部楼层
abcd1992719g 发表于 2015-11-3 11:13
遍历删除整颗树的话,可以用stack来做inorder的遍历,空间最多只需要log(n).不知道可不可行.代码在这里 githu ...

我跟他说了inorder 但貌似不是他想要的 他想让所有的点连在一起 连成一个链表一样的 这样应该可以O(1)吧 我也不太清楚
回复 支持 反对

使用道具 举报

Camel_Yan 发表于 2015-11-3 13:14:13 | 显示全部楼层
摸摸lz 加油
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-11-3 13:44:15 | 显示全部楼层
加油,别灰心,感觉google真是问的比较难的了
回复 支持 反对

使用道具 举报

abcd1992719g 发表于 2015-11-3 14:10:10 | 显示全部楼层
aliyucun 发表于 2015-11-3 14:03
right rotate the tree, once the root does not have any left node, we can delete the root and move to ...

好主意!
回复 支持 反对

使用道具 举报

abcd1992719g 发表于 2015-11-3 14:10:47 | 显示全部楼层
aliyucun 发表于 2015-11-3 14:03
right rotate the tree, once the root does not have any left node, we can delete the root and move to ...

记得以前在CLRS碰到题目说把一棵树转成一根链表
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-11-3 14:25:32 | 显示全部楼层
第二轮的题目我有点疑问,recursion太多导致的是stack overflow吧?考官说让你避免这个问题,那应该是提示要你写iterative的版本。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
iterative的版本就是用stack,最大空间复杂度就是树的高度而已,也就是O(lgn)。这个应该可以满足要求了。
进一步优化的确是可以做到O(1) space的,就是楼主想到的Morris Traversal,不过是iterative版本的。

具体做法也就是找每个节点左孩子的最右叶子节点,e.g,当前节点inorder traversal时的predecessor。然后设这个叶子节点的right为当前节点。
移动到左孩子,重复上述步骤。
如果当前节点没有左孩子,那么暂存当前节点的右孩子,删除当前节点,再对右孩子重复以上步骤。
  1. <b><font color="#ff8c00">def</font></b> delete(root):
  2.     <b>while</b> root:
复制代码

补充内容 (2015-11-3 14:26):
卧槽。。我真是给论坛的代码编辑功能给跪了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

小柯西 发表于 2015-11-3 14:29:17 | 显示全部楼层
aliyucun 发表于 2015-11-3 14:03
right rotate the tree, once the root does not have any left node, we can delete the root and move to ...

就是Morris Traversal~~
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-11-3 14:37:39 | 显示全部楼层
再问一下,第一题。。是指每个节点都有一个value,然后要找最长的consecutive value sequence?还是说,找一个最长的路径,与节点值无关?
如果是找节点值连续的最长路径。。那这题难度也是有点大
回复 支持 反对

使用道具 举报

AchillesMilleR 发表于 2015-11-3 14:56:03 | 显示全部楼层
感觉面试官好脑抽啊。。。不过 inorder traversal 有一个算法是O(1)的空间复杂度,不知道能不能用在这里。

leetcode上有一个Flat tree的方法,就是用right 来连成一个链表。。不过也需要Stack 来做。。空间复杂度是O(logn)
回复 支持 反对

使用道具 举报

abcd1992719g 发表于 2015-11-3 15:17:41 | 显示全部楼层
楼主加油,我觉得你碰到的问题比其他人难呢,尤其是第二题我问了同学才知道有morris traversal这种东西...
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-11-4 02:39:14 | 显示全部楼层
latioswang 发表于 2015-11-3 21:02
Hello, I rewrite your python code to C++ code :
void deleteTree(TreeNode *root) {
    TreeNode * ...

这个没问题~!
回复 支持 反对

使用道具 举报

mooc 发表于 2015-11-5 01:57:24 | 显示全部楼层
我到现在没搞懂,为什serialize会防止内存溢出?求大牛答案
回复 支持 反对

使用道具 举报

xin_gator 发表于 2015-11-5 02:39:23 | 显示全部楼层
感觉题好难啊,不过题难的话feedback不一定很差的,不哭不哭,加油呀!谢谢分享,我又学到了morris traversal。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 04:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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