一亩三分地论坛

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

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

Google Intern 面经

[复制链接] |试试Instant~ |关注本帖
BaskWind 发表于 2016-1-5 05:05:20 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 实习@Google - 内推 - HR筛选 |Passfresh grad应届毕业生

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

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

x
12月中旬的面试,一个白人小哥和一个白人大叔。过了圣诞假期HR给邮件说进入host match阶段了。
. visit 1point3acres.com for more.
第一个面试题是Word Abbreviation,蛮常见的。
1. 把单词只保留首尾字母,中间的缩成长度,如word --- w2d。
2. 不仅首尾,所有的字母都可以缩写成长度,如word --- w1rd/w2d/w3/4/...,要求generate all possible abbreviations。
3. 给一个query单词,一个dictionary,找出query的缩写中长度最短的、并且和dictionary中每一个单词的缩写都不相同的那个。

第二个面试题也是跟string相关的。
1. 给一个pattern string,里面有数字有字母。再给一个dictionary,都是单词,要求从中找出cover所有pattern中字母的单词长度最短的单词。
2. 如何preprocess这个dictionary来加速这个查找的过程。

求RP!求Host Match!求收留!. From 1point 3acres bbs

评分

2

查看全部评分

本帖被以下淘专辑推荐:

xiaozhuxiaozhu 发表于 2016-1-15 07:12:06 | 显示全部楼层
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-1-5 06:17:49 | 显示全部楼层
第二题是用trie做吗
回复 支持 反对

使用道具 举报

 楼主| BaskWind 发表于 2016-1-5 07:04:45 | 显示全部楼层
wtcupup 发表于 2016-1-5 06:17
第二题是用trie做吗

我是用hashmap做的,每一个单词一个hashmap,然后记录每一个字母有没有出现过。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-5 07:36:34 | 显示全部楼层
给一个query单词,一个dictionary,找出query的缩写中长度最短的、并且和dictionary中每一个单词的缩写都不相同的那个. more info on 1point3acres.com
什么意思?
回复 支持 反对

使用道具 举报

 楼主| BaskWind 发表于 2016-1-5 09:28:59 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-5 07:36
给一个query单词,一个dictionary,找出query的缩写中长度最短的、并且和dictionary中每一个单词的缩写都不 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
就是dictionary有很多单词,然后每一个单词都会有很多缩写,比如dictionary={cat,world}, dictAbbreviation={c2,c1t,w3d,wor2,...}这样。然后query是一个单词,比如word,然后在这个word的所有缩写里面找一个长度最短的,并且不在dictAbbreviation中的缩写,比如这个例子就是“4”了。
回复 支持 反对

使用道具 举报

zjuzqh 发表于 2016-1-5 10:14:35 | 显示全部楼层
BaskWind 发表于 2016-1-5 07:04
我是用hashmap做的,每一个单词一个hashmap,然后记录每一个字母有没有出现过。

不知你的hashmap怎么做的。也可以对字符串转为Int进行hash(26个字符,26位就可以表示了,忽略数字)。预处理把词典里的单词都转为int数字,pattern字符串也转为Int数字。然后pattern整型数字依次与词典里的单词数字做&运算。结果要大于等于pattern数字,且取含1个数最小的即可。这里位运算不知可有更好解法

补充内容 (2016-1-5 10:18):
说错了,应该是做异或操作
. visit 1point3acres.com for more.
补充内容 (2016-1-5 10:20):
与操作结果大于等于pattern说明包含那些字母,异或操作后取含1最少的字母
回复 支持 反对

使用道具 举报

 楼主| BaskWind 发表于 2016-1-5 11:57:58 | 显示全部楼层
zjuzqh 发表于 2016-1-5 10:14
不知你的hashmap怎么做的。也可以对字符串转为Int进行hash(26个字符,26位就可以表示了,忽略数字)。预 ...

嗯,后来follow up的时候我就想到了用26位bitstring的方法,不过我是用的与操作,pattern & word == pattern就表明可以match,然后只用找Int数值比pattern大的word进行与操作就行
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-5 12:14:10 | 显示全部楼层
第1面第2题是leetcode原体吧。.鏈枃鍘熷垱鑷1point3acres璁哄潧
我当时看标准答案看了3个小时,才学会了backtracking...
回复 支持 反对

使用道具 举报

asura23 发表于 2016-1-5 15:38:38 | 显示全部楼层
第一题第二问我试了下直接写1~2^n也能做,反正合并的时候也要在前面多个n的复杂度

