一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1537|回复: 13
收起左侧

弱渣的google电面

[复制链接] |试试Instant~ |关注本帖
uuuouou 发表于 2015-9-22 16:44:02 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - Other - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
         一个小时前的电面,可能参考价值不大,大家随便看看好了:
         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-1n个数,arr[][]是个二维数组,然后arr[0][]是已知的,且arr[0][]也存储了0~n-1n个数,且arr[]中前一行和后一行有这样的关系:arr[k] = p[arr[k-1]],然后给定p[]arr[0][],和K,求出二维矩阵的第K行,即arr[K][]
         实际上面试官写output的时候写的是arr[K],还以为要只求第K行第i个数呢,就说直接递推O(K)就可以了,然后被面试官纠正是求所有的arr[K],这才反应过来。说最简单暴力的想法是递推每一列,然后问了下是否对复杂度有要求,面试官说暴力递推的方法是O(nK)的,对于K > n*n的时候,有没有办法优化,就想着是不是有周期,然后嘀咕着想不出来周期的数学表达式,面试官说那有没有可能在程序中找出来这个周期。说如果能找到这个周期那用K%T就是要递推的步骤了,但转念一想,排列啊,会不会最坏的情况会遍历n!中排列,然后在doc上自己写了几种可能的变换情况。看我不说话了也不嘀咕了(弱爆了),面试官提示了一下,说可能是这样的,对于p = {1, 0, 3, 4, 2},会有这样的周期1 -> 0-> 1 -> 0, 3 -> 4 -> 2 -> 3 -> 4 -> 2
         在面试官的提醒下,似乎有了点明白,说我们需要找到每一列的T,然后对于第i列,我们只用递推到K%T,然后面试官问我会不会是这样子的循环呢:1 -> 2 -> 3 -> 4 -> 2 -> 3 -> 4 ,我说应该不会,虽然暂时想不出来为什么,但感觉1 -> 2 -> 3 -> 4是相互影响的,不会出现这种情况,然后面试官说,那写一下代码吧,怎样吧T[]求出来,然后就在继续在doc上码子,写完之后,面试官就指出了几个bug,修改了之后面试官说你觉得求T[]的复杂度是多少,以1 -> 2 -> 3 -> 4为例子说了一下,说对于长度为K的循环节,周期最多是K(这里也说错了,实际上应该就是等于K),getPeriod对一个循环节的复杂度是O(K)的,假设有M个循环节,则总的复杂度就是O(n)的,面试官说没问题,然后又指出我在getPeriod函数中用了memset,这会导致复杂度不是O(n)的,想了下就说可以修改成hashset,保存这个循环节中出现的所有数字,然后面试官说,嗯可以。
         接着面试官说,好了你现在有没有什么问题想要问我的,或者是关于公司的,感觉自己弱爆了,就问了下面试官,觉得自己的不足之处,面试官说第二题耗费的时间有点长,超出了我的预期,你是没见过这类问题是吧,我说是,那您的意思是我的头脑还是不够灵活是吧(已然心灰意冷),面试官然后安慰了一句,其实也还好啦,你还有别的问题吗,看了时间快到3点半了,就说没什么别的问题了(弱渣就不耽误google的大牛去改变世界的时间了),然后面试官说那好的,我们的hr会再跟你联系的,先这样了,然后说几声感谢就相互挂了电话。
         本来面试应该是总共45分钟的,但实际上第二个题感觉就有持续40分钟了,目测又是一轮游了,不过也满足了,算是长这么大和google的“最近”的一次接触。下面是doc上码的字,大家随便看看,红色加粗的地方的是面试官写的:
Please use this Google doc to code during yourinterview. To free your hands for coding, we recommend that you use a headsetor a phone with speaker option.
a_0, a_1, … ,a_{n-1}. s.
//f represents the maximum sum ending with a,then
//f = max{f[i-1] + a, a}
//the final result s, is the maximum sum endinganywhere, so
//s = max{f, 0 <= i < n}
int maxSubarraySum(int arr[], int n)
{
   assert(arr != NULL && n > 0);
   
    int s =arr[0]; //initialize final result with one possible candidate
    int f =arr[0]; //now f represents f[0]
    for(int i= 1; i < n; ++i){
        f =max(f + a, a); // figure out f
        s =max(s, f);           // update finalresult
    }
    return s;
}
2. 0 ~ n-1, p, a[0], a[k] = p[a[k-1]], find outa[K].
   input: K, p,a[0].
   output: a[K].
