一亩三分地论坛

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

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

3月google onsite

[复制链接] |试试Instant~ |关注本帖
trouble246 发表于 2016-3-21 08:26:30 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
3月11面的Google onsite,发个面筋攒人品!

Phone interview:
大概是一个多月之前了,做了之后好久才收到onsite,当时以为跪了也没在意。总共两题,第一题是写一个iterator of iterators class, 就是给你一些generic 的iterators, 用一个大的iterator去遍历所有,同样是有hasNex()和Next()两个method。 第二题是Leetcode 159. Longest Substring with At Most Two Distinct Characters。

onsite:
第一轮:白人小哥
上来寒暄了一下就上题了,第一题是resize一个图从AxB resize 到 CxD, 问新输出的图像尺寸,一开始我以为是给一个matrix让压缩,感觉挺难的,和他讨论了一下发现是给一个长和宽,算出resize之后的保持原长宽比的长和宽就行了,比如给一个800x600的图,resize到400x400的空间,输出应该是400x300, 因为要保持长宽比不变,所以直接判定一下计算一下比例就好,主要注意的就是明确一下如果input是0之类的特殊情况该咋处理。我把code写出来和他讨论了几个corner case,然后他质疑了一下后来被我强行说服了,然后他问了如果要test这个程序可能会有的错误情况是啥。 第二题是那个有一列袋子,袋子上标有内含的硬币价值,两个人轮流取,只能取头和尾的袋子,看谁最后能取到的总价值最大,然后程序是计算作为先手玩家最大能取多少。我以前只写过这题用backtracking的办法,给他说了之后他问我time complexity是多少,然后问我咋改进,我说用一个hashtable存下来所有遇到的情况,每次backtracking时去看那个hashtable里有没有这个情况,有的话就直接得到剩余最大的价值。他说行,我就开始写了,写完了backtrack的部分,我正准备加上hashtable时他说可以了,能写到这个也就行了,而且时间也到了。然后拍了照就走了。

第二轮:很geek的小哥不知道啥裔
这轮是4轮中面的最不好的个人感觉,就围绕着一道题写了两端代码,面试官上来先问迷宫该咋走能找到最短路径,我说BFS,他说好,然后给了个迷宫用小球走,每次确定一个方向之后小球会一直走到碰到障碍物或者边界才会停下,如果停下的地方恰好是出口就算出去了,然后现场画了一个迷宫让我在图上画一条可行的路线,我当时略微懵逼,居然没找到一条能走通的路,面试官微微一笑指了一条,我赶紧照葫芦画瓢又找了一条,心想这是算考brain teaser么。。。然后面试官问这种情况又应该咋走?时间复杂度是多少,如何改进,再他提示下我算是想出来了要新建一个和迷宫同样大小的matrix,先遍历整个图两遍,把每个空位上下左右的障碍物的位置都存到那个点的array里,然后再用bfs就可以直接读到从任意一个点出发小球能停到的位置,这样可以降低时间复杂度。然后我写了一次遍历这张图要用的code和完成预处理之后再做BFS所用的code,然后时间就到了。

二轮过后吃午饭,我看地里都是面三轮才吃午饭,以为自己二轮游了。。。没想到只是改了流程而已。吃饭时就聊聊天没啥特别的。

第三轮:和蔼的白人大叔
这个大叔迟到了好久,陪我吃饭的小哥打电话也没人接。最后又只写了一题,是一个类似于LRU的cache,要求cache里存一段时间之内所有的image cache, 如果超过了一定的时间这个image没有被用到,就把他清除出cache,和LRU不同的是这个cache没有size限制,但清除旧image的过程是每有一个过期的image就要进行一次,我就用了hashtable加heap来实现的,最后他问了一些关于timer和critical section一类的问题,大概就是不能让update cache和input新image冲突一类的,我虽然学过操作系统,但对于java multithread不太懂,就答了答概念,还好时间到了逃过一劫。

第四轮:华裔小哥

