一亩三分地论坛

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

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

Google最新电面

[复制链接] |试试Instant~ |关注本帖
zws0818 发表于 2015-7-30 04:08:12 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
7/29最新google电面,面完接着发面经,攒RP,求下一轮电面或者onsite!!!
通话质量不好,有杂音,好在面试官不是三哥/三姐,口音比较清楚,而且把问题写在了doc上
两个题
1. longest consecutive numbers
[size=13.3333330154419px]lc原题,但要考虑重复,而且numbers无序, 并且[size=13.3333330154419px]要输出最长的numbers,
[size=13.3333330154419px]example:
1, 2, 3, 4, 6, 7, 8, 9, 10, 11 → 6, 7,8, 9, 10, 11
.1point3acres缃
11, 10, 9, 8, 7, 6 4, 3, 2,1 ->11, 10, 9, 8, 7, 6
1, 2, 3, 1, 2, 3, 4, 5 -> 1, 2, 3, 4, 5

1, 2, 3, 4, 3, 4, 5, 6, 7 -> 3, 4, 5, 6, 7

2.第1题的follow-up
numbers变成二叉树,找longest consecutive numbers
[size=13.3333330154419px]example:
     1
  2     3
      5    3

→ 1, 2
树的题一向做的不好,感觉和树这种数据结构不来电,花了挺长时间,最后面试官说简化只要求最长的length就好,因为时间紧迫,随便写了一个递归就交了,不知道有没有bug,但是从面试官反应来看,应该写的不是太没水平~~

.鏈枃鍘熷垱鑷1point3acres璁哄潧
.1point3acres缃

评分

3

查看全部评分

zhouyoung1124 发表于 2015-7-30 04:34:58 | 显示全部楼层
这题思路应该和max path sum是一样的,立一个global 的 max, 递归求longestEndsAtT, 在求的过程中更新max,最后返回max
回复 支持 反对

使用道具 举报

 楼主| zws0818 发表于 2015-7-30 04:40:53 | 显示全部楼层
zhouyoung1124 发表于 2015-7-30 04:34
这题思路应该和max path sum是一样的,立一个global 的 max, 递归求longestEndsAtT, 在求的过程中更新max, ...

你的思路是对的,我想错了,估计要挂~~~
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-7-30 04:43:53 | 显示全部楼层
zws0818 发表于 2015-7-30 04:40.1point3acres缃
你的思路是对的,我想错了,估计要挂~~~

不一定的,,,可能就放过了也可能加面,,,我电面一面也面的不好,就加面了
回复 支持 反对

使用道具 举报

 楼主| zws0818 发表于 2015-7-30 05:32:10 | 显示全部楼层
zhouyoung1124 发表于 2015-7-30 04:43. visit 1point3acres.com for more.
不一定的,,,可能就放过了也可能加面,,,我电面一面也面的不好,就加面了
. more info on 1point3acres.com
在这攒RP吧
回复 支持 反对

使用道具 举报

maybeluo 发表于 2015-7-30 09:52:43 | 显示全部楼层
lz是大陆还是oversea?
回复 支持 反对

使用道具 举报

 楼主| zws0818 发表于 2015-7-30 10:40:18 | 显示全部楼层
maybeluo 发表于 2015-7-30 09:52
lz是大陆还是oversea?

oversea,不是大陆
回复 支持 反对

使用道具 举报

 楼主| zws0818 发表于 2015-7-30 10:40:29 | 显示全部楼层
maybeluo 发表于 2015-7-30 09:52.鏈枃鍘熷垱鑷1point3acres璁哄潧
lz是大陆还是oversea?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
oversea,不是大陆
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-7-30 11:22:15 | 显示全部楼层
zhouyoung1124 发表于 2015-7-30 04:34 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这题思路应该和max path sum是一样的,立一个global 的 max, 递归求longestEndsAtT, 在求的过程中更新max, ...

同意这个思路 同时maintain对应的TreeNode 最后求tree path也容易
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-7-30 11:56:33 | 显示全部楼层
二叉树是用inorder吧?
回复 支持 反对

使用道具 举报

say543 发表于 2015-7-30 16:33:51 | 显示全部楼层
弱弱的问一下思路要怎么同时考虑increasing 和decreasing 的sequence呢难道要做两次traversal?
回复 支持 反对

使用道具 举报

 楼主| zws0818 发表于 2015-7-31 02:51:14 | 显示全部楼层
hulahu 发表于 2015-7-30 11:56
二叉树是用inorder吧?

就是一般的二叉树,不是BST
回复 支持 反对

使用道具 举报

 楼主| zws0818 发表于 2015-7-31 02:52:39 | 显示全部楼层
say543 发表于 2015-7-30 16:33
弱弱的问一下思路要怎么同时考虑increasing 和decreasing 的sequence呢难道要做两次traversal?

用map一次遍历就可以
回复 支持 反对

使用道具 举报

say543 发表于 2015-7-31 17:12:29 | 显示全部楼层
LZ 说的是问题1用map 是嘛? 没说清楚我想问的是第二题二叉树怎么同时考虑increasing 和decreasing 的sequence呢?难道要做两次traversal?
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-7-31 21:45:59 | 显示全部楼层
say543 发表于 2015-7-31 17:12
LZ 说的是问题1用map 是嘛? 没说清楚我想问的是第二题二叉树怎么同时考虑increasing 和decreasing 的sequen ...

可以选择做两次,或者设两套global max,本质是一样的,不影响时间复杂度
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-7-31 23:44:01 | 显示全部楼层
zhouyoung1124 发表于 2015-7-30 04:34
这题思路应该和max path sum是一样的,立一个global 的 max, 递归求longestEndsAtT, 在求的过程中更新max, ...

不一定都是从root开始吧?感觉应该用DP
回复 支持 反对

使用道具 举报

UBCCS 发表于 2015-7-31 23:47:50 | 显示全部楼层
多谢分享,Mark
回复 支持 反对

使用道具 举报

eamon_felix4213 发表于 2015-8-2 02:41:02 | 显示全部楼层
感谢lz分享!请问比如 5,6,9, 10, 11, 1, 2, 3这样有两个相同长度的需要全部返回吗,还是只返回一个呢
回复 支持 反对

使用道具 举报

eamon_felix4213 发表于 2015-8-2 08:15:33 | 显示全部楼层
eamon_felix4213 发表于 2015-8-1 13:41
感谢lz分享!请问比如 5,6,9, 10, 11, 1, 2, 3这样有两个相同长度的需要全部返回吗,还是只返回一个 ...

已解决,嗯,但是follow up还是没跑过...求大神解答啊
回复 支持 反对

使用道具 举报

laike9m 发表于 2015-8-3 21:25:35 | 显示全部楼层
那个 follow up 不太懂,为什么结果是1,2不是1,2,3呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 20:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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