一亩三分地论坛

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

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

Google 3.3 intern 跪经

[复制链接] |试试Instant~ |关注本帖
thinkin 发表于 2016-3-4 07:32:24 | 显示全部楼层 |阅读模式

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

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

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

x

刚看到地里说google已经没坑了群发邮件拒人了,不知道真的假的。这个时候面反正已经是买彩票了吧。两个电话都是直接coding没有behavior question. more info on 1point3acres.com
第一个电话印度人,口音真的难懂。题目是找binary tree里所有相同的subtree。写出来之后优化部分答得不好,时间复杂度比较高,很多时候听不懂他的意思。. 1point3acres.com/bbs
第二个电话应该是native,题目是找树里最长连续上升序列长度(1,2,3,4或者3,4,5,6,7,只能parent往children走),我用BFS做了,然后他沉默了好几分钟说一般都用DFS做的,我不知道怎么给你follow up了。然后给的follow up是path也可以从children 往 parent走,我发现这样确实是用DFS比较好写,但是已经没时间了就说了思路。

都只写了一道题,并且follow up没答好,肯定跪了。祝进pool的同学能match到,写作业去了。

评分

2

查看全部评分

mingzhou1987 发表于 2016-3-4 11:50:18 | 显示全部楼层
第二题我觉得BFS好做一点。。
int findLongestIncreasingPathLen(TreeNode *root)
{
.鏈枃鍘熷垱鑷1point3acres璁哄潧        if (!root)return 0;
        if (!root->left && !root->right)return 1;
        queue<pair<TreeNode*, int>> q;
        q.push(make_pair(root, 1));
        int maxLen = 1;
        while (!q.empty())
        {
                pair<TreeNode*, int> it = q.front();
                q.pop();. more info on 1point3acres.com
                if (it.first->left)
                {
                        if (it.first->left->val >= it.first->val)
                        {
                                q.push(make_pair(it.first->left, it.second + 1));
                        }. 1point 3acres 璁哄潧
                        else
                        {. From 1point 3acres bbs
                                q.push(make_pair(it.first->left, 1));
                        }. 1point 3acres 璁哄潧
                }
                if(it.first->right)
                {
                        if (it.first->right->val >= it.first->val)
                        {
                                q.push(make_pair(it.first->right, it.second + 1));
                        }
                        else
                        {
                                q.push(make_pair(it.first->right, 1));
                        }
                }
                if (it.second > maxLen)
                {
                        maxLen = it.second;
                }. From 1point 3acres bbs
        }. 鍥磋鎴戜滑@1point 3 acres
        return maxLen;. visit 1point3acres.com for more.
}

谁能给个DFS版本。。
回复 支持 反对

使用道具 举报

 楼主| thinkin 发表于 2016-3-4 12:11:40 | 显示全部楼层
