一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 6346|回复: 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。
. 1point3acres.com/bbs
第二轮,刚开始主要谈论了一下现在项目,然后写了一个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. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3.         public static void main(String[] args) {
  4.                 char[][] matrix = {{'f', 'x', 'x', 'w', 'f'},
  5.                                      {'f', 'f', 'x' ,'x' ,'x'},.鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.                                      {'x', 'x', 'f', 'w', 'f'},
  7.                                      {'f', 'f', 'x', 'w', 'x'}};. 1point 3acres 璁哄潧
  8.                 maxFlowersInGarden(matrix);
  9.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.        
  11.         public static int maxFlowersInGarden(char[][] matrix) {
  12.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  13.                         return 0;
  14.                 }
    .1point3acres缃
  15.                 int m = matrix.length;
  16.                 int n = matrix[0].length;
  17.                
  18.                 int[][] res = new int[m][n];
  19.                 for (int i = 0; i < m; i++) {
  20.                         int count = 0;-google 1point3acres
  21.                         int j = 0;
  22.                         int start = 0;
  23.                         while (j < n) {
  24.                                 if (matrix[i][j] == 'f') {
  25.                                         count++;-google 1point3acres
  26.                                 } else if (matrix[i][j] == 'w') {
  27.                                         for (int k = start; k < j; k++) {
  28.                                                 res[i][k] = count;
  29.                                         }
  30.                                         start = j + 1;
  31.                                         count = 0;
  32.                                 }-google 1point3acres
  33.                                 j++;
  34.                         }. 1point 3acres 璁哄潧
  35.                         for (int k = start; k < j; k++) {. visit 1point3acres.com for more.
  36.                                 res[i][k] = count;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  37.                         }
  38.                 }
  39.                 for (int j = 0; j < n; j++) {
  40.                         int count = 0;
  41.                         int i = 0;
  42.                         int start = 0;
  43.                         while (i < m) {
  44.                                 if (matrix[i][j] == 'f') {
  45.                                         count++;
  46.                                 } else if (matrix[i][j] == 'w') {
  47.                                         for (int k = start; k < i; k++) {
  48.                                                 res[k][j] += count;
  49.                                         }
  50.                                         start = i + 1;
  51.                                         count = 0;
  52.                                 }
  53.                                 i++;
  54.                         }
  55.                         for (int k = start; k < i; k++) {
  56.                                 res[k][j] += count;
  57.                         }
  58.                 }
  59.                 for (int i = 0; i < m; i++) {
  60.                         for (int j = 0; j < n; j++) {
  61.                                 if (matrix[i][j] == 'f') {
  62.                                         res[i][j] -= 1;
  63.                                 }
  64.                         }
  65.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  66.                 int max = 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  67.                 for (int i = 0; i < m; i++) {
  68.                         for (int j = 0; j < n; j++) {
  69.                                 System.out.print(res[i][j] + " ");
  70.                                 max = Math.max(max, res[i][j]);
  71.                         }. from: 1point3acres.com/bbs
  72.                         System.out.println();
  73.                 }
  74.                
  75.                 .1point3acres缃
  76.                 return max;
  77.         }
  78. }
复制代码
回复 支持 0 反对 1

使用道具 举报

hanabeast 发表于 2016-3-10 09:30:28 | 显示全部楼层
能不能问下wall flower是啥题
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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
能不能问下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],
[f, f, x, w, x]]
这样,{3, 0} 和 {1,4}都能看到四朵花。. from: 1point3acres.com/bbs

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

使用道具 举报

 楼主| fdeng001 发表于 2016-3-11 06:24:50 | 显示全部楼层
guixi107 发表于 2016-3-10 14:41
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. From 1point 3acres bbs
第一轮是用四个指针?还有别的办法么?
. Waral 鍗氬鏈夋洿澶氭枃绔,
对就是用四个指针
回复 支持 反对

使用道具 举报

machen982003 发表于 2016-3-13 04:12:41 | 显示全部楼层
fdeng001 发表于 2016-3-11 06:22
给一个two D garden , 每一个slot可以是flower或者Wall. 找一个合适的位置,让游客可以看到最多的flower. ...
. 鍥磋鎴戜滑@1point 3 acres
那这个题是扫四遍的做法么? 做一遍右一遍, 上一遍下一边, 然后求和最大?
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| fdeng001 发表于 2016-3-16 00:57:41 | 显示全部楼层
lawinse 发表于 2016-3-15 17:55-google 1point3acres
感谢楼主0.0 请教一下第一题的四个指针做法具体是什么意思呢?谢谢!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
就是把scan一遍,找到第一大和第二大node的父亲节点并记录下来,然后swap就好了
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-3-28 09:17:03 | 显示全部楼层
楼主那个最长假期问题的递推式没看懂,是不是有typo,能再解释一下吗?谢谢!
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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,面试官对解法满意吗?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| fdeng001 发表于 2016-3-29 07:16:02 | 显示全部楼层
machen982003 发表于 2016-3-13 04:12
那这个题是扫四遍的做法么? 做一遍右一遍, 上一遍下一边, 然后求和最大?
. Waral 鍗氬鏈夋洿澶氭枃绔,
就是扫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
楼主那个最长假期问题的递推式没看懂,是不是有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. Waral 鍗氬鏈夋洿澶氭枃绔,
请问楼主第五轮的第一题是怎么做的,怎么计算 slidingwindow avg, global avg, update(insert) value都可以 ...
. more info on 1point3acres.com
就是保持一个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, 2017-1-24 01:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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