一亩三分地论坛

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

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

Google 电面+ campus+ mtv onsite

[复制链接] |试试Instant~ |关注本帖
lijl900805 发表于 2014-12-12 07:30:26 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Google - Other - 技术电面 Onsite 校园招聘会 |Other

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

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

x
开学前Google主动联系的我,估计是之前投实习有记录?

然后一直觉得自己没准备好,想到既然联系了就好好应付吧,于是跟recruiter说了预约的时间第一轮电面的时间(10月初)。.鏈枃鍘熷垱鑷1point3acres璁哄潧

第一轮,问了一些基本的问题和behavior,轻轻松松通过。然后那时Google的第一轮on campus已经过去,recruiter说要不直接把你放在第二轮on campus去面试,我说not problem。

于是第二轮是十月底的on campus. 共两轮,第一轮先问了下简历里面的东西,再问问你最熟悉的语言和它不好的地方,然后开始做题。Palindrome问题,不难。然后一题互换偶数(类似palindrome),巴拉巴拉写个dfs出去。 第二轮一上来写个缩写检索, 然后follow up来设计如何narrow down候选列表。

过了两三个工作日recruiter回信说你通过啦,开来预约onsite吧。当时作业考试比较多,加上又是第一个onsite(本人比较懒,一直不怎么投简历 = =),于是预约到了一个月后...
然后就是上周日坐了灰机到mtv。第二天高高兴兴去面试,共四轮。
. visit 1point3acres.com for more.
一上来一个小白哥笑嘻嘻地问我喜欢Google啥产品呀。我没多想就说search和map呗。然后他问我有啥地方可以改进的,我就对这两个东西吐槽了一遍。。。然后就问shift array,有哪些方法,都有啥优缺点。

第二轮一个阿三哥板着脸进来,把我吓到了。然后用非常标准的烙印英语给我讲了master和slave machine问题。一开始还以为是设计题,扯了一些design,后来发现是merge k sorted list,好吧,轻轻松松把代码写出来。然后又问一个array元素波浪排列问题,都有啥解决方法。讲完第一个approach后再想讲第二个就不够时间了。然后就是一个ABC带着我去参观Google食堂。。。

回来后进行第三轮面试,shadow, 先问我hash table 的原理,讲讲key是怎么做到O(1), 扯了一下大二学的东西。然后给个大的0 1二维矩阵,求所有长宽为a、b,里面1个数为k的矩形。一开始没啥头绪,写了个最笨的方法,然后慢慢优化优化。。。

最后一轮,在Google工作了四年的小白哥,先问我喜欢研究哪些方向,然后说那我考你设计题吧,然后叫我设计一个cache,要求object过段时间会expire掉,set要越少failure越好...大家懂的。. more info on 1point3acres.com


面完传说中高大上的G家,感觉自己要准备的东西还是有挺多的。一直觉得自己很幸运,可以去mountain view一日游。当然其他公司也会猛地投,大家一起加油!祝都能找到好工作!!!. Waral 鍗氬鏈夋洿澶氭枃绔,
e6175423 发表于 2014-12-25 19:42:01 | 显示全部楼层
不知道下面的代码对不?
时间和空间复杂度都要n^2
int solve(vector<vector<int> > board, int a, int b, int k)
{
    int M = board.size();
    int N = board[0].size();. more info on 1point3acres.com

    vector<vector<int> > part_sum(M+1, vector<int>(N+1));
    int cnt = 0;
    part_sum[1][1] = board[0][0];

    for(int i = 1; i<= M; i++). visit 1point3acres.com for more.
        for(int j = 1; j <= N; j++)
    {
        part_sum[i][j] = part_sum[i-1][j] + part_sum[i][j-1] - part_sum[i-1][j-1] + board[i-1][j-1];

        int val = part_sum[i][j]-k;

        if(i>=a && j>=b&& part_sum[i-a][j]+part_sum[i][j-b]-part_sum[i-a][j-b]==val)
            cnt++;
    }. From 1point 3acres bbs

    return cnt;
}
int main()
{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    vector<vector<int> > b({{1,0,1,1,1},{0,1,1,0,0},{1,1,1,0,0}});
    cout<<solve(b, 2, 2, 2)<<endl;
    return 0;. 1point3acres.com/bbs
}
回复 支持 1 反对 0