面试官Berkeley毕业的。。。但问的问题都不难!第一题是给你一个array,返回一个list存有任意N个相邻数字的平均数,比如input是[3, 5, 12, 43, 22, 6], n=3, 那么output就是[20/3, 20, 77/3, 71/3], 实现的时候和面试官商量要用double还是int, 我说了一个O(n)的方法,他觉得可行,我就写了,然后给他看了几个test cases,他就过了,第二题是地里说过好多遍的longest consecutive sequence in a tree, 就不多说了, 写完还有很久空闲,又跟面试官聊了一会儿。然后就把我送出了大楼。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
总的来说运气挺好的,没有碰到地里那些特别难的题目,但做的时候还是磕磕绊绊有时会回去涂涂改改,相当尴尬。

最后祝大家一切顺利!

评分

2

查看全部评分

bobzhang2004 发表于 2016-3-30 05:07:13 | 显示全部楼层
写了下第二题O(m * n)的代码
  1. public class Maze {.鐣欏璁哄潧-涓浜-涓夊垎鍦

  2.         static class Cell {
  3.                 List<Integer> nextPoints;

  4.                 public Cell() {
  5.                         nextPoints = new ArrayList<Integer>();
  6.                 }
  7.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  8.         public static int minimumStepToGetOutOfMaze(int[][] matrix, int x, int y,
  9.                         int endX, int endY) {
  10.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  11.                         return -1;
  12.                 }

  13.                 int m = matrix.length;
  14.                 int n = matrix[0].length;
  15.                 Cell[][] pointsMatrix = getNextPointsMatrix(matrix);
  16. //                for (int i = 0; i < m; i++) {
  17. //                        for (int j = 0; j < n; j++) {
  18. //                                for (int k : pointsMatrix[i][j].nextPoints) {
  19. //                                        System.out.print(k + " ");-google 1point3acres
  20. //                                }
  21. //                                System.out.println();
  22. //                        }.1point3acres缃
  23. //                }. visit 1point3acres.com for more.
  24.                 Queue<Integer> queue = new LinkedList<Integer>();
  25.                 int code = x * n + y;
  26.                 queue.offer(code);
  27.                 int step = 0;
  28.                 boolean[][] visited = new boolean[m][n];
  29.                 visited[x][y] = true;
  30.                 while (!queue.isEmpty()) {
  31.                         int size = queue.size();
  32.                         for (int k = 0; k < size; k++) {
  33.                                 code = queue.poll();
  34.                                 int i = code / n;. 1point 3acres 璁哄潧
  35.                                 int j = code % n;
  36.                                 if (i == endX && j == endY) {
  37.                                         return step;
  38.                                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  39.                                 List<Integer> points = pointsMatrix[i][j].nextPoints;
  40.                                 for (int p : points) {
  41.                                         int nx = p / n;. 1point3acres.com/bbs
  42.                                         int ny = p % n;
  43.                                         if (!visited[nx][ny]) {
  44.                                                 queue.offer(p);
  45.                                                 visited[nx][ny] = true;.1point3acres缃
  46.                                         }. visit 1point3acres.com for more.
  47.                                 }

  48.                         }
  49.                         step++;
  50.                 }

  51.                 return -1;
  52.         }

  53.         private static Cell[][] getNextPointsMatrix(int[][] matrix) {
  54.                 int m = matrix.length;
  55.                 int n = matrix[0].length;
  56.                 Cell[][] cells = new Cell[m][n];. 1point 3acres 璁哄潧
  57.                 for (int i = 0; i < m; i++) {
  58.                         for (int j = 0; j < n; j++) {
  59.                                 cells[i][j] = new Cell();
  60.                         }
  61.                 }
  62.                 for (int i = 0; i < m; i++) {
  63.                         int j = 0;
  64.                         int start = 0;
  65.                         int lastPos = 0;
  66.                         while (j <= n) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  67.                                 if (j == n || matrix[i][j] == 1) {
  68.                                         int code = i * n + (j - 1);
  69.                                         for (int k = start; k < j; k++) {
  70.                                                 cells[i][k].nextPoints.add(code);
  71.                                                 cells[i][k].nextPoints.add(lastPos);
  72.                                         }
  73.                                         start = j + 1;
  74.                                         lastPos = i * n + start;
  75.                                 }
    . 1point 3acres 璁哄潧
  76.                                 j++;
  77.                         }. 1point 3acres 璁哄潧
  78.                 }
  79.                 for (int j = 0; j < n; j++) {
  80.                         int i = 0;
  81.                         int start = 0;
  82.                         int lastPos = 0;
  83.                         while (i <= m) {
  84.                                 if (i == m || matrix[i][j] == 1) {
  85.                                         int code = (i - 1) * n + j;
  86.                                         for (int k = start; k < i; k++) {. visit 1point3acres.com for more.
  87.                                                 cells[k][j].nextPoints.add(code);
  88.                                                 cells[k][j].nextPoints.add(lastPos);
  89.                                         }
  90.                                         start = i + 1;
  91.                                         lastPos = start * n + j;
  92.                                 }
  93.                                 i++;
  94.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  95.                 }
  96.                 return cells;
    . 鍥磋鎴戜滑@1point 3 acres
  97.         }
  98. . 1point 3acres 璁哄潧
  99.         public static void main(String[] args) {-google 1point3acres
  100.                 int[][] matrix = { { 0, 0, 1, 0, 0, 0 },
  101.                                                    { 0, 0, 0, 0, 1, 0 },
  102.                                                    { 0, 1, 1, 0, 0, 0 },
  103.                                                    { 0, 0, 1, 0, 0, 0 } };
  104.                 System.out.println(minimumStepToGetOutOfMaze(matrix, 0, 0, 3, 5));. more info on 1point3acres.com
  105.         }
  106. }
复制代码
回复 支持 2 反对 0

使用道具 举报

bobzhang2004 发表于 2016-3-30 05:11:29 | 显示全部楼层
请问楼主第三题用heap是怎么实现呢?为什么不用leetcode 上的hashmap+doubly linked list,在每个node中存一下时间就行了吧,需要删除的时候重头到尾check一下时间 就行了啊
回复 支持 1 反对 0

使用道具 举报

bobzhang2004 发表于 2016-3-21 21:18:11 | 显示全部楼层
第一轮硬币题应该是dp做吧,请问第二题定义的迷宫结构是01矩阵吗?
回复 支持 反对

使用道具 举报

夜辉冥 发表于 2016-3-22 14:42:10 | 显示全部楼层
第三轮这个题目没太懂什么意思。 你是如何记录时间的。是有一个进程专门来检测哪些image过期了吗?
回复 支持 反对

使用道具 举报

 楼主| trouble246 发表于 2016-3-22 14:46:11 | 显示全部楼层
bobzhang2004 发表于 2016-3-21 21:18
第一轮硬币题应该是dp做吧,请问第二题定义的迷宫结构是01矩阵吗?

对, 但一上来我没想到DP具体要怎么写,就先写了backtrack的方法,迷宫是数字矩阵,0是可以通过的地方,1是障碍,2是出口这种
回复 支持 反对

使用道具 举报

 楼主| trouble246 发表于 2016-3-22 14:49:25 | 显示全部楼层
夜辉冥 发表于 2016-3-22 14:42
第三轮这个题目没太懂什么意思。 你是如何记录时间的。是有一个进程专门来检测哪些image过期了吗?

我的做法是每当一个image进入cache时给他一个time stamp,存到一个hash table里,用一个heap来保存timestamp,因为同一时间只能update一个image,所以其实timestamp是unique的,然后用一个进程去定时查看heap里的timestamp,过期了就把相应的image去掉,然后当同一个image被再次调用时要更新和他关联的那个timestamp重新存到heap里
回复 支持 反对

使用道具 举报

majia113 发表于 2016-3-23 01:55:50 | 显示全部楼层
矩阵那题不太明白,楼主能在详细举例说说怎么做么?
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-3-23 02:09:24 | 显示全部楼层
最后一轮不就是 windows average ,然后建立一个queue搞定?
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-3-23 02:10:59 | 显示全部楼层
第二轮的迷宫可不可以用dfs做?
回复 支持 反对

使用道具 举报

ok123 发表于 2016-3-23 05:26:22 | 显示全部楼层
trouble246 发表于 2016-3-22 14:49. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我的做法是每当一个image进入cache时给他一个time stamp,存到一个hash table里,用一个heap来保存timest ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
好像可以去掉hashtable
回复 支持 反对

使用道具 举报

 楼主| trouble246 发表于 2016-3-23 11:51:25 | 显示全部楼层
majia113 发表于 2016-3-23 01:55
矩阵那题不太明白,楼主能在详细举例说说怎么做么?

你是说那个迷宫矩阵么?就像以前那种用小钢珠在小盒子里走迷宫的小玩具一样,钢珠一滚起来就只有在撞到墙才会停下,所以每次在选一个方向就要一直走到障碍前一个空才会停。
1 0 0 1 0 0 1
0 0 0 0 1 0 0
1 1 1 0 0 0 1
0 0 0 1 1 1 0. Waral 鍗氬鏈夋洿澶氭枃绔,
就比如上面这个矩阵小球从[1, 0]出发向右,就会停在第二行第四个位置,然后可以选择向下或者向左,以此类推
回复 支持 反对

使用道具 举报

 楼主| trouble246 发表于 2016-3-23 11:53:31 | 显示全部楼层
qiuxuxing007 发表于 2016-3-23 02:09
最后一轮不就是 windows average ,然后建立一个queue搞定?

好像是的吧。。。queue可以做,我用了一个array,反正复杂度应该都是O(n),目前我还没想到更快的
回复 支持 反对

使用道具 举报

 楼主| trouble246 发表于 2016-3-23 11:55:29 | 显示全部楼层
qiuxuxing007 发表于 2016-3-23 02:10
第二轮的迷宫可不可以用dfs做?

面试官说要找最短路径,我就顺着他的意思往下说BFS了。。。DFS肯定也是可以的,只要你一直保存当前最短的path就好吧
回复 支持 反对

使用道具 举报

 楼主| trouble246 发表于 2016-3-23 11:58:28 | 显示全部楼层
ok123 发表于 2016-3-23 05:26
好像可以去掉hashtable

hash table主要是当访问这个cache读取image时可以在constant time内返回只是用来构建heap的话可能可以去掉吧,但面试时没考虑那么细,写了个自己想到能做通的,还特意问了面试官多用一个hashtable好不好?他说没事。。。
回复 支持 反对

使用道具 举报

ok123 发表于 2016-3-23 15:20:34 | 显示全部楼层
走迷宫用BFS 就成了dijkstra 了。用DFS最容易吧
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2016-3-23 15:22):
要算最短,可能真的BFS好
回复 支持 反对

使用道具 举报

ABCamille 发表于 2016-3-24 02:08:46 | 显示全部楼层
怎么办我觉得楼主的题好难啊。。
回复 支持 反对

使用道具 举报

chenyuhaohy 发表于 2016-3-25 09:07:39 | 显示全部楼层
大师兄太牛了。

补充内容 (2016-3-25 09:08):
我觉得最难的就是取硬币和LRU cache了。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-30 04:07:50 | 显示全部楼层
这些题目也不简单啊,楼主厉害!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-30 04:12:20 | 显示全部楼层
请问这个图片压缩必须是整数吗?如果是800x600, C和D是410x410怎么办?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-30 04:14:28 | 显示全部楼层
第二轮感觉还是bfs,只是对于每个位置都应该用个函数求出它上下左右的下一个有效停止点
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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