一亩三分地论坛

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

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

google onsite 7/25

[复制链接] |试试Instant~ |关注本帖
playgames 发表于 2016-7-26 07:56:41 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Google - 猎头 - Onsite |Other在职跳槽

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

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

x
今天面的, 虽然没遇到什么老题。 面之前没怎么刷题,基本上看看本版面经warm up, 感觉收获颇多,算回馈本版。R1:  印度phd,  问题很有意思, 一个2-D 矩阵,每个位置可以放一个字符。 有个文本,文本中每个词之间一个空格。问可以容纳多少次文本.   Follow up:  优化时间复杂度。 要写简单的O(RC) 算法。对给出的follow up 方法和时间复杂度分析表示很满意。 虽然还不是最优,但已经非常接近。此题follow up本身就不容易。  
R2:很nice 的美国大叔。 题目很有意思,10个digit(0,9), 任意取4个可重复构成密码,  求一个字符串可以cover所有密码。 举个例子:  密码1234.  那么字符串必须 包含1234的子串。   1. 求字符串长度 上下界。Follow up: 得到一个string, 尽可能接近下界。 在他一步步引导下,写出code.  聊得不错。 R3. 印度做test的, 两道简单的题, 1. max stock value 变形,唯一区别是即便亏本,也必须买一次股票。  2. 投骨子(1-6), 给个value, 算所有组合数。  DP 解决, 让run test, 两道题都bug free
R4. 印度manager,  两道简单题。  1. 给个1-100,找array 中missing的number. 此题很简单,估计是中午太困了,没想到这么简单,汗。。。,一开始没给出最优解。提示后得到最优。。。。。 2. 给个sorted array 和一个元素, 求一个元素出现的次数。 一开始以为要算所有元素出现次数。 clarify 只要算某个元素,之后此人有点不耐烦。我和他说稍微改改binary search即可求出上下界。 此人不理解此方法,他只想到recursive,有点不耐烦. 结果写了代码,run test验证无误。表示之前没想到此方法。 最后祝good luck........
R5. 不知哪国人。此题代码量很大,idea的方向很容易想到,但是要完善不是太容易, 此题比较复杂,不容易描述。格式化profile output. data structure 稍微复杂点。和他解释半天,表示此idea works (期间有个问题没clarify, 有个case 没考虑到). 然后开始写code. (部分伪代码), 验证的时候而且出了一个bug, 没时间fix,不过不难fix. 自己感觉此题关键在于figure out 方法,code bug free也许不是那么重要(也许我错了)。 他表示我的方法work, 有个地方用recursive不是太efficient.  最后送我出来,祝good luck...

.鐣欏璁哄潧-涓浜-涓夊垎鍦
这是第二次google onsite. 第一次其实前4面面的很好,最后没拿到offer, 可能是由于最后research面, 由于和interviewer research方向不一样,他都快睡着了。。。。。  最后送我出来good luck.....。因为上次feedback 好, 所以直接跳过了phone interview.
最后总结, 无论有没offer, 都尽力了。 两次google interview 都碰到一些有意思的题目,也比较享受解决没有做过的题目。 每次交流的感觉还不错。 Let's see. . 鍥磋鎴戜滑@1point 3 acres


评分

5

查看全部评分

 楼主| playgames 发表于 2016-7-26 11:39:23 | 显示全部楼层
adrian_yang84 发表于 2016-7-26 11:00
感谢楼主。能麻烦再解释一下第二题的题意么?没看明白。。

举个例子
字符串 “123456” 能够cover 的密码 “1234”, “3456”, “2345”。 其实也已经把解法说出来了

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

awesomeG 发表于 2016-7-26 08:34:46 | 显示全部楼层
求问前两轮的题楼主是怎么做的。
回复 支持 反对

使用道具 举报

mingruiyrh 发表于 2016-7-26 08:40:59 | 显示全部楼层
请问第一题问可以容纳多少次文本是什么意思?可以详细解释一下吗?
回复 支持 反对

使用道具 举报

 楼主| playgames 发表于 2016-7-26 08:48:12 | 显示全部楼层
awesomeG 发表于 2016-7-26 08:34
求问前两轮的题楼主是怎么做的。

解释起来比较费劲,周末整理下我的做法
回复 支持 反对

使用道具 举报

 楼主| playgames 发表于 2016-7-26 08:50:22 | 显示全部楼层
