一亩三分地论坛

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

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

google onsite 2/29

[复制链接] |试试Instant~ |关注本帖
hzyslddm 发表于 2016-3-1 10:02:37 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 猎头 - Onsite |Otherfresh grad应届毕业生

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

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

x
1. 印度姐姐
给一组有向图的边的array,找A->B同时B->A,这样两个点之间直接有两条边相连,符合这样条件的边的条数。比如A->B,B->A,A->C那么边的条数就是2. 鍥磋鎴戜滑@1point 3 acres
LZ说用hashset解决,把to Node value + "#" + from Node value, 存进set里面,下次如果from node value + "#" + to node value已经在set中存在了,说明找到了一对,则边数+2
follow up是如果图很大,边很多,可以用多台machine,该怎么办。LZ说把边array分成几段,每段交给一个machine处理,得到的hashset和num数再merge。姐姐又问怎么才能更好的切分这个数组,如果直接分的话,每个machine返回的hashset会很大,并起来的时候还是很大。姐姐提示了好多LZ还是没想出来,最后姐姐说可以对每组边算个hashcode,然后像bucket sort那样分给一个相应的machine处理

2.白人哥哥
高频题,从一个string里面找出至多有k个不同字符的最长子串,用hashmap加两个pointer解决,follow up是如果string很长很长,而且只给一个iterator,每次调用给一个字符,怎么办?
解决方法是hashmap里面不存字符的occurance,而是存字符最后出现的位置。返回值是substring的start index和end index

3.印度哥哥
strobogrammatic number
先是给一个数判断一下是不是strobogrammatic number,写完之后的follow up是生成所有小于n的strobogrammatic number,其实并不难,但是感觉corner case有点多,LZ想着想着就有点糊涂了,最后也没写多少code, 印度哥哥都提醒说可以先写出来再考虑corner case了,LZ还是一直在纠结。怪自己学艺不精。
这轮面跪了,主要还是LZ心态不好,看到又是印度人就想爆炸,其实哥哥并没有黑我的说

4.国人哥哥+印度shadow. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
题目是给一个string,找出符合条件的substring pair个数,条件是两个substring只有一个字母不同
LZ用dp做的,A[i] 表示用index为0到i的字符能找到的pair个数,A[i] = A[i-1] + 第二个字符串以i结尾以j开头,第一个字符串以k结尾(0 < j < i,  i-j <=k < i)可能的匹配个数
算法时间复杂度是O(N^4),复杂度还是很高,哥哥想follow up的,结果没有时间了,sigh
国人哥哥人很好,一直在帮LZ整理思路,一直在给hint,走的时候还用中文跟我说“加油“和”好运啦“,可惜LZ反应太慢,才做了一题还没有时间follow up

-google 1point3acres
发帖攒RP,希望有加面TAT

. more info on 1point3acres.com

评分

3

查看全部评分

dietpepsi 发表于 2016-5-31 08:55:49 | 显示全部楼层
第四题如果题意有且只有一个不同的意思是A中的一个字母被原位替换的话变成B,这题是可以做到O(n^2)的
一个O(n^3)的解法是这样:

1. 找到s != s[j]的pair (i < j)
2. 我们将s和s[j]视作A和B中那个不同字母,从i和j分别向左右扩展,例如s[i-1]==s[j-1]就可以向左扩展
3. 最后我们可以找到以i,j为不同的长pair,[i-x, i+y] 和[j-x, j+y],将总数增加 ans += y + x + 1;
4. return ans. 1point3acres.com/bbs

这个方法可以进一步优化为O(n^2)

补充内容 (2016-5-31 08:57):. 1point3acres.com/bbs
错了,应该是,ans += (y + 1) * (x + 1);
乘法原理

补充内容 (2016-5-31 08:59):
打不出来[~i~]前面那些s后面都有个i
回复 支持 5 反对 0

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-3 03:59:17 | 显示全部楼层
csgtc 发表于 2016-3-2 15:14
如果是任意character也是256*n^3,比n^4好啊。。

只是纠正一下不能做那个字符都是字母的assumption,不是说你的算法不行。。另外,用hashset可能会漏算,比如aab这样的字符串,"a"和"b"这样的pair有两组,感觉要改用hashmap
回复 支持 1 反对 0