mingzhou1987 发表于 2016-3-4 11:50.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二题我觉得BFS好做一点。。.1point3acres缃
int findLongestIncreasingPathLen(TreeNode *root)
{

不带follow up的我也觉得BFS容易些
回复 支持 反对

使用道具 举报

fl62 发表于 2016-3-4 12:17:31 | 显示全部楼层
thinkin 发表于 2016-3-4 12:11
不带follow up的我也觉得BFS容易些

楼主做的是二叉树?我记得我当初的题和你很像但是做的就是树,不是二叉树
回复 支持 反对

使用道具 举报

hshmy 发表于 2016-3-4 12:18:52 | 显示全部楼层
额 “我不知道怎么给你follow up了” 这面试官被楼主难住了
回复 支持 反对

使用道具 举报

 楼主| thinkin 发表于 2016-3-4 22:36:55 | 显示全部楼层
fl62 发表于 2016-3-4 12:17. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主做的是二叉树?我记得我当初的题和你很像但是做的就是树,不是二叉树

是不是二叉树应该问题不大吧,只要检查所有children应该就可以,主要是bfs求出最长序列后是把长度存在结尾,如果是dfs存在起点就比较方便
回复 支持 反对

使用道具 举报

 楼主| thinkin 发表于 2016-3-4 22:37:09 | 显示全部楼层
hshmy 发表于 2016-3-4 12:18
额 “我不知道怎么给你follow up了” 这面试官被楼主难住了

是我太非主流
回复 支持 反对

使用道具 举报

fl62 发表于 2016-3-4 22:43:53 | 显示全部楼层
thinkin 发表于 2016-3-4 22:36. more info on 1point3acres.com
是不是二叉树应该问题不大吧,只要检查所有children应该就可以,主要是bfs求出最长序列后是把长度存在结 ...

树的结构会设计的不一样吧。因为我看楼上的解法是看left还有right, 我最后需要返回的是所有path,不是长度。可能题目有变化吧
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-8 03:05:34 | 显示全部楼层
请问下第一题返回所有 的subtree的意思是用List<List<TreeNode>>来返回吗?

比如原树是
              1
             /  \. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            1    1
           / \   / \
         1  1  1  1
这样的话,一个node的same subtree有7个,2个node的same subtree有6个,3个node的same subtree有3个,所以是要返回所有 这些?
回复 支持 反对

使用道具 举报

leo817 发表于 2016-3-8 14:47:49 | 显示全部楼层
同问第一题
回复 支持 反对

使用道具 举报

 楼主| thinkin 发表于 2016-3-8 23:45:11 | 显示全部楼层
googlerr 发表于 2016-3-8 03:05. 1point3acres.com/bbs
请问下第一题返回所有 的subtree的意思是用List来返回吗?
. from: 1point3acres.com/bbs
比如原树是

如果有重复的,只返回一个就行了
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-9 00:48:17 | 显示全部楼层
本帖最后由 googlerr 于 2016-3-9 00:49 编辑
thinkin 发表于 2016-3-8 23:45
如果有重复的,只返回一个就行了

只返回任意一个same subtree pair?subtree必须是到leaf吗?还是中间随便截取一段就行?如果是中间随便截取一段就行,那么只要找到两个node的value相同就是一对same subtree pair吧?
回复 支持 反对

使用道具 举报

 楼主| thinkin 发表于 2016-3-9 03:21:07 | 显示全部楼层
googlerr 发表于 2016-3-9 00:48
只返回任意一个same subtree pair?subtree必须是到leaf吗?还是中间随便截取一段就行?如果是中间随便截 ...
. 1point 3acres 璁哄潧
必须到leaf,返回的是一组节点,以这些节点为root的subtree有重复的
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-9 04:58:56 | 显示全部楼层
thinkin 发表于 2016-3-9 03:21
必须到leaf,返回的是一组节点,以这些节点为root的subtree有重复的
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
OK,应该理解了。所以比如这个tree

              1
             /  \
            2    2. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
           / \   / \
         3  4  3  4

返回的就是两个以2为root的subtree。谢谢!
回复 支持 反对

使用道具 举报

 楼主| thinkin 发表于 2016-3-10 05:43:32 | 显示全部楼层
googlerr 发表于 2016-3-9 04:58
OK,应该理解了。所以比如这个tree

              1

客气客气,根据我的理解,返回的应该是节点2,3,4吧,这些subtree都有重复
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-6 06:21:38 | 显示全部楼层
有人能说一下第一题的思路吗,难道是比较tree里面的每一对node作为subtree的root?
回复 支持 反对

使用道具 举报

kiviljc 发表于 2016-4-8 22:01:20 | 显示全部楼层
第一题求思路啊。。
回复 支持 反对

使用道具 举报

GavinM 发表于 2016-4-22 05:46:02 | 显示全部楼层
kiviljc 发表于 2016-4-8 22:01
第一题求思路啊。。
  1. public static boolean compare(TreeNode node1, TreeNode node2, List<Integer> ans){
  2.                 if(node1 == null && node2 == null) return true;
  3.                 if(node1 == null || node2 == null) return false;. 1point3acres.com/bbs
  4.                 boolean left = compare(node1.left, node2.left, ans);
  5.                 boolean right = compare(node1.right, node2.right, ans);
  6.                 if(node1.val == node2.val && left && right){
  7.                         ans.add(node1.val);. more info on 1point3acres.com
  8.                         return true;
  9.                 }
  10.                 return false;
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.         }
复制代码
我的想法。如果不对请指正。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 06:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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