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

挺有意思的一个题，感谢楼主分享

其实不用那个附加的array

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

zhehua 发表于 2017-11-16 14:46
应该是有同样的数吧？不然环长度只能是N长啊？

不一定呀，譬如初始index是3，然后index 3处存的是1，然后index 1处存的是3。这样就会在1和3之间来回跳。

打电话拒绝后再来一封邮件拒信，简直就是双重伤害啊有木有！！

我ms第一次hr电面也是 精心准备加上超常发挥。然后还是被拒，根本不知道自己哪里做得不好

liukrimhim 发表于 2017-11-17 01:51
不一定呀，譬如初始index是3，然后index 3处存的是1，然后index 1处存的是3。这样就会在1和3之间来回跳。

对奥， 没考虑到这种情况

多谢Lz 有个问题一开始说“题目中保证输入的array中没有重复元素”， 后来面试官又问“如果array里面都是同样的数怎么办”？所以有没有重复的数尼？多谢

lqxshane 发表于 2017-11-16 13:08
两周前参加onsite前的GG安排的coaching session 当时就讲了这道题。。。没想到是真题啊

能说说思路吗？多谢~~~

这题难道不是linkedlist找环？ slow = nums[slow] fast = nums[nums[fast]] slow fast相遇的时slow循环的次数就是环的长度  下一步找到环的入口位置  然后加减除余就解决了
也可以像面试官那样用hash set找环的长度  但是需要额外空间  

一个hashset记录访问过的index就行了, 楼主讲的都是不知所云

corner case: value为负数, value大于等于array size,  

楼主基础要提高啊