一亩三分地论坛

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

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

两个月前的Google Onsite跪经, 时间有些久远,但希望可以帮助到大家

[复制链接] |试试Instant~ |关注本帖
chm34 发表于 2016-9-23 05:12:19 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - Onsite |Failfresh grad应届毕业生

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

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

x
由于楼主拖延症重度患者,现在奉上两个多月前的Google onsite跪经,希望可以帮助到大家。
话不多说,进入正题。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
电面 (白人大叔):
Question 1: LC 162 find peak element.
Question 2: LC 340 longest substring with at most K distinct charactes.  . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
         Follow up: Input is a char stream instead of a string.
Question 3: We want to transmit billions of var-length integer from source to distination, how to decode them in order to make the information to be sent as little as possible.. 1point3acres.com/bbs
                void encode(int data) { ... }
              PS: "var-length" means the number of digits of those integers can be variable, say, the length of "1" is 1 and the length of "248796" is 6.. 1point 3acres 璁哄潧
. 鍥磋鎴戜滑@1point 3 acres

Onsite:
Round 1 (年长三哥):
     Question 1: 给一个无限大的围棋棋盘,棋盘上的横纵线交点被称为grid。如果一个点是放在棋盘的grid上的,那么我们称这个点是on-grid的。求证明给任意5个on-grid的点,
                        必然至少存在两个点,他们连线的中点也是on-grid的。
     Question 2: 有一个set, 里面的数是从1到N, 要求将这个set分成两个部分Subset1和Subset2, 使得subset1里的数的和 与 subset2里的数的和相等, 问共有多少种分法。
                         比如N=4, 那么就只有{{1, 4},{2, 3}} 这1种分法,返回1.
                         楼主给出backtracking的解法。Follow up: 要求优化 time complexity。这里楼主没有写完代码。.鐣欏璁哄潧-涓浜-涓夊垎鍦

Round 2 (白人小哥):
     Question  1: 某一个股票的stock price时刻在发生变化,变化的price是 {timestamp, newPrice} 的stream形式输入的。但是由于会有错误发生,会需要更新之前的某个时刻的price.
                         例如输入的steam为{0, 2.01}, {1, 3.87}, {2, 4.53}, {3, 2.21}, {2, 1.44}. 最后这次的{2, 1.44} 就是对之前的{2, 4.53}这个错误的修正。
                         要求设计data structure and algorithm 实现以下几个methods:
                         1) 返回某个时刻的price: getPrice(int timestamp);
                         2) 返回最新的price: getNewestPrice();   
                         3) 返回历史最高和最低price: getHighestPrice();  getLowestPrice();
          中间夹杂问了好多问题: 比如stock price用什么类型的数据存储?答float, 问:float在做加减乘除计算后可能会有精确度的偏移,还可以其他什么类型?答string, 问:string是object,
         占用空间较多,还可以什么类型?楼主没有想出来,经提示得知就可以用int..

Round 3 (白人小哥):
      Question 1: 一个围棋棋盘,如果一个白子的group完全被黑子全部包围住,被黑子包围住的这个区域里无法再放任何白子了,那么称这个白子group是一个dead group. 现在要求实现一个.1point3acres缃
                        method来检测棋盘里是否有黑子或者白子的dead group。只要有,就返回true。 input类型自己定义。
                         Follow up: time / space complextiy 优化
. From 1point 3acres bbs
Round 4 (很nice的国人小哥):
      Question 1: 给一个int array, 这个array只读,不可以修改。如果要求从某个位置切一刀,分割这个array, 使得前半段array里的和 等于 后半段array里的和,问共多少种切割方法?
      Question 2: 同样的问题,现在要求切两刀,分成3段,要求这三段每段的和都相等,多少种切割方法?要求O(N) time complexity.

四轮下来,楼主都做出来了,但是也感觉没有一轮表现的很好的,都中规中矩,其中第一轮没有写完代码,所以还是跪了。
现在把面经分享出来,也希望能帮助到坛子里的同学。对于题目有问题的话可以和我交流,就酱~
. 1point3acres.com/bbs


. Waral 鍗氬鏈夋洿澶氭枃绔,
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2016-9-23 05:14):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
对了,Round 2里还需要实现一个method是void remove(int timestamp),要求删除某个时刻的price

评分

4

查看全部评分

本帖被以下淘专辑推荐:

hcheng81 发表于 2016-10-4 02:45:31 | 显示全部楼层
Round 1 Q2,看下对不对?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  1. public static int read(int n) {. visit 1point3acres.com for more.
  2.                 int target = 0;
  3.                 for (int i = 1; i <= n; i++) {. from: 1point3acres.com/bbs
  4.                         target = target + i; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.                 }
  6.                 if (target % 2 == 1) {
  7.                         return 0;
  8.                 }
  9.                 target = target / 2;
  10.                 int[][] dp = new int[n + 1][target + 1];
  11.                 dp[0][0] = 1;
  12.                 for (int i = 1; i < dp.length; i++) {. 1point3acres.com/bbs
  13.                         for (int j = 0; j < dp[0].length; j++) {
  14.                                 dp[i][j] = dp[i - 1][j];
  15.                                 if (j - i >= 0) {
  16.                                         dp[i][j] += dp[i - 1][j - i];
  17.                                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  18.                         }
  19.                 }
  20.                 return dp[dp.length - 1][dp[0].length - 1] / 2;
  21.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

daniel_hl 发表于 2016-9-23 08:06:19 | 显示全部楼层
第一题是奇偶判断把,分析一下几种情况就行
回复 支持 1 反对 0

使用道具 举报

 楼主| chm34 发表于 2016-9-23 08:55:27 | 显示全部楼层
xpli521 发表于 2016-9-23 08:08
问一下楼主电面Q3怎么做的?
另外dead group的话,
我现在想的是 先找一下有没有和白子同一个row的黑子, ...

电面Q3当时就是var-length这个信息给了我提示,就想到用类似trie的结构就行了,结点里存储当前这个数字出现的frequency。而且因为integer最长也就10位,所以trie的高度最多为10
回复 支持 1 反对 0

使用道具 举报

calalia 发表于 2016-9-23 05:50:55 | 显示全部楼层
哇塞 好多围棋棋盘
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-9-23 05:58:07 | 显示全部楼层
Round2遇到了,楼主早发就好了。感觉自己也是中规中矩,要多久知道feedback啊。
回复 支持 反对

使用道具 举报

calalia 发表于 2016-9-23 06:57:13 | 显示全部楼层
话说 Round 1的第一个 问题 难道就是个证明题么
回复 支持 反对

使用道具 举报

NakedKID 发表于 2016-9-23 07:19:53 | 显示全部楼层
Round 1, Q1 这种题都能出,都做出来已经很不简单了
回复 支持 反对

使用道具 举报

calalia 发表于 2016-9-23 07:39:46 | 显示全部楼层
NakedKID 发表于 2016-9-22 17:19
Round 1, Q1 这种题都能出,都做出来已经很不简单了
. 1point 3acres 璁哄潧
这看起来真的太像奥数题了 然而已经忘记了奥数选拔赛的套路
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-23 08:08:58 | 显示全部楼层
问一下楼主电面Q3怎么做的?. Waral 鍗氬鏈夋洿澶氭枃绔,
另外dead group的话,
我现在想的是 先找一下有没有和白子同一个row的黑子,有的话,从这个黑子开始,四个方向dfs,target就是现在这个黑子。就是说如果能返回,就是true,否则false。楼主有啥好建议吗
回复 支持 反对

使用道具 举报

Romeobaby 发表于 2016-9-23 08:27:09 | 显示全部楼层
楼主能全部想出思路已经超厉害了。在现场那么紧张的情况下。水平好高。
回复 支持 反对

使用道具 举报

 楼主| chm34 发表于 2016-9-23 08:51:00 | 显示全部楼层
gaocan1992 发表于 2016-9-23 05:58
Round2遇到了,楼主早发就好了。感觉自己也是中规中矩,要多久知道feedback啊。

额 看来下次还是要早点发。。onsite完了大概2个多礼拜收到的拒信
回复 支持 反对

使用道具 举报

 楼主| chm34 发表于 2016-9-23 08:51:35 | 显示全部楼层
calalia 发表于 2016-9-23 06:57
话说 Round 1的第一个 问题 难道就是个证明题么

对的 不用写代码 就口述思路
回复 支持 反对

使用道具 举报

 楼主| chm34 发表于 2016-9-23 08:52:38 | 显示全部楼层
NakedKID 发表于 2016-9-23 07:19
Round 1, Q1 这种题都能出,都做出来已经很不简单了

我以前记得看过有面经好像考过类似的,所以当时才能想出思路,不然感觉现场想出来也不是特别容易
回复 支持 反对

使用道具 举报

 楼主| chm34 发表于 2016-9-23 08:53:00 | 显示全部楼层
daniel_hl 发表于 2016-9-23 08:06. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一题是奇偶判断把,分析一下几种情况就行

对的 字数字数字数
回复 支持 反对

使用道具 举报

daddyyang 发表于 2016-9-23 08:54:05 | 显示全部楼层
请问LZ Round2 是怎么设计的?我现在想的是用Linked List + Hash Table,不知道对不对
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-9-23 08:59:39 | 显示全部楼层
觉得LZ的功底应该挺强了,没过可惜,不过以你的水平肯定能拿到好offer
回复 支持 反对

使用道具 举报

 楼主| chm34 发表于 2016-9-23 09:05:19 | 显示全部楼层
xpli521 发表于 2016-9-23 08:08
问一下楼主电面Q3怎么做的?.1point3acres缃
另外dead group的话,
我现在想的是 先找一下有没有和白子同一个row的黑子, ...

dead group 楼主当时的方法就是从当前点bfs或者dfs,同时记着那个点的颜色,比如当前点是黑色,那么就从这个点bfs或者dfs黑子点,看能不能search到一个空点,如果search到了那么就返回true. 1point 3acres 璁哄潧

补充内容 (2016-9-23 09:16):
打错了 如果search到空点,就backtracking, 将所有dfs到的点都标记为活点。之后再从下个点做dfs的时候,只要dfs到了活点就不用再search了,因为肯定这个点也肯定是活点了
回复 支持 反对

使用道具 举报

wzy1991527 发表于 2016-9-23 09:07:26 | 显示全部楼层
感觉楼主没过真是有点心疼,那么好的机会啊。希望能拿到ONSITE
回复 支持 反对

使用道具 举报

 楼主| chm34 发表于 2016-9-23 09:20:46 | 显示全部楼层
wzy1991527 发表于 2016-9-23 09:07
感觉楼主没过真是有点心疼,那么好的机会啊。希望能拿到ONSITE

G家的要求还是蛮高的,所以还是看开了,而且表现的确没有想象中发挥的好
回复 支持 反对

使用道具 举报

 楼主| chm34 发表于 2016-9-23 09:25:06 | 显示全部楼层
daddyyang 发表于 2016-9-23 08:54
请问LZ Round2 是怎么设计的?我现在想的是用Linked List + Hash Table,不知道对不对

我是用的hashtable+priorityQueue的方法
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 16:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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