一亩三分地论坛

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

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

Google电面被虐成X

  [复制链接] |试试Instant~ |关注本帖
silverwind 发表于 2015-2-24 04:21:20 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Fail

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

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

x
20分钟前结束的谷歌电话面试,发现自己真的不擅长让别人盯着敲代码,虽然这是我人生经历的第二次,各种思维短路,各种大脑空白,顺带一提自己的第一次面Bloomberg也是这样。唉,其实自己刷题实力不济才是根本原因吧。废话不多说了,上面经。
白人小哥,马丁,他的电话声音质量极差,挂断重打了一次,浪费了3,4分钟的样子。第二次接听后上来啥都不问,直接上题,(撒杯酒悼念我随风而去的两年工作项目经验),而且他以打字为主,似乎是懒得跟我废话:
我有一个输入字符,然后我有一个英文字典,说白了就是字符串数组,然后写一个function返回字典里拥有输入字符串里所有字母(非数字或者空格等符号,就是纯字母)的最短的那个字符串。举个例子:
输入字符串"SR 456 T",字符串数组里有"SORT",而且是最短的,那么就返回它。.1point3acres缃
. 1point3acres.com/bbs
我首先把brute force的想法给他听了,他说哦好,然后我说我要想想改进算法,他说哦好,然后马丁同学全程鸦雀无声,我试图索要Hint,无果。在一段压抑的寂静和大脑空白之后,我发现时间不多了,我只能把brute force用代码实现了,当然我知道这明显不够但是至少比什么代码都没有要好一点……然后跟他提了一下算法复杂度,他还特意打在了google doc里囧,最后他问我有没有“quick” question,我说我没有,其实我已经郁闷的没有想法了,发现自己真没用啊,同志们对这道题有啥想法吗,讨论讨论(别鄙视我)

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2015-2-24 06:15):
忘了说了,字母可以是无序的,比如“SR 456 T”的话,字典里有“ARTS”也是可以的,所以我觉得Trie不可行

评分

3

查看全部评分

zhiyiting 发表于 2015-2-26 12:21:48 | 显示全部楼层
zuying 发表于 2015-2-26 04:34
36楼已经结案了, 大家不用吵了

用int表示单词不能处理重复字符串的问题
反例:
输入:“SS 12 RT”
字典:“SORT”,“SSORT”
应返回SSORT,实则返回SORT
回复 支持 2 反对 0

使用道具 举报

yarmyarch 发表于 2015-2-24 21:13:07 | 显示全部楼层
这题的确跟min window(最短摘要问题)没关系。

附一个用js正则的解决方案。O(N)时间,O(1)空间。

对于输入字符串s:SR 456 T,直接处理为SRT;. Waral 鍗氬鏈夋洿澶氭枃绔,
字典单词w:SORT。
判断 s.match("[" + new RegExp(w.split("").join(|)) + "]{" + s.length + "}", "i")。

因为 "SRT" 是符合正则 /[S|O|R|T]{3}/i 的,亦即在给定word中搜索s的长度个字符匹配。如果能搜索到,就表明s中的所有字符都在word里出现了(无论顺序)。
找到所有的match,选一个最短的。

对没正则的语言意义不大。。。
回复 支持 1 反对 1

使用道具 举报

小柯西 发表于 2015-7-16 07:22:53 | 显示全部楼层
我觉得这题的解法还是应该用min window。. From 1point 3acres bbs
Preprocess: scan the given string. Use a HashTable to store the characters we are looking for and the corresponding number of each character.
. 1point3acres.com/bbsSet a var count to represent the number of the characters we found so far in the current word. When count == len(letters in the given string), we find a valid window.

用一个var minLen存当前的min window宽度,e.g.当前包含所有所需characters的最短单词长度。再用一个var保存该word在dictionary中的index。
然后scan整个词典word by word。对每个word都用min window的方法来检测其是否包含所有characters。不同的地方在于,当找到一个valid window时,我们取的是len(word)而不是真实的window长度。然后更新minLen和index。
注意每处理完一个单词后都要reset count, hashtable.

Total time complexity is O(n). n表示的是sum(len(word) for word in dictionary).
Space complexity is O(m). m is the sum(len(alphabetic characters in the given string)).. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

对内存的optimization应该就是hashtable里的key用ord(charater),而不是直接存string. Cut the space by half.
回复 支持 0 反对 1

使用道具 举报

