一亩三分地论坛

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

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

Google On Campus Interview面经

[复制链接] |试试Instant~ |关注本帖
sweeney1130 发表于 2014-10-3 08:42:27 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 实习@Google - 内推 - 校园招聘会 |Other

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

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

x
来美帝第一个面试就献给了Google,面试的是2015 Summer Intern。两个面试官,一个美国大叔一个中国大叔。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Problem 1: Tilt Maze,就只只能沿着一个方向走迷宫,不能一步步走,只能向一个方向走到边界或者遇到障碍物。面试官出了几个问题:
1.写一个数据结构来记录这个Maze
2.找到一条从起点s到终点e的路径,要求使用最少的move. 1point 3acres 璁哄潧
.1point3acres缃
3.找到一条从起点s到终点e的路径,要求使用距离最少. from: 1point3acres.com/bbs

Problem 2:给两个长度N的数组,A, B,它们都是sorted的,找出矩阵 M[j] = A + B[j]中,N个最大的数,输出它们。

今天刚刚面完,保佑我能进入host match!.鏈枃鍘熷垱鑷1point3acres璁哄潧


补充内容 (2014-10-3 11:29):
说下我的做法吧,第一题2就是BFS嘛,3是要建一个新的图,从s开始BFS,以到达的每一个顶点的距离为权值建一个新的图,如果该点已经被访问过了,则丢弃;最坏的情况下,有N^2个图。然后用Dijkstra做吧。. more info on 1point3acres.com

补充内容 (2014-10-3 11:35):
解答看#16楼

评分

2

查看全部评分

 楼主| sweeney1130 发表于 2014-10-3 11:35:19 | 显示全部楼层
说下我的做法吧
第一题
1就是给每个节点填一个byte 1110 用二进制mark每个方向是否能走
2就是BFS嘛
3是要建一个新的图,从s开始BFS,以一个点到达的另外一个顶点的距离为权值建一个新的图,如果该点已经被访问过了,则不用继续bfs这个节点;最坏的情况下,有N^2个节点。然后用Dijkstra做吧。

第二题
面试官说有O(n)的方法,鄙人不才还是大神自己想吧,附链接http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf

我就是用堆来做吧,每次扩展当前点的i-1或者j-1加入到堆里,每次迭代去堆中去最小的加入结果中,做N次就行,但是主要要判断重复。可是面试的时候忘记了,面试官也一直没有给我hint,最后这个bug也没fix,后来才想起来。

大家有什么想法也可以分享下,我的就这么多。
回复 支持 2 反对 0

使用道具 举报

e6175423 发表于 2014-10-4 12:10:17 | 显示全部楼层
  1. 最短距离:
  2. struct node
  3. {
  4.     long long val;
  5.     long long dis;
  6.     node(long long v, long long d):val(v), dis(d){}
  7. };
  8. struct cmp
  9. {
  10.     bool operator()(const node& n1, const node& n2)
  11.     {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.         return n1.dis > n2.dis;. 1point3acres.com/bbs
  13.     }
  14. };
  15. priority_queue<node, vector<node>, cmp> q;
  16. int dis[M][M];
  17. long long step(vector<vector<int> >board, point start, point end)
  18. {
  19.     int m = board.size(), n=board[0].size();
  20.      for(int i = 0; i < m*n; i++)
  21.          for(int j = 0; j < m*n; j++)
  22.           dis[i][j]=INT_MAX/2;
  23.      long long e = (end.x)*n+(end.y);
  24.     long long s = start.x * n + start.y;
  25.     q.push(node(s,0));
  26.     dis[s][s]=0;
  27.     while(!q.empty())
  28.     {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  29.        long long v = q.top().val;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.        long long d = q.top().dis;
  31.        q.pop();
  32.        int x = v/n;
  33.        int y = v%n;
  34.        if(v==e) return d;
  35.         if(dis[x][y] < d) continue;
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  36.        int i;
  37.        for(i = x; i<m &&board[i][y]==0 && i*n+y!=e ;i++);
  38.        if(i*n+y!=e)
  39.            i--;. From 1point 3acres bbs
  40.             if(dis[i][y]>d+i-x) {. 1point3acres.com/bbs
  41.                 dis[i][y]=d+i-x;. 鍥磋鎴戜滑@1point 3 acres
  42.                q.push(node(i*n+y,d+i-x));
  43.                cout<<"1: "<<i<<" "<<y<<" "<<"cnt: "<<d+i-x<<endl;
  44.             }
  45.         for(i = x; i>=0 && board[i][y]==0 && i*n+y!=e;i--);
  46.        if(i*n+y!=e)
  47.            i++;
  48.           if(dis[i][y]>d-i+x) {-google 1point3acres
  49.                 dis[i][y]=d-i+x;
  50.            q.push(node(i*n+y,d-i+x));
  51.            cout<<"2: "<<i<<" "<<y<<" "<<"cnt: "<<d-i+x<<endl;
  52.          }
  53.        for(i = y; i<n &&board[x][i]==0 && x*n+i!=e;i++);
  54.         if(x*n+i!=e) i--;
  55.            if(dis[x][i]>d+i-y) {
  56.                 dis[x][i]=d+i-y;
  57.            q.push(node(x*n+i,d+i-y));
  58.            cout<<"3: "<<x<<" "<<i<<" "<<"cnt: "<<d+i-y<<endl;
  59.           }
  60.        for(i = y; i>=0 &&board[x][i]==0 && x*n+i!=e;i--);. more info on 1point3acres.com
  61.        if(x*n+i!=e)i++;
  62.            if(dis[x][i]>d-i+y) {
  63.                 dis[x][i]=d-i+y;
  64.            q.push(node(x*n+i,d-i+y));
  65.             cout<<"4: "<<x<<" "<<i<<" "<<"cnt: "<<d-i+y<<endl;
  66.            }
  67.     }
  68. }
