弱渣的google电面

         一个小时前的电面，可能参考价值不大，大家随便看看好了：

         8月份参加的APAC，非常幸运的，第二天收到了google的简历投递邀请邮件。“梦想总是要有的，万一遇到鬼了呢”，抱着试一试的心态就投了简历，9月份收到了google hr的电话，上海的号码，可能是因为投简历的时候报的是上海的SE吧。电面安排到了9.22下午2.30，实际上由于前一次没有及时查收邮件，这个时间reschedule了一次。安排电面之前，hr在邮件中有让自己对一些基础的问题进行回答，关键是说明自己常用的语言，我写的C++。

         安排的是下午2.30，面试官电话打过来是2.35，北京的号，听声音，感觉和自己差不多岁数吧（感觉像90后），真心仰慕，能去google这种dream company的绝对都是精英中的精英。一上来先让自己做一下自我介绍，说实话提前没有准备自我介绍，只是在地里上看了很多google的面经，实际上电话打过来之前，心情一直是很激动的，因为从来没有想过能进，所以也不紧张会不会搞砸了什么的，只是觉得能得到dream company的面试已经很满足了。但事实是电话打过来之后，感觉自己说都不会话了，各种吞吞吐吐，紧张的不得了，唉。。。

         做完简单的自我介绍，面试官就说我们面试主要还是coding和算法，回答说好的，然后面试官就在google doc上写了题目，实际就是给一个数组，求最大的子数组和，leetcode和剑指offer上应该都有原题吧，也坦然的跟面试官说自己见过这个题，问他要不要换一个，他说不用，然后我说自己先里一下思路，就在doc上写了下DP的状态转移方程，他看了之后说没问题，就让我把代码写出来，开始码之前，也问了下是否要考虑溢出，面试官说不用，就很快写出了代码 + 注释。然后面试官说，行，这段代码没问题，我们再来看下一个问题。

         第二个问题就没见过了，最后听面试官的语气“你是没见过这类问题是吧”，可能也是有出处的题目吧，只是自己没有见到过，当然，还是自己太弱，临场想不出来。第二个问题是跟排列有关系的，说p[]存储了0~n-1这n个数，arr[][]是个二维数组，然后arr[0][]是已知的，且arr[0][]也存储了0~n-1这n个数，且arr[]中前一行和后一行有这样的关系：arr[k][i] = p[arr[k-1][i]]，然后给定p[]，arr[0][]，和K，求出二维矩阵的第K行，即arr[K][]。

         实际上面试官写output的时候写的是

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

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

iv>

int getPeriod(int T[], int p[], int seed, int n)

{

    int times= 0, next = seed;

    booloccured[n];

   memset(occured, false, n);//unorderer_set,

    do{

       occured[next] = true;//O(1) insert

        next= p[next];

       ++times;

   }while(next != seed);

    for(int i= 0; i < n; ++i){

       if(occured[i]) T[i] = times;//O(1) query

    }

    returntimes;

}

int getT(int T[], int p[], int seeds[], intn)//seeds[] = a[0][]

{

    memset(T,0, sizeof(int) * n);

    for(int i= 0; i < n; ++i){

       if(T[i] == 0) T[i] = getPeriod(T, p, i, n);

    }

}

//

         

补充内容 (2015-9-22 18:13):
4.40就接到电话了，是跪了的

gp89757 发表于 2015-9-22 21:04
面试官为什么第二题要这么表述。。好奇怪
permutation的循环周期应该等于所有置换群的长度的最小公倍数吧

求出总的循环周期并没有意义     还是得每一个去算   所以得求T[0~n]分开算吧

我把循环节存了一下，对a中有重复的无影响，p中有重复的表示会有影响，p中有重复的话，不能构成环了啊。。

我的C++代码，复杂度是O（N），假设p中无重复

1. vector<int> findKthVector(vector<int> &p, vector<int> &a, int k) {
   
2.     int n = p.size();
   
3.     unordered_map<int, pair<int, int> > cid;
   
4.     vector<vector<int> > cycle;
   
5.     vector<bool> visit(n, false);
   
6.     for (int i = 0; i < n; i++) {
   
7.         if (!visit[i]) {
   
8.             vector<int> c;
   
9.             c.resize(0);
   
10.             int pre = i;
    
11.             int t = i;
    
12.             do {
    
13.                 visit[t] = true;
    
14.                 cid[t] = make_pair(cycle.size(), c.size());
    
15.                 c.push_back(t);
    
16.                 t = p[t];
    
17.             } while (t != i);
    
18.             cycle.push_back(c);
    
19.         }
    
20.     }
    
21.     vector<int> ans;
    
22.     for (int i = 0; i < n; i++) {
    
23.         int t = a[i];
    
24.         int ci = cid[t].first;
    
25.         int pi = cid[t].second;
    
26.         int c_len = cycle[ci].size();
    
27.         int idx = (pi + c_len + k) % c_len;
    
28.         ans.push_back(cycle[ci][idx]);
    
29.     }
    
30.     for (auto e : ans)
    
31.         cout << e <<' ';
    
32.     return ans;
    
33. }

复制代码

int[] findKRow(int[][] a, int[] p, int k) {
        if (a == null || p == null || a.length == 0 || a[0].length != p.length || k < 0)
            return null;
        int n = p.length;
        if (n ==1)
            return p;
        int t = (n/2)*(n/2+1);
        k = k % t;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = p[a[i - 1][j]];
            }
        }
        return a[k];
    }

补充内容 (2015-9-23 05:31):
有错误，请忽略这个答案。。。。

补充内容 (2015-9-23 05:32):
有错误，请忽略这个答案。。。。

赞一下楼主，顺便提一下1->2->3->4->2->3->4这类循环之所以不可能，是因为如果存在这样的循环，那表示p[1]和p[4]都等于2，但是题中已经说明了p中是没有重复数字的，所以这种循环不可能出现。

顺便鄙视一下万恶的[i]标签。

stellari 发表于 2015-9-22 17:08
赞一下楼主，顺便提一下1->2->3->4->2->3->4这类循环之所以不可能，是因为如果存在这样的循环，那表示p[1] ...

感谢指点，感谢。自己还是太弱了，一下子就懵逼了，啥都想不出来

apac 是啥

中文面试？

面试官为什么第二题要这么表述。。好奇怪

面试官为什么第二题要这么表述。。好奇怪
permutation的循环周期应该等于所有置换群的长度的最小公倍数吧

从另一个帖子link到LZ这个帖子的，看到上面有人分析说1 -> 2 -> 3 -> 4 -> 2 -> 3 -> 4这样不对是因为没有重复的value，不过题目中没看到说这个限制条件，如果有的话，题目就简单一点，因为此时任何给定一个index，都会在某一条循环路径中，那么只需要找到一次循环，然后N % 一次循环数，再遍历一遍就好。如果允许重复的value，处理起来就稍微麻烦点，不过也是一样的思路。不知道理解的正确与否。