使用道具 举报

googlerr 发表于 2016-3-1 10:19:49 | 显示全部楼层
第2题最近似乎经常出现啊
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-3-1 11:25:27 | 显示全部楼层
第二题 尼玛就是google 超高频
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-3-1 12:19:31 | 显示全部楼层
题都挺难的。请教第一题hashcode 怎么取才能保证对应边会分到一个bucket?
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-3-1 12:20:46 | 显示全部楼层
第四题也挺难的
不知道有什么好解法没有?
回复 支持 反对

使用道具 举报

panlong222 发表于 2016-3-1 12:38:01 | 显示全部楼层
楼主进hc了吗?
回复 支持 反对

使用道具 举报

panlong222 发表于 2016-3-1 13:04:22 | 显示全部楼层

楼主的题比我的难一个档次。。。
回复 支持 反对

使用道具 举报

panlong222 发表于 2016-3-1 13:11:04 | 显示全部楼层
第四题 每对substring pair里的俩substring允许overlap吗
回复 支持 反对

使用道具 举报

Czon 发表于 2016-3-2 01:26:36 | 显示全部楼层
楼主麻烦问一下第二题存了index以后怎么处理
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-2 01:44:00 | 显示全部楼层
panlong222 发表于 2016-3-1 13:11 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第四题 每对substring pair里的俩substring允许overlap吗

允许overlap,一开始LZ写的是没overlap的,后来被中国哥哥提醒了下
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-2 01:45:15 | 显示全部楼层
kinggarden2001 发表于 2016-3-1 12:19
题都挺难的。请教第一题hashcode 怎么取才能保证对应边会分到一个bucket?

就是这个讨论了半天,我提出的几种方案都不是特别好,姐姐不满意,最后也没说该怎么做比较好
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-2 01:48:17 | 显示全部楼层
楼主可以解释下A->B,B->A,A->C那么边的条数就是2,是怎么找到的吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-2 01:49:10 | 显示全部楼层
第四题有更好的方法吗?
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-3-2 01:49:28 | 显示全部楼层
哪位能指点一下第四题?我觉得楼主的解法已经很好了!
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-2 01:49:56 | 显示全部楼层
bobzhang2004 发表于 2016-3-2 01:48
楼主可以解释下A->B,B->A,A->C那么边的条数就是2,是怎么找到的吗?

A和B两个节点,有直接A到B的边,也有直接B到A的边,这两条边算是满足条件的边,所以边数是2
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-2 01:51:05 | 显示全部楼层
bobzhang2004 发表于 2016-3-2 01:49.鐣欏璁哄潧-涓浜-涓夊垎鍦
第四题有更好的方法吗?

不知道了,哥哥刚想follow up时间就到了,房间被后面来的人定了,又跟了一个印度shadow,哥哥也不能多说什么
回复 支持 反对

使用道具 举报

echo33 发表于 2016-3-2 01:58:45 | 显示全部楼层
第四题写code了吗?复杂度好高啊
first thought是给一个hash table记录每个字符出现过的位置. visit 1point3acres.com for more.
做dp的时候对于s[i] for 2<=k<=i 找所有s[:i]里含有这个字符的长度为k的substring跟s[i+1-k:i+1]比较是否只差1个 应该不会很久,取决于是否有大量重复出现的字符
k=1的情况是character 只要不同的character都算一个pair吧?
回复 支持 反对

使用道具 举报

echo33 发表于 2016-3-2 02:00:26 | 显示全部楼层
我也想知道第四题有没有什么精妙解答 trick应该就在比较substring那里 是否可以通过rolling hash之类的大大减少计算?
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-2 02:18:43 | 显示全部楼层
echo33 发表于 2016-3-2 01:58
第四题写code了吗?复杂度好高啊
first thought是给一个hash table记录每个字符出现过的位置
做dp的时候 ...

code写完了,测的时候因为比较复杂就只测了一半,做的时候脑子一直不太清楚,还是国人哥哥一直在帮我整理思路
回复 支持 反对

使用道具 举报

panlong222 发表于 2016-3-2 07:02:46 | 显示全部楼层
“两个substring只有一个字母不同” 指的是 一定有一个字母不同 还是 最多有一个字母不同?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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