一亩三分地论坛

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

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

[3/8] Google Onsite

[复制链接] |试试Instant~ |关注本帖
fdeng001 发表于 2016-3-9 15:56:44 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 猎头 - Onsite |Other在职跳槽

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

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

x
今天面了google,也是最近面试非常重要的一次,从昨天晚上就非常紧张,地里的面经看了好多遍。非常有帮助,今天的面试总结下来,有难有简单,总体来说是meidum 难度偏上,有几道hard。晚上见证了alphaGo战胜了李世石,感慨科技进步飞快啊卧槽

第一轮,linkedlist,找出最大的两个, 然后swap,不是swap value,swap reference。

第二轮,刚开始主要谈论了一下现在项目,然后写了一个topological sort。
第三轮,RGB颜色转换比如现有#2f3d13,有16进制的00,33,66,99,cc, ff.要把现有的数字转成最close to这几个数字。比如#2f3d13 -> #333300;
              第二题是findNthsmallest element in BST. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第四轮,三道题啊。。。。1. one edit distance 2. wall, flower, matrix找到能看见最多flower的点,地里高频题 3. count of smaller number before itself
第五轮, 给一个API,O(1)时间计算 slidingwindow avg, global avg, update(insert) value;
              第二题,DP, 有几座城市,每个月在每个城市都有不同的假期,然后每个城市有飞往不同城市的航班,求最大能获取的假期和Path. dp(i)(j) 代表第i个月在第j个城市所能获得的最大假期。
             DP 方程大概是 dp(i)(j) = Math.max(dp(i-1)(fromCity)+map(i)(j), dp(i)(j)). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


总体来说题目有难有简单吧,我觉得多多准备看看面经还是可以的,还有推荐九章的高级算法班(对有一定算法基础的同学),我觉得非常有帮助,至少我觉得有些题,上课老师的讲解和题目对我的帮助很大。

再谢谢地里的栽培哈

评分

3

查看全部评分

bobzhang2004 发表于 2016-3-29 12:50:37 | 显示全部楼层
machen982003 发表于 2016-3-13 04:12
那这个题是扫四遍的做法么? 做一遍右一遍, 上一遍下一边, 然后求和最大?

分享下代码吧
  1. public class FlowersInGarden {

  2.         public static void main(String[] args) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.                 char[][] matrix = {{'f', 'x', 'x', 'w', 'f'},
  4.                                      {'f', 'f', 'x' ,'x' ,'x'},. visit 1point3acres.com for more.
  5.                                      {'x', 'x', 'f', 'w', 'f'}, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  6.                                      {'f', 'f', 'x', 'w', 'x'}};.鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.                 maxFlowersInGarden(matrix);
  8.         }
  9.        
  10.         public static int maxFlowersInGarden(char[][] matrix) {
  11.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  12.                         return 0;. from: 1point3acres.com/bbs
  13.                 }
  14.                 int m = matrix.length;
  15.                 int n = matrix[0].length;
  16.                
  17.                 int[][] res = new int[m][n];
  18.                 for (int i = 0; i < m; i++) {
  19.                         int count = 0;
  20.                         int j = 0;
  21.                         int start = 0;
  22.                         while (j < n) {
  23.                                 if (matrix[i][j] == 'f') {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.                                         count++; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.                                 } else if (matrix[i][j] == 'w') {
  26.                                         for (int k = start; k < j; k++) {
  27.                                                 res[i][k] = count;
  28.                                         }
  29.                                         start = j + 1;
  30.                                         count = 0;
  31.                                 }
  32.                                 j++;
  33.                         }
  34.                         for (int k = start; k < j; k++) {
  35.                                 res[i][k] = count;
  36.                         }
  37.                 }
  38.                 for (int j = 0; j < n; j++) {
  39.                         int count = 0;
  40.                         int i = 0;
  41.                         int start = 0;
  42.                         while (i < m) {
  43.                                 if (matrix[i][j] == 'f') {
  44.                                         count++;. Waral 鍗氬鏈夋洿澶氭枃绔,
  45.                                 } else if (matrix[i][j] == 'w') {
  46.                                         for (int k = start; k < i; k++) {
  47.                                                 res[k][j] += count;
  48.                                         }
  49.                                         start = i + 1;
  50.                                         count = 0;
  51.                                 }
  52.                                 i++;
  53.                         }
  54.                         for (int k = start; k < i; k++) {
  55.                                 res[k][j] += count;
  56.                         }
  57.                 }
  58.                 for (int i = 0; i < m; i++) {
  59.                         for (int j = 0; j < n; j++) {
  60.                                 if (matrix[i][j] == 'f') {
  61.                                         res[i][j] -= 1;. 鍥磋鎴戜滑@1point 3 acres
  62.                                 }
  63.                         }
  64.                 }
  65.                 int max = 0;
  66.                 for (int i = 0; i < m; i++) {
  67.                         for (int j = 0; j < n; j++) {
  68.                                 System.out.print(res[i][j] + " ");
  69.                                 max = Math.max(max, res[i][j]);
  70.                         }
  71.                         System.out.println();
  72.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  73.                
  74.                 -google 1point3acres
  75.                 return max;
  76.         }
  77. }. 1point 3acres 璁哄潧
