一亩三分地论坛

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

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

Google Undergraduate Intern 电面面经,通知要加面

[复制链接] |试试Instant~ |关注本帖
jacky841102 发表于 2016-1-7 21:33:21 | 显示全部楼层 |阅读模式

2016(7-9月) 工程类 本科 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
昨天刚面的电面两轮,可能是本科实习,所以问题都不难

第一轮是国人大哥
给一个input string 和一个dictionary Set, 把input string的字元删除後判断是否在dictionary中,求出最长的满足条件的string
例如:input string = "appple"   dictionary = {"apple", "ape"} 返回 "apple"
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二轮感觉是native的妹子
第一题是判断string是否是palindrome, follow-up 是leetcode原题Longest Palindrome Substring

两轮都只有一个问题,写完後才过半小时就问我有没有问题要问。。。  
感觉跟面试官聊得都不错,结果HR通知要加面。。。 请问这是怎么回事?加面的难度是不是比较高?该怎么准备?

评分

2

查看全部评分

木易wen 发表于 2016-1-13 03:31:56 | 显示全部楼层
第一题用LCS就行了吧?把input和dict里面的每一个串匹配一下找到最长的,O(m*n*k)
回复 支持 2 反对 0

使用道具 举报

bobzhang2004 发表于 2016-1-25 13:03:52 | 显示全部楼层
木易wen 发表于 2016-1-13 03:31
第一题用LCS就行了吧?把input和dict里面的每一个串匹配一下找到最长的,O(m*n*k)

感觉这个应该是对的,这个题其实就是LCS的改写吧
回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 01:41:43 | 显示全部楼层
按照你的描述,你第一题并不简单。
如果可以随便删除char的次数和位置。
你第一要用backtracking把所有删除以后的结果保留,按照str length大到小排列。
比如adcdef,每次遍历每个char有2个情况,该char删除和保留。然后写个dfs。
然后为了优化,再写个trie,把所有dict种的字符加进去。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
最后才用trie的find function查找每一个删除的情况。。. from: 1point3acres.com/bbs
这题,没有个45分钟,写不完吧? 尤其是还要你implements trie的情况。  

补充内容 (2016-1-9 01:45):
我觉的这是hard难度的题,尤其你backtracking用stringbuilder还能加快速度
回复 支持 0 反对 1

使用道具 举报

 楼主| jacky841102 发表于 2016-1-9 00:39:57 | 显示全部楼层
怎么都没人回
我第一轮用的是暴力法,复杂度是O(2^n),不知道可不可以优化,面试官就直接让我写code了,是不是这有问题?
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-9 01:09:31 | 显示全部楼层
第一题用 trie做 ? 同问什么是字元?
回复 支持 反对

使用道具 举报

g56422 发表于 2016-1-9 01:10:08 | 显示全部楼层
第一題可以用dfs或bfs做
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-1-9 01:20:55 | 显示全部楼层
字元就是字母。。。alphabet呗
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-1-9 01:22:12 | 显示全部楼层
wtcupup 发表于 2016-1-9 01:09
第一题用 trie做 ? 同问什么是字元?

我有想过用trie,但是似乎与共同前缀没什么关联
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-9 01:29:01 | 显示全部楼层
jacky841102 发表于 2016-1-9 01:22. From 1point 3acres bbs
我有想过用trie,但是似乎与共同前缀没什么关联

比如说appple,删除一个char就是apple,然后apple在dict里,所以return true ?对于一个input string ,最多能删几个char ?
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-1-9 01:31:20 | 显示全部楼层
wtcupup 发表于 2016-1-9 01:29
比如说appple,删除一个char就是apple,然后apple在dict里,所以return true ?对于一个input string ,最 ...
.1point3acres缃
对的,可以删除多个char,如果全部删完都没有出现在dict中就返回空字串
删除的char可以在input string的任何位置
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-9 01:34:55 | 显示全部楼层
jacky841102 发表于 2016-1-9 01:31
对的,可以删除多个char,如果全部删完都没有出现在dict中就返回空字串. 1point3acres.com/bbs
删除的char可以在input string的 ...

楼主,请问是这道题目吗? http://www.careercup.com/question?id=5732809947742208
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-1-9 01:41:03 | 显示全部楼层
wtcupup 发表于 2016-1-9 01:34 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼主,请问是这道题目吗? http://www.careercup.com/question?id=5732809947742208

不一样. more info on 1point3acres.com
我遇到的是要保持input string中char的次序
appple可以变成apple, ape, aple... 但是不能变成alpe
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-1-9 01:45:40 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-9 01:41
按照你的描述,你第一题并不简单。
如果可以随便删除char的次数和位置。
你第一要用backtracking把所有删 ...

对的,大致上就是这样说的,我没有用到trie
我就提了个dfs遍历全部组合再sort,他就让我开始写了
後来我说可以不用sort,按照substring的长度搜索就好
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 01:49:20 | 显示全部楼层
jacky841102 发表于 2016-1-9 01:45
对的,大致上就是这样说的,我没有用到trie
我就提了个dfs遍历全部组合再sort,他就让我开始写了
後来 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
可能你是大神吧,让我做这题给最优解,我估计就挂了
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-9 01:54:29 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-9 01:41
按照你的描述,你第一题并不简单。
如果可以随便删除char的次数和位置。
你第一要用backtracking把所有删 ...
. From 1point 3acres bbs
请问怎么用backtracking 把所有删除后的结果保留啊?能否给个伪代码?
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-1-9 01:54:41 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-9 01:49
可能你是大神吧,让我做这题给最优解,我估计就挂了

给个本科申实习的叫大神也是。。。
我面完後有想到一些优化的地方
像是appple直接dfs会产生很多重复的substring如apple就会出现三次
或是input string = ababababab的情形也会产生重复的substring
去重的方法我不是很清楚
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-9 01:57:47 | 显示全部楼层
jacky841102 发表于 2016-1-9 01:54
给个本科申实习的叫大神也是。。。
我面完後有想到一些优化的地方
像是appple直接dfs会产生很 ...

放在hashet里面??
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-1-9 02:00:15 | 显示全部楼层

也是个办法,但是原本就是不想要额外的储存空间才说不用全部存起来再sort
不知有否办法在dfs时就避免产生重复的substring
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-9 02:50:38 | 显示全部楼层
jacky841102 发表于 2016-1-9 02:00.鏈枃鍘熷垱鑷1point3acres璁哄潧
也是个办法,但是原本就是不想要额外的储存空间才说不用全部存起来再sort
不知有否办法在dfs时就避免产 ...

我后来研究了一下发现这个generate 所有删除char后的possibilities类似于leetcode 上的subsets2, 那道题做法就是有办法删除duplicate的
回复 支持 反对

使用道具 举报

lotustree86 发表于 2016-1-9 03:35:46 | 显示全部楼层
用bfs,比dfs快一点。每一个level字符串长度减一;同一层里,依次删每一个字母,查看是否存在字典里,是就break,不是就放到set里,防止推入重复单词。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 22:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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