复制代码

补充内容 (2014-10-4 12:13):
代码解释:  方法是利用优先队列,动态更新s点到其他点的最小距离(dijkstra)
回复 支持 1 反对 0

使用道具 举报

xnature 发表于 2014-11-22 05:53:29 | 显示全部楼层
算法导论问的是Extract-min。反正求最大值最小值都一样。假设求最小值。第一最小值就是[0,0]。假设f(m,n)是矩阵m x n的最小值。那么把[0,0]取出来以后,第二最小值要去填空。min(f(m-1, n), f(m,n-1))。这样就可以递归了。每一次都要么在m减少1,要么n减少1。所以时间复杂度是m + n。
回复 支持 0 反对 1

使用道具 举报

lhh_NJU 发表于 2014-10-3 19:01:32 | 显示全部楼层
shinichish 发表于 2014-10-3 15:36.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二题,我又仔细想了下。我觉得可以优化:
1. 只需要一个大小为N的小顶堆就可以了. From 1point 3acres bbs
2. 搜索的时候,对角 ...

你这样是只将矩阵中对角线的元素加进来吗? 不太对吧? 我的想法是, 先把右下角的元素加进堆, 然后一个while循环, 每次pop出堆顶元素的同时push进它左边和上边的元素, 这样最先pop出来的N个元素就是最大的N个。
. 鍥磋鎴戜滑@1point 3 acres
while循环里的每次操作会把堆的元素加1, 所以每次push操作的时间复杂度是O(logN), 然后总的时间复杂度也是O(NlogN)
回复 支持 1 反对 0

使用道具 举报

austurela 发表于 2014-10-3 09:35:56 | 显示全部楼层
第一题我的想法是用2D Array,每个格子放个quadruple,分别记录距离碰撞上下左右的距离,这样只要查quadruple就知道往上下左右走几步后会碰撞
第二题用个max priority queue,最大的是右下角,第二第三在最下一边和最右一边,所以全放到priorityqueue里面,N如果是4的话放最右下角的左上,因为这是剩下的里面的最大的。第五第六放倒数第二row和倒数第二column,然后重复。。。. Waral 鍗氬鏈夋洿澶氭枃绔,
lz可否分享下你的方法?
回复 支持 反对

使用道具 举报

Interviwer 发表于 2014-10-3 09:46:19 | 显示全部楼层
第一个问题,是不是就是用二维数组就可以啊?2是DFS 3是BFS ; 第二个问题应该是智力题吧?要是我就是N = m^2 + n, 然后直接输出数字
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2014-10-3 09:49):
写错了,2是BFS 3是DFS
回复 支持 反对

使用道具 举报

pystone 发表于 2014-10-3 09:55:24 | 显示全部楼层
austurela 发表于 2014-10-3 09:35
第一题我的想法是用2D Array,每个格子放个quadruple,分别记录距离碰撞上下左右的距离,这样只要查quadrup ...

第二题没必要考虑那个矩阵 其实就问两个有序数组中任意两个数字和的最大的n个 两个指针初始放在两个数组最大的数字上 每次输出加和 然后把两个指针下一个数字更大的那个指针后移一位 移位时如果某个指针已经超出当前数组的范围 把他重置到这个数组最大的位置 然后把另一个指针往小的方向移一位 直到输出了N个数或者两个指针都已经到最小的位置

不过这个方法极限情况下(N=len(A)*len(B))复杂度跟用heap的方法一样 只是会有些常数级别的优势
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2014-10-3 09:56:12 | 显示全部楼层
1矩阵2bfs3dijkstra 第二题用heap
回复 支持 反对

使用道具 举报

pystone 发表于 2014-10-3 09:57:48 | 显示全部楼层
austurela 发表于 2014-10-3 09:35
第一题我的想法是用2D Array,每个格子放个quadruple,分别记录距离碰撞上下左右的距离,这样只要查quadrup ...

以及第一题第二问是用BFS 第三问似乎只能爆搜(DFS或BFS都行)加剪枝?
不清楚还有没有更优的方法 同问LZ的解答
回复 支持 反对

使用道具 举报

austurela 发表于 2014-10-3 10:12:26 | 显示全部楼层
pystone 发表于 2014-10-3 09:55
第二题没必要考虑那个矩阵 其实就问两个有序数组中任意两个数字和的最大的n个 两个指针初始放在两个数组 ...

