[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4718|回复: 26
收起左侧

攒人品

[复制链接] |试试Instant~ |关注本帖
johnnywsd 发表于 2014-11-8 12:07:27 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Other |

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

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

x
1. 有这么个游戏,举个例子:给你5个空_ _ _ _ _, 每次猜一个字母,这里出题人想让你猜出来clock,假如你猜a,告诉你这里面没有。你又猜c,他把c全写出来,所以你有c _ _ c _。 让你最多猜10次。写一个程序去猜。输入是几个空,要考虑每次猜的反馈,尽量把词猜出来。. Waral 博客有更多文章,
2. 坐标系第一象限上加射线,接下来所有输入的数据都是不相等的整数,不用考虑任何edge case。 想要这两个操作:1. insertX(x), insertY(y),比如insertX, 就是现有的图上面加上x这条射线,象限会被插入的这些射线分成网格,每个格叫一个区域。 2. find(x,y), 就是给个坐标,返回这个坐标所在的区域。可以返回区域的id,区域的id自己定。用二叉树。.1point3acres网
3. 大整数加法,我去,还结结实实问了45分钟...
4. 1. 两个数组,问是不是permutation。 然后如果只能用constant space怎么做:quicksort。然后如果再让这两个数组是imutable,而且只能是n的复杂度,那不可能有办法给出正确答案,给出的答案可以是错的,可以怎么做:找他们的几个次序统计量比一比,一样就说是,不一样就说不是。如果得到不是,那一定不是,如果得到是,那可能不是。
   2. 二叉树直径,用dp达到n的复杂度。



补充内容 (2014-11-24 09:09):
已offer,谢谢大家的人品。

评分

2

查看全部评分

北美农民 发表于 2014-11-8 12:35:01 | 显示全部楼层
第1,2题能更清楚些么, 输入是啥, 输出是啥。
回复 支持 反对

使用道具 举报

ctozlm 发表于 2014-11-8 14:22:30 | 显示全部楼层
第二题是二叉树吗? 怎么觉得应该用quad tree,或者是带四个坐标的二叉树。 但是不管哪一种,每次insert都要更新数个branch。不知道lz能不能给点提示?谢谢
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-9 01:46:16 | 显示全部楼层
ctozlm 发表于 2014-11-8 14:22
第二题是二叉树吗? 怎么觉得应该用quad tree,或者是带四个坐标的二叉树。 但是不管哪一种,每次insert都 ...

这个题不用二叉树。yongskew的方法来做index 就可以的。

比如 我们假设水平方向是x轴, 垂直方向是y轴, 则你可以按如下方式做index
0    1     3      6      10   ......                                       
2    4      7     11  ......   
5      8    12   .....
9     13  ....
.留学论坛-一亩-三分地14  ....



回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-9 02:06:18 | 显示全部楼层
什么叫直径,宽度?
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-9 02:09:47 | 显示全部楼层
4.1 是在在immutable的情况下,然后,也不能用O(n)的memory?. 围观我们@1point 3 acres


补充内容 (2014-11-9 02:23):
我想明白了。谢谢。不用O(n)的memory。constant memory是可以的。
回复 支持 反对

使用道具 举报

zhenggao1986 发表于 2014-11-9 04:46:19 | 显示全部楼层
averillzheng 发表于 2014-11-9 02:09. from: 1point3acres
4.1 是在在immutable的情况下,然后,也不能用O(n)的memory?

immutable O(n) memory O(n) time hashmap 搞一下
mutable O(1) memory O(nlogn) time quicksort 搞一下
immutable O(1) memory O(n) time 正确性不保证的话,用几个统计量大概看看就好
回复 支持 反对

使用道具 举报

lin126 发表于 2014-11-9 04:49:40 | 显示全部楼层
楼主,你是在哪里面的呀? NYC 吗?Mountain View?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

zhenggao1986 发表于 2014-11-9 04:55:20 | 显示全部楼层
averillzheng 发表于 2014-11-9 02:06 来源一亩.三分地论坛.
什么叫直径,宽度?

直径那个应该说的是找一个Node之间最大距离吧,二叉树标准题
int maxDistance(Node* root) {
        int depth = 0;
        return maxDistanceHelper(root, depth); . 1point3acres
}
. from: 1point3acres
int maxDistanceHelper(Node* root, int &depth) { . 围观我们@1point 3 acres
        if (root == NULL) {.本文原创自1point3acres论坛
                depth = 0;
                return 0;
        }
        int leftDepth = 0, rightDepth = 0;
        int maxDistanceFromLeft = maxDistanceHelper(root->left, leftDepth);
        int maxDistanceFromRight = maxDistanceHelper(root->right, rightDepth);
        depth = max(leftDepth, rightDepth) + 1;
        return max(leftDepth + rightDepth + 1, max(maxDistanceFromLeft, maxDistanceFromRight));
}
回复 支持 反对

使用道具 举报

ctozlm 发表于 2014-11-9 06:19:06 | 显示全部楼层
averillzheng 发表于 2014-11-9 01:46. 围观我们@1point 3 acres
这个题不用二叉树。yongskew的方法来做index 就可以的。
-google 1point3acres
比如 我们假设水平方向是x轴, 垂直方向是y轴 ...
. 1point 3acres 论坛
没看懂,分割的是网格,如何用tree表示。id随机分配然后去重也行吧,貌似不是考点,而且插入的顺序是随机的。。
回复 支持 反对

使用道具 举报

yannan 发表于 2014-11-9 06:21:22 | 显示全部楼层
zhenggao1986 发表于 2014-11-9 04:46
immutable O(n) memory O(n) time hashmap 搞一下
mutable O(1) memory O(nlogn) time quicksort 搞一下 ...

这个4.1题(两个数组,问是不是permutation,)能解释一下吗,一直没看明白题
回复 支持 反对

使用道具 举报

zhenggao1986 发表于 2014-11-9 08:25:46 | 显示全部楼层
yannan 发表于 2014-11-9 06:21
这个4.1题(两个数组,问是不是permutation,)能解释一下吗,一直没看明白题

这个就是判断一个数组里面的数是不是和另一个数组里面的数一样呀
如果可以另外用空间的话,你用hashmap做一下就好啦。. visit 1point3acres for more.
不可以另外用空间的话,你就排序比较一下。
如果immutable的话那就是说,数组内部的数据不可以交换变化了,那排序就不能用,如果还不让用额外空间,那就没法O(N)时间判断了,只能找几个顺序统计数大概判断一下,比如最大值,最小值,均值,方差,中位数之类的...
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2014-11-9 08:31:13 | 显示全部楼层
第一题其实就是经典的游戏 hangman......wiki之..
回复 支持 反对

使用道具 举报

yannan 发表于 2014-11-9 09:28:28 | 显示全部楼层
zhenggao1986 发表于 2014-11-9 08:25
这个就是判断一个数组里面的数是不是和另一个数组里面的数一样呀
如果可以另外用空间的话,你用hashmap ...

多谢解释!现在明白了. 之前理解错了哈
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-9 09:46:55 | 显示全部楼层
ctozlm 发表于 2014-11-9 06:19. 牛人云集,一亩三分地
没看懂,分割的是网格,如何用tree表示。id随机分配然后去重也行吧,貌似不是考点,而且插入的顺序是随机 ...
. 留学申请论坛-一亩三分地
按我给的方法,每个格子的index可以由x,y的值算出来。和 insertX,insertY,和find(x,y)调用的次序一毛钱关系都没有。
回复 支持 反对

使用道具 举报

ctozlm 发表于 2014-11-9 10:43:00 | 显示全部楼层
averillzheng 发表于 2014-11-9 09:46
按我给的方法,每个格子的index可以由x,y的值算出来。和 insertX,insertY,和find(x,y)调用的次序一 ...

谁告诉你grid是均匀的了,这和skew半毛钱关系都没有。。。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-9 23:40:16 | 显示全部楼层
ctozlm 发表于 2014-11-9 10:43
谁告诉你grid是均匀的了,这和skew半毛钱关系都没有。。。

我什么时候说过grid是均匀的了。
回复 支持 反对

使用道具 举报

ctozlm 发表于 2014-11-10 02:04:11 | 显示全部楼层
那你什么时候说不是均匀的了。。。难道你返回的id每次是变的?直径都不知道。。。

补充内容 (2014-11-10 02:10):
要么就说的详细点,不会讨论问题别瞎喷。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-10 02:49:21 | 显示全部楼层
我服你,牛人。我是**
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-10 02:49:36 | 显示全部楼层
我是xiao 弱
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-24 07:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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