May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

google 二面

[复制链接] |试试Instant~ |关注本帖
tianshaobo47 发表于 2015-10-27 09:02:30 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - Other - 技术电面 |Otherfresh grad应届毕业生

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

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

x


三周前就一面了,当时感觉答得一般,果然面试官也觉得我一般。。然后HR过了两周给我打电话说要二面,于是就约到了今天下午。
一面传送门在此: http://www.1point3acres.com/bbs/thread-143304-1-1.html

今天上来一个听不出来哪里口音的小哥,像烙印但也不确定。。

就面了一道题。给了一个函数
Set<words> wordSet;
boolean isMatch(char c) {. From 1point 3acres bbs

}

然后这个函数会被重复的调用去匹配一个字符串的子字符串是否能组成在word set 中的单词。
举个例子
input Stream: a,b,c,d,e,f,. 鍥磋鎴戜滑@1point 3 acres
wordSet = [ag, bcd, cde]
每个字母输入时都会调用一下isMatch(char c) 这个函数
在这个例子中,当d输入时,因为bcd在set中,所以会返回true;

当时光理解题意就花了我十分钟,然后第一遍写完还发现理解错题意了,以为必须从sream中的第一个开始匹配,别写还边想怎么这么简单。。。写完了小哥给我说我,从中间任意一个开始匹配就行。。
然后就又重新开始写。。。
最后到点,将将写完。。被小哥挑了两个bug..

这次面完感觉还是一般。。估计是没有三面了,所以感觉On site 还是很悬。。. 1point 3acres 璁哄潧
楼主之前准备了一周的面经,本以为面经准备的很充分,这次会面的很顺利,结果一道类似的都没有遇到,不开心. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
郁闷了一下午,晚上上来赶紧发面筋攒攒RP..

希望对大家有帮助。

. visit 1point3acres.com for more.

补充内容 (2015-10-29 03:18):
发面经大发真好用,拿到on site了!大家加油

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| tianshaobo47 发表于 2015-10-29 03:17:10 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
发面经大发真好用,拿到on site了!大家加油
回复 支持 2 反对 0

使用道具 举报

 楼主| tianshaobo47 发表于 2015-10-29 03:15:09 | 显示全部楼层
关注一亩三分地微博:
Warald
宝贝忆彼岸 发表于 2015-10-29 02:41
请问lz的做法,我只能想出暴力解,就是把之前的subsets都存起来,然后进来一个新的char,就添加subsets然后 ...

我觉得楼上说的方法很简单,就是把字典的词语reverse,然后新建一个字典
。之后每次就倒着查找就好了的。. 1point 3acres 璁哄潧
我的方法挺麻烦的,建了一个map<integer, map<String, integer>>
第一个integer是输入char的index, string 是满足的单词。第二个integer是匹配的长度。。
挺麻烦的。。
回复 支持 1 反对 0

使用道具 举报

Ziyan 发表于 2015-10-27 09:38:53 | 显示全部楼层
LZ是用trie做的吗
回复 支持 反对

使用道具 举报

 楼主| tianshaobo47 发表于 2015-10-27 11:21:12 | 显示全部楼层
Ziyan 发表于 2015-10-27 09:38. 1point 3acres 璁哄潧
LZ是用trie做的吗

不是,用Map做的。。TRIE怎么做?
回复 支持 反对

使用道具 举报

头像被屏蔽
bitware 发表于 2015-10-27 12:05:09 来自手机 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

Ziyan 发表于 2015-10-27 12:21:46 | 显示全部楼层
bitware 发表于 2015-10-27 12:05
把单词倒着插入字典?

嗯 我也是这么想的
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-27 13:50:55 | 显示全部楼层
Ziyan 发表于 2015-10-27 12:21
嗯 我也是这么想的

弱弱的问一下 倒着怎么用tries 做呢?
回复 支持 反对

使用道具 举报

头像被屏蔽
bitware 发表于 2015-10-27 14:31:55 来自手机 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

fatalme 发表于 2015-10-27 15:46:16 | 显示全部楼层
和上次的技巧一样,其实就是prefix sum,算了,这个太复杂。我说个简单粗暴的做法吧:建表。. From 1point 3acres bbs

.鐣欏璁哄潧-涓浜-涓夊垎鍦一个26维的table,对这些word建表(int|boolean)[]...[] A[i1]...[i26]表示,或者bitset表示成一维。
a的个数<=i1
b的个数<=i2
...
z的个数<=i26
的单词的个数,或者是否存在。
然后查表就行了。
回复 支持 反对