使用道具 举报

liuzhe1218 发表于 2014-12-12 09:27:08 | 显示全部楼层
一看就是粘过来的~~~
回复 支持 反对

使用道具 举报

 楼主| lijl900805 发表于 2014-12-12 11:31:40 | 显示全部楼层
liuzhe1218 发表于 2014-12-12 09:27
一看就是粘过来的~~~

哎哟,头像很漂亮嘛
回复 支持 反对

使用道具 举报

liuzhe1218 发表于 2014-12-12 12:10:53 | 显示全部楼层
lijl900805 发表于 2014-12-12 11:31
哎哟,头像很漂亮嘛
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那是~~你也很靓哦
回复 支持 反对

使用道具 举报

liuzhe1218 发表于 2014-12-12 12:11:03 | 显示全部楼层
lijl900805 发表于 2014-12-12 11:31.鏈枃鍘熷垱鑷1point3acres璁哄潧
哎哟,头像很漂亮嘛

那是~~你也很靓哦
回复 支持 反对

使用道具 举报

Dexter_syr 发表于 2014-12-13 10:29:14 | 显示全部楼层
第三轮lz怎么答的?
回复 支持 反对

使用道具 举报

brainrpi 发表于 2014-12-22 06:50:05 | 显示全部楼层
求k个1的问题有空间要求吗?
回复 支持 反对

使用道具 举报

犬座 发表于 2014-12-25 02:42:48 | 显示全部楼层

  1. int find(const vvi& ma, int a, int b, int k) {
  2.   int m = ma.size();
  3.   int n = ma[0].size();
  4.   int count = 0;

  5.   // rowOnes[i][j] = ma[0][j] + ma[1][j] + .. + ma[i][j]
  6.   // colOnes[i][j] = ma[i][0] + ma[i][1] + .. + ma[i][j]
  7.   vvi rowOnes(m, vi(n, 0));
  8.   vvi colOnes(m, vi(n, 0));

  9. . 鍥磋鎴戜滑@1point 3 acres
  10.   // processing matrix and generate rowOnes and colOnes
  11.   for(int i = 0; i < m; i++) {
  12.     for(int j = 0; j < n; j++) {. 鍥磋鎴戜滑@1point 3 acres
  13.       rowOnes[i][j] = i == 0 ? ma[i][j] : rowOnes[i-1][j] + ma[i][j];
  14.       colOnes[i][j] = j == 0 ? ma[i][j] : colOnes[i][j-1] + ma[i][j];
  15.     }
  16.   }

  17.   int topOnes = 0;
  18.   int countOnes = 0;

  19.   // calculate # of ones in the top left rectangle
  20.   for(int i = 0; i < a; i++) {
  21.     topOnes += colOnes[i][b-1];
  22.   }. 鍥磋鎴戜滑@1point 3 acres

  23.   for(int row = 0; row <= m - a; row++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  24.     int removeRow = row - 1;
  25.     int addRow = row + a - 1;
  26. . more info on 1point3acres.com
  27.     // if row == 0 then don't add/sub from topOnes
  28.     topOnes -= row == 0 ? 0 : colOnes[removeRow][b - 1];
  29.     topOnes += row == 0 ? 0 : colOnes[addRow][b - 1];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  30.     countOnes = topOnes;. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.     if(countOnes == k) count++;

  32.     for(int col = 1; col <= n - b; col++) {
  33.       int removeCol = col - 1;
  34.       int addCol = col + b - 1;

  35.       countOnes -= rowOnes[addRow][removeCol] - (row == 0 ? 0 : rowOnes[removeRow][removeCol]);
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  36.       countOnes += rowOnes[addRow][addCol] - (row == 0 ? 0 : rowOnes[removeRow][addCol]);

  37.       if(countOnes == k) count++;
  38.     }
  39.   }

  40.   return count;
  41. }
