一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 13810|回复: 39
收起左侧

[3/8] Google Onsite

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

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

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

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

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,
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
-google 1point3acres


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

再谢谢地里的栽培哈. From 1point 3acres bbs

评分

5

查看全部评分

本帖被以下淘专辑推荐:

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

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

  2.         public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.                 char[][] matrix = {{'f', 'x', 'x', 'w', 'f'},
  4.                                      {'f', 'f', 'x' ,'x' ,'x'},
  5.                                      {'x', 'x', 'f', 'w', 'f'},. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  6.                                      {'f', 'f', 'x', 'w', 'x'}};
  7.                 maxFlowersInGarden(matrix);-google 1point3acres
  8.         }
  9.        
  10.         public static int maxFlowersInGarden(char[][] matrix) {
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  11.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  12.                         return 0;
  13.                 }
  14.                 int m = matrix.length;. From 1point 3acres bbs
  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;. 1point 3acres 璁哄潧
  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') {. 1point3acres.com/bbs
  26.                                         for (int k = start; k < j; k++) {
  27.                                                 res[i][k] = count;
  28.                                         }
  29.                                         start = j + 1;
  30.                                         count = 0;-google 1point3acres
  31.                                 }
  32.                                 j++;
  33.                         }
  34.                         for (int k = start; k < j; k++) {
  35.                                 res[i][k] = count;. 1point3acres.com/bbs
  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) {. from: 1point3acres.com/bbs
  43.                                 if (matrix[i][j] == 'f') {
  44.                                         count++;
  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;. visit 1point3acres.com for more.
  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;.1point3acres缃
  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.                
  75.                 return max;
  76.         }
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  77. }
复制代码
回复 支持 1 反对 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
能不能问下wall flower是啥题

给一个two D garden , 每一个slot可以是flower或者Wall. 找一个合适的位置,让游客可以看到最多的flower.可以站在flower上,不能站在墙上。。
如果被墙挡了,就看不到墙后面的花。然后游客只能竖直或者水瓶看,不能看对角线。。比如. visit 1point3acres.com for more.
[ [f, x, x, w, f],
[f, f, x ,x ,x],
[x, x, f, w, f],
[f, f, x, w, x]]
这样,{3, 0} 和 {1,4}都能看到四朵花。

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

使用道具 举报

 楼主| 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
第一轮是用四个指针?还有别的办法么?

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

使用道具 举报

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
感谢楼主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
楼主那个最长假期问题的递推式没看懂,是不是有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. 鍥磋鎴戜滑@1point 3 acres
楼主厉害啊! 请问第三轮 "第三轮,RGB颜色转换比如现有#2f3d13,有16进制的00,33,66,99,cc, ff."是怎么做 ...
-google 1point3acres
提示一下,不想说太细了,看看java中round函数是什么样的,怎么实现的
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-24 06:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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