May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 944|回复: 15
收起左侧

电面遇到一个没见过的排序算法

[复制链接] |试试Instant~ |关注本帖
dylanwang 发表于 2015-7-8 14:06:06 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Amazon - 内推 - 技术电面 |Fail在职跳槽

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

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

x
题目:
给定一个大数据量未排序数组和int k. 1point 3acres 璁哄潧
这个数组满足这样的条件:
排序过之后数组和原数组比较,每个位置的移动范围小于k
写出排序算法

我想到的思路是,类似冒泡排序,但是只需要做k轮冒泡。
挂了

没明白面试官的思路,他想要考察什么。大家有好的想法么?


补充内容 (2015-7-8 14:25):
解法1:
[code]public void Sort(int[] arr, int k)
{
     for(int i=0; i<k; i++)
     {. 1point 3acres 璁哄潧
            for(int j=0; j<arr.Length-k; j++)
            {
                if(arr[j+1]<arr[j]) { exchange a[j...

补充内容 (2015-7-9 08:58):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

谢谢 shuishuimiao 指出,这个是geeksforgeeks上的那个k sorted array排序 http://www.geeksforgeeks.org/nearly-sorted-algorithm/   用Insert sort 复杂度是O(n*k), 用最小堆是O(n*logk)
 楼主| dylanwang 发表于 2015-7-8 14:14:10 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
解题思路是:

使用一个大小为K的最小堆,开始将前K个建一个最小堆,然后将最小的取出,然后将第K+1个元素添加到最小堆,然后取第二个最小,然后将第K+2个放入最小堆,...

如此可以使用O(N*log(K))的时间可以排序。

证明为什么可以使用最小堆来做:
.1point3acres缃. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1. 首先可以证明最小的一个一定出现在前K个元素中,否则排序之后最小的元素和原来的位置相差一定超过K。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

2. 利用1的性质可以知道第二小的元素一定出现在去掉最小元素后的堆和K+1的元素集合中,而不可能出现在第K+2及其以后的元素中
回复 支持 1 反对 0

使用道具 举报

shuishuimiao 发表于 2015-7-9 01:57:35 | 显示全部楼层
关注一亩三分地微博:
Warald
xujun 发表于 2015-7-9 01:03
如果第一个数是最大的数,你这个算法是必然会排到最后的。

好像是那个geeksforgeeks上的那个k sorted array排序, 题目是意思是input的数组本身就满足排序之后每个数都移动不超过k这个性质, 不是说让找到一个算法满足这个性质   所以只需要维护K大小的heap,时间是NlogK
回复 支持 1 反对 0

使用道具 举报

 楼主| dylanwang 发表于 2015-7-8 14:13:32 | 显示全部楼层
搜索一下,原来这也不是新题
回复 支持 反对

使用道具 举报

xujun 发表于 2015-7-9 01:03:40 | 显示全部楼层
dylanwang 发表于 2015-7-8 14:14
解题思路是:

使用一个大小为K的最小堆,开始将前K个建一个最小堆,然后将最小的取出,然后将第K+1个元 ...

如果第一个数是最大的数,你这个算法是必然会排到最后的。
回复 支持 反对

使用道具 举报

mayijie88 发表于 2015-7-9 05:53:35 | 显示全部楼层
这是典型的insertion sort, 复杂度可以做到O(n*k),可以看一下它的wiki,并且insertion sort是online sorting,可以处理大数据。. 1point3acres.com/bbs

补充内容 (2015-7-9 05:56):
不对,我看错题目了,我以为“每个位置的移动范围小于k”是assumption,不好意思楼主!
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-7-9 06:00):
不过又看了下评论,好像“每个数组的位置和它sorted的位置差k”确实是条件?

这样吧:如果是条件,可以用insertion sort,O(n*k)
             如果是需要实现成这样,那么可以用quicksort,设置constant cutoff为k

补充内容 (2015-7-9 06:41):
不过用heap那样做nlog(k)确实是更好的方法
回复 支持 反对

使用道具 举报

larry_cn 发表于 2015-7-9 06:46:14 | 显示全部楼层
额想 问个 比较 小白的问题 。。。。 排序后 可不可以 不是 “严格 完成 排序”.1point3acres缃

也就是说  排序的同时 要考虑 每个位置的 限制
如果是这样 就有点像 排列任务 不仅有 优先级还有 时间周期
. visit 1point3acres.com for more.
那额 感觉可以 用一个 k长度的 doubly list和 k大小的 heap来实现. from: 1point3acres.com/bbs
排序完前 k-1个 元素后:先check list的 head item(如果 后面的item是 一次放入tail的话) 如果周期未结束 再extract heap的(heap 的每个 item 也有一个 指向list的 指针 有点像 LRU)

补充内容 (2015-7-9 06:51):
list里面的 每个 item 也要有一个 指针指向 heap

running time 应该是 O(n log k)
回复 支持 反对

使用道具 举报

buaawj 发表于 2015-7-9 06:52:17 | 显示全部楼层
请问是google的店面题吗? 楼上sliding window + heap 是正解!
回复 支持 反对

使用道具 举报

 楼主| dylanwang 发表于 2015-7-9 08:48:35 | 显示全部楼层
larry_cn 发表于 2015-7-9 06:46
额想 问个 比较 小白的问题 。。。。 排序后 可不可以 不是 “严格 完成 排序”

也就是说  排序的同时  ...

给定的数组,再引入double list有点麻烦了吧,没看太明白
回复 支持 反对

使用道具 举报

 楼主| dylanwang 发表于 2015-7-9 08:49:16 | 显示全部楼层
buaawj 发表于 2015-7-9 06:52
请问是google的店面题吗? 楼上sliding window + heap 是正解!

Amazon的
回复 支持 反对

使用道具 举报

 楼主| dylanwang 发表于 2015-7-9 08:49:59 | 显示全部楼层
xujun 发表于 2015-7-9 01:03
如果第一个数是最大的数,你这个算法是必然会排到最后的。
.1point3acres缃
不会的,第一个数一定在0到k之间
回复 支持 反对

使用道具 举报

 楼主| dylanwang 发表于 2015-7-9 08:50:40 | 显示全部楼层
mayijie88 发表于 2015-7-9 05:53
这是典型的insertion sort, 复杂度可以做到O(n*k),可以看一下它的wiki,并且insertion sort是online sorti ...

是的,每个位置的移动范围小于k,是条件
回复 支持 反对

使用道具 举报

 楼主| dylanwang 发表于 2015-7-9 08:53:30 | 显示全部楼层
shuishuimiao 发表于 2015-7-9 01:57
好像是那个geeksforgeeks上的那个k sorted array排序, 题目是意思是input的数组本身就满足排序之后每个 ...

果然是这道题
http://www.geeksforgeeks.org/nearly-sorted-algorithm/

Thx!
回复 支持 反对

使用道具 举报

 楼主| dylanwang 发表于 2015-7-9 08:54:16 | 显示全部楼层
谢谢 Shuishuimiao 指出,这个是geeksforgeeks上的那个k sorted array排序题
回复 支持 反对

使用道具 举报

 楼主| dylanwang 发表于 2015-7-9 08:54:51 | 显示全部楼层
谢谢 Shuishuimiao 指出,这个是geeksforgeeks上的那个k sorted array排序题  http://www.geeksforgeeks.org/nearly-sorted-algorithm/
回复 支持 反对

使用道具 举报

 楼主| dylanwang 发表于 2015-7-9 08:55:52 | 显示全部楼层
谢谢 shuishuimiao 指出,这个是geeksforgeeks上的那个k sorted array排序 http://www.geeksforgeeks.org/nearly-sorted-algorithm/   用Insert sort 复杂度是O(n*k), 用最小堆是O(n*logk)
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-28 07:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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