mingruiyrh 发表于 2016-7-26 08:40
请问第一题问可以容纳多少次文本是什么意思?可以详细解释一下吗?

给个例子:  I am student.. 1point3acres.com/bbs
2-D array: R=5, C=9

那么
I am
student I
am
student
I
所以res = 2 (可以容纳两次)
回复 支持 反对

使用道具 举报

mdyuki1016 发表于 2016-7-26 09:04:21 | 显示全部楼层
playgames 发表于 2016-7-26 08:50
给个例子:  I am student.
2-D array: R=5, C=9

暴力做法应该不难. 估计难点是 follow up
回复 支持 反对

使用道具 举报

wugoat 发表于 2016-7-26 09:04:32 | 显示全部楼层
Good luck. 最后一题能具体点?
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-26 11:00:04 | 显示全部楼层
感谢楼主。能麻烦再解释一下第二题的题意么?没看明白。。
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-26 13:41:27 | 显示全部楼层
嗯,我知道这样解,但是我还是不清楚题干是什么。. 1point3acres.com/bbs
是让你生成0-9的四位全排列么?一共10*10*10*10=10000中情况,所以长度上限是10000*4位=40000
下限的话,不会少于10000 + 3吧?但这个下限应该是达不到的。
生成下限的话,是不是从2个数字的组合开始推导。然后是3个数字(22组合 + 3个数字都用上),一直递推到10个数字。
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-26 13:41:51 | 显示全部楼层
第一题是不是要找循环节?
回复 支持 反对

使用道具 举报

Fustang 发表于 2016-7-26 19:52:58 | 显示全部楼层
playgames 发表于 2016-7-26 11:39
举个例子
字符串 “123456” 能够cover 的密码 “1234”, “3456”, “2345”。 其实也已经把解法说出 ...

是不是给一个4位密码集合S,然后求一个最短字符串str使得S中的任意4位密码都是str的子串。。。
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-26 21:18:33 | 显示全部楼层
我来给印度人点个赞
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-26 21:39:28 | 显示全部楼层
第一个题的I am student 能打乱顺序么?
.1point3acres缃
第二题 先sort一下strings, 然后找strings[i]的后缀和string[i+1]的前缀的最长匹配?比如string[i] = "1234" string[i+1] = "3456" 所以 结果就是 12[34]56?

第三题 几个骰子?

回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-27 10:45:57 | 显示全部楼层
我觉得第一题i am student 顺序不能打乱。而且要考虑到一行能容纳一至多条文本与一行容纳不了完整的一条文本。我建了vector作为循环数组,存读一次完整的文本占的行数与这些行数能读多少条完整的文本。在用一个map,映射行首词的下标与vector中对应的下标。
回复 支持 反对

使用道具 举报

CescTom 发表于 2016-7-27 12:50:33 | 显示全部楼层
第一题我的做法是可以先循环遍历文本,遍历的过程中不断记录新一行起始单词的坐标,如果找到一个重复的起始坐标就证明找到了循环节。然后可以算出第一次循环开始之前需要占多少空间 & 包含了多少次文本 + 每个循环占的空间&文本次数 * 循环次数 + 最后一次未完成的循环之中文本次数。. 1point 3acres 璁哄潧
这个做法找循环节的worst case 是O(n^2),n是文本单词个数
计算文本次数的worst case是O(n)
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-28 13:42:17 | 显示全部楼层
playgames 发表于 2016-7-26 11:39.鐣欏璁哄潧-涓浜-涓夊垎鍦
举个例子
字符串 “123456” 能够cover 的密码 “1234”, “3456”, “2345”。 其实也已经把解法说出 ...


楼主能说说解法吗? thanks
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-28 13:51:50 | 显示全部楼层
CescTom 发表于 2016-7-27 12:50
第一题我的做法是可以先循环遍历文本,遍历的过程中不断记录新一行起始单词的坐标,如果找到一个重复的起始 ...


是不是用文本第一行的第一个word 的row ㄝcol index 来判断有没有重复? 如果有重复就知道文本绕了几次是这个meaning 吗? 这样的话找重复循环节的time complexity 怎么算出o (n^2)?
回复 支持 反对

使用道具 举报

yetangzhi 发表于 2016-7-30 11:32:19 | 显示全部楼层
第一题暴力做不就是O(RC)的嘛?还是我理解错了?
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-7-30 13:45:50 | 显示全部楼层
感谢分享。 关注下第一题的解法
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 21:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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