《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 3408|回复: 17
收起左侧

google 二面

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

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

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

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

x

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

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

就面了一道题。给了一个函数
Set<words> wordSet;
boolean isMatch(char c) {

}

然后这个函数会被重复的调用去匹配一个字符串的子字符串是否能组成在word set 中的单词。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
举个例子
input Stream: a,b,c,d,e,f,.鏈枃鍘熷垱鑷1point3acres璁哄潧
wordSet = [ag, bcd, cde]
每个字母输入时都会调用一下isMatch(char c) 这个函数
在这个例子中,当d输入时,因为bcd在set中,所以会返回true;

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

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

希望对大家有帮助。

.1point3acres缃

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| tianshaobo47 发表于 2015-10-29 03:17:10 | 显示全部楼层
发面经大发真好用,拿到on site了!大家加油
回复 支持 2 反对 0

使用道具 举报

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

我觉得楼上说的方法很简单,就是把字典的词语reverse,然后新建一个字典. more info on 1point3acres.com
。之后每次就倒着查找就好了的。
我的方法挺麻烦的,建了一个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
LZ是用trie做的吗
. Waral 鍗氬鏈夋洿澶氭枃绔,
不是,用Map做的。。TRIE怎么做?
回复 支持 反对

使用道具 举报

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

使用道具 举报

Ziyan 发表于 2015-10-27 12:21:46 | 显示全部楼层
bitware 发表于 2015-10-27 12:05. 1point 3acres 璁哄潧
把单词倒着插入字典?

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

使用道具 举报

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: 1point3acres.com/bbs
. visit 1point3acres.com for more.
一个26维的table,对这些word建表(int|boolean)[]...[] A[i1]...[i26]表示,或者bitset表示成一维。
a的个数<=i1
b的个数<=i2
.... 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
z的个数<=i26
的单词的个数,或者是否存在。-google 1point3acres
然后查表就行了。-google 1point3acres
回复 支持 反对

使用道具 举报

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. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.         def isMatch(self, c):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.                 for key in self.dic:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.                         if self.dic[key] == len(key):
  9.                                 self.dic[key] = 0
  10.                                 return True

  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 | 显示全部楼层

你也加油!
回复 支持 反对

使用道具 举报

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 = {}. from: 1point3acres.com/bbs
  4.         self.lable = val
  5.         self.final = False
  6. . from: 1point3acres.com/bbs
  7. class streamMatcher(object):
  8.     def __init__(self, wordSet):
  9.         self.inputString = ''
  10.         self.root = TrieNode()
  11.         for word in wordSet:. more info on 1point3acres.com
  12.             reversedWord = word[::-1]
  13.             self.insert(reversedWord)

  14.     def insert(self, word):
  15.         currNode = self.root. 1point3acres.com/bbs
  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. . 鍥磋鎴戜滑@1point 3 acres
  22.     def hasSubstringOf(self, word):
  23.         currNode = self.root. 1point 3acres 璁哄潧
  24.         for l in word:
  25.             if l not in currNode.children:
  26.                 return False
  27.             else:
  28.                 currNode = currNode.children[l]
  29.             if currNode.final:
  30.                 return True
  31.         return False

  32.     def isMatch(self, letter):
  33.         self.inputString = letter + self.inputString
  34.         return self.hasSubstringOf(self.inputString)


  35. matcher = streamMatcher(['ag', 'bcd', 'cde'])
  36. print matcher.isMatch('a')
  37. print matcher.isMatch('b')
  38. print matcher.isMatch('c')
  39. print matcher.isMatch('d')
  40. print matcher.isMatch('e')
  41. print matcher.isMatch('a') 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  42. print matcher.isMatch('g')
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-22 10:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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