使用道具 举报

fatalme 发表于 2015-10-27 15:50:36 | 显示全部楼层
没看清题目trie+kmp就行了。sorry。
回复 支持 反对

使用道具 举报

tangvictor 发表于 2015-10-28 08:44:49 | 显示全部楼层
贴个自己的代码,如有bug麻烦告诉我。
  1. class StreamMatch:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  2.         def __init__(self, wordSet):
  3.                 self.dic = {word: 0 for word in wordSet}
  4.                 self.wordSet = wordSet

  5. . From 1point 3acres bbs
  6.         def isMatch(self, c):
  7.                 for key in self.dic:. From 1point 3acres bbs
  8.                         if self.dic[key] == len(key):
  9.                                 self.dic[key] = 0
  10.                                 return True-google 1point3acres

  11.                         if key[self.dic[key]] == c:
  12.                                 self.dic[key] += 1
  13.                         else:
  14.                                 self.dic[key] = 0
  15.                 return False
复制代码
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-28 14:10:40 | 显示全部楼层
bitware 发表于 2015-10-27 14:31
就是比方说有单词abc,就插入树cba,然后string每增加一个字母,就从这个字母往前比较

在问一  以tries 有order, 这边的input stream 如果是a,b,c 可以match word in dictinoary 像是bca, abc, bac..... 这样tries 还能用吗? 能给我个example吗?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-29 02:41:20 | 显示全部楼层
请问lz的做法,我只能想出暴力解,就是把之前的subsets都存起来,然后进来一个新的char,就添加subsets然后和词典中的单词比较,但是感觉空间和时间复杂度都很高,不知道有没有更加优化的解法,还有怎么样保存stream的char呢?
回复 支持 反对

使用道具 举报

tangvictor 发表于 2015-10-29 03:28:20 | 显示全部楼层
tianshaobo47 发表于 2015-10-28 15:17
发面经大发真好用,拿到on site了!大家加油

恭喜恭喜!
回复 支持 反对

使用道具 举报

 楼主| tianshaobo47 发表于 2015-10-29 04:10:45 | 显示全部楼层
. From 1point 3acres bbs
你也加油!
回复 支持 反对

使用道具 举报

lightmark 发表于 2015-10-29 04:49:17 | 显示全部楼层
我觉得应该用Trie + set<TrieNode*>
每进来一个c, 匹配set中TrieNode以及root的第c-'a'个Node。如果没有就删掉这个node,有的话要么找到了返回。要么更新node为第c-'a'个node。
回复 支持 反对

使用道具 举报

snklee 发表于 2015-10-29 10:19:52 | 显示全部楼层
reverse Trie solution
  1. class TrieNode(object):
  2.     def __init__(self, val=None):
  3.         self.children = {}.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4.         self.lable = val
  5.         self.final = False. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  6. class streamMatcher(object):
  7.     def __init__(self, wordSet):-google 1point3acres
  8.         self.inputString = ''.鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.         self.root = TrieNode()
  10.         for word in wordSet:
  11.             reversedWord = word[::-1].鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.             self.insert(reversedWord) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13. . 1point3acres.com/bbs
  14.     def insert(self, word):
  15.         currNode = self.root-google 1point3acres
  16.         for l in word:
  17.             if l not in currNode.children:
  18.                 currNode.children[l] = TrieNode(l)
  19.             currNode = currNode.children[l]
  20.         currNode.final = True

  21.     def hasSubstringOf(self, word):
  22.         currNode = self.root
  23.         for l in word:
  24.             if l not in currNode.children:
  25.                 return False
  26.             else:
  27.                 currNode = currNode.children[l]
  28.             if currNode.final:
  29.                 return True. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  30.         return False
  31. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  32.     def isMatch(self, letter):
  33.         self.inputString = letter + self.inputString
  34.         return self.hasSubstringOf(self.inputString)
  35. . more info on 1point3acres.com

  36. matcher = streamMatcher(['ag', 'bcd', 'cde'])
  37. print matcher.isMatch('a')
  38. print matcher.isMatch('b'). visit 1point3acres.com for more.
  39. print matcher.isMatch('c')
  40. print matcher.isMatch('d')
  41. print matcher.isMatch('e'). From 1point 3acres bbs
  42. print matcher.isMatch('a').鏈枃鍘熷垱鑷1point3acres璁哄潧
  43. print matcher.isMatch('g')
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-26 17:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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