推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 10471|回复: 79
收起左侧

Google电面被虐成X

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
20分钟前结束的谷歌电话面试,发现自己真的不擅长让别人盯着敲代码,虽然这是我人生经历的第二次,各种思维短路,各种大脑空白,顺带一提自己的第一次面Bloomberg也是这样。唉,其实自己刷题实力不济才是根本原因吧。废话不多说了,上面经。
白人小哥,马丁,他的电话声音质量极差,挂断重打了一次,浪费了3,4分钟的样子。第二次接听后上来啥都不问,直接上题,(撒杯酒悼念我随风而去的两年工作项目经验),而且他以打字为主,似乎是懒得跟我废话:
我有一个输入字符,然后我有一个英文字典,说白了就是字符串数组,然后写一个function返回字典里拥有输入字符串里所有字母(非数字或者空格等符号,就是纯字母)的最短的那个字符串。举个例子:
输入字符串"SR 456 T",字符串数组里有"SORT",而且是最短的,那么就返回它。

我首先把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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
zuying 发表于 2015-2-26 04:34
36楼已经结案了, 大家不用吵了

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

使用道具 举报

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

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

对于输入字符串s:SR 456 T,直接处理为SRT;. 1point 3acres 璁哄潧
字典单词w:SORT。
判断 s.match("[" + new RegExp(w.split("").join(|)) + "]{" + s.length + "}", "i")。. 1point 3acres 璁哄潧

因为 "SRT" 是符合正则 /[S|O|R|T]{3}/i 的,亦即在给定word中搜索s的长度个字符匹配。如果能搜索到,就表明s中的所有字符都在word里出现了(无论顺序)。
找到所有的match,选一个最短的。
. From 1point 3acres bbs
对没正则的语言意义不大。。。
回复 支持 1 反对 1

使用道具 举报

小柯西 发表于 2015-7-16 07:22:53 | 显示全部楼层
我觉得这题的解法还是应该用min window。.1point3acres缃
Preprocess: scan the given string. Use a HashTable to store the characters we are looking for and the corresponding number of each character.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Set 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.. more info on 1point3acres.com

用一个var minLen存当前的min window宽度,e.g.当前包含所有所需characters的最短单词长度。再用一个var保存该word在dictionary中的index。-google 1point3acres
然后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
Minimum Window Substring
https://oj.leetcode.com/problems/minimum-window-substring/

谢谢了,果然还是自己准备的不充分,看来是千万不能觉得HARD的题目不会在电面中出现啊

补充内容 (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. 1point3acres.com/bbs
http://homepage.cs.uiowa.edu/~sr ... /code/TestTrie.java
回复 支持 1 反对 0

使用道具 举报

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

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

使用道具 举报

 楼主| silverwind 发表于 2015-2-24 06:14:39 | 显示全部楼层
Freetymekiyan 发表于 2015-2-24 05:33
自学吧,根据Google给出的面试范围自学基础知识是肯定要做的一件事。
.1point3acres缃
基础知识学了,看来学的还不够深……现在忽然发现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 | 显示全部楼层
我木有看懂这道题目,楼主可以再举个具体的例子麻?
输入到底是字符还是字符串哈? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
还有楼主的例子"SR 456 T",字符串数组里有"SORT"--可是"SR 456 T"里面没有o额~
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

 楼主| silverwind 发表于 2015-2-24 04:49:01 | 显示全部楼层
leyhzm 发表于 2015-2-24 04:42
我木有看懂这道题目,楼主可以再举个具体的例子麻?
输入到底是字符还是字符串哈?
还有楼主的例子"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
!!!!我实习电面第一轮也是他!! 也是同一个题目! 我的处女面啊。。。。 就是挂他手上了。。
. 鍥磋鎴戜滑@1point 3 acres
是不是也是全程无交流,惜字如金,一声不吭……最后你怎么答的这题
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| silverwind 发表于 2015-2-24 04:57:07 | 显示全部楼层
yangbin009 发表于 2015-2-24 04:49
会不会是考Trie? 把字典里所有词 遍历-toCharArray-sort-建Trie. Trie node里面一个需要一个list存原始单词 ...

我电面结束后有想到过这个,把字典里的词构建成一个Trie,然后返回深度最浅的那个path,但是让我用代码写,40分钟不到的时间里我恐怕也是要呵呵……
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

我先给乐暴力法。 他说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.鏈枃鍘熷垱鑷1point3acres璁哄潧
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:. From 1point 3acres bbs
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.
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-29 00:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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