zuying 发表于 2015-2-26 04:34:00 | 显示全部楼层
36楼已经结案了, 大家不用吵了
回复 支持 0 反对 1

使用道具 举报

 楼主| silverwind 发表于 2015-2-24 06:28:23 | 显示全部楼层
Arthur2012 发表于 2015-2-24 06:24. 1point 3acres 璁哄潧
Minimum Window Substring
https://oj.leetcode.com/problems/minimum-window-substring/
. visit 1point3acres.com for more.
谢谢了,果然还是自己准备的不充分,看来是千万不能觉得HARD的题目不会在电面中出现啊. visit 1point3acres.com for more.

补充内容 (2015-2-24 06:46):
但还有个区别就是原题中是一长串字符,而这题里是字符串数组,我觉得还是有所区别的
回复 支持 1 反对 0

使用道具 举报

baifriend 发表于 2015-7-18 08:03:03 | 显示全部楼层
mk01 发表于 2015-2-25 01:17
想了半天发现可以把每个String表示成一个int,然后利用AND判断两个String里字符的交集,这样对已每个字典里 ...

单词很长呢?
用一个整数不会溢出吗?
回复 支持 1 反对 0

使用道具 举报

yangbin009 发表于 2015-2-24 06:11:25 | 显示全部楼层
silverwind 发表于 2015-2-24 04:57
我电面结束后有想到过这个,把字典里的词构建成一个Trie,然后返回深度最浅的那个path,但是让我用代码写 ...

可以参考一下这三个文件:
http://homepage.cs.uiowa.edu/~sriram/21/spring07/code/Trie.java
http://homepage.cs.uiowa.edu/~sriram/21/spring07/code/Node.java
http://homepage.cs.uiowa.edu/~sr ... /code/TestTrie.java
回复 支持 1 反对 0

使用道具 举报

CrossTheWall 发表于 2015-3-11 10:34:46 | 显示全部楼层
YY大帝 发表于 2015-2-25 05:41
可不可以把所有string都sort了,然后remove dup char,轮次比较,大概是O(n*m)

恐怕不行,对每个string排序, 这样的复杂度貌似比对每个单词找MinWindow还高
回复 支持 1 反对 0

使用道具 举报

 楼主| silverwind 发表于 2015-2-24 06:14:39 | 显示全部楼层
Freetymekiyan 发表于 2015-2-24 05:33. more info on 1point3acres.com
自学吧,根据Google给出的面试范围自学基础知识是肯定要做的一件事。

基础知识学了,看来学的还不够深……现在忽然发现Trie不可以,因为被包含在单词里的字母可以是无序的,比如“SR 456 T”的话,字典里有ARTS也是可以的
回复 支持 1 反对 0

使用道具 举报

yangbin009 发表于 2015-2-25 06:27:12 | 显示全部楼层
Trie思路不好。 能不能先对词典建TreeMap<Anagram, Word>(new Comparator(by word.length)), Anagram是排序后的Word。对输入filter&sort成一个新词,然后iterate treemap, 遇到第一个indexOf 不为-1的就输出?
回复 支持 1 反对 0

使用道具 举报

nathanwong 发表于 2015-2-24 04:25:50 | 显示全部楼层
不是你不行,是你没遇到原题。大家都这样。不要灰心啦。继续加油
回复 支持 反对

使用道具 举报

LawranceH 发表于 2015-2-24 04:42:12 | 显示全部楼层
!!!!我实习电面第一轮也是他!! 也是同一个题目! 我的处女面啊。。。。 就是挂他手上了。。
回复 支持 反对

使用道具 举报

leyhzm 发表于 2015-2-24 04:42:30 | 显示全部楼层
我木有看懂这道题目,楼主可以再举个具体的例子麻?
. 1point 3acres 璁哄潧输入到底是字符还是字符串哈?
还有楼主的例子"SR 456 T",字符串数组里有"SORT"--可是"SR 456 T"里面没有o额~

回复 支持 反对

使用道具 举报

 楼主| silverwind 发表于 2015-2-24 04:49:01 | 显示全部楼层
leyhzm 发表于 2015-2-24 04:42
我木有看懂这道题目,楼主可以再举个具体的例子麻?. 鍥磋鎴戜滑@1point 3 acres
输入到底是字符还是字符串哈?.鐣欏璁哄潧-涓浜-涓夊垎鍦
还有楼主的例子"SR 45 ...

只要包含这3个字母即可,然后返回需要最短的那个词
回复 支持 反对

