买新车如何让dealer直接竞价?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3553|回复: 17
收起左侧

google 二面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
tianshaobo47 发表于 2015-10-27 09:02:30 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x


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

今天上来一个听不出来哪里口音的小哥,像烙印但也不确定。。. 围观我们@1point 3 acres

就面了一道题。给了一个函数
Set<words> wordSet;
boolean isMatch(char c) {.留学论坛-一亩-三分地

}. From 1point 3acres bbs
. 一亩-三分-地,独家发布
然后这个函数会被重复的调用去匹配一个字符串的子字符串是否能组成在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 还是很悬。。
楼主之前准备了一周的面经,本以为面经准备的很充分,这次会面的很顺利,结果一道类似的都没有遇到,不开心. 1point 3acres 论坛
郁闷了一下午,晚上上来赶紧发面筋攒攒RP..

希望对大家有帮助。



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

评分

参与人数 1大米 +50 收起 理由
小K + 50

查看全部评分


上一篇:热乎乎的Palantir电面
下一篇:10/26 SnapChat 店面

本帖被以下淘专辑推荐:

我的人缘0
 楼主| tianshaobo47 发表于 2015-10-29 03:17:10 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
发面经大发真好用,拿到on site了!大家加油
回复 支持 2 反对 0

使用道具 举报

我的人缘0
 楼主| tianshaobo47 发表于 2015-10-29 03:15:09 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
宝贝忆彼岸 发表于 2015-10-29 02:41
请问lz的做法,我只能想出暴力解,就是把之前的subsets都存起来,然后进来一个新的char,就添加subsets然后 ...

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

使用道具 举报

我的人缘0
Ziyan 发表于 2015-10-27 09:38:53 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
LZ是用trie做的吗
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| tianshaobo47 发表于 2015-10-27 11:21:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Ziyan 发表于 2015-10-27 09:38
LZ是用trie做的吗

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

使用道具 举报

我的人缘0
bitware 发表于 2015-10-27 12:05:09 来自手机 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
tianshaobo47 发表于 2015-10-27 11:21
不是,用Map做的。。TRIE怎么做?

把单词倒着插入字典?
回复 支持 反对

使用道具 举报

我的人缘0
Ziyan 发表于 2015-10-27 12:21:46 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
bitware 发表于 2015-10-27 12:05
把单词倒着插入字典?

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

使用道具 举报

我的人缘0
say543 发表于 2015-10-27 13:50:55 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Ziyan 发表于 2015-10-27 12:21
嗯 我也是这么想的

弱弱的问一下 倒着怎么用tries 做呢?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
bitware 发表于 2015-10-27 14:31:55 来自手机 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
say543 发表于 2015-10-27 13:50
弱弱的问一下 倒着怎么用tries 做呢?

就是比方说有单词abc,就插入树cba,然后string每增加一个字母,就从这个字母往前比较
回复 支持 反对

使用道具 举报

我的人缘0
fatalme 发表于 2015-10-27 15:46:16 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
和上次的技巧一样,其实就是prefix sum,算了,这个太复杂。我说个简单粗暴的做法吧:建表。

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

使用道具 举报

我的人缘0
fatalme 发表于 2015-10-27 15:50:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
没看清题目trie+kmp就行了。sorry。
回复 支持 反对

使用道具 举报

我的人缘0
tangvictor 发表于 2015-10-28 08:44:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
贴个自己的代码,如有bug麻烦告诉我。
  1. class StreamMatch:
  2.         def __init__(self, wordSet):. visit 1point3acres for more.
  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:. 围观我们@1point 3 acres
  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
    . 1point 3acres 论坛
  14.                 return False
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
say543 发表于 2015-10-28 14:10:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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吗?
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
tangvictor 发表于 2015-10-29 03:28:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
tianshaobo47 发表于 2015-10-28 15:17
发面经大发真好用,拿到on site了!大家加油
. from: 1point3acres
恭喜恭喜!
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| tianshaobo47 发表于 2015-10-29 04:10:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

你也加油!
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
snklee 发表于 2015-10-29 10:19:52 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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(). visit 1point3acres for more.
  10.         for word in wordSet:.本文原创自1point3acres论坛
  11.             reversedWord = word[::-1]. 留学申请论坛-一亩三分地
  12.             self.insert(reversedWord)

  13.     def insert(self, word):. 1point 3acres 论坛
  14.         currNode = self.root-google 1point3acres
  15.         for l in word:
  16.             if l not in currNode.children:
  17.                 currNode.children[l] = TrieNode(l)
  18.             currNode = currNode.children[l]-google 1point3acres
  19.         currNode.final = True
    . Waral 博客有更多文章,

  20.     def hasSubstringOf(self, word):
  21.         currNode = self.root
  22.         for l in word:
  23.             if l not in currNode.children:
  24.                 return False
  25.             else:. Waral 博客有更多文章,
  26.                 currNode = currNode.children[l].留学论坛-一亩-三分地
  27.             if currNode.final:. 牛人云集,一亩三分地
  28.                 return True
  29.         return False-google 1point3acres
  30. . 围观我们@1point 3 acres
  31.     def isMatch(self, letter):
  32.         self.inputString = letter + self.inputString
  33.         return self.hasSubstringOf(self.inputString)-google 1point3acres


  34. matcher = streamMatcher(['ag', 'bcd', 'cde'])
  35. print matcher.isMatch('a')
  36. print matcher.isMatch('b')
  37. print matcher.isMatch('c'). From 1point 3acres bbs
  38. print matcher.isMatch('d')
  39. print matcher.isMatch('e')
  40. print matcher.isMatch('a')
  41. print matcher.isMatch('g') 来源一亩.三分地论坛.
复制代码
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-6-22 09:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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