一亩三分地论坛

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

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

Google实习面经

[复制链接] |试试Instant~ |关注本帖
yixianpig 发表于 2016-2-28 11:01:01 | 显示全部楼层 |阅读模式

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

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

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

x
google是我的处女电面,2.2背靠背(还是通过NBA才知道背靠背的意思,之前看地里面经说背靠背,都不知道在说什么T.T)

第一面是国人小哥(刚去一年的新人,我觉得新人的题都偏难?)
给一个undirected graph,举个栗子如下:
0-(0)--1--(1)--2. from: 1point3acres.com/bbs
\        \
  (1)    (1). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    \        \. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
     3-(0)--4
给两个数字,代表起点和终点,请问最短的从起点到终点的路径,且最多经过一个(0)的arc
第一次电面有点懵,当时水平真的是也不够(面前各种祈祷不要graph不要dp,一语成谶)...不敢下手写,硬是跟小哥火热的聊了20分钟的思路(手动笑cry).鏈枃鍘熷垱鑷1point3acres璁哄潧
小哥犹豫的问我:你想咱们再接着讨论思路呢,还是你写写代码? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我说这是technical interview,当然要写代码呀~硬着头皮开始写....鐣欏璁哄潧-涓浜-涓夊垎鍦
最后写出来了,可是忘记没检查该node走没走过...觉得是这面太差了所以没过...
好处是之后看到graph或者dp连带backtracking我都牟足了劲儿看~哈哈哈

第二面是一个六年了的大哥. from: 1point3acres.com/bbs
gray code原题不细说啦~https://leetcode.com/problems/gray-code/
follow up是返回n sequence的第m行


2.19收到的拒信,虽然没过,收获很多~

评分

3

查看全部评分

