一亩三分地论坛

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

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

Google电面面经

[复制链接] |试试Instant~ |关注本帖
neomiracle 发表于 2014-4-9 23:44:57 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other

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

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

x
新出炉的G家面经,攒人品,求讨论。. 1point 3acres 璁哄潧

问题1: 假设有一个dictionary和一个字符的set,找到从该字符集中能组成的存在于dictionary中的最长的word。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
问题2: 给一个只包含0, 1, * 的String,将所有的* 替换成0 或者 1, 返回所有的可能行。For example, “00*1*0” => {“001100”, “001110”, “000110”, “000100”}.鐣欏璁哄潧-涓浜-涓夊垎鍦

. visit 1point3acres.com for more.
第一题我给出的idea是利用Trie Tree,然后DFS字符集,同时记录最长的word。问面试官可不可以,面试官小白说you tell me ==。听他的意思是有些overkill,过后想想如果字符集很大的话DFS时间复杂度太高,不知道有没有更好的办法。

. from: 1point3acres.com/bbs
第二题比较容易,解出后被指出有个小bug,修改完后似乎没有什么问题。

.鐣欏璁哄潧-涓浜-涓夊垎鍦
.鏈枃鍘熷垱鑷1point3acres璁哄潧
总体感觉题目不是很难,但是跟面试官沟通不好。也许是自己太紧张,以前面试感觉都是在跟面试官相互讨论,如果解法有问题也会给出一些提示,但是今天感觉都是我自己在说,在征求自己想法对不对的时候,对方也不说,所以现在心里十分没底,求bless,希望电面能过

评分

1

查看全部评分

本帖被以下淘专辑推荐:

readman 发表于 2014-4-9 23:50:01 | 显示全部楼层
第一个 我觉得也是trie, 字符集不是set么 直接不能找出来么?
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-4-10 00:12:16 | 显示全部楼层
有建立trie的时间复杂度为毛不直接遍历所有单词并且判断是否由set的字符集组成呢?
回复 支持 反对

使用道具 举报

 楼主| neomiracle 发表于 2014-4-10 00:28:37 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| neomiracle 发表于 2014-4-10 00:35:59 | 显示全部楼层
北美农民 发表于 2014-4-9 11:12
有建立trie的时间复杂度为毛不直接遍历所有单词并且判断是否由set的字符集组成呢?

对的,过后跟同学讨论,其实是可以这么做。但是建立trie的时间比遍历一遍多吗, 也跟Trie的实现方式有关吧
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-4-10 00:44:16 | 显示全部楼层
neomiracle 发表于 2014-4-9 11:35
对的,过后跟同学讨论,其实是可以这么做。但是建立trie的时间比遍历一遍多吗, 也跟Trie的实现方式有关吧

暴力方法就是n*l, l是平均单词长度。 你建立trie tree也得遍历和插入每个单词每个字符, 不是一样的么?
回复 支持 反对

使用道具 举报

 楼主| neomiracle 发表于 2014-4-10 00:56:19 | 显示全部楼层
北美农民 发表于 2014-4-9 11:44 . From 1point 3acres bbs
暴力方法就是n*l, l是平均单词长度。 你建立trie tree也得遍历和插入每个单词每个字符, 不是一样的么?

对的,建Trie的时间是nl。看来是要跪的节奏。。。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-4-10 00:58:04 | 显示全部楼层
neomiracle 发表于 2014-4-9 11:56 . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
对的,建Trie的时间是nl。看来是要跪的节奏。。。

做出来了应该不会, good luck
回复 支持 反对

使用道具 举报

老子ggyy 发表于 2015-3-31 13:09:40 | 显示全部楼层
你好,刚看到你关于YouTube的帖子,我刚刚收到他家的邮件让我setup电面,想请教一下:
.鏈枃鍘熷垱鑷1point3acres璁哄潧
一个是他家电面大致侧重那些东西?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

另外问一下全部的面试有多少环节呢?

多谢多谢啦!
回复 支持 反对

使用道具 举报

zdcx 发表于 2016-5-7 17:59:06 | 显示全部楼层
顶顶顶顶顶顶顶顶顶顶顶顶顶顶
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 23:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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