传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2807|回复: 31
收起左侧

骨骼昂赛特

[复制链接] |试试Instant~ |关注本帖
寂寞的季节 发表于 2017-6-11 11:26:39 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 全职@Google - Other - Onsite |Other在职跳槽

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

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

x
这周1才面的,回来回报一下大家~

一共5轮:
1. 印度人但口音不重
Warm up: 输入是一个字符串,写一个function判断这个字符串有没有任意的permutation能够组成一个palindrome。很简单,统计一个每个字符的个数就行了
第2题: 基本跟course schedule一样,有n个event,还有一些这n个event发生的关系,比如{1, 2}表示2要在1之前发生,输出任意的event发生的顺序。拓扑排序,应该是很常见的题目

2. 白人+白人shadow.1point3acres缃
有一个二叉树,有一个节点有2个父亲节点指向了它,删除其中的一条指向它的边,再返回这个二叉树.鐣欏璁哄潧-涓浜-涓夊垎鍦
Follow up: 如果有很多个这样的节点怎么办,需要返回一个valid的二叉树
再Follow up: 如果是BST怎么做,要返回valid的BST. From 1point 3acres bbs
最后再问问怎么unit test,再想一些corner case

3. 印度人印度口音
有一个class是用来写log的,大概是这样:
class Logger {
    void start(int requestID, int timestamp);
    void finish(int requestID, int timestamp);
}
每一个requestID都会start和finish,当一个request finish的时候就可以写入log了,但是log的request必须按照时间顺序排好,意思就是先start的要写在前面
我开始想的是start需要排好序,想用hashmap + treemap,但三哥说start的timestamp一直都是递增的,写了一个hashmap + queue

Lunch: 白人妹子陪吃饭陪聊天

4. 白人妹子
没记错的话应该是一道面经题,输入是一个矩阵,只有0和1,路径只能上下左右包含1,判断这个矩阵是否有一条路径从这个矩阵的第一行到这个矩阵的最后一行. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Follow up: 返回任意一条这样的路径
我还特意问了一下是不是返回最短的路径,妹子看了看题说就返回任意的一条。。dfs或者bfs,分析了一下矩阵会长什么样子和tradeoff,哪种情况下用哪种方法更好

5. ABC
上来先问我用什么语言写,我说Java,他说好,那就假设输入是Java的source file,需要remove source file里面所有的comment,再输出这个文件
对于各种各样的情况讨论了一会,有哪些corner case,然后时间复杂度和空间复杂度,最后才开始写code
最后一轮我有点不太清醒了,code有些小错误没发现,不过总体应该还行
. From 1point 3acres bbs

面完感觉就是。。。略简单。。其实这次面试我准备了很长时间,看了地里的各种面经,然后我准备的什么KMP, BIT, Segment tree,Union find,trie,值二分,区间DP等等这些面经里常见的都没考。。
但是没出结果之前还是很虚,一直在想面试时还有哪些地方应该做得更好。

最后感谢地里每个人每个面经对我的帮助以及每个帖子下积极回答问题的同学们~~求保佑一个offer。。。

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2017-6-14 09:38):
今天好像过HC了,再回来看看,大家加油~~

评分

2

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 462, 订阅: 95
 楼主| 寂寞的季节 发表于 2017-6-14 09:36:48 | 显示全部楼层
jyttwc901231 发表于 2017-6-14 09:11. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请问Lz, 值二分 是什么?

值二分就是按值二分,一般是对最后的结果做二分法
比较的常见的题是这道:410. Split Array Largest Sum
跟lintcode的Copy Books是一样的
Copy Books II 也是,面经里还有些题也可以这么做,改了点描述,一个套路

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

f1371342385 发表于 2017-6-11 11:31:05 | 显示全部楼层
我就好奇 谷歌不是hire freeze了吗 为啥LZ可以拿到面试呀
回复 支持 反对

使用道具 举报

 楼主| 寂寞的季节 发表于 2017-6-11 11:37:40 | 显示全部楼层
f1371342385 发表于 2017-6-11 11:31
我就好奇 谷歌不是hire freeze了吗 为啥LZ可以拿到面试呀

我不知道。。我不是new grad,面试那天也有其他人在check in啊
回复 支持 反对

使用道具 举报

