10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 3360|回复: 17
收起左侧

google 二面

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

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

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

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

x
. more info on 1point3acres.com

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

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

就面了一道题。给了一个函数
Set<words> wordSet;
boolean isMatch(char c) {. visit 1point3acres.com for more.

}. 1point 3acres 璁哄潧

然后这个函数会被重复的调用去匹配一个字符串的子字符串是否能组成在word set 中的单词。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
举个例子
input Stream: a,b,c,d,e,f,
wordSet = [ag, bcd, cde]
每个字母输入时都会调用一下isMatch(char c) 这个函数
在这个例子中,当d输入时,因为bcd在set中,所以会返回true;

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

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

. 鍥磋鎴戜滑@1point 3 acres
补充内容 (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. visit 1point3acres.com for more.
请问lz的做法,我只能想出暴力解,就是把之前的subsets都存起来,然后进来一个新的char,就添加subsets然后 ...

我觉得楼上说的方法很简单,就是把字典的词语reverse,然后新建一个字典
。之后每次就倒着查找就好了的。
我的方法挺麻烦的,建了一个map<integer, map<String, integer>> . 1point 3acres 璁哄潧
第一个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做的吗

不是,用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,算了,这个太复杂。我说个简单粗暴的做法吧:建表。

一个26维的table,对这些word建表(int|boolean)[]...[] A[i1]...[i26]表示,或者bitset表示成一维。. more info on 1point3acres.com
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):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.                 self.dic = {word: 0 for word in wordSet}
  4.                 self.wordSet = wordSet

  5.         def isMatch(self, c):. From 1point 3acres bbs
  6.                 for key in self.dic:. 1point3acres.com/bbs
  7.                         if self.dic[key] == len(key):
  8.                                 self.dic[key] = 0-google 1point3acres
  9.                                 return True. 鍥磋鎴戜滑@1point 3 acres
  10. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  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 | 显示全部楼层
. visit 1point3acres.com for more.
你也加油!
回复 支持 反对

使用道具 举报

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 = {}
  4.         self.lable = val
  5.         self.final = False

  6. class streamMatcher(object):
  7.     def __init__(self, wordSet):
  8.         self.inputString = ''
  9.         self.root = TrieNode()
  10.         for word in wordSet:
  11.             reversedWord = word[::-1]
  12.             self.insert(reversedWord). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  13.     def insert(self, word):
  14.         currNode = self.root. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.         for l in word:
  16.             if l not in currNode.children:
  17.                 currNode.children[l] = TrieNode(l)
  18.             currNode = currNode.children[l]
  19.         currNode.final = True

  20.     def hasSubstringOf(self, word):
  21.         currNode = self.root
  22.         for l in word:. more info on 1point3acres.com
  23.             if l not in currNode.children:
  24.                 return False.鏈枃鍘熷垱鑷1point3acres璁哄潧
  25.             else:
  26.                 currNode = currNode.children[l]
  27.             if currNode.final:
  28.                 return True. from: 1point3acres.com/bbs
  29.         return False

  30.     def isMatch(self, letter):. from: 1point3acres.com/bbs
  31.         self.inputString = letter + self.inputString 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  32.         return self.hasSubstringOf(self.inputString)

  33. . Waral 鍗氬鏈夋洿澶氭枃绔,

  34. matcher = streamMatcher(['ag', 'bcd', 'cde']). 1point 3acres 璁哄潧
  35. print matcher.isMatch('a')
  36. print matcher.isMatch('b')
  37. print matcher.isMatch('c')
  38. print matcher.isMatch('d')
  39. print matcher.isMatch('e')
  40. print matcher.isMatch('a')
  41. print matcher.isMatch('g')
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 09:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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