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

一亩三分地论坛

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

Zenefits skype 面经

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

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

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

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

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. 1point 3acres 论坛
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次。

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 ...

赞解法!
不擅长写堆。
回复 支持 反对

使用道具 举报

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

另外请问楼主这个题目是给k个数组,然后自己创建一个merge好的大数组返回吗?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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的
. 1point 3acres 论坛
所以最好是建立class Node{
int value;
int array;
}

int array放的是array的index
这样就当成linkedlist来做了
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-24 12:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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