一亩三分地论坛

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

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

Godaddy电面面经

[复制链接] |试试Instant~ |关注本帖
tianchijushi 发表于 2015-11-2 19:28:59 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Godaddy - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
发一个godaddy面经,新人处女贴
前一阵面的电面,是一个要求三年工作经验的岗位,半年前投的刚给的面试,面试官是个MIT的phd
面试三道题,前两道leetcode难度,毫无新意,难点在第三个
面试官给出了n个机器,每台机器上存了m个int,然后给出一个新的空闲的机器,要求找出所有m * n个数的median。
其中每台机器最多只能存m个数字,n可以远大于m,这些机器两两相连

评分

2

查看全部评分

 楼主| tianchijushi 发表于 2015-11-3 02:38:06 | 显示全部楼层
其中这道题楼主提到了两种做法这位MIT的面试官貌似都不满意,觉得很是困惑,哪位大神有好的做法可以大家讨论一下
回复 支持 反对

使用道具 举报

arrxinn_gl 发表于 2015-11-3 12:09:48 | 显示全部楼层
请问楼主面的是什么职位呢?谢谢
回复 支持 反对

使用道具 举报

 楼主| tianchijushi 发表于 2015-11-3 14:23:51 | 显示全部楼层
arrxinn_gl 发表于 2015-11-3 12:09. visit 1point3acres.com for more.
请问楼主面的是什么职位呢?谢谢

就是software engineer,貌似是dns api开发
回复 支持 反对

使用道具 举报

jinger8910 发表于 2015-11-5 07:55:40 | 显示全部楼层
geek for geek 有讲这个哎
记得就是分别对每个机器找median 然后 再找这n个median里的median
回复 支持 反对

使用道具 举报

 楼主| tianchijushi 发表于 2015-11-5 08:01:36 | 显示全部楼层
jinger8910 发表于 2015-11-5 07:55
geek for geek 有讲这个哎
记得就是分别对每个机器找median 然后 再找这n个median里的median

能说的详细一点吗?如果第一个是1,2,3, 第二个是4,5,6,第三个是1,6,7。应该找2,5,6的median吗?那不是5而正确的是4啊,我事后网上找了很久也没找到做法
回复 支持 反对

使用道具 举报

jinger8910 发表于 2015-11-5 08:26:27 | 显示全部楼层
tianchijushi 发表于 2015-11-5 08:01
能说的详细一点吗?如果第一个是1,2,3, 第二个是4,5,6,第三个是1,6,7。应该找2,5,6的median吗 ...

对哦

那你看看这个?https://www.quora.com/Distribute ... different-computers
回复 支持 反对

使用道具 举报

rememberthemilk 发表于 2015-11-9 00:35:03 | 显示全部楼层
tianchijushi 发表于 2015-11-5 08:01
能说的详细一点吗?如果第一个是1,2,3, 第二个是4,5,6,第三个是1,6,7。应该找2,5,6的median吗 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我觉得思路应该是这样:
1. 首先确认的是我们需要算median而不是mean。如果算mean的话,用gossip algorithm里面的push sum做可以很快的得到非常近似于mean的值。
2. {1, 2, 3}里median是2,{4, 5, 6}里median是5, {1, 6, 7}里median是6。根据此信息,我们可以确定第一个array里面左半段不可能有三个array共同的median。同样的,第三个array的右半段也不可能有。所以三个array变成了{2, 3}(2), {4, 5, 6}(5), {1, 6}(1),那么再次排序,1《2《5.因此我们可以去掉第二个array的右半段,第三个array的左半段得到:{2, 3}(2),{4,5}(4), {6}(6)。同样的,得到{3}(3), {4,5}(4), {},再做一次,得到4.
回复 支持 反对

使用道具 举报

 楼主| tianchijushi 发表于 2015-11-9 07:32:11 | 显示全部楼层
rememberthemilk 发表于 2015-11-9 00:35
我觉得思路应该是这样:
1. 首先确认的是我们需要算median而不是mean。如果算mean的话,用gossip algori ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
的确是找median,但是你的算法有两个问题。第一个比较容易解决的,median是两个数的平均值,2,3的median是2.5而不是2,这个是小问题。第二个大问题在于题目的背景,给了n台机器,每个机器有m个数,现在只给你一个额外的有着m内存的机器,这些机器两两相连,让求median。如果有10000台机器,每台存3个数,新的机器只有3的内存,你怎么标记取舍啊?这位MIT的面试官给的提示是我没有利用这些机器两两相连的条件,所以很困惑
回复 支持 反对

