Google 电面（准备二面求人品）

听声音是个白人小哥，全程很nice，给了很多提示，优化上自己的表现很是不给力，但是最终还是给我了个二面的机会，求人品！

题目不难，是这样的：

Given:

int array of size k

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

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

"left">A_i = arr[A_i-1]

Find A_N.

感觉是这个意思，大概写了下

1. class Solution:
   
2.     def bruteForce(self, nums, N, a_init):
   
3.         # O(N)
   
4.         if not nums: return None
   
5.         A = a_init
   
6.         for i in range(N):
   
7.             A = nums[A]
   
8. 
   
9.         return A
   
10. 
    
11.     def countinuousFinding(self, nums, N, a_init):
    
12.         # O(k)
    
13.         if not nums: return None
    
14.         occuredIndex = {}
    
15.         A = a_init
    
16.         occuredIndex[A] = 1
    
17. 
    
18.         cycleStart = None
    
19.         for i in range(1, N+1):
    
20.             A = nums[A]
    
21.             if A in occuredIndex:
    
22.                 cycleStart = occuredIndex[A]
    
23.                 break
    
24.             else:
    
25.                 occuredIndex[A] = i + 1
    
26. 
    
27.         if not cycleStart:
    
28.             return A
    
29.         else:
    
30.             N = (N - cycleStart + 1) % (len(occuredIndex) - cycleStart + 1)
    
31. 
    
32.         A = a_init
    
33.         for i in range(cycleStart - 1 + N):
    
34.             A = nums[A]
    
35.         return A

复制代码

按我的理解写了一段可以跑通的代码 求指正！

1. public static int inferNthElement(int[] arr, int i, int n) {
   
2.                 List<Integer> items = new ArrayList<Integer>();
   
3.                 int cycle = 0;
   
4.                 int start = 0;
   
5.                 for(int j = 0; j <= n; j++) {
   
6.                         if(j == 0) items.add(arr[i]);
   
7.                         else if(!items.contains(arr[items.get(j - 1)])) {
   
8.                                 items.add(arr[items.get(j - 1)]);
   
9.                         }else {
   
10.                                 start = items.indexOf(arr[items.get(j - 1)]);
    
11.                                 cycle = j - start;
    
12.                         }
    
13.                 }
    
14.                 if(items.size() != n + 1) {
    
15.                         return items.get((n - start) % cycle + start);
    
16.                 }else {
    
17.                         return items.get(items.size() - 1);
    
18.                 }
    
19.         }

复制代码

python代码粘过来以供大家参考，多谢楼主分享。
第一个函数是k不大的时候，第二个是k可能很大的情况，考虑有环的解法。

1. def arrayIndex(A, N, k, init):
   
2.         a = init
   
3.         for i in range(1, N + 1):
   
4.                 a = A[a]
   
5. 
   
6.         return a
   
7. 
   
8. def indexCycle(A, N, k, init):
   
9.         cycle = []
   
10.         a = init
    
11.         i = 1
    
12.         while i <= N:
    
13.                 if a not in cycle:
    
14.                         cycle.append(a)
    
15.                         a = A[a]
    
16.                         i += 1
    
17.                 else:
    
18.                         break
    
19. 
    
20.         if i == N:
    
21.                 return a
    
22.         else:
    
23.                 return cycle[N % len(cycle)]

复制代码

LZ多久收到消息啊？

优化是考虑周期？

就一个题吗？

坐看云起 发表于 2015-10-6 07:00
优化是考虑周期？

对的的的

sc.77885 发表于 2015-10-6 06:59
LZ多久收到消息啊？

上周三面试，刚收到回复

wxr.dal 发表于 2015-10-6 07:08
就一个题吗？

嗯，就一个，表现不好，所以二面了

williamwjs 发表于 2015-10-6 07:09
嗯，就一个，表现不好，所以二面了

我也是即将二面，祝楼祝好运

坐看云起 发表于 2015-10-6 07:10
我也是即将二面，祝楼祝好运

同祝你好运！！！

看是简单， 楼主举个例子吧。