// p = {2, 0, 1}, a[0][] = {1, 0, 2}
// a[1][] = {p[arr[0][0]], p[arr[0][1]],p[arr[0][2]]} = {0, 2, 1}
// p = {1, 0, 3, 4, 2}
// 0 -> 1 -> 0, 2 -> 3 -> 4 -> 2.
// cycle T, K > T, K % T, K < T[j],
// T[0] = 0, 1, 2, 3. .. n-1, x
// T <= n
1 -> 2 -> 3 -> 4 -> 2 -> 3 -> 4 -> 2
// 0 ~ n-1, k different numbers as a set, the cyclefor these k numbers is k at most
// suppose there are M sets, then figure out T[] ism1 + m2 + … mM = n
// getT is O(n)
//arr[0][], p[], K, i
//f(int i, int j) => result = f(K, i)
//f(i, j) = p[f(i-1, j)], f(0, j) = arr[0][j]
//O(K) for each i, so O(nK)
(K > n*n)
//to figure out T, {x, y, z } iteratetill f(n, i) = x, T = n
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) T = 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 == 0) T = getPeriod(T, p, i, n);
    }
}
//
         



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

评分

3

查看全部评分

本帖被以下淘专辑推荐:

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

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

使用道具 举报

stellari 发表于 2015-9-22 17:08:42 | 显示全部楼层
赞一下楼主,顺便提一下1->2->3->4->2->3->4这类循环之所以不可能,是因为如果存在这样的循环,那表示p[1]和p[4]都等于2,但是题中已经说明了p中是没有重复数字的,所以这种循环不可能出现。

顺便鄙视一下万恶的[i]标签。
回复 支持 反对

使用道具 举报

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

感谢指点,感谢。自己还是太弱了,一下子就懵逼了,啥都想不出来
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-22 21:03:30 | 显示全部楼层
面试官为什么第二题要这么表述。。好奇怪
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-22 21:04:11 | 显示全部楼层
面试官为什么第二题要这么表述。。好奇怪
permutation的循环周期应该等于所有置换群的长度的最小公倍数吧
回复 支持 反对

使用道具 举报

evilbobo 发表于 2015-9-23 05:28:31 | 显示全部楼层
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;
. more info on 1point3acres.com        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[j] = p[a[i - 1][j]];
            }
        }
        return a[k];
    }. 1point 3acres 璁哄潧
. from: 1point3acres.com/bbs
补充内容 (2015-9-23 05:31):.鐣欏璁哄潧-涓浜-涓夊垎鍦
有错误,请忽略这个答案。。。。
. From 1point 3acres bbs
补充内容 (2015-9-23 05:32):. visit 1point3acres.com for more.
有错误,请忽略这个答案。。。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| uuuouou 发表于 2015-10-7 09:55:27 | 显示全部楼层
pengzewen37 发表于 2015-10-7 06:37
从另一个帖子link到LZ这个帖子的,看到上面有人分析说1 -> 2 -> 3 -> 4 -> 2 -> 3 -> 4这样不对是因为没有 ...

因为题设中有p[]中存了0~n-1这n个数,如果有这样的cycle,则p[1]=p[4]=2,就不满足题设了
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-10-7 10:09:50 | 显示全部楼层
uuuouou 发表于 2015-10-6 20:55
因为题设中有p[]中存了0~n-1这n个数,如果有这样的cycle,则p[1]=p[4]=2,就不满足题设了

thx, 那题目就变简单了,任何一个index都是某一个cycle,那么遍历一遍直到下一个出现,找到这个周期的size就差不多解出来了
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-8 14:59:21 | 显示全部楼层
我把循环节存了一下,对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;. visit 1point3acres.com for more.
  12.             do {
  13.                 visit[t] = true;
  14.                 cid[t] = make_pair(cycle.size(), c.size());. 1point3acres.com/bbs
  15.                 c.push_back(t);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.                 t = p[t];
  17.             } while (t != i);-google 1point3acres
  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). 鍥磋鎴戜滑@1point 3 acres
  31.         cout << e <<' ';
  32.     return ans;
  33. }
复制代码
回复 支持 反对

使用道具 举报

arjiang 发表于 2015-10-15 16:07:14 | 显示全部楼层
第二题是个洗牌方法,p[] 是洗牌数组,作用是把第i个点map到第j个位置上去;那个反例要求p[2]=4 and p[2]=1, 这显然不可能;
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 06:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表