Google Intern Interview加open offer

两周前面的G家实习，两轮电面，前天收到hr消息，拿到open offer，可以guarantee internship，但还要和team host聊，由Google定项目。
第一轮，一个m*n的matrix , 从左上到左下有多少种走法。用dp
follow up 1 : 有一个点(x,y)必须要经过，有多少走法。然后优化内存，用rolling array
follow up 2 : 有一个set的点都要经过，有多少走法。我说要用HashSet来快速找点，然后问Po

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

-20 21:35):
请版主看到尽快删帖！我怕被hr发现就挂了

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

tinyrookie 发表于 2016-11-22 17:58
哦哦，示意图是在doc里画吗。。。我以为doc里只能打码的。。

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

zhan1612 发表于 2016-11-22 11:58
楼主可不可以说下第一题的follow up 怎么做的？
第一个我是先从start 到 必须经过的点， 然后从这个点再到 ...

到每一行，看这一行有没有必须要经过的点，有的话只保留那个格的步数就可以了，其他都是0，没有就正常dp，有超过两个就直接return 0吧

zhihaosun 发表于 2016-11-21 12:57
嗯，每步必须向下，水平上可以向左右或不动三中选择

dp是不能走回路的。如果水平上可以左右移，是没法dp的吧。比如［1，1］点既可以从［1，0］点到达，［1，0］点也可从［1，1］点到达，应该先算dp［1，0］还是dp［1，1］。

hashCode直接 x << 16 + y就差不多了，面试官说可以

楼主好强啊！厉害

不用删帖，hr看不懂中文的

wtcupup 发表于 2016-11-21 05:21
不用删帖，hr看不懂中文的

希望吧，不过听说有人被发现，撤销offer的

楼主是 本科生吗

补充内容 (2016-11-21 11:25):
真心好强

笑眯眯的白云 发表于 2016-11-21 11:25
楼主是 本科生吗

补充内容 (2016-11-21 11:25):

谢谢～现在大三。之前刷了很多题

你确定是左上到左下？ 不是到右下？

格格笑 发表于 2016-11-21 11:54
你确定是左上到左下？ 不是到右下？

嗯，每步必须向下，水平上可以向左右或不动三中选择