一亩三分地论坛

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

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

google on campus 实习面试

[复制链接] |试试Instant~ |关注本帖
bluefreedom 发表于 2015-10-30 06:46:01 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Google - 内推 - 其他 |Otherfresh grad应届毕业生

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

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

x
看了很久一亩三分地,今天回馈一下地里。上午校园面试的谷歌,一共两轮,每轮45分钟,没有onsite。都是在纸上写代码。
第一个人问的问题是给一个二维矩阵,里面有一些墙,一个起点,一个终点,每次行走类似于滑冰,如果没有墙,则可以走到底,问最短路径怎么做。我用bfs做的,之后follow up让你返回起始究竟是选择的哪个路径。第一个人面试的时候没面试好,前一天没睡好,头一直疼。。。。写代码的时候那哥们也不怎么听也不怎么看,可能是刚开始我回答的不太好,估计跪在这里了。。。
第二个人先让我说一个我遇见的bug,然后写题,题目也是一个二维矩阵,里面存着各种符号,如果横着或者竖着连续出现三个及三个以上重复的就返回false。我就brute force做的。。。。。不过小哥很nice,沟通不错,之后先让我说test case,时间复杂度之类的,然后就是如果用多线程来做可以怎么优化,就是每个thread扫不同行。然后就随便聊了聊就完了。

评分

1

查看全部评分

zjh08177 发表于 2015-11-16 04:23:53 | 显示全部楼层
Augustus 发表于 2015-11-15 14:38. from: 1point3acres.com/bbs
楼主第一题看起来好像很难,想了半天没想出来,求解答。。。

用BFS就可以啦,遍历每个节点的时候用map保存起始节点到当前节点的路径,遍历到终点的时候返回就可以了。. 1point3acres.com/bbs
用一个class来定义每个节点
class node{
int x,y; //位置信息
vector<*node> //路径信息. From 1point 3acres bbs
}

补充内容 (2015-11-16 04:27):
用queue来做bfs, 想要优化的话改为用priority_queue做GBFS(greedy best first search) class里面再加一个变量表示当前节点到终点的直线距离,每次queue里弹出当前距终点最进的节点。
回复 支持 1 反对 0

使用道具 举报

不高兴 发表于 2015-10-30 06:52:53 | 显示全部楼层
峰兄nb,字数字数

补充内容 (2015-10-30 06:54):
哦,错了,田兄nb= =
回复 支持 反对

使用道具 举报

 楼主| bluefreedom 发表于 2015-10-30 06:54:29 | 显示全部楼层
不高兴 发表于 2015-10-30 06:52
峰兄nb,字数字数

认错人了
回复 支持 反对

使用道具 举报

 楼主| bluefreedom 发表于 2015-10-30 06:57:34 | 显示全部楼层
不高兴 发表于 2015-10-30 06:52
峰兄nb,字数字数

补充内容 (2015-10-30 06:54):

学长nb!!.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

JoeWest 发表于 2015-11-2 00:16:13 | 显示全部楼层
第二题不用brute force该怎么做呢?
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-11-15 14:38:56 | 显示全部楼层
楼主第一题看起来好像很难,想了半天没想出来,求解答。。。
回复 支持 反对

使用道具 举报

 楼主| bluefreedom 发表于 2015-11-16 02:06:12 | 显示全部楼层
Augustus 发表于 2015-11-15 14:38
楼主第一题看起来好像很难,想了半天没想出来,求解答。。。

第一题我也不太会,当时瞎写的
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 11:55:44 | 显示全部楼层
请问使用int[][] 表示矩阵,数字表示墙呢?还是有特殊符号?走到底是指到达m - 1, n - 1吗?还是到达边界?
回复 支持 反对

使用道具 举报

 楼主| bluefreedom 发表于 2015-12-9 02:45:26 | 显示全部楼层
bobzhang2004 发表于 2015-12-7 11:55
请问使用int[][] 表示矩阵,数字表示墙呢?还是有特殊符号?走到底是指到达m - 1, n - 1吗?还是到达边界?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
表示墙就是他让我自己设计的,我当时不太会,单独建了个矩阵,看自己设计了,我弄的不太好。走到的不是m-1,n-1,是有一个end点
回复 支持 反对

使用道具 举报

singku 发表于 2016-1-8 12:14:52 | 显示全部楼层
二维矩阵就是个图 有没有墙代表有没有路径,问题就变成了求单源最短路径,迪克斯特拉算法啊
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-5 11:26:05 | 显示全部楼层
请问最短路径指的是什么?如果一步滑动了很长也是算一步吗?还是算的是滑动的这个有多少个格子?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-5 11:26:44 | 显示全部楼层
zjh08177 发表于 2015-11-16 04:23
用BFS就可以啦,遍历每个节点的时候用map保存起始节点到当前节点的路径,遍历到终点的时候返回就可以了。 ...

BFS怎么控制它的停止呢?
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-5 14:58:42 | 显示全部楼层
第一题dp 也行吧?
回复 支持 反对

使用道具 举报

carthus 发表于 2016-2-6 00:01:02 | 显示全部楼层
bobzhang2004 发表于 2016-2-5 11:26
请问最短路径指的是什么?如果一步滑动了很长也是算一步吗?还是算的是滑动的这个有多少个格子?

同问这个问题,最短路径是数格子还是数步数
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 13:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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