一亩三分地论坛

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

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

Google Oncampus Interview

[复制链接] |试试Instant~ |关注本帖
xiaokai1205 发表于 2014-10-8 08:59:20 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Google - 内推 - 校园招聘会 |Fail

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

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

x
LZ今天面Google oncampus interview, 两轮back to back,各45分钟,然后可能因为lz比较水,觉得面的题都好难啊,然后估计就挂了,让lz先去哭会T。T
第一轮先扯扯淡,问为什么喜欢Google之类的,然后问了问实习的code review过程,然后看了他写的一段代码主要是求某个数字是不是素数之类的,要求code review,问代码有没啥问题,算法有啥改进没,巴拉巴拉扯了一堆。接着就出了一道题就是说google有很多文档是javascript格式,比如bar.js, foo.js, 里面各自定义自己的foo, bar, 可是bar.js文件运行需要foo.js作为requirement, 要求输出array类似于['foo.js','bar.js'],就是作为requirement的文件必须排在前面,原谅lz比较啰嗦,follow up的问题就是如果foo.js里面定义了foo1,foo2,..., bar.js里面只列出了foo2, 但是输出还是['foo.js','bar.js']要怎么办。
第二轮对lz简直就是个disaster,就是一个房间也就是二维矩阵里面有obstacle,已知有k个点,求房间中离这k个点距离之和最短的那个点。然后lz死活就只能想到recursion, 复杂度是o(n^k+1), 当时脑子就短路,死活想不到更优解法,忘了直接用bfs,经面试官提醒也没有写完代码,觉得实在太复杂了,求各位大神轻拍。。。
lz已经相继挂掉很多面试了,果然还是水平太次,发点面经攒攒rp,回去好好学习了

评分

6

查看全部评分

本帖被以下淘专辑推荐:

shinichish 发表于 2014-10-8 10:18:51 | 显示全部楼层
请问第二轮那题是从k个点出发bfs,k个hashmap互查吗?
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2014-10-8 10:54:41 | 显示全部楼层
你们哥大这么快就有google on campus了。。。。
回复 支持 反对

使用道具 举报

 楼主| xiaokai1205 发表于 2014-10-8 11:05:36 | 显示全部楼层
shinichish 发表于 2014-10-8 10:18
请问第二轮那题是从k个点出发bfs,k个hashmap互查吗?

对的,差不多,就用k个矩阵存下各个点分别到这k个点的距离然后相加就行了,就是要注意要保证每个点的距离都是最短的,经常要update一下
回复 支持 反对

使用道具 举报

 楼主| xiaokai1205 发表于 2014-10-8 11:06:44 | 显示全部楼层
kelvinzhong 发表于 2014-10-8 10:54
你们哥大这么快就有google on campus了。。。。

这么早对我就是妥妥跪的节奏,弱弱问句你认识我么。。。
回复 支持 反对

使用道具 举报

e6175423 发表于 2014-10-8 14:18:07 | 显示全部楼层
xiaokai1205 发表于 2014-10-8 11:05
对的,差不多,就用k个矩阵存下各个点分别到这k个点的距离然后相加就行了,就是要注意要保证每个点的距离 ...

你这样就是暴力求解了,应该不行吧。
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2014-10-8 14:40:47 | 显示全部楼层
xiaokai1205 发表于 2014-10-8 11:06
这么早对我就是妥妥跪的节奏,弱弱问句你认识我么。。。

我不认识你e...但我认识你的同学.... 我们UCLA11/3号才on campus interview
回复 支持 反对

使用道具 举报

上里巴人 发表于 2014-10-8 14:42:16 | 显示全部楼层
我朋友遇到的题目也很变态
回复 支持 反对

使用道具 举报

TonyJang 发表于 2014-10-8 22:33:00 | 显示全部楼层
google bar这么高啊,这题一道不会啊
回复 支持 反对

使用道具 举报

sj1456 发表于 2014-10-8 22:43:13 | 显示全部楼层
shinichish 发表于 2014-10-8 10:18
请问第二轮那题是从k个点出发bfs,k个hashmap互查吗?

是从每个点出发吧。。。
回复 支持 反对

使用道具 举报

sj1456 发表于 2014-10-8 22:43:22 | 显示全部楼层
shinichish 发表于 2014-10-8 10:18
请问第二轮那题是从k个点出发bfs,k个hashmap互查吗?

是从每个点出发吧。。。
回复 支持 反对

使用道具 举报

Interviwer 发表于 2014-10-9 00:14:36 | 显示全部楼层
这道题怎么定义距离啊?是只能走4个方向还是8个方向啊?要是4个方向,直接给k个点的x 坐标和y 坐标排个序不就成了?然后取中位x坐标和中位y坐标
回复 支持 反对

使用道具 举报

 楼主| xiaokai1205 发表于 2014-10-9 02:46:49 | 显示全部楼层
e6175423 发表于 2014-10-8 14:18. visit 1point3acres.com for more.
你这样就是暴力求解了,应该不行吧。

那你还能想到更简单的方法吗?这个已经比我自己想的简单多了
回复 支持 反对

使用道具 举报

 楼主| xiaokai1205 发表于 2014-10-9 02:47:08 | 显示全部楼层
kelvinzhong 发表于 2014-10-8 14:40. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我不认识你e...但我认识你的同学.... 我们UCLA11/3号才on campus interview
.鐣欏璁哄潧-涓浜-涓夊垎鍦
爽啊,还有一个月时间准备呢
回复 支持 反对

使用道具 举报

 楼主| xiaokai1205 发表于 2014-10-9 02:47:46 | 显示全部楼层
上里巴人 发表于 2014-10-8 14:42
我朋友遇到的题目也很变态

我是运气不太好,我有同学就直接leetcode原题的
回复 支持 反对

使用道具 举报

 楼主| xiaokai1205 发表于 2014-10-9 04:25:05 | 显示全部楼层
Interviwer 发表于 2014-10-9 00:14
这道题怎么定义距离啊?是只能走4个方向还是8个方向啊?要是4个方向,直接给k个点的x 坐标和y 坐标排个序不 ...

四个方向,但是有obstacle啊
回复 支持 反对

使用道具 举报

 楼主| xiaokai1205 发表于 2014-10-9 04:25:32 | 显示全部楼层
sj1456 发表于 2014-10-8 22:43
是从每个点出发吧。。。

对,k个点的每个点
回复 支持 反对

使用道具 举报

littlecoolblaxk 发表于 2014-10-9 05:25:53 | 显示全部楼层
foo bar那道有点不太懂啊- -lz给个输入输出的接口好么 谢谢啦~~~~

是不是就是每个文件内有说明需要的pre-requisite  然后输出一个pre-requisite在前的string?输入是啥样的呀 需要自己解析每个文件的pre-requisite么?谢谢- -bless~~
回复 支持 反对

使用道具 举报

littlecoolblaxk 发表于 2014-10-9 05:39:28 | 显示全部楼层
再问下第二轮 我的暴力思路是这样的

for (point p : Points) { //这个就类似伪代码了 就是遍历整个matrix上所有的点 正常应该写两层循环 i , j 遍历. From 1point 3acres bbs
  double totalDistance = getTotal(p); // 单写一个函数求出当前点 到所有k个点得的距离的和
  min = Math.min(min, totalDistance);
}. more info on 1point3acres.com

但是复杂度就是O(矩阵长 * 矩阵宽 * k * 某点到k的距离的算法所需时间)。。。。至于障碍怎么绕还没想好。。A*或者dijxxxx那个算法还不太熟。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 05:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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