http://eager2007.blog.hexun.com/26216090_d.html
本来今天想写的是“面试记”,八一八HR姐姐和面试官叔叔。但聊到面试难免要聊面试题,而算法题自是其重中之重。为了日后能专心地八面试官,今天就先说说这个算法。。。
本篇涉及专业知识,外行止步,发生危险概不负责。
算法与数据结构,属于IT技能中较“高雅”的一类,所谓阳春白雪、曲高和寡,往往只有大公司才对此有兴趣。而急功近利的小公司面试官只会问“会不会用Struts”之类……
其
中,数据结构比较基础些。一般开发类职位都会考考Linked List或者Hash
table之类的,相信上过这门课的人都能写出来。要求更高的面试官会真正地考算法,(而不仅仅是数据结构)。算法有两种考法,一是考课本知识,主要集中
在排序、查找和二叉树相关三类算法。考查的是基础知识掌握,以及编程基本功。
另一类就是考书上没有的算法,这往往出现在对创造性较高的岗位中。想要令面试官满意的话,完全寄希望于现场发挥是很难的,最好平时有算法方面的积累。建议大家平时多逛逛百合的Algorithm版什么的……另外百度历年的笔试题也是增加积累的好素材。
最后不得不提一个出场率最高的算法,我曾经在四场面试中用上它:
问题:[Random Select]求已知N个数中第k小的数。(k<N)
先排序再取数的做法需要O(n*Logn)的复杂度,事实上此问题O(n)可解。具体做法是:按照类似快速排序算
法中的“分类”步骤,任选一个参考数,把整个数组分成左右两部分。左边部分小于参考数,右边部分大于参考数。然后根据左右部分各自包含元素的个数,计算出
要求的元素在哪个数组中。(要求的元素或者是左数组中的第k小数,或者是右数组中第[k-l]小的数。l为左数组的长度)然后递归之。
贴个伪代码:
int select(int[] arr, int lw, int hi, int k)
// lw:下标下界, hi:下标上届。
{
if(lw==hi)
return arr[lw];
int q = partition(lw,hi);//调用quicksort里面的partition, q指向参考数
int l = q-lw+1; // l为左数组长度
if(k==l)
return arr[q];
if(k<l)
return select(arr,lw,q-1,k);
if(k>l)
return select(arr,q+1,hi,k-l);
}
没看懂的话也没关系,百度一下“第k小数”或者“random select问题”会有更详细的解释。
如何向面试官描述这个算法:
如果手中有纸笔,画图可以描述地更清楚。如果是电话面抓住关键词“快排”“分类”“递归”即可。
进一步,面试官会问这个算法的复杂度。此算法额外空间复杂度为O(logn),可以进一步优化为O(1)——将递归改写为非递归即可。时间复杂度为O(n)——虽然乍看上似乎是n*Logn。平均每个数组元素被访问两次。
时间复杂度的证明是另一个关键,如果证不出来赶快百度一下啦。
下面解释为什么这个算法在面试中的应用:
首先,此问题可以推广:求数组中最小的k个数(而不是第k小的数)。答案很简单:求出第k小数之后,其左边的(k-1)个数都比它小。所以……
其次,它可以退化求中位数问题:如何在O(n)时间内求数组的中位数。
我曾在某次面试中被提了这个问题,随后面试官又推广了此问题。他问道:
如果有一个数组,对其取中位数,然后移除此元素。重复此操作k次,求这k个被移除的数。如何设计算法?
(注,当数组长度为偶数时,中位数有两种不同的定义。此处定义第[n/2]个数为中位数,而不是中间两数之平均。)
也许不可思议,此问题仍然有O(n)的解法:
可以证明:如果将数组排序,那么问题等价于求数组最中间的一段k个数。当然“最中间一段”这样的说法有些含糊,但大致上就是求下标为[n/2-k/2, n/2+k/2]这个区间上的一段数,但是在区间两端要根据n和k的奇偶性作+1或-1的调整。因此,原问题转化为:
求某个数组中第a小到第b小之间的k个数。(b>=a,k==b-a+1)
剩下的问题就很简单了:先求原数组中最小的b个数,然后在此结果中求最大的(b-a+1)个数。
最后一个推广,此算法还可以用在著名的“主元素”问题上。主元素的定义是:
如果一个数组中,有一个数出现次数达到数组长度的一半以上,则称其为数组的主元素。
主元素问题就是:
给定一个数组,判断其是否有主元素,并求这个元素。
使用Random select算法,可以在O(n)时间内解决此问题:1 求中位数。2 检验中位数是否为主元素。
不过这样需要平均扫描每个元素3次。事实上此问题还有更巧妙的解法,可以只扫描每个元素2次。欲知解法如何,去Google上百度一下……
分享到:
相关推荐
17082 两个有序数序列中找第k小(必做) 时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0 题型: 编程题 语言: C++;C;VC;JAVA Description 已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为...
第一行有三个数,分别是长度m、长度n和k,中间空格相连(1,n; 1<=k<=m+n)。 第二行m个数分别是非减序的序列X。第三行n个数分别是非减序的序列Y。 输出格式 序列X和Y的第k小的数。 输入样例 5 6 7 1 8 12 12 21...
已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为n, 现在请你用分治算法,找出X和Y的第k小的数,算法时间复杂度为O(max{logm, logn})。
求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分: 6; 5+1; 4+2,4+1+1; 3+3,3+2+1,3+1+1+1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1。 Input 输入包含n+1行; 第一行是一个整数n,...
分治思想:将难以直接求解的大问题分解为k个相同的子问题;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;
5.15 数据段中已定义了一个有N个字数据的数组M,试编写一程序求出M中绝对值最大的数,把它放在数据段的M+2n单元中,并将该数的偏移地址存放在M+2(n+1)单元中。 5.16 在首地址为DATA的字数组中,存放了100H个16位...
列出所有数字1到数字n的连续自然数的排列,要求所产生的任一数字序列中不允许出现得复数字。 Input 输入:n(1<=n) Output 由1~n组成的所有不重复的数字序列,每行一个序列。 Sample Input 3 Sample Output 1 2 3...
已知n个人(不妨分别以编号1,2,3,…,n 代表 )围坐在一张圆桌周围,首先从编号为 k 的人从1开始顺时针报数,1, 2, 3, ...,记下顺时针数到 m 的那个人,同时从编号为 k 的人开始逆时针报数,1, 2, 3, ...,数到 ...
已知不相同的数不超过10000个,现在需要在其中查找某个自然数,如找到则输出并统计这个自然数出现的次数,如没找到则输出NO。 Input 输入由多组测试数据组成。 每组测试数据输入包含n+1行; 第一行是两个整数n...
一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从下一个人开始重新从1开始报数,如此下去,直至所有人全部出列为止。...
已知n个人(不妨分别以编号1,2,3,…,n 代表)围坐在一张圆桌周围,从编号为 k 的人开始,从1开始顺时针报数1, 2, 3, ...,顺时针数到m 的那个人,出列并输出。然后从出列的下一个人开始,从1开始继续顺时针报数...
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。 ...
一,已知十个数,求平均数。 L=[1,2,3,4,5,6,7,8,9,10] a=sum(L)/len(L) print("avge is:", round(a,3) ) 运行结果: avge is: 5.5 二,设置输入个数,求平均数 n = int(input("请输入所求平均数的个数: ")) l = ...
已知n项作业E={1, 2, … ,n} 需要完成,只有一台机器,同一时刻至多完成一个作业,而且每项作业需要的时间都是单位时间1。 第k项作业要求在时间fk时刻完成,而且完成这项作业将获得效益pk,(k=1, 2, … , n)。 E的...
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律...
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律...
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
每个测试数据的第一行包含一个整数 n (1 <= n ),表示右鸽的好友个数,接下来的一行,包含 n 个整数,按顺序表示右鸽每个好友的能力值ai(-100 )。接下来的一行包含两个整数,k 和 d (1 <= k , 1 <=