一亩三分地论坛

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

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

google MTV onsite

[复制链接] |试试Instant~ |关注本帖
see_you2012 发表于 2016-3-13 23:21:45 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Passfresh grad应届毕业生

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

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

x
前不久的google MTV onsite~ 昨天收到offer~ 特来发面经感谢地里的帮助!!

一共四轮:
1. 阿三小哥: 第一题,面经中经常出现的排队问题,follow up是再插入的时候用tree来优化时间复杂度。第二题,leetcode原题,数组中找和为一个定值的最长子序列
2. 貌似中东来的小哥: 先扯简历10分钟,然后问你让你建字符串的一个字典,但是不许你用Hash fucntion, 你怎么做。当即想到Trie 树,说思路描述算法,然后15分钟
写完代码, 有add search 等功能。follow up: 添加正则匹配的功能
3. 白人小哥: 也是先问简历,然后出了一道warm up的简单的dp问题, 不用写代码,描述dp方程和如何初始化。第二题,Leetcode原题,substring with at most k distinct . visit 1point3acres.com for more.
charactors.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
4. 国人小哥:来的时候看起来很严肃,弄得我很心虚。第一题: 问一棵二叉树能不能通过 swap 左右子树变成另一颗树,很简单,直接递归解,然后跑了跑case,问了复杂度。
第二题,问一二叉棵树通过swap操作能不能变为二分查找树,这个代码比较长,也是递归解。
. more info on 1point3acres.com
感觉我运气比较好,四轮都面的挺顺利,跟面试官沟通也很愉快~ 面完就感觉挺有戏的

祝大家都面试顺利~ 然后顺便求大米!!. visit 1point3acres.com for more.


. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴补充内容 (2016-3-17 22:31):
不知道怎么补充附件。。。 总结的资料在最后楼层中! 希望能帮到大家!

评分

7

查看全部评分

 楼主| see_you2012 发表于 2016-3-17 22:30:38 | 显示全部楼层
附上我总结的 最近的google 高频面试题!!  希望能帮到大家~~

G.zip

142.83 KB, 阅读权限: 1, 下载次数: 332, 下载积分: 大米 -1 升

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

Ulu2005 发表于 2016-3-14 00:05:01 | 显示全部楼层
楼主求问最后一轮第二题怎么解啊?
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-3-14 03:40:23 | 显示全部楼层
面经中经常出现的排队问题  是什么题目啊?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
二叉棵树通过swap操作能不能变为二分查找树
这题你怎么做的?
回复 支持 反对

使用道具 举报

Sendoh2015 发表于 2016-3-14 03:52:40 | 显示全部楼层
同问二叉树怎么变二分查找树,楼主能说说吗?谢谢啊
回复 支持 反对

使用道具 举报

xiaoniqiuqiu 发表于 2016-3-14 04:41:45 | 显示全部楼层
同求问最后一题第二问~多谢~
回复 支持 反对

使用道具 举报

AlstonLYG 发表于 2016-3-14 21:47:10 | 显示全部楼层
祝贺! 请问有hc和team match环节吗?能问下timeline吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-14 23:17:38 | 显示全部楼层
请问第二轮正则表达式功能怎么做?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-14 23:18:30 | 显示全部楼层
请问第二轮正则表达式功能怎么做?
回复 支持 反对

使用道具 举报

majia113 发表于 2016-3-15 04:40:59 | 显示全部楼层
面经中经常出现的排队问题  是什么题目啊?
. visit 1point3acres.com for more.
二叉棵树通过swap操作能不能变为二分查找树
这题你怎么做的?

同问这两个,另外swap操作有什么限制么?
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-3-15 10:34:15 | 显示全部楼层
第一题排队问题能描述一下吗? 第4轮第一题是不是直接判断左右子树是否是same tree? 第2问也是swap左右子树的操作吗? 如果每一个node.val都介于left.val, right.val就可以?
回复 支持 反对

使用道具 举报