复制代码
. more info on 1point3acres.com
补充内容 (2014-12-25 02:43):
第三轮k个1的代码,vvi是vector<vector<int> >

补充内容 (2014-12-25 02:44):
time: O(n^2), space: O(n^2)
回复 支持 反对

使用道具 举报

e6175423 发表于 2014-12-25 16:15:21 | 显示全部楼层
互换偶数是啥啊~?
回复 支持 反对

使用道具 举报

kwang75 发表于 2014-12-29 03:25:15 | 显示全部楼层
楼主能不能再讲讲设计cache和那个array元素波浪排列?谢谢!
回复 支持 反对

使用道具 举报

 楼主| lijl900805 发表于 2015-1-4 17:32:59 | 显示全部楼层
kwang75 发表于 2014-12-29 03:25
楼主能不能再讲讲设计cache和那个array元素波浪排列?谢谢!

该题的Cache 就是leetcode里面的那道LRU cache题,array波浪排列是指第k个位置放某个数(k>0),第k-1和k+1个位置都要比A[k]大,然后A[k+2]要比A[k+1]小,A[k+3]要比A[k+2]大... 彼此类推
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2015-12-25 08:08:02 | 显示全部楼层
e6175423 发表于 2014-12-25 19:42
不知道下面的代码对不?
时间和空间复杂度都要n^2
int solve(vector board, int a, int b, int k)
. 1point 3acres 璁哄潧
很赞啊,我照着写了一个java的
  1. public static int numberOfRectangle(int[][] board, int k, int a, int b) {
  2.                 int m = board.length;
  3.                 if (m == 0 || board[0].length == 0) return 0;
  4.                 int n = board[0].length;
  5.                
  6.                 int count = 0;
  7.                 int[][] dp = new int[m + 1][n + 1];
  8.                 for (int i = 1; i <= m; i++) {
  9.                         for (int j = 1; j <= n; j++) {
  10.                                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + board[i - 1][j - 1];
  11.                                 if (i >= a && j >= b) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.                                         if (dp[i][j] - dp[i - a][j] - dp[i][j - b] + dp[i - a][j - b] == k) count++;. 1point 3acres 璁哄潧
  13.                                 }
  14.                         }
  15.                 }
  16.                
  17.                 return count;
  18.         }
  19.        
  20.         public static void main(String[] args) {
  21.                 int[][] board = {{0,0,0,1,1,1}, {0,1,1,1,1,0}, {1,0,1,0,1,0}, {0,1,1,0,1,1}};
  22.                 System.out.println(numberOfRectangle(board, 5, 2, 3));
  23.         }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-12 11:37:07 | 显示全部楼层
e6175423 发表于 2014-12-25 19:42
. visit 1point3acres.com for more.不知道下面的代码对不?
时间和空间复杂度都要n^2
int solve(vector board, int a, int b, int k)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这个长和宽是不能变的吗?可不可能是倒着的长方形?
回复 支持 反对

使用道具 举报

e6175423 发表于 2016-2-13 14:25:39 | 显示全部楼层
liuzhe1218 发表于 2014-12-12 09:27
一看就是粘过来的~~~

是啊,在xcode先写好啊,不可能在这里直接编辑,我没这么腻害……
回复 支持 反对

使用道具 举报

e6175423 发表于 2016-2-13 14:26:38 | 显示全部楼层
javaprogrammer 发表于 2015-12-25 08:08
很赞啊,我照着写了一个java的

恩~赞!你的更简洁
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 16:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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