请问第一题第三问LZ是怎么做的?我想的是拿query对比字典中每一个元素得到一个最长的共同缩写,再把所有非空的共同缩写取交集。感觉码起来细节好复杂……
回复 支持 反对

使用道具 举报

 楼主| BaskWind 发表于 2016-1-5 16:11:05 | 显示全部楼层
asura23 发表于 2016-1-5 15:38
第一题第二问我试了下直接写1~2^n也能做,反正合并的时候也要在前面多个n的复杂度

请问第一题第三问LZ ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我是dictionary直接用缩写建Trie树,然后query的缩写由短到长排序一个一个查,第一个Trie中间查不到的缩写就是最短缩写了。不过这一问他没让我写代码,就问了一下复杂度。
回复 支持 反对

使用道具 举报

 楼主| BaskWind 发表于 2016-1-5 16:13:35 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-5 12:14
第1面第2题是leetcode原体吧。-google 1point3acres
我当时看标准答案看了3个小时,才学会了backtracking...

应该是的吧...我有同学说是原题
回复 支持 反对

使用道具 举报

哗啦啦 发表于 2016-1-10 11:55:36 | 显示全部楼层
请问第二题说pattern string里有数字有字母是什么意思?是第一题的follow up吗?还是里面的数字有另外的意思?
回复 支持 反对

使用道具 举报

singku 发表于 2016-1-12 02:20:49 | 显示全部楼层
zjuzqh 发表于 2016-1-5 10:14
不知你的hashmap怎么做的。也可以对字符串转为Int进行hash(26个字符,26位就可以表示了,忽略数字)。预 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
word转换的bit串在低位和高位都有可能比pattern的bit串多几个1
异或出来的结果并不一定比pattern大或者小。如果word和pattern的bit串完全一样 异或出来的结果是0
所以这个是没法判断的。

楼主的pattern &word == pattern 才能得出正确的结果。
回复 支持 反对

使用道具 举报

 楼主| BaskWind 发表于 2016-1-12 07:25:39 | 显示全部楼层
哗啦啦 发表于 2016-1-10 11:55
. From 1point 3acres bbs请问第二题说pattern string里有数字有字母是什么意思?是第一题的follow up吗?还是里面的数字有另外的意 ...

不是第一题的follow up。只是碰巧第二题也是这种string相关的。. From 1point 3acres bbs
有数字有字母的意思就是pattern = 3ba5ee4c这种由数字和字母组成的,数字也没有什么意义...其实我觉得按他的问法,直接忽略pattern中的数字就好了
回复 支持 反对

使用道具 举报

哗啦啦 发表于 2016-1-12 09:40:38 | 显示全部楼层
我对第二题的想法;
1. 用HashSet存储pattern中的字母。然后一个个比较dicitionary的单词,找出目标

2. 将dictionary中的单词都转换成HashSet的形式。
请问有人有更好的思路吗?
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-1-12 09:58:15 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-5 12:14
第1面第2题是leetcode原体吧。. visit 1point3acres.com for more.
我当时看标准答案看了3个小时,才学会了backtracking...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
是哪道原题啊?
回复 支持 反对

使用道具 举报

neverlandly 发表于 2016-1-13 07:20:33 | 显示全部楼层
BaskWind 发表于 2016-1-5 16:11
我是dictionary直接用缩写建Trie树,然后query的缩写由短到长排序一个一个查,第一个Trie中间查不到的缩 ...

为什么要用Trie来存dictionary的缩写呢? 每个query的缩写在Trie里面查找起来还要用O(K)的时间,不如直接用hashSet存所有dictionary的缩写,每个查找只用O(1)。 这道题感觉跟prefix没什么关系,不需要trie吧?
回复 支持 反对

使用道具 举报

neverlandly 发表于 2016-1-13 08:15:33 | 显示全部楼层
第二道题pattern有重复字母吗?比如pattern是aabc,那我dictionary的word只要有a,b,c这三个字母就算match了,还是要至少有2个a,1个b,1个c?
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-1-13 08:58:22 | 显示全部楼层
楼主求问第一题第二问的做法?
回复 支持 反对

使用道具 举报

 楼主| BaskWind 发表于 2016-1-15 07:04:12 | 显示全部楼层
neverlandly 发表于 2016-1-13 08:15. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二道题pattern有重复字母吗?比如pattern是aabc,那我dictionary的word只要有a,b,c这三个字母就算match了 ...
. 1point3acres.com/bbs
只要有abc就算match了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 02:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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