一亩三分地论坛

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

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

Google新鲜面经,攒人品

[复制链接] |试试Instant~ |关注本帖
longteng6046 发表于 2015-8-26 23:55:06 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Google - Other - Onsite |Otherfresh grad应届毕业生

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

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

x
面完攒人品求offer帖。
. from: 1point3acres.com/bbs
一共五轮,其中一轮讨论博士论文,四轮技术面。感觉都比较常规的题,没有leetcode上的难题。可能跟多注重思路和交流吧。以下题目混着给了。

1. 给定双曲线方程y = a* x * x + b * x + c和一个排好序的数组,求输出一个数组,包含所有y的排序后的值。
2. 给定一个数组,求所顺序遍历为这个数组binary tree的个数。经典题了。
. from: 1point3acres.com/bbs 3. 设计题,给定f(x,y),如果有海量数据分布在1000台机器上,每个机器中存放巨大(x,y) pair,如何取得使得f(x,y)最大的pair?
4. 假设定义两个数字串symmetric: 数字串翻转后和以前一样。例如:121和1221,翻转后依然是自己。同时如果2翻转后变成5,5翻转后变成2,
    6和9互相翻转,0,1和8翻转后是自己,别的数字(3,4,7)翻转后无效。例如12翻转后是51,71翻转后无效。给定一个n,求所有长度为n的翻转
    后有效并且和原数字串symmetric的数字串。 follow up: 如何多机scale?
5. Binary Tree求and操作。例如:
        *                  *                    *
      /   \              /   \                /    \
     1    *   and    *     0  =        *      0
         /  \          / \                 /  \
        0   1        1   0              1   0
     Follow up: deepCopy(tree)
     Follow up2: 如何合并结果中出现的情况?
          * -google 1point3acres
        /   \    =>      0
       0    0
. 鍥磋鎴戜滑@1point 3 acres
题目基本就这样。求大家bless,赶紧拿到offer.


.鏈枃鍘熷垱鑷1point3acres璁哄潧补充内容 (2015-10-17 05:07):
拿到offer了,过来还愿,感谢大家的blessing。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| longteng6046 发表于 2015-10-12 04:05:35 | 显示全部楼层
returning 发表于 2015-10-12 03:31
我的意思其实是说,中间的88可以由一台机器获得,两边的11也由一台机器获得,他们的工作其实是重复的。也 ...

我们想的算法可能不一样。我的算法是,当已知N=2:{00,11,88, 69, 96, 52, 25}的时候,生成N=4的过程即为在每个N=2的基础上两边同时加0,1,8,或者配对加(6,9), (9,6), (2,5), (5,2) 就好了。所以结果是:{{0000, 1001, 8008, 6009, 9006, 2005, 5002}, {0110, 1111, 8118, 6119, 9116, 2115, 5112, …}}。可见,对应N-2中每一个数字串,求得它对应的长度为N的生产集的过程是完全独立于别的数字的。所以只要把N-2的字符串们平均分配到一定机器上,他们求得N的运算过程就是完全独立的。
回复 支持 1 反对 0

使用道具 举报

 楼主| longteng6046 发表于 2015-8-27 11:33:58 | 显示全部楼层
wenqiang88 发表于 2015-8-27 10:27. from: 1point3acres.com/bbs
valid是指说不能以0开始。然后symmetric的话,0,1,8自身就是symmetric的,6和9, 2和5是互相symmetric。
...
.1point3acres缃
抱歉是我没说清楚。这里symmetric是指数字串经过180度翻转后依然和自己一样。valid是指数字串不包含3,4,7三个数字,因为他们180度翻转后不等于任何别的数字。面试官说,2翻转后等于5,5翻转后等于2,6和9翻转后呼唤。所以by definition,单个数字0,1,8翻转后都等于自己,所以是symmetric的;3,4,7翻转后invalid,所以不symmetric,而2,5,6,9翻转后不等于自己,所以也不symmetric。因此,长度为1的symmetric数字串就只包含[0,1,8]。类似定义,长度为2的symmetric数字串包含[00,11,88, 69, 96, 52, 25]。题目所求的,是给定长度n,求出所有长度为n的symmetric数字串。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

jiebour 发表于 2015-8-27 01:08:24 | 显示全部楼层
楼主,第二题是什么遍历顺序?前中后?而且如果是普通二叉树的话,不需要给数组吧?就给个N就可以作为输入了吧
回复 支持 反对

使用道具 举报

 楼主| longteng6046 发表于 2015-8-27 01:13:16 | 显示全部楼层
jiebour 发表于 2015-8-27 01:08.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主,第二题是什么遍历顺序?前中后?而且如果是普通二叉树的话,不需要给数组吧?就给个N就可以作为输入 ...

第二题是inorder遍历。对的,其实不需要数组,只需要数字。也许给的数组算是干扰吧。
回复 支持 反对

使用道具 举报

donghao 发表于 2015-8-27 01:20:16 | 显示全部楼层
楼主第一题 如何解??没想明白
回复 支持 反对

使用道具 举报

 楼主| longteng6046 发表于 2015-8-27 01:51:49 | 显示全部楼层
