一亩三分地论坛

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

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

发个Google电话面经, 求onsite

[复制链接] |试试Instant~ |关注本帖
finalItw 发表于 2016-11-17 04:14:37 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚结束的电话面试, 感觉有点悬.. from: 1point3acres.com/bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
1. check two binary tree are similar
  1. . from: 1point3acres.com/bbs
  2.        5. more info on 1point3acres.com
  3.    2      4
  4. 1   3   null   6. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  5.       5
  6.   2       4
  7. 3   1  6    null
复制代码
即root要相等, left/right可以交换. "交换"可以进行多次.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

首先想到的就是recursion遍历, 相等则继续比较, 不相等就交换着比较.

  1. public boolean helper(root1, root2){
  2.     if(root1==null || root2==null) return true;
  3.     if(!(root1!=null && root2!=null && root1.val==root2.val)) return false;. Waral 鍗氬鏈夋洿澶氭枃绔,
  4.     return (helper(root1.left, root2.right) && helper(root1.right, root2.left)) || (helper(root1.right, root2.right) && helper(root1.left, root.left));  
  5. }. 1point3acres.com/bbs
复制代码
对面一直在纠结空指针怎么办, 然后我说前两个if就能排除空指针的可能性, 然后他举了几个例子, 觉得没问题, 就问了复杂度. 这里我先说复杂度是O(2*N), 然后感觉不对, 毕竟涉及到recursion, 赶紧改口说应该是O(N^2). 对方说不对, 说可以用数学的方法证明, 我说哦, 那就是 master theorem, 他说对, 不过也没继续问.

这时已经过去33分钟了, 他说那我们问一个简单题吧, 俩list, 交叉打印.
我说如果只有2个, 可以two pointer, 如果有多个可以用queue装多个, 他说两个就好. 然后5分钟写完了.

这时已经过去了40分钟, 我问了俩问题, 然后就结束了. 感觉第一题做得不好, 估计要跪, 求onsite.




补充内容 (2016-11-29 04:20):
11月21日 已收到onsite...

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| finalItw 发表于 2016-11-17 04:17:28 | 显示全部楼层
其实到现在我也不知道自己的解法对不对...  唉, 脑子里一团浆糊.
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-17 04:26:13 | 显示全部楼层
你第一题是我年初面google实习加面的原题,代码应该是对的。我当时记得time complexity是4n好像。遍历tree有recursion也应该不会是n^2, 比如in order,pre order这些,都是o(n)吧。. more info on 1point3acres.com
我第2题是个iterator的题。
回复 支持 反对

使用道具 举报

 楼主| finalItw 发表于 2016-11-17 04:33:53 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-17 04:26
你第一题是我年初面google实习加面的原题,代码应该是对的。我当时记得time complexity是4n好像。遍历tree ...

唉 我刚发现我当时写代码 最后的return 缺了最外面的括号

当时写的时候也不是很顺  对方一直说有null pointer  解释了很久

回复 支持 反对

使用道具 举报

novking 发表于 2016-11-17 09:34:58 | 显示全部楼层
请问 为什么是
  1. if(root1==null || root2==null) return true;
复制代码
而不是
  1. if(root1==null && root2==null) return true;
复制代码
一个是null 一个不是,返回的就是True了呀?
回复 支持 反对

使用道具 举报

fay19 发表于 2016-11-17 09:49:53 | 显示全部楼层
novking 发表于 2016-11-17 09:34
请问 为什么是  而不是  一个是null 一个不是,返回的就是True了呀?

我也认为这里是 &&
回复 支持 反对

使用道具 举报

stephen_std 发表于 2016-11-17 10:04:16 | 显示全部楼层
good luck  一定onsite!
回复 支持 反对

使用道具 举报

antonioybw 发表于 2016-11-17 11:00:58 | 显示全部楼层
感觉按照代码  应该是   T(N)=4T(N/2) + O(1)    master theory 或者换算 应该是   O(N^2)  复杂度?   楼主过了的话来更新下吧
回复 支持 反对

使用道具 举报

 楼主| finalItw 发表于 2016-11-17 13:27:12 | 显示全部楼层
novking 发表于 2016-11-17 09:34
请问 为什么是  而不是  一个是null 一个不是,返回的就是True了呀?

是我的笔误  应该是 &&  
回复 支持 反对

使用道具 举报

 楼主| finalItw 发表于 2016-11-17 13:28:36 | 显示全部楼层
antonioybw 发表于 2016-11-17 11:00. Waral 鍗氬鏈夋洿澶氭枃绔,
感觉按照代码  应该是   T(N)=4T(N/2) + O(1)    master theory 或者换算 应该是   O(N^2)  复杂度?    ...
. 1point 3acres 璁哄潧
哈哈 你这么一说 我当时应该坚持一下 推导出N^2的
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
当时脑子里想的全是明明没有空指针 你这货非说有空指针
回复 支持 反对

使用道具 举报

fay19 发表于 2016-11-18 09:53:37 | 显示全部楼层
finalItw 发表于 2016-11-17 13:28. visit 1point3acres.com for more.
哈哈 你这么一说 我当时应该坚持一下 推导出N^2的
.鏈枃鍘熷垱鑷1point3acres璁哄潧. 1point3acres.com/bbs
当时脑子里想的全是明明没有空指针 你这货非说有空 ...

我感觉应该是O(2N)哎,因为最后一步是平行的,没有嵌套,只能是反正交叉遍历一次O(N)发现不Ok, 在left pair left, right pair right的正着遍历一次O(N), 楼主O(N^2)能解释一下吗?谢啦!
回复 支持 反对

使用道具 举报

小A要当码农 发表于 5 天前 | 显示全部楼层
这个题的复杂度  应该是O(N^2)把?
回复 支持 反对

使用道具 举报

cgxy1991 发表于 5 天前 | 显示全部楼层
如果n=node数,则是O(n)
如果n=树深度,则是O(n^2)
回复 支持 反对

使用道具 举报

 楼主| finalItw 发表于 4 天前 | 显示全部楼层
cgxy1991 发表于 2016-12-1 13:54. From 1point 3acres bbs
如果n=node数,则是O(n)
如果n=树深度,则是O(n^2)

如果是深度 那得是2^h吧
回复 支持 反对

使用道具 举报

cgxy1991 发表于 4 天前 | 显示全部楼层
finalItw 发表于 2016-12-2 01:58
如果是深度 那得是2^h吧

我算了一下。node数和树深度的关系是O(n^2)(也就是说如果树深度从n变成2n,node数就从x变成x^2), 所以应该是O(n^2)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 04:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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