一亩三分地论坛

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

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

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

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

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

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

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

x
题目:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
给定一个大数据量未排序数组和int k
这个数组满足这样的条件:
排序过之后数组和原数组比较,每个位置的移动范围小于k
写出排序算法

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

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


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

补充内容 (2015-7-9 08:58):
.1point3acres缃
谢谢 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 | 显示全部楼层
解题思路是:

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

如此可以使用O(N*log(K))的时间可以排序。
. 1point 3acres 璁哄潧
证明为什么可以使用最小堆来做:
. From 1point 3acres bbs
1. 首先可以证明最小的一个一定出现在前K个元素中,否则排序之后最小的元素和原来的位置相差一定超过K。
. From 1point 3acres bbs
2. 利用1的性质可以知道第二小的元素一定出现在去掉最小元素后的堆和K+1的元素集合中,而不可能出现在第K+2及其以后的元素中
回复 支持 1 反对 0

使用道具 举报

shuishuimiao 发表于 2015-7-9 01:57:35 | 显示全部楼层
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
解题思路是:. 1point3acres.com/bbs

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

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

使用道具 举报

mayijie88 发表于 2015-7-9 05:53:35 | 显示全部楼层
这是典型的insertion sort, 复杂度可以做到O(n*k),可以看一下它的wiki,并且insertion sort是online sorting,可以处理大数据。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2015-7-9 05:56):
不对,我看错题目了,我以为“每个位置的移动范围小于k”是assumption,不好意思楼主!

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷补充内容 (2015-7-9 06:00):
不过又看了下评论,好像“每个数组的位置和它sorted的位置差k”确实是条件?
. 鍥磋鎴戜滑@1point 3 acres
这样吧:如果是条件,可以用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 | 显示全部楼层
额想 问个 比较 小白的问题 。。。。 排序后 可不可以 不是 “严格 完成 排序”
. 1point 3acres 璁哄潧
也就是说  排序的同时 要考虑 每个位置的 限制
如果是这样 就有点像 排列任务 不仅有 优先级还有 时间周期

那额 感觉可以 用一个 k长度的 doubly list和 k大小的 heap来实现.鏈枃鍘熷垱鑷1point3acres璁哄潧
排序完前 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
如果第一个数是最大的数,你这个算法是必然会排到最后的。

不会的,第一个数一定在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/
. From 1point 3acres bbs
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)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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