iwofr 发表于 2016-3-1 07:15:15 | 显示全部楼层
happy_john 发表于 2016-3-1 06:33
我觉得johnjavabean 的疑问是道理的。
假设有两条path从src到中间点m (e.g., 一条不经过0arc, 距离为2, ...

有道理,我开始只考虑了只能经过一个0,那么最短path应该differ most by 1,而differ most by 1的nodes都同时会在queue里所以都会被算出来。不过你说的情况也存在。那么直接用BFS确实就是不对的。
目前想到两种解决你说的情况的方法,一个就是最基本的backtracking search出所有path做比较,两个剪枝的地方是如果碰见第二个0就可以返回了,另外一个是如果当前积累的路径>已经找到的最短路径也就可以返回了。
第二种是BFS不对node做isVisited check,除非碰见第二个0以外无论如何都要push到queue上,这样你给的例子里面m就会两次被push到queue 上面,这样第一次碰见destination时候还是最短路径,算法可以直接停止了,不过中间会push 多余的node到queue上,计算时间会比正常的bfs多。
感觉可以进一步优化第二种方法,利用differ most by 1这个信息把redundent的nodes减少到最低,不过还没想到怎么做。
回复 支持 1 反对 0

使用道具 举报

sunnywrq 发表于 2016-3-1 01:02:19 | 显示全部楼层
求问第一个graph的题怎么做啊?
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-3-1 01:25:50 | 显示全部楼层
sunnywrq 发表于 2016-3-1 01:02
求问第一个graph的题怎么做啊?

如果每个edge的distance 不是1就是0的话(看lz的例子应该是这样),就用BFS,只不过queue里除了记录当前node,还要记录之前有没有经过edge是0的edge,如果有再次碰到0就不push 到queue里了。. Waral 鍗氬鏈夋洿澶氭枃绔,
如果每个edge除了0剩下的distance是随意正数的话就用dikstra找最短路径,除了distance同样要记录有没有经过0的edge
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-3-1 02:39:04 | 显示全部楼层
iwofr 发表于 2016-3-1 01:25
如果每个edge的distance 不是1就是0的话(看lz的例子应该是这样),就用BFS,只不过queue里除了记录当前n ...
.1point3acres缃
dijkstra这里有点疑问,你在不同的node经过0很可能导致不同的最短距离啊,所以你不能仅仅判断经过一个0以后就不用再考虑其他0了....这样不能保证最短...感觉这个题没这么简单,可能要枚举每个0的位置...
回复 支持 反对

使用道具 举报

echo33 发表于 2016-3-1 02:57:07 | 显示全部楼层
johnjavabean 发表于 2016-3-1 02:39
dijkstra这里有点疑问,你在不同的node经过0很可能导致不同的最短距离啊,所以你不能仅仅判断经过一个0以 ...

没错吧,指的是不能走两次经过0的path啊。。。其他的判断应该都一样的
回复 支持 反对

使用道具 举报

leo817 发表于 2016-3-1 03:38:26 | 显示全部楼层
楼主 n sequence的第m 行是什么意思呢?
回复 支持 反对

使用道具 举报

 楼主| yixianpig 发表于 2016-3-1 03:46:50 | 显示全部楼层
johnjavabean 发表于 2016-3-1 02:39
dijkstra这里有点疑问,你在不同的node经过0很可能导致不同的最短距离啊,所以你不能仅仅判断经过一个0以 ...

你说的我不太明白,题目想说的是只能经过一个值为0的arc
回复 支持 反对

使用道具 举报

 楼主| yixianpig 发表于 2016-3-1 03:47:34 | 显示全部楼层
leo817 发表于 2016-3-1 03:38
楼主 n sequence的第m 行是什么意思呢?

比如n=2, m=1返回01
回复 支持 反对

使用道具 举报

 楼主| yixianpig 发表于 2016-3-1 03:49:12 | 显示全部楼层
iwofr 发表于 2016-3-1 01:25
如果每个edge的distance 不是1就是0的话(看lz的例子应该是这样),就用BFS,只不过queue里除了记录当前n ...

谢谢大神!!!只有0或1,不过随意正数真是一个好follow up!
回复 支持 反对

使用道具 举报

leo817 发表于 2016-3-1 03:58:42 | 显示全部楼层
yixianpig 发表于 2016-3-1 03:47
比如n=2, m=1返回01
.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个不会是先用之前写的graycode的function算出n个,然后再找到第m个?
回复 支持 反对

使用道具 举报

happy_john 发表于 2016-3-1 06:33:28 | 显示全部楼层
echo33 发表于 2016-3-1 02:57
没错吧,指的是不能走两次经过0的path啊。。。其他的判断应该都一样的

我觉得johnjavabean 的疑问是道理的。
假设有两条path从src到中间点m (e.g., 一条不经过0arc, 距离为2, 另一条经过 0arc距离为1), 从m再到dst. 完全有可能第一条path的总距离最短(比如m直接通过一个0arc与dst相连,第一条路可以走,但第二条路不行了)
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果只是BFS的话,只有第二条路能被记录下来
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-3-1 08:51:02 | 显示全部楼层
iwofr 发表于 2016-3-1 07:15. visit 1point3acres.com for more.
有道理,我开始只考虑了只能经过一个0,那么最短path应该differ most by 1,而differ most by 1的nodes都 ...

dfs+backtracking可行,而且无论边长是1或者n都是一样解,的确没想出边长都是1有什么可以利用的地方
回复 支持 反对

使用道具 举报

 楼主| yixianpig 发表于 2016-3-2 01:13:42 | 显示全部楼层
leo817 发表于 2016-3-1 03:58
这个不会是先用之前写的graycode的function算出n个,然后再找到第m个?

因为太简单所以不敢相信吗~其实不用完整算出第n个,既然简单就尽量简化time和space。这样虽然题目简单也能显得表现还行T.T
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-3 13:11:24 | 显示全部楼层
第一题是dfs,记录下遇到了多少0吗?并且不断更新最短路径
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-3-31 07:26:10 | 显示全部楼层
这第一题算得上是graph中的难题了吧 哎 这面试官真会挑题目。。。
回复 支持 反对

使用道具 举报

dimi 发表于 2016-3-31 09:54:21 | 显示全部楼层
多謝楼主面经,每想到google这么爱问图的問題。实习都不放过
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-28 05:26:00 | 显示全部楼层
感谢分享,bfs+记录路径应该可以的。
回复 支持 反对

使用道具 举报

wujingzhishui 发表于 2016-7-11 11:59:18 | 显示全部楼层
这题是dfs+dp的方法么,虽然感觉行的通但是写不出来的感觉。。。。。顺便问下楼主是怎么知道面试是国人小哥的,,难道面试还中文了,额
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 04:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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