“然后把两个指针下一个数字更大的那个指针后移一位”
1, 2, 3, 70,100. 鍥磋鎴戜滑@1point 3 acres
1, 2, 3, 50, 51. From 1point 3acres bbs
最大151,第二150,但是按你说的就成了第二是70+51了。。。
回复 支持 反对

使用道具 举报

austurela 发表于 2014-10-3 10:13:04 | 显示全部楼层
ototsuyume 发表于 2014-10-3 09:56.1point3acres缃
1矩阵2bfs3dijkstra 第二题用heap

请问第二题具体怎么用heap得?
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2014-10-3 10:29:41 | 显示全部楼层
austurela 发表于 2014-10-3 10:13
请问第二题具体怎么用heap得?

把你矩阵画出来,先看右下角那个数,盯着看,然后看右下角左边的数和上边的数,继续看就能找到规律了。靠移动指针来做这题不实际,要处理各种边界情况的话非常复杂

第一题第三问就是一个教科书般的dijkstra最短路算法,需要考虑每一次的移动距离
回复 支持 反对

使用道具 举报

pystone 发表于 2014-10-3 10:30:27 | 显示全部楼层
austurela 发表于 2014-10-3 10:12
“然后把两个指针下一个数字更大的那个指针后移一位”. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1, 2, 3, 70,100. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1, 2, 3, 50, 51

啊对。。思考漏了 应该是分别往小的后移一位跟另一个当前相加 找出大的那个后移 因为下一个最大和一定是某个指针后移一位得到的

heap就是把每个加和算出来扔堆里 然后取出N个就可以了 因为平均复杂度都一样 所以直接用heap更方便 其他方法一不小心就会思考出错【例如我=。=】
回复 支持 反对

使用道具 举报

pystone 发表于 2014-10-3 10:31:46 | 显示全部楼层
ototsuyume 发表于 2014-10-3 09:56
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴1矩阵2bfs3dijkstra 第二题用heap

第三问dijk好想法!我疏忽了。膜拜下大神
回复 支持 反对

使用道具 举报

austurela 发表于 2014-10-3 10:35:44 | 显示全部楼层
ototsuyume 发表于 2014-10-3 10:29
把你矩阵画出来,先看右下角那个数,盯着看,然后看右下角左边的数和上边的数,继续看就能找到规律了。靠 ...

除了我上面说的规律,没看出来啥规律。。。
回复 支持 反对

使用道具 举报

austurela 发表于 2014-10-3 10:38:25 | 显示全部楼层
pystone 发表于 2014-10-3 10:30
啊对。。思考漏了 应该是分别往小的后移一位跟另一个当前相加 找出大的那个后移 因为下一个最大和一定是 ...

google面试如果无脑heap就挂了把。。。
回复 支持 反对

使用道具 举报

austurela 发表于 2014-10-3 10:41:59 | 显示全部楼层
pystone 发表于 2014-10-3 10:30
啊对。。思考漏了 应该是分别往小的后移一位跟另一个当前相加 找出大的那个后移 因为下一个最大和一定是 ...

“下一个最大和一定是某个指针后移一位得到的”
1,3
2,4-google 1point3acres
第一7,第二2+3,第三1+4,第二到第三就不是某个指针后移一位得到的,感觉指针不靠谱
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-10-3 12:03:28 | 显示全部楼层
指针有办法做吗??heap需要O(n^2)的空间,O(logn)的时间,感觉不是很好,而且做法感觉有点脑残。。。

补充内容 (2014-10-3 15:38):
错了。。复杂度是O(N^2 longN)
回复 支持 反对

使用道具 举报

pkusnail 发表于 2014-10-3 13:43:54 | 显示全部楼层
VIP   MAKR
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-10-3 15:36:12 | 显示全部楼层
第二题,我又仔细想了下。我觉得可以优化:
1. 只需要一个大小为N的小顶堆就可以了
2. 搜索的时候,对角线搜索

这样的空间复杂度是O(N),时间复杂度O(NlogN)。请问还有更好的办法吗?
  1. public int[] findNLargest(int[] A, int[] B) {
  2.                 int n = A.length;
  3.                 int[] res = new int[n];
  4.                
  5.                 Queue<Integer> heap = new PriorityQueue<Integer>(n);. from: 1point3acres.com/bbs
  6.                 for (int i = n - 1; i >= 0; i--) {
  7.                         int x = n - 1;
  8.                         int y = i;
  9.                         while (y < n) {
  10.                                 if (heap.size() < n) {. more info on 1point3acres.com
  11.                                         heap.offer(A[x] + B[y]);
  12.                                 } else if (A[x] + B[y] > heap.peek()) {
  13.                                         heap.poll();
  14.                                         heap.offer(A[x] + B[y]);
  15.                                 }
  16.                                 x--;
  17.                                 y++;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.                         }
  19.                         if (heap.size() == n) {
  20.                                 break;
  21.                         }
  22.                 }
  23.                 int i = 0;
  24.                 while (!heap.isEmpty()) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.                         res[i++] = heap.poll();
  26.                 }
  27.                
  28.                 return res;
  29.         }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 04:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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