推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

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

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

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

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

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

x
题目: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
给定一个大数据量未排序数组和int k-google 1point3acres
这个数组满足这样的条件: .鏈枃鍘熷垱鑷1point3acres璁哄潧
排序过之后数组和原数组比较,每个位置的移动范围小于k
写出排序算法

我想到的思路是,类似冒泡排序,但是只需要做k轮冒泡。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
挂了

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

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-7-8 14:25):.鐣欏璁哄潧-涓浜-涓夊垎鍦
解法1:
[code]public void Sort(int[] arr, int k)
{
     for(int i=0; i<k; i++)
     {
            for(int j=0; j<arr.Length-k; j++)
            { . visit 1point3acres.com for more.
                if(arr[j+1]<arr[j]) { exchange a[j...
. from: 1point3acres.com/bbs
补充内容 (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个放入最小堆,...
-google 1point3acres
如此可以使用O(N*log(K))的时间可以排序。

证明为什么可以使用最小堆来做:

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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果第一个数是最大的数,你这个算法是必然会排到最后的。
. 1point 3acres 璁哄潧
好像是那个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,可以处理大数据。

补充内容 (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):. from: 1point3acres.com/bbs
不过用heap那样做nlog(k)确实是更好的方法
回复 支持 反对

使用道具 举报

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

也就是说  排序的同时 要考虑 每个位置的 限制
如果是这样 就有点像 排列任务 不仅有 优先级还有 时间周期

那额 感觉可以 用一个 k长度的 doubly list和 k大小的 heap来实现. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
排序完前 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
额想 问个 比较 小白的问题 。。。。 排序后 可不可以 不是 “严格 完成 排序”
. visit 1point3acres.com for more.
也就是说  排序的同时  ...

给定的数组,再引入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/

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 下一条

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

custom counter

GMT+8, 2017-8-17 12:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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