一亩三分地论坛

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

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

G家onsite

[复制链接] |试试Instant~ |关注本帖
Eclat 发表于 2016-8-20 00:30:02 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
一共四轮:
第一轮,一个泰国小哥,deep copy一个无向图成有向图,方向是从value小的node指向value大的
第二轮,一个中国姐姐,给两个字符串,找到第二个在第一个中第一次出现的位置(自己写string.indexOf这个函数吧),followup1,找一个字符串中period的字符段,followup2,找到period次数最少的,例如abababab,ab出现了4次,abab出现了2次,返回2
第三轮,美国大哥,给一个矩阵,每一块都被涂了颜色,找到给定点所在的那一块的颜色的边长
第四轮,中国小哥,edit distance变种,change的cost是2,delete和insert是1

评分

5

查看全部评分

本帖被以下淘专辑推荐:

 楼主| Eclat 发表于 2016-8-26 22:06:17 | 显示全部楼层
say543 发表于 2016-8-26 12:47
感觉是一个BFS 加上visited array 就搞定?

是的~~~~~~~~~~
回复 支持 0 反对 1

使用道具 举报

larry_cn 发表于 2016-8-21 07:46:33 | 显示全部楼层
frank11118 发表于 2016-8-21 06:40
求問二題二問解法

比如 “aaaaaaaaa” (9a) 对映的 failure function是 0, 0, 1, 2, 3, 4, 5, 6, 7, 8  (10个 第一个 默认为0)
然后 len - 8 = 1  就是 最小的 循环的 单位,9 / 1 = 9 可以 拆分成 3 * 3 所以 最后 应该是 3 个 ‘aaa’

比如 “abcabcabcabcabcabc” (6abc) 对映的 failure function 是 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, ..., 15
所以 len - 15 = 3 就是 最小 循环单位,18 / 3 = 6 = 2 * 3 额们 取3按 倍数乘3 所以是 2 * 9
就是 2个 abcabcabc
回复 支持 1 反对 0

使用道具 举报

mooc 发表于 2016-8-20 07:23:55 | 显示全部楼层
第二题需要kmp算法吗?
回复 支持 反对

使用道具 举报

1370786136.1.3 发表于 2016-8-20 07:34:16 | 显示全部楼层
第三题是number of islands 的变形吗?改成求岛的周长了?
回复 支持 反对

使用道具 举报

sitsit 发表于 2016-8-20 11:50:13 来自手机 | 显示全部楼层
第三题是max square的变种吗
回复 支持 反对

使用道具 举报

laoxie09 发表于 2016-8-20 12:03:29 | 显示全部楼层
1370786136.1.3 发表于 2016-8-20 07:34
第三题是number of islands 的变形吗?改成求岛的周长了?

dfs发现颜色不对直接加一
回复 支持 反对

使用道具 举报

taobingxue 发表于 2016-8-20 12:40:17 | 显示全部楼层
1. 暴力?
2. KMP ? KMP? size(string) - KMP最后一位的值是最小循环节 如果循环的话?
3. bfs ?
4. dp ?
回复 支持 反对

使用道具 举报

larry_cn 发表于 2016-8-20 14:56:58 | 显示全部楼层
taobingxue 发表于 2016-8-20 12:40
1. 暴力?
2. KMP ? KMP? size(string) - KMP最后一位的值是最小循环节 如果循环的话?
3. bfs ?

2题 2问 用 kmp的 点子 不错

补充内容 (2016-8-20 15:47):
要得到解 应该还得 求 小于 len / 最小循环长度 的 prime
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-8-21 07:41):
. 1point 3acres 璁哄潧上面 说的 prime 不对,, 应该是 看能不能 拆分成 除了 1 * 自己 以外的 两个数乘积 然后 取较大的

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

larry_cn 发表于 2016-8-20 15:00:07 | 显示全部楼层
第一题 也该就和 clone graph 一样吧
就是 判断一下 给不给 加边就 可以了

3 题 之前有过类似的 面经 块的边长是 4 所以 bfs  有相邻的 减掉
公共边
回复 支持 反对

使用道具 举报

frank11118 发表于 2016-8-21 06:40:35 | 显示全部楼层
larry_cn 发表于 2016-8-20 14:56
2题 2问 用 kmp的 点子 不错

补充内容 (2016-8-20 15:47):
-google 1point3acres
求問二題二問解法
回复 支持 反对

使用道具 举报

Josh 发表于 2016-8-21 23:29:37 | 显示全部楼层
求问楼主第二题是求substring中循环字段还是整个string就是个循环的然后求循环字段?
回复 支持 反对

使用道具 举报

sarah617 发表于 2016-8-22 08:23:02 | 显示全部楼层
laoxie09 发表于 2016-8-20 12:03
dfs发现颜色不对直接加一

什么意思
回复 支持 反对

使用道具 举报

frank11118 发表于 2016-8-22 12:11:06 | 显示全部楼层

意思是只要一個點擁有不同顏色的鄰居,代表該點在邊上
回复 支持 反对

使用道具 举报

 楼主| Eclat 发表于 2016-8-22 21:40:35 | 显示全部楼层
Josh 发表于 2016-8-21 23:29
求问楼主第二题是求substring中循环字段还是整个string就是个循环的然后求循环字段?
-google 1point3acres
先判断是不是循环字段,是的话再求~
回复 支持 反对

使用道具 举报

say543 发表于 2016-8-23 11:24:39 | 显示全部楼层
第三轮不太懂 楼主能在elaborate 一下吗? 第四轮 因该是dp 求最小cost?
回复 支持 反对

使用道具 举报

 楼主| Eclat 发表于 2016-8-24 01:46:26 | 显示全部楼层
say543 发表于 2016-8-23 11:24
第三轮不太懂 楼主能在elaborate 一下吗? 第四轮 因该是dp 求最小cost?

第三题,假如白色是1,红色是2,蓝色是3,给了一个矩阵,它里面所有数都是1,2,3,然后给一个点,跟它相连的相同颜色的色块的边长,如果它只有自己这一块,旁边颜色都不一样,那么边长就是4,如果左右或者上下有一块颜色一样的,那么边长就是6
第四题是dp
回复 支持 反对

使用道具 举报

南慕伦 发表于 2016-8-25 01:04:10 | 显示全部楼层
第三题应该就是数有多少不同颜色的邻居吧,在矩阵边上的也算不同颜色
回复 支持 反对

使用道具 举报

南慕伦 发表于 2016-8-25 01:06:32 | 显示全部楼层
南慕伦 发表于 2016-8-25 01:04
第三题应该就是数有多少不同颜色的邻居吧,在矩阵边上的也算不同颜色

FLOODFILL做就好。
回复 支持 反对

使用道具 举报

say543 发表于 2016-8-26 12:47:50 | 显示全部楼层
南慕伦 发表于 2016-8-25 01:06. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
FLOODFILL做就好。
. from: 1point3acres.com/bbs

感觉是一个BFS 加上visited array 就搞定?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 01:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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