复制代码
回复 支持 0 反对 1

使用道具 举报

hanabeast 发表于 2016-3-10 09:30:28 | 显示全部楼层
能不能问下wall flower是啥题
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-3-10 14:41:28 | 显示全部楼层
lz: #2f3d13 -> #333300可以解释一下怎么转换吗? findNthsmallest element in BST每个节点除了有子节点,还有rank吗?
回复 支持 反对

使用道具 举报

cascade15 发表于 2016-3-10 15:10:51 | 显示全部楼层
第一轮是用四个指针?还有别的办法么?
回复 支持 反对

使用道具 举报

 楼主| fdeng001 发表于 2016-3-11 06:22:52 | 显示全部楼层
hanabeast 发表于 2016-3-10 09:30. more info on 1point3acres.com
能不能问下wall flower是啥题

给一个two D garden , 每一个slot可以是flower或者Wall. 找一个合适的位置,让游客可以看到最多的flower.可以站在flower上,不能站在墙上。。
如果被墙挡了,就看不到墙后面的花。然后游客只能竖直或者水瓶看,不能看对角线。。比如
[ [f, x, x, w, f],
[f, f, x ,x ,x],.鐣欏璁哄潧-涓浜-涓夊垎鍦
[x, x, f, w, f],
. Waral 鍗氬鏈夋洿澶氭枃绔,[f, f, x, w, x]]
这样,{3, 0} 和 {1,4}都能看到四朵花。

找一个点能看到最多的花
回复 支持 反对

使用道具 举报

 楼主| fdeng001 发表于 2016-3-11 06:24:50 | 显示全部楼层
guixi107 发表于 2016-3-10 14:41. visit 1point3acres.com for more.
lz: #2f3d13 -> #333300可以解释一下怎么转换吗? findNthsmallest element in BST每个节点除了有子节点, ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
比如2f 最接近 33对吧,所以就转换成33, 3d 最接近33也转换成33,比如5a->66
findNthsmallest element in BST 就是inorder search 呀
回复 支持 反对

使用道具 举报

 楼主| fdeng001 发表于 2016-3-11 06:25:02 | 显示全部楼层
cascade15 发表于 2016-3-10 15:10
第一轮是用四个指针?还有别的办法么?

对就是用四个指针
回复 支持 反对

使用道具 举报

machen982003 发表于 2016-3-13 04:12:41 | 显示全部楼层
fdeng001 发表于 2016-3-11 06:22
给一个two D garden , 每一个slot可以是flower或者Wall. 找一个合适的位置,让游客可以看到最多的flower. ...

那这个题是扫四遍的做法么? 做一遍右一遍, 上一遍下一边, 然后求和最大?
回复 支持 反对

使用道具 举报