使用道具 举报

brotherchun 发表于 2015-11-10 15:37:36 | 显示全部楼层
请问楼主前两道题面的是什么,还记得吗?多谢 !
回复 支持 反对

使用道具 举报

 楼主| tianchijushi 发表于 2015-11-11 03:56:24 | 显示全部楼层
brotherchun 发表于 2015-11-10 15:37
请问楼主前两道题面的是什么,还记得吗?多谢 !

. 1point 3acres 璁哄潧求开方sqrt和拼接两个字符串,无脑的,不用担心
回复 支持 反对

使用道具 举报

brotherchun 发表于 2015-11-11 08:28:12 | 显示全部楼层
多谢哈,,楼主方便留个联系方式吗?
回复 支持 反对

使用道具 举报

 楼主| tianchijushi 发表于 2015-11-11 10:14:17 | 显示全部楼层
brotherchun 发表于 2015-11-11 08:28
多谢哈,,楼主方便留个联系方式吗?

怎么了,有什么需要帮忙的?
回复 支持 反对

使用道具 举报

tyr034 发表于 2015-11-12 06:27:02 | 显示全部楼层
tianchijushi 发表于 2015-11-11 03:56
求开方sqrt和拼接两个字符串,无脑的,不用担心

拼接两个字符是啥意思?lz能讲讲吗?
回复 支持 反对

使用道具 举报

大大大拥抱 发表于 2016-1-27 10:48:51 | 显示全部楼层
tianchijushi 发表于 2015-11-9 07:32
的确是找median,但是你的算法有两个问题。第一个比较容易解决的,median是两个数的平均值,2,3的median ...

九章算法里面讲过一题类似的,用两个heap去存median左边的数和右边的数,median左边的是最大堆,右边的是最小堆。新来一个数的时候,先根据两个heap的数量判断应该放在哪个堆,然后放进去。最后返回的就是两个堆顶部的数之一(或者平均值)。

感觉和这题有点像?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-1-29 11:52:23 | 显示全部楼层
大大大拥抱 发表于 2016-1-27 10:48
九章算法里面讲过一题类似的,用两个heap去存median左边的数和右边的数,median左边的是最大堆,右边的是 ...

感觉有些靠谱,能说再详细点么?
回复 支持 反对

使用道具 举报

大大大拥抱 发表于 2016-1-30 01:07:18
googlerr 发表于 2016-1-29 11:52
感觉有些靠谱,能说再详细点么?

你去搜一下九章算法的Median in Data Stream这题的解法,这题目前只有C++的解答。
支持 反对

大大大拥抱 发表于 2016-1-30 03:10:03 | 显示全部楼层
之前的回了一条貌似一直在审核?什么情况。。。

补充内容 (2016-1-30 03:18):
可以参考九章算法里面Median in Data Stream这题,但是目前只有C++的解答。这题是把所有的数都放到heap里,能保证堆顶的正确性。而楼主这题,新机器容量有限,当连续来很多小于当前中间数的值,加入最大堆后会出错?
-google 1point3acres
补充内容 (2016-1-30 03:33):
唉,没用到9楼里面楼主说“这些机器两两相连的条件”
回复 支持 反对

使用道具 举报

大大大拥抱 发表于 2016-1-30 03:15:34 | 显示全部楼层
googlerr 发表于 2016-1-29 11:52
感觉有些靠谱,能说再详细点么?

可以参考九章算法里面Median in Data Stream这题的解法,但是目前只有C++版本的解答。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
但我有个小疑问,Median in Data Stream这题是把所有的数都放到了heap里面,能保证堆顶那个数的正确性。而楼主这题,新机器的space应该没法存所有的数,这样用heap不一定对吧?假如新出现了很多小于当前medin的数,最大堆此时的最大值有可能就是错的了。。
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-1-30 05:40:36 | 显示全部楼层
大大大拥抱 发表于 2016-1-30 03:10
之前的回了一条貌似一直在审核?什么情况。。。

补充内容 (2016-1-30 03:18):

谢谢,不过两两相连可能有什么价值?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 22:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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