《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 13477|回复: 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.



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

再谢谢地里的栽培哈

评分

5

查看全部评分

本帖被以下淘专辑推荐:

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'}};
  8.                 maxFlowersInGarden(matrix);
  9.         }. 1point3acres.com/bbs
  10.         . 1point3acres.com/bbs
  11.         public static int maxFlowersInGarden(char[][] matrix) {
  12.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  13.                         return 0;
  14.                 }
  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;. 1point3acres.com/bbs
  21.                         int j = 0;
  22.                         int start = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  23.                         while (j < n) {
  24.                                 if (matrix[i][j] == 'f') {
  25.                                         count++;
  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;
    . 1point 3acres 璁哄潧
  32.                                 }
  33.                                 j++;
  34.                         }
  35.                         for (int k = start; k < j; k++) {
  36.                                 res[i][k] = count;
  37.                         }. From 1point 3acres bbs
  38.                 }
  39.                 for (int j = 0; j < n; j++) {
  40.                         int count = 0;
  41.                         int i = 0;
  42.                         int start = 0;. 1point 3acres 璁哄潧
  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++) {. 鍥磋鎴戜滑@1point 3 acres
  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++) {. more info on 1point3acres.com
  68.                         for (int j = 0; j < n; j++) {-google 1point3acres
  69.                                 System.out.print(res[i][j] + " ");. 1point 3acres 璁哄潧
  70.                                 max = Math.max(max, res[i][j]);
  71.                         }
  72.                         System.out.println();
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  73.                 }
  74.                
  75.                
  76.                 return max;
  77.         }
  78. }
复制代码
回复 支持 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. visit 1point3acres.com for more.
能不能问下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}都能看到四朵花。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
找一个点能看到最多的花
回复 支持 反对

使用道具 举报

 楼主| 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. ...
. from: 1point3acres.com/bbs
那这个题是扫四遍的做法么? 做一遍右一遍, 上一遍下一边, 然后求和最大?
回复 支持 反对

使用道具 举报

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. 鍥磋鎴戜滑@1point 3 acres
那这个题是扫四遍的做法么? 做一遍右一遍, 上一遍下一边, 然后求和最大?

就是扫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))-google 1point3acres
就是说第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. 1point3acres.com/bbs
楼主厉害啊! 请问第三轮 "第三轮,RGB颜色转换比如现有#2f3d13,有16进制的00,33,66,99,cc, ff."是怎么做 ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-22 23:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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