一亩三分地论坛

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

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

Google 电面和 onsite

[复制链接] |试试Instant~ |关注本帖
ManitobaFarmer 发表于 2015-5-1 11:00:56 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite 在线笔试 |Failfresh grad应届毕业生

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

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

x
电面是 find range.
. more info on 1point3acres.com
onsite:
1. 白人,输入为缺了 n 个数的 Latin numbers 二维矩阵,要求把 n 个数填回去。我的解法为根据所在行和列各自缺的 number set 求 intersection,然后 backtracking,理论上复杂度为n!,但是实际不会这么复杂。 后来有个假设 intersection 有且仅有一个数 (这个假设是正确的),这样backtracking 的复杂度降为 n^2。按这个假设写好之后,他要求证明这个假设,时间到了没证出来。

2. 印度人,给 Read4K(byte[] buffer, int offset) ,实现 Read(byte[] buffer, int count)。先写了个特别丑陋的实现,他照过相之后问有没有 improvement。花几分钟之改进之后他没照相。

3. 白人, 压缩字符串。

4. 印度人,给一个 n*m 的房间,房间里存在各种可能的墙,房间的格子里已经放了 e 个器材,要求新放一个器材,放置位置距其它 e 个器材的距离最近。Breadth-first search.
. visit 1point3acres.com for more.. 鍥磋鎴戜滑@1point 3 acres
. 鍥磋鎴戜滑@1point 3 acres
没给 offer.

评分

2

查看全部评分

本帖被以下淘专辑推荐:

lxia 发表于 2015-5-2 15:23:48 | 显示全部楼层
为什么我觉得证明不出来。
比如
{1 2 x y
2 1 w z
3 4 1 2
4 3 2 1}
x y w z可以是4 3 3 4
也可以是3 4 4 3
它们就是对称的。
题目还有其他要求?
回复 支持 1 反对 0

使用道具 举报

houqingniao 发表于 2015-5-1 11:04:39 | 显示全部楼层
第一题啥意思啊
回复 支持 反对

使用道具 举报

 楼主| ManitobaFarmer 发表于 2015-5-1 11:08:39 | 显示全部楼层

刚刚搜了一下,这货叫 latin square,不叫 latin numbers ,但是面试的时候给我说是 latin numbers,真是日狗。latin square 的定义可以去维基百科上看。输入为一个缺了 n 个数的 n * n 的 latin square,要求把这 n 个数填回去。
回复 支持 反对

使用道具 举报

Mahalkita 发表于 2015-5-1 13:13:25 | 显示全部楼层
ManitobaFarmer 发表于 2015-5-1 11:08
刚刚搜了一下,这货叫 latin square,不叫 latin numbers ,但是面试的时候给我说是 latin numbers,真是 ...
. visit 1point3acres.com for more.
跟sudoku差不多吧
回复 支持 反对

使用道具 举报

 楼主| ManitobaFarmer 发表于 2015-5-2 00:25:58 | 显示全部楼层

有点相似,具体定义可以在 Wiki 上找到。. 鍥磋鎴戜滑@1point 3 acres

这道题只要能得到每个 intersection 有且仅有一个数这个结论,解法就特别简单,代码很短,复杂度也只有 n^2。如果没有这个假设,就只能用 backtracking,理论复杂度为高达 n!。
回复 支持 反对

使用道具 举报

Mahalkita 发表于 2015-5-2 04:34:26 | 显示全部楼层
ManitobaFarmer 发表于 2015-5-2 00:25
. Waral 鍗氬鏈夋洿澶氭枃绔,有点相似,具体定义可以在 Wiki 上找到。

这道题只要能得到每个 intersection 有且仅有一个数这个结论 ...

但是这个假设怎么得到呢 感觉不太好证明呀
回复 支持 反对

使用道具 举报

 楼主| ManitobaFarmer 发表于 2015-5-2 09:29:47 | 显示全部楼层
Mahalkita 发表于 2015-5-2 04:34
但是这个假设怎么得到呢 感觉不太好证明呀

不知道啊,我没证出来。
回复 支持 反对

使用道具 举报

 楼主| ManitobaFarmer 发表于 2015-5-2 11:06:22 | 显示全部楼层
更新一下,第二道题 Read4K 是 LeetCode 上的原题 Read N Characters Given Read4.
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-5-7 13:45:56 | 显示全部楼层
最后一题不是一个NP hard问题么?楼主是对每个可能的点做BFS么?中间的障碍怎么考虑呢?
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-5-7 13:55:59 | 显示全部楼层
难道要对e个器材,每个做bfs,存下到空间每点的距离,就要有e个m*n的矩阵,然后所有矩阵对应位置加起来再算空间最小值的点?
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-9-11 02:08:19 | 显示全部楼层
求问,第四题我的解法时间复杂度算下来要O(n^4), n 为矩阵的长边
大家有没有什么优化的方法 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谢了!
回复 支持 反对

使用道具 举报

allen6432 发表于 2015-9-11 14:17:01 | 显示全部楼层
最后一题是不是所有位置围成图形的中心呢?
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-11 16:52:08 | 显示全部楼层
allen6432 发表于 2015-9-11 14:17
最后一题是不是所有位置围成图形的中心呢?

主要是有墙 所以不是中心. Waral 鍗氬鏈夋洿澶氭枃绔,
我觉得应该是从器材出发做bfs,然后更新每个点的距离和,复杂度应该是e*m*n。
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-11 16:55:43 | 显示全部楼层
ManitobaFarmer 发表于 2015-5-2 00:25. from: 1point3acres.com/bbs
有点相似,具体定义可以在 Wiki 上找到。. 1point3acres.com/bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这道题只要能得到每个 intersection 有且仅有一个数这个结论 ...

请问intersection是什么意思?可以贴下简单版的code吗?
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-16 01:15:21 | 显示全部楼层
对呀,对每一个点做一次bfs求最短路径的话复杂度O(n^3)了啊

补充内容 (2015-9-16 01:15):
。。是O(n^4)
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-16 01:26:06 | 显示全部楼层
kelvinzhong 发表于 2015-9-16 01:15
对呀,对每一个点做一次bfs求最短路径的话复杂度O(n^3)了啊
. more info on 1point3acres.com
补充内容 (2015-9-16 01:15):

只需要对器材做BFS即可
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-16 01:27:41 | 显示全部楼层
wenqiang88 发表于 2015-9-16 01:26
只需要对器材做BFS即可

你的意思是对每一个存在的器材做一次bfs? 然后求每个点对这个点到器材的距离相加最短?
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-16 01:34:52 | 显示全部楼层
kelvinzhong 发表于 2015-9-16 01:27
你的意思是对每一个存在的器材做一次bfs? 然后求每个点对这个点到器材的距离相加最短?

我是这么想的,想不到更好的方法
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-16 01:41:13 | 显示全部楼层
wenqiang88 发表于 2015-9-16 01:34
我是这么想的,想不到更好的方法

你这个解法也是O(n^4)的e.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 10:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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