一亩三分地论坛

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

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

Google 不甘心的跪经

[复制链接] |试试Instant~ |关注本帖
lyc1994 发表于 2016-11-22 14:11:33 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 校园招聘会 - Onsite |Otherfresh grad应届毕业生

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

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

x
10月底面的Google onsite,
第一轮三姐,问题是常见的给字典,再给词语前缀,然后返回所有是该前缀的词语,用Trie加DFS做出
. 1point3acres.com/bbs第二轮白人小哥,一开始问了一道至今不懂的问题,好像是一个vector<uint8_t> nums, 然后又一个256位的vector<int> counts,遍nums,然后counts[nums]++如何化,提示要用到CPU cache西(完全不知道)。小白哥见我懵逼,后来又给了一道3sum,迅速做出。
第三轮白人大叔,判断两个binary search tree是否相等,一开始的想法是将tree in order转化为vector然后比较,后来大叔说可以写个iterator来从小到大遍历树,按照他的想法写了写
第四轮白人大叔,问如何表示稀疏矩阵,一开始可以用两个hash table解决,一个的key 是行数,value是一个key为列数value为值的hash table,另一个是key为列数,value是一个key 为行数value为值的hashtable,follow up,如果想要整行,整列删除,设值该用什么结构?没答上来,应该是用十字链表


过两周后加面,伤心的加面,本来LZ还觉得加面好好表现还挺有希望的
第一轮
白人小哥,第一题,判断括号是否合法,秒做,第二题,两个array表示两个整数,相加,秒做,第三题很有意思,给一个逻辑运算树,问最少翻转几个运算符可以翻转最终结果,例如,(True && False) || (False || True),结果是true,若想翻转成false,最少翻转一次(第三个||翻转成为&&),没写code,讨论下来应该分情况讨论然后recursive做


. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷跪在第二轮,白人大叔,题目是部分sort,即sort数组中一半的元素,例如{9, 1, 8, 3, 0} sort成{0, 1, 9, 3, 8},本来用quick sort 加个条件解决即可,但是大叔硬是要我用C++的template,语法忘记,结果卡了三十分钟,大叔也一直不给提示,心态爆炸,最后算法也没用对,面到四十分钟大叔就说有事先走了,真的是不甘心,之前onsite也有一些轮答得不是很好,但没有这么差过,竟然完跪在最后加面一轮。

评分

5

查看全部评分

本帖被以下淘专辑推荐:

3d596d24 发表于 2016-11-23 13:09:06 | 显示全部楼层
比较两个 bst 只需要比较两个的 preorder 一样。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

因为知道 preorder,inorder 就已经确定(BST),然后根据 preorder 和 inorder 就可以还原出一棵 binary tree。
回复 支持 2 反对 0

使用道具 举报

leixiang5 发表于 2016-11-22 14:34:41 | 显示全部楼层
给点大米..安慰下楼主...看开就好...明年再来就好了...运气在面试也占蛮大部分的~
回复 支持 反对

使用道具 举报

luffy_zc 发表于 2016-11-22 15:22:42 | 显示全部楼层
请问一下第三题, in order 的比较方法我有一点疑问?比如 root(1).right(3) 和 root(3).left(1)的in order是一样的,但是树的结构不一样,这种是不是就不适用了? 楼主能解释一下iterator是怎么写的嘛,我只想到递归判断两课树是否相等的写法,不过没有用到BST的性质。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-22 16:52:04 | 显示全部楼层
一半sort 不应该是 0 1 3 吗
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-22 16:52:25 | 显示全部楼层
zyoppy008 发表于 2016-11-22 16:52
一半sort 不应该是 0 1 3 吗
. From 1point 3acres bbs
哦哦 两个也可以
回复 支持 反对

使用道具 举报

在浙里 发表于 2016-11-22 16:58:59 | 显示全部楼层
楼主很厉害了,加油,一定会拿到好公司的offer的。
回复 支持 反对

使用道具 举报

tinyrookie 发表于 2016-11-22 18:48:47 | 显示全部楼层
luffy_zc 发表于 2016-11-22 15:22
请问一下第三题, in order 的比较方法我有一点疑问?比如 root(1).right(3) 和 root(3).left(1)的in order ...

同想知道iterator是怎么写的、、、
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-11-22 22:37:59 | 显示全部楼层
luffy_zc 发表于 2016-11-22 15:22
请问一下第三题, in order 的比较方法我有一点疑问?比如 root(1).right(3) 和 root(3).left(1)的in order ...

Inorder 输出的数组是排序好的,因为是BST所以肯定可以比较。后面的iterator大叔加了两个条件,一个是知道最小那个数的node,另一个是每个node有个parent,这样就很简单了,implement next与hasnext
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-11-22 22:39:14 | 显示全部楼层
leixiang5 发表于 2016-11-22 14:34
给点大米..安慰下楼主...看开就好...明年再来就好了...运气在面试也占蛮大部分的~

并没有明年,要去google只能以后跳槽了sigh...
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-11-22 23:07:38 | 显示全部楼层
lyc1994 发表于 2016-11-22 22:39
并没有明年,要去google只能以后跳槽了sigh...

对啊-.-...那就跳槽咯~~~.
回复 支持 反对

使用道具 举报

MulinZz 发表于 2016-11-22 23:46:23 | 显示全部楼层
加面那个题要怎么做谁知道啊。
回复 支持 反对

使用道具 举报

MulinZz 发表于 2016-11-22 23:47:04 | 显示全部楼层
白人大叔本来就想坑你吧我觉得是,lz加油!!!
回复 支持 反对

使用道具 举报

tinyrookie 发表于 2016-11-23 02:10:38 | 显示全部楼层
lyc1994 发表于 2016-11-22 22:37
Inorder 输出的数组是排序好的,因为是BST所以肯定可以比较。后面的iterator大叔加了两个条件,一个是知 ...

还是没明白啊。。。root(3).left(1)和root(1).right(3)的in-order是一样的呀。。。
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-11-23 02:46:38 | 显示全部楼层
tinyrookie 发表于 2016-11-23 02:10
还是没明白啊。。。root(3).left(1)和root(1).right(3)的in-order是一样的呀。。。

有道理!好像面试的时候那个大叔也没发现,这样的话我感觉还是用recursive做比较靠谱,return (root1.val == root2.val) && IsEqual(root1.left, root2.left) && IsEqual(root1.right, root2.right)
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-11-23 02:47:29 | 显示全部楼层
MulinZz 发表于 2016-11-22 23:46.鐣欏璁哄潧-涓浜-涓夊垎鍦
加面那个题要怎么做谁知道啊。

加面哪道题啊?
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-11-23 02:53:22 | 显示全部楼层
tinyrookie 发表于 2016-11-23 02:10
还是没明白啊。。。root(3).left(1)和root(1).right(3)的in-order是一样的呀。。。

我感觉可以用stack模拟inorder遍历,然后每步需要保证stack的长度是一样的?
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-11-23 02:56:27 | 显示全部楼层
求问第二轮那个优化怎么做呀?
回复 支持 反对

使用道具 举报

MulinZz 发表于 2016-11-23 03:18:46 | 显示全部楼层

大叔那个题
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-11-23 03:26:31 | 显示全部楼层
回复 支持 反对

使用道具 举报

liqingfd 发表于 2016-11-23 12:54:58 | 显示全部楼层
求问楼主在onsite之后多久收到加面的通知呀~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 16:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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