一亩三分地论坛

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

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

Zenefits skype 面经

[复制链接] |试试Instant~ |关注本帖
melody_qyao 发表于 2015-4-25 05:20:30 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Zenefits - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚面完Z家skype interview,是个三哥给我面的,那口音也是醉了。。。叫Mahesh。。。一开始上来给我讲他家是干嘛的,呱呱呱说了5分钟,我愣是一句也没听懂,就零星的听懂几个单词。。然后问我为什么要申请他家,问问项目的问题。他家主要技术是后端python Django框架,前端一个什么JS的框架。。完后开始coding。题一出来我就笑了,merge k sorted array,我一想这个我会啊,用最小堆做啊!然后开始刷刷刷写代码,写到一半卡住了,md是array不是linkedlist啊,我要怎么取下一个element啊!然后就全程卡死在这里!!!然后hashmap各种什么全想了不行啊,小哥说用hashmap不能处理duplicates啊!!!期间气氛一度很尴尬。最后想出来在构建最小堆的时候不是单独存这个数,而是存数和他所在的array的index,也就是类似Pair<Integer, Integer>这种。。但是后来发现java的priorityqueue里面不能这样存,所以你需要新建一个class来wrap up this pair.还有一点在于找到了元素所在的array,怎么找他的下一个元素呢?然后我就说把array转成arraylist然后每次add到heap里面去之后都把元素在该arraylist里面删掉,这样每次的第一个元素就是next element了。虽然最后写出来了,但是感觉交流的很不好,目测要挂。。。。哎

评分

1

查看全部评分

本帖被以下淘专辑推荐:

mileschen2008 发表于 2015-4-25 06:42:03 | 显示全部楼层
Array的话,就只Divide Conquer就行吧。
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-4-25 08:06:43 | 显示全部楼层
mileschen2008 发表于 2015-4-25 06:42
Array的话,就只Divide Conquer就行吧。

我只记得divide and conquer是找median的吧, 怎么用divide and conquer来sort k array啊求解
回复 支持 反对

使用道具 举报

cuiyang36 发表于 2015-4-25 08:34:29 | 显示全部楼层
array用minHeap做的话是有点麻烦,但楼主的想法是绝对正确的,得写个wrapper class去存数据,我感觉的是Triple<Integer, Integer, Integer> 第一个存array在总array中的index,第二个存当前元素在array中的index然后最后一个存数值(这样可以防止规定输入的大array为final,当我们需要写comparator的时候)。
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-4-25 08:57:58 | 显示全部楼层
mileschen2008 发表于 2015-4-25 06:42
Array的话,就只Divide Conquer就行吧。

比如说现在4个数组,a1, a2, a3, a4,那么先merge a1 and a2 to be an array for example A, 并且merge a3 and a4 to be an array for instance B. Then merge A and B to be a single array。所以的话,如果有k个数组,这样的Divide and Conquer方法的复杂度是O(nlogk),n是所有k个数组的数目和,因为每个元素会被touch logk次。
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-4-25 08:58:58 | 显示全部楼层
melody_qyao 发表于 2015-4-25 08:06
我只记得divide and conquer是找median的吧, 怎么用divide and conquer来sort k array啊求解

比如说现在4个数组,a1, a2, a3, a4,那么先merge a1 and a2 to be an array for example A, 并且merge a3 and a4 to be an array for instance B. Then merge A and B to be a single array。所以的话,如果有k个数组,这样的Divide and Conquer方法的复杂度是O(nlogk),n是所有k个数组的数目和,因为每个元素会被touch logk次。.鏈枃鍘熷垱鑷1point3acres璁哄潧

PS: 刚点回复按钮点错了,囧!
回复 支持 反对

使用道具 举报

这里没有鱼 发表于 2015-4-26 16:18:49 | 显示全部楼层
mileschen2008 发表于 2015-4-25 08:58
比如说现在4个数组,a1, a2, a3, a4,那么先merge a1 and a2 to be an array for example A, 并且merge a ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
赞解法!. Waral 鍗氬鏈夋洿澶氭枃绔,
不擅长写堆。
回复 支持 反对

使用道具 举报

xieqilu1989 发表于 2015-4-28 12:44:35 | 显示全部楼层
这题如果是array的话最好就用merge sort做比较简单,用heap做的话怎么判定顶端元素属于哪个数组确实比较麻烦,我能想到也就和楼主一样必须用wrapper class, 记录每个元素在哪个数组,这样取出heap顶端元素之后就可以继续把对应数组的下一个元素放进heap中。

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴另外请问楼主这个题目是给k个数组,然后自己创建一个merge好的大数组返回吗?
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-4-29 02:52:01 | 显示全部楼层
mileschen2008 发表于 2015-4-25 08:57
比如说现在4个数组,a1, a2, a3, a4,那么先merge a1 and a2 to be an array for example A, 并且merge a ...

但如果是用recursive做的话,空间复杂度应该相当大吧。要一直保存合并后的数组。
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-4-29 04:15:43 | 显示全部楼层
EchoO 发表于 2015-4-29 02:52
但如果是用recursive做的话,空间复杂度应该相当大吧。要一直保存合并后的数组。

是一样的,你可以在merge后消掉原来的数组。因为最终你总得返回一个你创建的大数组来保存所有的merge后的元素。所以空间复杂度除了多余的log(k)以外。
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-4-29 04:21:57 | 显示全部楼层
mileschen2008 发表于 2015-4-29 04:15
是一样的,你可以在merge后消掉原来的数组。因为最终你总得返回一个你创建的大数组来保存所有的merge后的 ...

recursive不是会一直保存运行状态么。并不是在一次递归结束后就释放全部状态
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-4-29 07:07:08 | 显示全部楼层
xieqilu1989 发表于 2015-4-28 12:44
这题如果是array的话最好就用merge sort做比较简单,用heap做的话怎么判定顶端元素属于哪个数组确实比较麻 ...

是的,input是int[][] output是int[]
回复 支持 反对

使用道具 举报

xieqilu1989 发表于 2015-4-29 11:46:23 | 显示全部楼层
melody_qyao 发表于 2015-4-29 07:07
是的,input是int[][] output是int[]

多谢楼主啦!
回复 支持 反对

使用道具 举报

dmsehuang 发表于 2015-6-26 02:38:50 | 显示全部楼层
所以是原版的merge k sorted array吗?还是变种?
回复 支持 反对

使用道具 举报

yyboyz 发表于 2016-1-27 07:24:24 | 显示全部楼层
我突然觉得跟merge k linked list 道理也一样。。。

楼主说不知道怎么取下一个, 那我matain一个List<Integer> pointers不就行了。。 pointers.get(i)放的是list[i]的指针 , 每次丢进去heap一个数字 对应的指针就++
你的难点应该是怎么知道heap pop出来的数字是来自哪个array的.1point3acres缃

所以最好是建立class Node{
int value;
int array;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}

int array放的是array的index. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这样就当成linkedlist来做了
回复 支持 反对

使用道具 举报

灰色的乌鸦 发表于 2016-2-8 08:03:42 | 显示全部楼层
想了一会儿。。。竟然没有看懂为啥要删掉。。如果用priorityqueue,不是扫一遍然后挨个插入就完了么。。。小弟题都没有刷完。。。还请有空给简单讲讲。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 21:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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