一亩三分地论坛

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

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

google 二面

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

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

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

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

x


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

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

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

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

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

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

希望对大家有帮助。



补充内容 (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,然后新建一个字典
。之后每次就倒着查找就好了的。
我的方法挺麻烦的,建了一个map<integer, map<String, integer>> -google 1point3acres
第一个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. from: 1point3acres.com/bbs
嗯 我也是这么想的

弱弱的问一下 倒着怎么用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表示成一维。
a的个数<=i1. from: 1point3acres.com/bbs
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.         def isMatch(self, c):
  6.                 for key in self.dic:. From 1point 3acres bbs
  7.                         if self.dic[key] == len(key):
  8.                                 self.dic[key] = 0
  9.                                 return True

  10.                         if key[self.dic[key]] == c:
  11.                                 self.dic[key] += 1
  12.                         else:
  13.                                 self.dic[key] = 0. more info on 1point3acres.com
  14.                 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):. 鍥磋鎴戜滑@1point 3 acres
  2.     def __init__(self, val=None):
  3.         self.children = {}
  4.         self.lable = val
  5.         self.final = False
    . From 1point 3acres bbs

  6. class streamMatcher(object):
  7.     def __init__(self, wordSet):
  8.         self.inputString = ''. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.         self.root = TrieNode()
  10.         for word in wordSet:
  11.             reversedWord = word[::-1]. 1point 3acres 璁哄潧
  12.             self.insert(reversedWord)

  13.     def insert(self, word):
  14.         currNode = self.root
  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. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  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:. more info on 1point3acres.com
  27.                 currNode = currNode.children[l]
  28.             if currNode.final:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.                 return True
  30.         return False
  31. . visit 1point3acres.com for more.
  32.     def isMatch(self, letter):-google 1point3acres
  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')
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 14:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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