一亩三分地论坛

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

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

攒人品

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

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

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

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

x
1. 有这么个游戏,举个例子:给你5个空_ _ _ _ _, 每次猜一个字母,这里出题人想让你猜出来clock,假如你猜a,告诉你这里面没有。你又猜c,他把c全写出来,所以你有c _ _ c _。 让你最多猜10次。写一个程序去猜。输入是几个空,要考虑每次猜的反馈,尽量把词猜出来。
2. 坐标系第一象限上加射线,接下来所有输入的数据都是不相等的整数,不用考虑任何edge case。 想要这两个操作:1. insertX(x), insertY(y),比如insertX, 就是现有的图上面加上x这条射线,象限会被插入的这些射线分成网格,每个格叫一个区域。 2. find(x,y), 就是给个坐标,返回这个坐标所在的区域。可以返回区域的id,区域的id自己定。用二叉树。
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.1point3acres缃
第二题是二叉树吗? 怎么觉得应该用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?

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

使用道具 举报

zhenggao1986 发表于 2014-11-9 04:46:19 | 显示全部楼层
averillzheng 发表于 2014-11-9 02:09
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?
回复 支持 反对

使用道具 举报

zhenggao1986 发表于 2014-11-9 04:55:20 | 显示全部楼层
averillzheng 发表于 2014-11-9 02:06
什么叫直径,宽度?

直径那个应该说的是找一个Node之间最大距离吧,二叉树标准题. 1point3acres.com/bbs
int maxDistance(Node* root) {
        int depth = 0;
        return maxDistanceHelper(root, depth);
}

int maxDistanceHelper(Node* root, int &depth) {
        if (root == NULL) {
                depth = 0;
                return 0;
        }
        int leftDepth = 0, rightDepth = 0;. visit 1point3acres.com for more.
        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
这个题不用二叉树。yongskew的方法来做index 就可以的。

比如 我们假设水平方向是x轴, 垂直方向是y轴 ...

没看懂,分割的是网格,如何用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做一下就好啦。.鐣欏璁哄潧-涓浜-涓夊垎鍦
不可以另外用空间的话,你就排序比较一下。. From 1point 3acres bbs
如果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随机分配然后去重也行吧,貌似不是考点,而且插入的顺序是随机 ...
-google 1point3acres
按我给的方法,每个格子的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)调用的次序一 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
谁告诉你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 弱
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 21:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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