使用道具 举报

yangbin009 发表于 2015-2-24 04:49:02 | 显示全部楼层
会不会是考Trie? 把字典里所有词 遍历-toCharArray-sort-建Trie. Trie node里面一个需要一个list存原始单词。但是这种思路太难了,电面他可能就是考brute force.

加油加油。
回复 支持 反对

使用道具 举报

 楼主| silverwind 发表于 2015-2-24 04:52:01 | 显示全部楼层
LawranceH 发表于 2015-2-24 04:42
!!!!我实习电面第一轮也是他!! 也是同一个题目! 我的处女面啊。。。。 就是挂他手上了。。

是不是也是全程无交流,惜字如金,一声不吭……最后你怎么答的这题
回复 支持 反对

使用道具 举报

Freetymekiyan 发表于 2015-2-24 04:53:42 | 显示全部楼层
Google电面太喜欢考Trie了,我前段时间第一轮电面也被问到。
没关系,有可能有第二次电面机会,楼主请继续加油好好准备!
回复 支持 反对

使用道具 举报

 楼主| silverwind 发表于 2015-2-24 04:57:07 | 显示全部楼层
yangbin009 发表于 2015-2-24 04:49
会不会是考Trie? 把字典里所有词 遍历-toCharArray-sort-建Trie. Trie node里面一个需要一个list存原始单词 ...
-google 1point3acres
我电面结束后有想到过这个,把字典里的词构建成一个Trie,然后返回深度最浅的那个path,但是让我用代码写,40分钟不到的时间里我恐怕也是要呵呵……
回复 支持 反对

使用道具 举报

 楼主| silverwind 发表于 2015-2-24 04:59:42 | 显示全部楼层
Freetymekiyan 发表于 2015-2-24 04:53
Google电面太喜欢考Trie了,我前段时间第一轮电面也被问到。
没关系,有可能有第二次电面机会,楼主请继续 ...

他们是不是最近在用Trie做些什么吗……唉,我的工作和学术项目都没有用到过Trie,没有经验
回复 支持 反对

使用道具 举报

LawranceH 发表于 2015-2-24 05:01:53 | 显示全部楼层
silverwind 发表于 2015-2-24 04:52. more info on 1point3acres.com
是不是也是全程无交流,惜字如金,一声不吭……最后你怎么答的这题

我先给乐暴力法。 他说ok。 然后让我优化。 我稍微剪枝了下。 但他要我对字典优化。 我当时想不到啊。。。 要他给hint。 也不给。。
回复 支持 反对

使用道具 举报

Freetymekiyan 发表于 2015-2-24 05:33:57 | 显示全部楼层
silverwind 发表于 2015-2-23 15:59
他们是不是最近在用Trie做些什么吗……唉,我的工作和学术项目都没有用到过Trie,没有经验

自学吧,根据Google给出的面试范围自学基础知识是肯定要做的一件事。
回复 支持 反对

使用道具 举报

唯一 发表于 2015-2-24 05:43:28 | 显示全部楼层
这样做不知道可不可以。。为每一个字设一个int型。第一位为a,第二位为b,以此类推,如ab 就表示成 11 0*24个*0。。然后aaabbbb和ab的值完全一样 就可以抛弃了。。用一个map<int,int> 前面是字典字的值。后面是长度。。
空间复杂度O(2^26)。。
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2015-2-24 06:13:27 | 显示全部楼层
这个是leetcode原题?
https://oj.leetcode.com/problems/minimum-window-substring/
就是一个把输入字符串"SR 456 T"放入hashtable中计数,然后一对快慢指针找在字符串数组中最短的?
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2015-2-24 06:14:53 | 显示全部楼层
和原题唯一的区别是把输入字符串"SR 456 T"中非字母的部分忽略掉
回复 支持 反对

使用道具 举报

 楼主| silverwind 发表于 2015-2-24 06:20:58 | 显示全部楼层
Arthur2012 发表于 2015-2-24 06:14
和原题唯一的区别是把输入字符串"SR 456 T"中非字母的部分忽略掉

请问原题是啥,有链接吗?我很想知道解法
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2015-2-24 06:24:55 | 显示全部楼层
silverwind 发表于 2015-2-24 06:20 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
请问原题是啥,有链接吗?我很想知道解法
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Minimum Window Substring
https://oj.leetcode.com/problems/minimum-window-substring/

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
.鐣欏璁哄潧-涓浜-涓夊垎鍦
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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