Google店面面经－－始料未及地挂了

找朋友内推的new grad全职岗位。上星期一电面的。当时感觉非常良好，和面试官谈笑风生，对答如流。挂了电话都快高兴得跳了起来。结果刚刚接到HR电话，告诉我我挂了………………肝肠寸断…………

题目很简单：给一个N长度的array of int，保证所有int都是 0<= n <= N-1。 再告诉你一个初始index和一个总步数k。array中每一个位置上的值都告诉你下一步跳到哪个位置。需要你输出经过k步后，最后停在那个位置上的值。

我一上来的解法很brute force：就是while loop N次，一步步地跳，输出最后结果。

面试官问我会出现啥问题。我检查了一些常规可能出现的问题，譬如invalid输入，总步数为负数或0， infinite loop啥的，然后没检查出啥问题。最后面试官提醒我说：如果array里面都是同样的数怎么办？我回答说：我的solution也能跑，无非是在原地重复很多次呗。面试官说：如果我给的总步数很大，譬如两百万次，你这solution就不是很高效，你可不可以优化一下？（我觉得此处可能减分了，没有自己发现自己solution的问题

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

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

给你打电话问下准备的怎么样了，虽然知道这些都是公司定好的流程，但是心里依然感觉暖暖的。就冲这点也一定要进去！！明年再战！！


补充内容 (2017-11-16 09:04):
忘了说，题目中保证输入的array中没有重复元素

gameboyying 发表于 2017-12-29 05:25
我修改下我之前的评论
corner case 要加一个value为0,的情况
hashset改成hashmap

如果没有重复的数 任意一点都在环里 应该不需要考虑环的入口

其实不用那个附加的array

用hash map， key为值， value为一个从0往上不断增加的counter value
如果遇到重复的话，检查之前重复的那个counter value和当前的counter value之差就是环的周长了，之前的那个counter value就是进入环之前的那段长度了
楼主说的那些口误啊啥的都是小问题，主要还是算法本身效率不高的问题

lz 这个题的描述感觉面试官 说的是 在array中有重复元素的情况下做的啊，如果array中没有重复元素在的话， obit的长度就应该等于 hashset的周长啊，很明显面试官是让考虑有重复元素的情况，才要找环的入口。可lz的补充内容为啥说保证输入没有重复呢？

其实问题没那么复杂，估计面试官被弄晕了，没获取到想要的信息

lz以后可以假定面试官水平没你高，然后用普通的概念给他解释，沟通起来会更好

printboo 发表于 2017-11-16 09:37
lz以后可以假定面试官水平没你高，然后用普通的概念给他解释，沟通起来会更好

多谢提醒！主要是我介绍背景时提到过我本科是数学和CS双专业。联系到抽象代数也是为了显示我确实学过数学，而且能把各学科的知识联系起来。本来想impress一下面试官的，结果起了反效果。

楼主，这个题LC有类似题，LC原题是找最大环。题号565 Array Nesting，现已下架，你直接在problem里是搜不到的，可以在contest 34里找到

其实楼主说实话没什么太大的槽点，但是你要说最减分的地方，我觉得应该是HashSet的查询复杂度你第一次说成了O(n)，这个很基础，不应该有口误的。

richarddia 发表于 2017-11-16 11:31
楼主，这个题LC有类似题，LC原题是找最大环。题号565 Array Nesting，现已下架，你直接在problem里是搜不到 ...

好的，谢谢告知！

nwpx 发表于 2017-11-16 11:33
其实楼主说实话没什么太大的槽点，但是你要说最减分的地方，我觉得应该是HashSet的查询复杂度你第一次说成 ...

唉，都是命啊！太珍惜这次机会了，面试的时候其实紧张得浑身冷汗，还得强作轻松地样子和面试官谈笑风生

两周前参加onsite前的GG安排的coaching session 当时就讲了这道题。。。没想到是真题啊

应该是有同样的数吧？不然环长度只能是N长啊？