jerryisback 发表于 2016-3-15 12:31:35 | 显示全部楼层
贴下我的解法,第四题第二问。顺便问下第一题排队是哪个题?

bool canSwapToBST ( TreeNode* root){
return        canSwapToBST( root, min_val, max_val); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

}

bool canSwapToBST( TreeNode* root, int min_val, int max_val){
        if( !root) return true;. From 1point 3acres bbs
        if( root->val >= max_val || root->val < min_val) return false;
        return  (canSwapToBST( root->left, min_val, root->val) && canSwapToBST( root->right, root->val, max_val)  ). 1point 3acres 璁哄潧
|| ( canSwapToBST( root->right , min_val, root->val) && canSwapToBST( root->left, root->val, max_val) )
}


补充内容 (2016-3-15 12:34):
上边应该是canSwapToBST(root, INT_MAX,INT_MIN);
回复 支持 反对

使用道具 举报

 楼主| see_you2012 发表于 2016-3-15 22:37:59 | 显示全部楼层
补充一下: 排队那个题: 一队人,每个人只知道自己前面有几个比自己高的,然后打乱顺序,告诉你每个人的高度,让你恢复原来的顺序
回复 支持 反对

使用道具 举报

 楼主| see_you2012 发表于 2016-3-15 22:42:49 | 显示全部楼层
然后最后一轮第二问,我是递归解的,我可能没太说清楚题意, swap操作是交换左右子树的,然后子树也可以进行swap。这跟leetcode有道题,verify BST有点像,可是每步verify的时候,你还要考虑swap的可能性。
回复 支持 反对

使用道具 举报

 楼主| see_you2012 发表于 2016-3-15 22:45:54 | 显示全部楼层
Ulu2005 发表于 2016-3-14 00:05.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主求问最后一轮第二题怎么解啊?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充在最后了~
回复 支持 反对

使用道具 举报

 楼主| see_you2012 发表于 2016-3-15 22:46:13 | 显示全部楼层
duduhaha 发表于 2016-3-14 03:40
面经中经常出现的排队问题  是什么题目啊?. from: 1point3acres.com/bbs

二叉棵树通过swap操作能不能变为二分查找树
-google 1point3acres
补充在最后了~
回复 支持 反对

使用道具 举报

 楼主| see_you2012 发表于 2016-3-15 22:46:21 | 显示全部楼层
Sendoh2015 发表于 2016-3-14 03:52
同问二叉树怎么变二分查找树,楼主能说说吗?谢谢啊

补充在最后了~
回复 支持 反对

使用道具 举报

 楼主| see_you2012 发表于 2016-3-15 22:46:31 | 显示全部楼层
xiaoniqiuqiu 发表于 2016-3-14 04:41
同求问最后一题第二问~多谢~

补充在最后了~
回复 支持 反对

使用道具 举报

 楼主| see_you2012 发表于 2016-3-15 22:48:58 | 显示全部楼层
AlstonLYG 发表于 2016-3-14 21:47
祝贺! 请问有hc和team match环节吗?能问下timeline吗?

2.29  面试,一周后hc,然后还有一轮review,再一周后给offer,拿deadline催的。

然后team match是入职前一两个月。
回复 支持 反对

使用道具 举报

 楼主| see_you2012 发表于 2016-3-15 22:50:48 | 显示全部楼层
bobzhang2004 发表于 2016-3-14 23:18
请问第二轮正则表达式功能怎么做?

比如a??b, 中间问好可以代表任意字符,用backtracking解。如果是*号,可以代表任意长度任意字符,也是一样用backtracking,这个没写代码只说了想法。
回复 支持 反对

使用道具 举报

 楼主| see_you2012 发表于 2016-3-15 22:50:55 | 显示全部楼层
bobzhang2004 发表于 2016-3-14 23:18
请问第二轮正则表达式功能怎么做?

比如a??b, 中间问好可以代表任意字符,用backtracking解。如果是*号,可以代表任意长度任意字符,也是一样用backtracking,这个没写代码只说了想法。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 06:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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