一亩三分地论坛

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

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

Google Intern 两轮电面

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

2015(10-12月) 码农类 本科 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
刚刚面完Google Intern,背靠背两轮。

第一轮,烙印。
Q1. Given a sorted array of integer and another integer, find a closest number from the array.
Q2. Given a n-ary tree, find longest consecutive sequence. Follow up: If you have a graph instead of tree
. 鍥磋鎴戜滑@1point 3 acres. from: 1point3acres.com/bbs
第二轮,美国纽约白人
1.Find the height of a tree.
2. Implement a function addLandAndCountIslands(x, y) that marks a place on a grid as being “land” where unmarked locations are “water”. Follow up: 方程会被call很多次,如何优化。应该就是用一个变量纪录当前的岛数,如果mark的xy周围都是海,就直接加1,如果周围有有1个以上的陆地,需要分情况讨论。 (最后问了如果这样优化efficiency是多少,这个没答好。)
3. Given a string of characters s and a character c, find the max substring of s with at most two instances of c. 只说算法,不用写。

总的来说比地里面经简单一些,可能因为职位还有学历吧,祝大家都好运。
. Waral 鍗氬鏈夋洿澶氭枃绔,
求offer,赞rp,再求点大米.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

3

查看全部评分

JoeWest 发表于 2015-11-11 10:39:20 | 显示全部楼层
hey楼主,第一轮第二问的graph应该用什么方法?
我想到的是对于每个结点用DFS找最深的路径...但是这样效率太低了...
还有,n-ary tree和graph可以用同一种方法吗?
望指教,多谢~
回复 支持 反对

使用道具 举报

 楼主| Jaden 发表于 2015-11-11 13:56:33 | 显示全部楼层
JoeWest 发表于 2015-11-11 10:39
hey楼主,第一轮第二问的graph应该用什么方法?
我想到的是对于每个结点用DFS找最深的路径...但是这样效率 ...

graph面试官没有让我写程序,就只是两个人在讨论。我们说到还是用dfs搜索每条路径,然后要记得标记每个节点,因为会grahh会导致很多重复的访问。其次就是讨论圈,圈的话本质上对这个题没有影响,面试官就是希望我说到需要纪录没个节点,发现圈之后,要从recursion里跳出来,而不是无限循环的做。 我也没有想出更好的方法做graph,如果有大牛想出来,求留言指点。
回复 支持 反对

使用道具 举报

JoeWest 发表于 2015-11-11 14:27:36 | 显示全部楼层
Jaden 发表于 2015-11-11 13:56
graph面试官没有让我写程序,就只是两个人在讨论。我们说到还是用dfs搜索每条路径,然后要记得标记每个节 ...

多谢指点!还有个地方不太明白,graph中的圈对某个结点的dfs应该没有影响吧?毕竟圈里的点已经遍历过了,不会循环做
回复 支持 反对

使用道具 举报

 楼主| Jaden 发表于 2015-11-11 14:33:52 | 显示全部楼层
JoeWest 发表于 2015-11-11 14:27
多谢指点!还有个地方不太明白,graph中的圈对某个结点的dfs应该没有影响吧?毕竟圈里的点已经遍历过了, ...

我的方法是这样的,有节点就进,进去之后判断是不是连续,如果是连续dfs里的len就加一然后继续做dfs,如果不连续len就按0传进去。对于树的话,它到root==NULL 就会return,但是graph不一样,如果graph有圈,你找不到一个null就停不下来。所以就要提前判断是否有圈,然后纪录没个访问的node,这样当所有node都被纪录访时,递归停止。 :)
回复 支持 反对

使用道具 举报

netario 发表于 2015-11-11 16:12:33 | 显示全部楼层
island那题图不大的话能不能用并查集做
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-11-11 17:08:18 | 显示全部楼层
第一题 用binary search么?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-11-11 17:10:59 | 显示全部楼层
lz怎么找的内推。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-11-11 17:13:33 | 显示全部楼层
“ 总的来说比地里面经简单一些,可能因为职位还有学历吧,祝大家都好运“
lz的意思是 学校特别好,题也会简单么?
回复 支持 反对

