一亩三分地论坛

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

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

Google Intern Interview加open offer

[复制链接] |试试Instant~ |关注本帖
zhihaosun 发表于 2016-11-20 20:55:01 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 实习@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
两周前面的G家实习,两轮电面,前天收到hr消息,拿到open offer,可以guarantee internship,但还要和team host聊,由Google定项目。
第一轮,一个m*n的matrix , 从左上到左下有多少种走法。用dp
follow up 1 : 有一个点(x,y)必须要经过,有多少走法。然后优化内存,用rolling array.鏈枃鍘熷垱鑷1point3acres璁哄潧
follow up 2 : 有一个set的点都要经过,有多少走法。我说要用HashSet来快速找点,然后问Point class怎么做hashing,写了hashCode function

第二轮,先是两道特简单的字符串题,然后面试官说"Here comes the real question"
给一个字符串的abbreviation ,就是把一些连续的字符转成数字,比如apple -> a2l1 , 然后让写一个函数验证一个带数字缩写是不是另一个字符串的缩写。two pointer秒过
第二道是给一个排好序的字符串数组,有n个字符串,还有一个前缀prefix字符串,长为m,要求函数返回start index和end index,其中所有字符串都以prefix开始,先用binary search,达到m*log(n)复杂度,面试官挺满意,然后我又给了个Trie树预处理O(所有字符串长之和),之后每个prefix都可以有O(m)的查找。面试官挺高兴,又聊了聊java 8的新feature,保证lamda和stream api。

题挺简单的,代码都写完了,后来想起来个exception,面试官下线后趁还没把我踢出去给改了


补充内容 (2016-11-20 21:04):
另外求版主尽快删帖,我也不敢放太久.1point3acres缃

补充内容 (2016-11-20 21:35):
请版主看到尽快删帖!我怕被hr发现就挂了

补充内容 (2016-11-21 13:40):
不好意思,第一题没说清楚哈,matrix中每一步有要求,必须要向下走,同时水平方向上每次有(-1,0,1)三个选择

评分

3

查看全部评分

本帖被以下淘专辑推荐:

 楼主| zhihaosun 发表于 2016-11-20 21:26:45 | 显示全部楼层
hashCode直接 x << 16 + y就差不多了,面试官说可以
回复 支持 反对

使用道具 举报

hypsm 发表于 2016-11-20 23:55:41 | 显示全部楼层
楼主好强啊!厉害
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-21 05:21:22 | 显示全部楼层
不用删帖,hr看不懂中文的
回复 支持 反对

使用道具 举报

 楼主| zhihaosun 发表于 2016-11-21 11:02:19 | 显示全部楼层
wtcupup 发表于 2016-11-21 05:21
不用删帖,hr看不懂中文的

希望吧,不过听说有人被发现,撤销offer的
回复 支持 反对

使用道具 举报

笑眯眯的白云 发表于 2016-11-21 11:25:01 | 显示全部楼层
楼主是 本科生吗

补充内容 (2016-11-21 11:25):
真心好强
回复 支持 反对

使用道具 举报

 楼主| zhihaosun 发表于 2016-11-21 11:45:04 | 显示全部楼层
笑眯眯的白云 发表于 2016-11-21 11:25
楼主是 本科生吗
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2016-11-21 11:25):
-google 1point3acres
谢谢~现在大三。之前刷了很多题
回复 支持 反对

使用道具 举报

格格笑 发表于 2016-11-21 11:54:32 | 显示全部楼层
你确定是左上到左下? 不是到右下?
回复 支持 反对

使用道具 举报

 楼主| zhihaosun 发表于 2016-11-21 12:57:33 来自手机 | 显示全部楼层
格格笑 发表于 2016-11-21 11:54
你确定是左上到左下? 不是到右下?

嗯,每步必须向下,水平上可以向左右或不动三中选择
回复 支持 反对

使用道具 举报

qeroqero 发表于 2016-11-21 13:37:09 | 显示全部楼层
zhihaosun 发表于 2016-11-21 12:57
嗯,每步必须向下,水平上可以向左右或不动三中选择

dp是不能走回路的。如果水平上可以左右移,是没法dp的吧。比如[1,1]点既可以从[1,0]点到达,[1,0]点也可从[1,1]点到达,应该先算dp[1,0]还是dp[1,1]。
回复 支持 反对

使用道具 举报

 楼主| zhihaosun 发表于 2016-11-21 13:39:05 | 显示全部楼层
qeroqero 发表于 2016-11-21 13:37
dp是不能走回路的。如果水平上可以左右移,是没法dp的吧。比如[1,1]点既可以从[1,0]点到达,[1,0 ...

每一个点走法是上一行相应左右中三个点走法之和,就可以dp了,处始为左上点走法为1
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-22 11:58:38 | 显示全部楼层
楼主可不可以说下第一题的follow up 怎么做的?.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一个我是先从start 到 必须经过的点, 然后从这个点再到end, 不知道这样做对吗?  楼主怎么做的?

还有第二个follow up, 给一个set 的点,楼主怎么做的?
回复 支持 反对

使用道具 举报

 楼主| zhihaosun 发表于 2016-11-22 12:17:18 来自手机 | 显示全部楼层
zhan1612 发表于 2016-11-22 11:58. Waral 鍗氬鏈夋洿澶氭枃绔,
楼主可不可以说下第一题的follow up 怎么做的?
第一个我是先从start 到 必须经过的点, 然后从这个点再到 ...
. From 1point 3acres bbs
到每一行,看这一行有没有必须要经过的点,有的话只保留那个格的步数就可以了,其他都是0,没有就正常dp,有超过两个就直接return 0吧
回复 支持 反对

使用道具 举报

tinyrookie 发表于 2016-11-22 17:14:37 | 显示全部楼层
问下楼主那个trie树预处理,需要code实现吗?还是说就行了?
回复 支持 反对

使用道具 举报

 楼主| zhihaosun 发表于 2016-11-22 17:40:06 来自手机 | 显示全部楼层
tinyrookie 发表于 2016-11-22 17:14
问下楼主那个trie树预处理,需要code实现吗?还是说就行了?

时间不够了,说了说,画了一下示意图,怎么找start index和end index
回复 支持 反对

使用道具 举报

tinyrookie 发表于 2016-11-22 17:58:39 | 显示全部楼层
哦哦,示意图是在doc里画吗。。。我以为doc里只能打码的。。
回复 支持 反对

使用道具 举报

 楼主| zhihaosun 发表于 2016-11-22 19:35:23 | 显示全部楼层
tinyrookie 发表于 2016-11-22 17:58
哦哦,示意图是在doc里画吗。。。我以为doc里只能打码的。。

就是空格换行,画一下简单的Trie示意图,然后说一下怎么从prefix的最后一个Trie Node出发找start index和end index. start index一直向最左走,直到遇到第一个index , end index一直向最右到尽头
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 23:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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