您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 招聘面试 > _程序员面试智力算法题汇总一
程序员面试智力编程题汇总——Bytzj1、12球三次称出坏球及轻重:2、数组循环移位设计一个算法,把一个含有N个元素的数组循环右移K位,要求时间复杂度为O(N),且只允许使用两个附加变量。首先我们来看下解法一,一般人都会想到的voidrightShift(int*arr,intn,intk){k%=n;while(k){intt=arr[n-1];for(inti=n-1;i0;i--)arr[i]=arr[i-1];arr[0]=t;k--;}}复杂度为O(k*N),0kN有点不符合要求哈哈。。。解法二:我们来举个例子看看清楚啊比如12345abcde,向右移4个位置,则移动后变为bcde12345a,我们看出bcde和12345a顺序都保存不变,所,我们可以这样处理啊。。。(1)12345a反转得a54321;(2)bcde反转得edcb,此时数组a54321edcb;(3)哈哈,看出来了吧,再反转bcde12345a。复杂度多少呢O(N)。voidreverse(int*arr,intbegin,intend){for(;beginend;begin++,end--){inttemp=arr[begin];arr[begin]=arr[end];arr[end]=temp;}}voidrightShift(int*arr,intk,intn){k%=n;reverse(arr,0,n-k-1);reverse(arr,n-k,n-1);reverse(arr,0,n-1);}3、求二进制中1的个数题:对于一个正整数,用二进制表示,求其中1的个数解法一:思路:我们一般都会想到模2操作,余1则加1intcount(intv){intnum=0;while(v){if(v%2==1){num++;}v/=2;}returnnum;}解法二:思路:位操作,0x01和末位1与为1,和末位0与为0intcount(intv){intnum=0;while(v){num+=v&0x01;v=1;}returnnum;}解法三:我们知道,如果一个数v为2的整数次幂,则v&(v-1)=0;受到这个启发,我们可以让每一次减1,则每次会消灭一个1(从低位到高位),复杂度O(m),m为v中1的个数:intcount(intv){intnum=0;while(v){v&=(v-1);num++;}returnnum;}解法四:如果该整数的范围在一定范围内,且该操作十分频繁,则可以先建立一个查找表,即数组,o(1)的复杂度。4、使用用最小堆来找N个数中最大的K个数题目描述:有很多个(N个)无序的数,我们姑且假定它们各不相等,怎么选出其中最大的若干个(k个)数呢?1、N=100,K=10的时候怎么处理?2、N=1000,k=100呢?3、N=1亿亿个,K=100呢?如果这些数是整数的话,怎么处理?如果是浮点数呢?如果这些数是整数,并且存在上界呢?如果将题目中的“各不相等”这个条件去掉呢?处理方式又会出现什么变动么?针对这个问题,我们根据不同的数据量,可能采取不同的处理方式:第一,针对小数据量,我们可以采用好的排序算法,将数据排序后找出最大的k个数。第二,针对数据量比较大,不能一次性全部装入内存的情况,我们可以采用外排序的方法。第三,就是Hilbert提到的,当数据量巨大的情况下,排序可能已经没办法得到比较好的效果,我们可以采用建立k个元素的最大堆来处理。另外,如果需要处理的数据是整数,各不相同,而且知道最大值,那么我们可以采用位图的思想,如果某个数存在,那么对应的那一位就置1,然后从高位往低位扫描位图,输出前k个为1的位的下标即可。具体讨论如下:////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一道经典的面试题:如何从N个数中选出最大(小)的n个数?这个问题我前前后后考虑了有快一年了,也和不少人讨论过。据我得到的消息,Google和微软都面过这道题。这道题可能很多人都听说过,或者知道答案(所谓的“堆”),不过我想把我的答案写出来。我的分析也许存有漏洞,以交流为目的。但这是一个满复杂的问题,蛮有趣的。看完本文,也许会启发你一些没有想过的解决方案(我一直认为堆也许不是最高效的算法)。在本文中,将会一直以寻找n个最“大”的数为分析例子,以便统一。注:本文写得会比较细节一些,以便于绝大多数人都能看懂,别嫌我罗嗦:)我很不确定多少人有耐心看完本文!Naive方法:首先,我们假设n和N都是内存可容纳的,也就是说N个数可以一次load到内存里存放在数组里(如果非要存在链表估计又是另一个challenging的问题了)。从最简单的情况开始,如果n=1,那么没有任何疑惑,必须要进行N-1次的比较才能得到最大的那个数,直接遍历N个数就可以了。如果n=2呢?当然,可以直接遍历2遍N数组,第一遍得到最大数max1,但是在遍历第二遍求第二大数max2的时候,每次都要判断从N所取的元素的下标不等于max1的下标,这样会大大增加比较次数。对此有一个解决办法,可以以max1为分割点将N数组分成前后两部分,然后分别遍历这两部分得到两个“最大数”,然后二者取一得到max2。也可以遍历一遍就解决此问题,首先维护两个元素max1,max2(max1=max2),取到N中的一个数以后,先和max1比,如果比max1大(则肯定比max2大),直接替换max1,否则再和max2比较确定是否替换max2。采用类似的方法,对于n=2,3,4……一样可以处理。这样的算法时间复杂度为O(nN)。当n越来越大的时候(不可能超过N/2,否则可以变成是找N-n个最小的数的对偶问题),这个算法的效率会越来越差。但是在n比较小的时候(具体多小不好说),这个算法由于简单,不存在递归调用等系统损耗,?堆:当n较大的时候采用什么算法呢?首先我们分析上面的算法,当从N中取出一个新的数m的时候,它需要依次和max1,max2,max3……maxn比较,一直找到一个比m小的maxx,就用m来替换maxx,平均比较次数是n/2。可不可以用更少的比较次数来实现替换呢?最直观的方法是,也就是网上文章比较推崇的堆。堆有这么一些好处:1.它是一个完全二叉树,树的深度是相同节点的二叉树中最少的,维护效率较高;2.它可以通过数组来实现,而且父节点p与左右子节l,r点的数组下标的关系是s[l]=2*s[p]+1和s[r]=2*s[p]+2。在计算机中2*s[p]这样的运算可以用一个左移1位操作来实现,十分高效。再加上数组可以随机存取,效率也很高。3.堆的Extract操作,也就是将堆顶拿走并重新维护堆的时间复杂度是O(logn),这里n是堆的大小。具体到我们的问题,如何具体实现呢?首先开辟一个大小为n的数组区A,从N中读入n个数填入到A中,然后将A维护成一个小顶堆(即堆顶A[0]中存放的是A中最小的数)。然后从N中取出下一个数,即第n+1个数m,将m与堆顶A[0]比较,如果m=A[0],直接丢弃m。否则应该用m替换A[0]。但此时A的堆特性可能已被破坏,应该重新维护堆:从A[0]开始,将A[0]与左右子节点分别比较(特别注意,这里需要比较“两次”才能确定最大数,在后面我会根据这个来和“败者树”比较),如果A[0]比左右子节点都小,则堆特性能够保证,勿需继续,否则如左(右)节点最大,则将A[0]与左(右)节点交换,并继续维护左(右)子树。依次执行,直到遍历完N,堆中保留的n个数就是N中最大的n个数。这都是堆排序的基本知识,唯一的trick就是维护一个小顶堆,而不是大顶堆。不明白的稍微想一下。维护一次堆的时间复杂度为O(logn),总体的复杂度是O(Nlogn)这样一来,比起上面的O(nN),当n足够大时,堆的效率肯定是要高一些的。当然,直接对N数组建堆,然后提取n次堆顶就能得到结果,而且其复杂度是O(nlogN),当n不是特别小的时候这样会快很多。但是对于online数据就没办法了,比如N不能一次load进内存,甚至是一个流,根本不知道N是多少。败者树:有没有别的算法呢?我先来说一说败者树(losertree)。也许有些人对losertree不是很了解,其实它是一个比较经典的外部排序方法,也就是有x个已经排序好的文件,将其归并为一个有序序列。败者树的思想咋一看有些绕,其实是为了减小比较次数。首先简单介绍一下败者树:败者树的叶子节点是数据节点,然后两两分组(如果节点总数不是2的幂,可以用类似完全树的结构构成树),内部节点用来记录左右子树的优胜者中的“败者”(注意记录的是输的那一方),而优胜者则往上传递继续比较,一直到根节点。如果我们的优胜者是两个数中较小的数,则根节点记录的是最后一次比较中的“败者”,也就是所有叶子节点中第二小的那个数,而最小的那个数记录在一个独立的变量中。这里要注意,内部节点不但要记录败者的数值,还要记录对应的叶子节点。如果是用链表构成的树,则内部节点需要有指针指向叶子节点。这里可以有一个trick,就是内部节点只记录“败者”对应的叶子节点,具体的数值可以在需要的时候间接访问(这一方法在用数组来实现败者树时十分有用,后面我会讲到)。关键的来了,当把最小值输出后,最小值所对应的叶子节点需要变成一个新的数(或者改为无穷大,在文件归并的时候表示文件已读完)。接下来维护败者树,从更新的叶子节点网上,依次与内部节点比较,将“败者”更新,胜者往上继续比较。由于更新节点占用的是之前的最小值的叶子节点,它往上一直到根节点的路径与之前的最小值的路径是完全相同的。内部节点记录的“败者”虽然称为“败者”,但却是其所在子树中最小的数。也就是说,只要与“败者”比较得到的胜者,就是该子树中最小的那个数(这里讲得有点绕了,看不明白的还是找本书看吧,对照着图比较容易理解)。注:也可以直接对N构建败者树,但是败者树用数组实现时不能像堆一样进行增量维护,当叶子节点的个数变动时需要完全重新构建整棵树。为了方便比较堆和败者树的性能,后面的分析都是对n个数构建的堆和败者树来分析的。总而言之,败者树在进行维护的时候,比较次数是logn+1。与堆不同的是,败者树是从下往上维护,每上一层,只需要和败者节点比较“一次”即可。而堆在维护的时候是从上往下,每下一层,需要和左右子节点都比较,需要比较两次。从这个角度,败者树比堆更优一些。但是,请注意但是,败者树每一次维护必定需要从叶子节点一直走到根节点,不可能中间停止;而堆维护时,“有可能”会在中间的某个层停止,不需要继续往下。这样一来,虽然每一层败者树需要的比较次数比堆少一倍,但是走的层数堆会比败者树少。具体少多少,从平均意义上到底哪一个的效率会更好一些?那我就不知道了,这个分析起来有点麻烦。感兴趣的人可以尝试一下,讨论讨论。但是至少说明了,也许堆并非是最优的。具体到我们的问题。类似的方法,先构建一棵有n个叶子节点的败者树,胜出者w是n个中最小的那一个。从N中读入一个新的数m后,和w比较,如果比w小,直接丢弃,否则用m替换w所在的叶子节点的值,然后维护该败者树。依次执行,直到遍历完N,败者树中保留的n个数就是N中最大的n个数。时间复杂度也是O(Nlogn)。前面有提到,堆的优点中包括“完全树”,“用数组实现”,以及“父节点与左右子节点之间的下标的特殊关系”。其实败者树也可以用数组来实现。其实我以前没有这么想过,我进微软实习的时候的考我的编程题就是文件归并,我是用败者树做的,当时是用指针来构建树,2个小时的题,我弄了3个小时才弄出来,差点没弄死我。指针维护起来太麻烦了。昨天旁边的David提到败者树可以用数组实现,恍然大悟。其原理和堆的数组实现是相同的,唯一的区别是堆的所有节点都是数据节点,而败者树只有叶子节点是数据节点。所以在空间复杂度上,败者树所需的空间大小是堆的一倍(
本文标题:_程序员面试智力算法题汇总一
链接地址:https://www.777doc.com/doc-5980740 .html