tangkangkai 发表于 2017-6-11 11:42:14 | 显示全部楼层
寂寞的季节 发表于 2017-6-11 11:37. visit 1point3acres.com for more.
我不知道。。我不是new grad,面试那天也有其他人在check in啊
-google 1point3acres
没有考System Design么
回复 支持 反对

使用道具 举报

shunli 发表于 2017-6-11 12:00:34 | 显示全部楼层
感谢分享,狗家又招人了,好消息呀

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

edyyy 发表于 2017-6-11 12:08:50 | 显示全部楼层
谢谢楼主分享,祝楼主好运!!
回复 支持 反对

使用道具 举报

edyyy 发表于 2017-6-11 12:16:22 | 显示全部楼层
"然后我准备的什么KMP, BIT, Segment tree,Union"?? BIT 是啥?
回复 支持 反对

使用道具 举报

 楼主| 寂寞的季节 发表于 2017-6-11 12:21:35 | 显示全部楼层
tangkangkai 发表于 2017-6-11 11:42
没有考System Design么
.1point3acres缃
没考。。5轮都是做题
回复 支持 反对

使用道具 举报

f1371342385 发表于 2017-6-11 12:22:42 | 显示全部楼层
寂寞的季节 发表于 2017-6-11 11:37
我不知道。。我不是new grad,面试那天也有其他人在check in啊

哈哈 看来谷歌又开始有面试了 感谢LZ
回复 支持 反对

使用道具 举报

 楼主| 寂寞的季节 发表于 2017-6-11 12:24:46 | 显示全部楼层
edyyy 发表于 2017-6-11 12:16
"然后我准备的什么KMP, BIT, Segment tree,Union"?? BIT 是啥?

Binary Indexed Tree,最常见的题是Range Sum Query 2D - Mutable
回复 支持 反对

使用道具 举报

scredwood 发表于 2017-6-11 14:18:48 | 显示全部楼层
LZ多久的经验呀,竟然没有系统设计》
回复 支持 反对

使用道具 举报

fatalme 发表于 2017-6-12 00:33:53 | 显示全部楼层
楼主最后一题怎么做的?
回复 支持 反对

使用道具 举报

byrlhb 发表于 2017-6-12 01:54:18 | 显示全部楼层
祝lz好运,顺便问下第二题follow up思路,感觉不是很直观的样子,有很多很复杂的情况要考虑
回复 支持 反对

使用道具 举报

ddcfv 发表于 2017-6-12 02:07:34 | 显示全部楼层
同问lz多少年经验啊?我也是在职跳槽不过onsite被取消了说是junior招满了
回复 支持 反对

使用道具 举报

jy_121 发表于 2017-6-12 12:14:23 | 显示全部楼层
同想问下第二题,谢谢。
回复 支持 反对

使用道具 举报

liuhuan2002767 发表于 2017-6-12 13:33:28 | 显示全部楼层
同求第二题
回复 支持 反对

使用道具 举报

ninja 发表于 2017-6-12 22:13:32 | 显示全部楼层
祝楼主好运啊
回复 支持 反对

使用道具 举报

 楼主| 寂寞的季节 发表于 2017-6-13 07:36:21 | 显示全部楼层
ddcfv 发表于 2017-6-12 02:07
同问lz多少年经验啊?我也是在职跳槽不过onsite被取消了说是junior招满了

如果不算intern的话,应该是2年多吧,onsite还会取消?。。
回复 支持 反对

使用道具 举报

 楼主| 寂寞的季节 发表于 2017-6-13 07:55:12 | 显示全部楼层
那再说下第二题。。
开始面试官给我的例子大概是这样的:
      1
     / \
    2   3. 1point3acres.com/bbs
   / \ / \. Waral 鍗氬鏈夋洿澶氭枃绔,
  4  5   6. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
.1point3acres缃
然后我问面试官要删哪一条边,因为删除其中一条之后都是一个valid的二叉树,面试官想了想说随便
我想的是用一个set来记录每个点,如果遍历的时候已经有父亲节点指向这个点,说明这一条指向这个点边需要赋值成null
当然这个输入可能有很多种情况,比如子节点的左子树或者右指数指向了root节点,所以一开始的时候就要把root加进set里
. more info on 1point3acres.com如果是BST,还需判断节点在不在一个valid BST的range范围内,可参考98. Validate Binary Search Tree这道题。。
回复 支持 反对

使用道具 举报

fatalme 发表于 2017-6-13 08:41:52 来自手机 | 显示全部楼层
最后一题呢?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-23 08:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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