使用道具 举报

 楼主| Jaden 发表于 2015-11-11 17:25:51 | 显示全部楼层
netario 发表于 2015-11-11 16:12
island那题图不大的话能不能用并查集做

. visit 1point3acres.com for more.我不太确定唉
回复 支持 反对

使用道具 举报

 楼主| Jaden 发表于 2015-11-11 17:27:34 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-11-11 17:13. more info on 1point3acres.com
“ 总的来说比地里面经简单一些,可能因为职位还有学历吧,祝大家都好运“
lz的意思是 学校特别好,题也会 ...

是的第一题用binary search就好了
内推我是找的朋友.鏈枃鍘熷垱鑷1point3acres璁哄潧
我的意思不是说学校好题目简单啦  我的意思是说我觉得intern的职位面本科和master的时候好像有点区别  因为这些题目比地里的面经会简单很多 我只是胡乱猜测  跟学校肯定是没有关系的 :)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

JoeWest 发表于 2015-11-11 22:41:39 | 显示全部楼层
Jaden 发表于 2015-11-11 14:33
我的方法是这样的,有节点就进,进去之后判断是不是连续,如果是连续dfs里的len就加一然后继续做dfs,如果 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
OK,多谢指点啦
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-12 04:53:44 | 显示全部楼层
请问第一轮第二题的graph是有向图还是无向图?
回复 支持 反对

使用道具 举报

 楼主| Jaden 发表于 2015-11-12 05:02:22 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-12 04:53
请问第一轮第二题的graph是有向图还是无向图?

其他我们好像都忽略了这个问题,不过面试官和我讨论的时候都是按有向图来说的,如果无向的话应该是dfs的时候需要增加一个变量判断这条路径是递减还是递增。 我们没有说到无向图的具体实现。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-12 09:10:38 | 显示全部楼层
Jaden 发表于 2015-11-12 05:02
其他我们好像都忽略了这个问题,不过面试官和我讨论的时候都是按有向图来说的,如果无向的话应该是dfs的 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
哦哦,好的,请问那个longest consecutive sequence in n-ary tree是什么样的,是能从任意地方开始和结束吗?
回复 支持 反对

使用道具 举报

 楼主| Jaden 发表于 2015-11-12 10:23:31 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-12 09:10
哦哦,好的,请问那个longest consecutive sequence in n-ary tree是什么样的,是能从任意地方开始和结束 ...

恩 从任意节点开始和结束 一个node有n个children  只能从小到大不能逆序
回复 支持 反对

使用道具 举报

JoeWest 发表于 2015-11-12 11:42:20 | 显示全部楼层
Jaden 发表于 2015-11-12 10:23
恩 从任意节点开始和结束 一个node有n个children  只能从小到大不能逆序

leetcode的binary tree consecutive sequence是只能从parent到children,这里不一样吗?可以从children到parent再到其他children?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-12 12:58:40 | 显示全部楼层
JoeWest 发表于 2015-11-12 11:42
leetcode的binary tree consecutive sequence是只能从parent到children,这里不一样吗?可以从children到 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我觉得lz说的意思应该是一条边上可以从任一点开始任一点结束,就是不会经过root在折过来这样,不知道有没有理解对 @LZ

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| Jaden 发表于 2015-11-12 13:38:12 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-12 12:58. from: 1point3acres.com/bbs
我觉得lz说的意思应该是一条边上可以从任一点开始任一点结束,就是不会经过root在折过来这样,不知道有没 ...

是的是的 你说的是对的  就是说dfs肯定从root开始 但是最长的连续不一定从root开始  思路跟leetcode上的没有太大差异 不可以从子树到根再转换到另外一个子树

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| Jaden 发表于 2015-11-12 13:38:41 | 显示全部楼层
JoeWest 发表于 2015-11-12 11:42
leetcode的binary tree consecutive sequence是只能从parent到children,这里不一样吗?可以从children到 ...

请看上面一楼 :)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 15:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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