lawinse 发表于 2016-3-15 17:55:37 | 显示全部楼层
感谢楼主0.0 请教一下第一题的四个指针做法具体是什么意思呢?谢谢!
回复 支持 反对

使用道具 举报

 楼主| fdeng001 发表于 2016-3-16 00:57:41 | 显示全部楼层
lawinse 发表于 2016-3-15 17:55. 1point3acres.com/bbs
感谢楼主0.0 请教一下第一题的四个指针做法具体是什么意思呢?谢谢!

就是把scan一遍,找到第一大和第二大node的父亲节点并记录下来,然后swap就好了
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-3-28 09:17:03 | 显示全部楼层
楼主那个最长假期问题的递推式没看懂,是不是有typo,能再解释一下吗?谢谢!
回复 支持 反对

使用道具 举报

simplessssss 发表于 2016-3-28 09:53:14 | 显示全部楼层
请问楼主第五轮的第一题是怎么做的,怎么计算 slidingwindow avg, global avg, update(insert) value都可以得到O(1)的复杂度?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-29 05:20:21 | 显示全部楼层
楼主厉害啊! 请问第三轮 "第三轮,RGB颜色转换比如现有#2f3d13,有16进制的00,33,66,99,cc, ff."是怎么做的呢?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-29 05:21:09 | 显示全部楼层
请问” count of smaller number before itself“ 这个题楼主是选择建树还是divide and conquer,面试官对解法满意吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-29 05:22:00 | 显示全部楼层
楼主可以给下“求最大能获取的假期和Path. ”的具体代码吗?看到很多次这个题,但还是不清楚具体怎么做
回复 支持 反对

使用道具 举报

 楼主| fdeng001 发表于 2016-3-29 07:16:02 | 显示全部楼层
machen982003 发表于 2016-3-13 04:12.鐣欏璁哄潧-涓浜-涓夊垎鍦
那这个题是扫四遍的做法么? 做一遍右一遍, 上一遍下一边, 然后求和最大?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
就是扫4遍,可以简化一下控制一个一头一尾的指针,这样就是O(2mn)
回复 支持 反对

使用道具 举报

 楼主| fdeng001 发表于 2016-3-29 07:18:23 | 显示全部楼层
lawinse 发表于 2016-3-15 17:55
感谢楼主0.0 请教一下第一题的四个指针做法具体是什么意思呢?谢谢!

其实是两个指针,就是保持两个parent node pointer, 如果有一个比max_parent 大就替换 max_parent, 并且把 max_parent 复制给sec_parent,如果比sec_parent大就替换sec_parent,否则不动,loop一遍以后swap一下parent的child
回复 支持 反对

使用道具 举报

 楼主| fdeng001 发表于 2016-3-29 07:20:20 | 显示全部楼层
singledog2016 发表于 2016-3-28 09:17. 鍥磋鎴戜滑@1point 3 acres
楼主那个最长假期问题的递推式没看懂,是不是有typo,能再解释一下吗?谢谢!

dp(i)(j) = Math.max(dp(i-1)(fromCity)+map(i)(j), dp(i)(j))
就是说第i 个月在第j个城市的最大假期肯定是从第i-1个月从飞过来的城市的最大假期+当前假期中的最大值,还是比较好理解的吧
回复 支持 反对

使用道具 举报

 楼主| fdeng001 发表于 2016-3-29 07:21:15 | 显示全部楼层
simplessssss 发表于 2016-3-28 09:53
请问楼主第五轮的第一题是怎么做的,怎么计算 slidingwindow avg, global avg, update(insert) value都可以 ...

就是保持一个queue with sliding sizeK,sum, 然后加一个数就check一下
回复 支持 反对

使用道具 举报

 楼主| fdeng001 发表于 2016-3-29 07:23:23 | 显示全部楼层
bobzhang2004 发表于 2016-3-29 05:20
楼主厉害啊! 请问第三轮 "第三轮,RGB颜色转换比如现有#2f3d13,有16进制的00,33,66,99,cc, ff."是怎么做 ...

提示一下,不想说太细了,看看java中round函数是什么样的,怎么实现的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 22:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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