本篇内容介绍了“Python算法面试题有哪些”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
1、25匹马,有一条只能5匹马比赛的赛道,我们无法计时,只能看到马的排名,如何用最短的次数找出跑的最快的5匹马?
这道题目的话最好的情况是7次,最坏的情况是10次。我们首先建立一个表格,先把25匹马分为如下的五组:
每组进行比赛,假设第一组快慢顺序为A1、A2、A3、A4和A5,第二组依次类推。那么各组的第一分别是A1、B1、C1、D1、E1。
在最好的情况下,先让A1、B1、C1、D1、E1比赛,得到第一名,假设A1是第一名,并且顺序是A1 > B1 > C1 > D1 > E1;然后让A2加入比赛,若比赛结果为B1 > C1 > D1 > A2。那么前五名是A1、B1、C1、D1、E1,共需比赛7次。那么在最坏的情况下,每次新加入一个候补,得到一个新的名次的马,此时共需要10次比赛。
这个题更加常考的是问如何用最短的次数找出最快的3匹马,这个题和找出5匹马还不太一样。如果找出3匹马,只需要比赛7次即可,前六次假设和上面的过程一样,A1是最快的马,剩下的名次是B1 > C1 > D1 > E1。此时并不是让A2、B1、C1、D1、E1进行比赛,先仔细分析一下,第二名一定出现在B1 和 A2之中,若B1 > A2,那么第三名出现在A2 、B2、C1之中,若A2 > B1,那么第三名出现在A3 、B1之中。因此,第七场比赛只需要让A2、A3、B1、B2、C1五匹马比赛,得到前两名即可。因此只需要7场比赛就可以得到跑的最快的3匹马。
2、一条无限长的直线,有两个机器人,两个机器人执行同一段代码,这一段代码中只有几条语句:right代表向右走,left代表向左走,if arrived else代表另一个机器人是否走过这个地方。goto代表代码的跳转,请写一段代码确保两个机器人能够相遇。
伪代码如下:
start: if arrived: right right else: right goto start
简单解释一下,假设两个机器人A和B都往右走,B在前A在后,一开始二者保持相同的速度前进,当A到达曾经B经过的点后,发现此后的路是B此前经过的,那么A开始提速两倍,B一直保持原来的一倍速度不变,那样的话,A一定会追上B。
3、海量数据如何求中位数?数据无法放入内存,只需考虑空间复杂度,不需要考虑时间复杂度。
假设我们的数据都是无符号的32位整数,既然不考虑时间复杂度,可以通过二进制来解决,从高位到低位依次判断,首先遍历所有数据,并记录最高位为0和1的个数(最高位为0的肯定是小于最高位为1的)记为N0、N1。
那么根据N0和N1的大小就可以知道中位数的最高位是0还是1
若N0>N1,那么再计算N00和N01,如果N00>(N01+N1)(这里一定注意是N00要大于N01和N1数量的总和,而非N00大于N01),则说明中位数的最高两位是00,那么再计算N000和N001....依次计算就能找到中位数。
4、信息流采样,有n份数据,但是n的长度并不知道,设计一个采样算法,使得每份被选择的概率是相同的。
这道题其实考察的是蓄水池采样的方法,这里咱们简单介绍下蓄水池算法的思路。
一开始选择第一个数据作为候选数据,以概率1/2拿第二个数据替换当前候选,以1/3选择拿三个数据替换当前候选,依次类推。
这样,第x个数据为最终选择的数据的概率 = x被选择的概率 * (x+1没被选择的概率) * (x+2没有被选择的概率) ......(n没有被选择的概率)
举个例子,第2哥数据被选择的概率为:1/2 * (2/3 * 3/4 * 4/5 .... n-1/n) = 1 / n
5、n个[0,n)的数,求每个数的出现次数(不能开辟额外空间)
这里关键是看清楚题意,n个数,然后是左闭右开的区间,也就是说每个数都不会大于等于n,那么思路主要有以下两点:
1)如果我们给一个索引下的数不管加上多少个n,那么这个数对n取余的话,我们就能知道这个数原来是多少;
2)另一方面,如果一个数出现一次,我们就在对应索引位置下的数加上n,那么每个数对应索引位置上的数对n取商的话,就是这个数出现的次数。这样就做到了没有开辟额外的空间。
代码如下:
public class timeDemo { public static void main(String[] args){ int[] arr = {0,1,3,4,3,2,5,4,3,7,3,2,4,6}; int n = 8; for(int i = 0;i输出为:
6、 已知有个rand7()的函数,返回1到7随机自然数,怎样利用这个rand7()构造rand10(),随机1~10。
产生随机数的主要原则是每个数出现的概率是相等的,如果可以得到一组等概率出现的数字,那么就可以从中找到映射为1~10的方法。
rand7()返回1~7的自然数,构造新的函数 (rand7()-1)*7 + rand7(),这个函数会随机产生1~49的自然数。原因是1~49中的每个数只有唯一的第一个rand7()的值和第二个rand7()的值表示,于是它们出现的概率是相等,均为1/49。
但是这里的数字太多,可以丢弃41~49的数字,把1~40的数字分成10组,每组映射成1~10中的一个,于是可以得到随机的结果。
具体方法是,利用(rand7()-1)*7 + rand7()产生随机数x,如果大于40则继续随机直到小于等于40为止,如果小于等于40,则产生的随机数为(x-1)/4+1。
“Python算法面试题有哪些”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联-成都网站建设公司网站,小编将为大家输出更多高质量的实用文章!
分享文章:Python算法面试题有哪些-创新互联
新闻来源:http://cdkjz.cn/article/ieosc.html