donghao 发表于 2015-8-27 01:20
楼主第一题 如何解??没想明白

y的值其实是双曲线. 取决于a的正负,必定有最高值或者最低值.那么对于已经排序的x输入,要么掉在双曲线的一侧,所以输出的y也是有序的;要么生成一个先减后增或者先增后减的输出.只要在运算中检测y的变化趋势,如果有增减趋势变化,那么把递增和递减的y的值放在两个array中,然后合并就好了.O(n)复杂度.
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-27 01:57:31 | 显示全部楼层
longteng6046 发表于 2015-8-27 01:13
第二题是inorder遍历。对的,其实不需要数组,只需要数字。也许给的数组算是干扰吧。

明白了。。。这样的话,就瞬间变成leetcode原题了。。。。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-8-27 01:57:42 | 显示全部楼层
求问第三题LZ思路,是每台机器上的pair都带入f(x,y)算一遍,求出最大的pair,然后再从1000个最大的里面选出最大的么?
回复 支持 反对

使用道具 举报

 楼主| longteng6046 发表于 2015-8-27 02:09:53 | 显示全部楼层
抱歉第三题描述有误. 重新说一下: 假设你有billion数量级的key, 分别存放在1000台电脑上. 现在给你一个f(x, y)函数, 对应两个key: x和y, 可以获得一个value. 要求设计一个运算系统, 对所有key的combination求value, 并且获得value最大的一对(x, y) pair. 设计思路其实就是mapReduce()啦,细节主要涉及不同node之间数据的传输, 以及任务的分配.
回复 支持 反对

使用道具 举报

donghao 发表于 2015-8-27 02:13:29 | 显示全部楼层
longteng6046 发表于 2015-8-27 01:51. more info on 1point3acres.com
y的值其实是双曲线. 取决于a的正负,必定有最高值或者最低值.那么对于已经排序的x输入,要么掉在双曲线的一 ...
. 鍥磋鎴戜滑@1point 3 acres
大致明白了,是不是就是先求出来说有的 y 值,而y值得变化那么是由减变增,那么就是由增变减,把递减的放在一个数组中,把递增的放入到一个数组中,然后merge 就行了,是这样吗???
回复 支持 反对

使用道具 举报

donghao 发表于 2015-8-27 02:14:11 | 显示全部楼层
jiebour 发表于 2015-8-27 01:57
明白了。。。这样的话,就瞬间变成leetcode原题了。。。。

对呀,直接就是那个 unique BST,对吧
回复 支持 反对

使用道具 举报

 楼主| longteng6046 发表于 2015-8-27 02:17:11 | 显示全部楼层
donghao 发表于 2015-8-27 02:13
大致明白了,是不是就是先求出来说有的 y 值,而y值得变化那么是由减变增,那么就是由增变减,把递减的放 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
对的.不过求y值和寻找渐变规律可以放到同一次遍历里面, 这样就不需要两次访问x的数组了.
回复 支持 反对

使用道具 举报

 楼主| longteng6046 发表于 2015-8-27 02:18:55 | 显示全部楼层
这个板块无法update已发布的内容? 原帖第三题描述有误, 却没办法修改, 郁闷...
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-27 02:20:24 | 显示全部楼层
longteng6046 发表于 2015-8-27 02:18
这个板块无法update已发布的内容? 原帖第三题描述有误, 却没办法修改, 郁闷...

楼主,你直接回复吧。。。。
求说清。。。
thanks!
回复 支持 反对

使用道具 举报

 楼主| longteng6046 发表于 2015-8-27 02:25:28 | 显示全部楼层
jiebour 发表于 2015-8-27 02:20
楼主,你直接回复吧。。。。
求说清。。。
thanks!

clarification已经贴在八楼啦 :)
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-27 03:01:27 | 显示全部楼层
楼主,※号表示到底是啥意思?最后一题。。。。
回复 支持 反对

使用道具 举报

 楼主| longteng6046 发表于 2015-8-27 03:03:40 | 显示全部楼层
jiebour 发表于 2015-8-27 03:01
楼主,※号表示到底是啥意思?最后一题。。。。
. From 1point 3acres bbs
*表示Internal node, 不含数值的. 只有leaf node含有0或者1的值.
回复 支持 反对

使用道具 举报

laurie洁 发表于 2015-8-27 03:19:31 | 显示全部楼层
求问楼主,第三题是考MapReduce吗?
回复 支持 反对

使用道具 举报

 楼主| longteng6046 发表于 2015-8-27 03:26:22 | 显示全部楼层
laurie洁 发表于 2015-8-27 03:19
求问楼主,第三题是考MapReduce吗?
. From 1point 3acres bbs
对的.主楼的描述有点问题,我无法修改,请看我八楼的介绍:)
回复 支持 反对

使用道具 举报

laurie洁 发表于 2015-8-27 06:30:55 | 显示全部楼层
谢谢楼主~能再问问最后那个binary tree求and吗?看不懂~~~TT
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-27 06:46:20 | 显示全部楼层
楼主电面面金可以分享吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 13:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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