积累(二)

简介: 阿里2014实习生招聘 问:某国家非常重男轻女,若一户人家生了一个女孩,便要继续生,直到得到男孩为止。假设生男生女概率相等,请问平均每户人家有(1)个女孩。 答:此题即高数中的级数。         引申:   int f(int x){ int s=0; while(x--) s+=f(x); return max(x,1); } //若调用f(35)

微笑阿里2014实习生招聘

问:某国家非常重男轻女,若一户人家生了一个女孩,便要继续生,直到得到男孩为止。假设生男生女概率相等,请问平均每户人家有(1)个女孩。

答:此题即高数中的级数。

     

 

引申:

 

微笑

int f(int x){
	int s=0;
	while(x--) s+=f(x);
	return max(x,1);
}
//若调用f(35),此程序运行时间()
 

若调用f(35),主流PC上此程序运行时间(D)

A.几毫秒 B.几秒 C.几分钟 D.几小时

答:函数调用--复杂度

f(1)-1;f(2)-1;f(3)-2;f(4)-4;f(5)-8;f(6)-16;...;f(n)=pow(2,n-2);

f(35)=pow(2,33)=O(pow(10,9)),主流计算机一秒执行语句数O(pow(10,6)),一小时=O(pow(10,3)秒,相除得1,所以在小时级别。

 微笑问:将n条长度均为m的有序链表进行合并,合并以后的链表也保持有序。时间复杂度为多少?

答:

思路一:对长度为a和b的有序表进行归并,复杂度是O(a+b)。构造n个权重均为m的叶结点,对其构造最优二叉树。则树中所有非叶结点的权值和即为所求。答案为O(n*m*log(下标:2)(真数:n)).

引申:

对长度为n的无序数组(链表同样适用)进行二路归并排序,复杂度为n*log(n).

分析:对长度为a和b的有序表进行归并,复杂度是O(a+b)。

每趟归并将有序表的数目减少一半,初始可视为n个长度为1的有序表,所以共

lg(n)/lg(2)趟归并。

每趟归并,调用n/(2*length)次归并函数将n/length个长度为length的有序表进行两两归并。每次归并复杂度是O(2*length)。所以每趟归并复杂度是O(n)。

总的复杂度为O(n*log(n))。

思路二:等价于n*m个元素,初始状态无序,归并到log(下:2)(真:m)趟时,后续的复杂度。

 微笑问:ABCD四人夜里要过一座桥,每次最多过两人,过桥必须有手电筒。他们只有一只手电筒,四人过桥时间分别是1、2、5、10。问:安排最优方案,使过桥时间最短。

答:时间长的一块过,相当于并行处理,效率高。所以:AB-A-CD-B-AB=2+1+10+2+2=17min.

微笑有两个链表A和B,试求其首个公共结点的地址。

 微笑问:判断一棵树是否是完全二叉树的算法:

答:完全二叉树具有性质——如果一个结点没有左子树,那么它一定没有右子树。利用此性质,在广度优先搜索中对遍历结点逐一判断。

微笑问:八个人的单打比赛,选手编号由强至弱为1~8,当实力相差两个等级内(含)才有爆冷门的可能。也就是说8号存在打败6号的可能。这八个人进行1/4决赛、半决赛和决赛。问所有可能夺冠的选手中,编号最大的是几号?(6)

答:尚没发现通用解法。

微笑问:2的100次方mod 7等于(2)。

答:公约数只有1的两个数,叫做互质数。

mod,取余数运算符,7 mod 5=2;c++中为‘%’运算符。

费马小定理:a是整数,p是质数,且a,p互质,则[a的(p-1)次方mod p]恒等于1。

此题有pow(2,6)%7=1。pow(2,100)=(2的6次方)的16次方*2的4次方,故答案为16 mod 7=2。

微笑所谓两棵二叉树T1与T2相似,是指

1.都是空树;

2.都只有根结点;

3.T1左子树和右子树与T2左子树和右子树均相似。

验证算法:

bool is_similar(node*t1,node*t2){//判断两棵树是否相似 
	if(!t1&&!t2) return true;
	if(!t1||!t2) return false;
	if (is_similar(t1->lchild,t2->lchild)&&\
	    is_similar(t1->rchild,t2->rchild))
	    return true;
    return false;
}

微笑问:【2012研招真题】在内部排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中,每一趟排序结束都至少能够确定一个元素最终位置的方法是(A)

a.简单选择排序 b.希尔排序c.快速排序d.堆排序e.二路归并排序

A.acd   B.ace   C.bcd   D.cde

答:简单选择排序每次都选择未排序列中最小的元素放入最终位置。

希尔排序每次是对等步长的序列进行排序,得到的是局部有序。

堆排序,每趟堆顶的元素就是待排序列中最大或最小的(大根堆或小根堆)。

快速排序每趟后都将基准元素放入到最终位置。

归并排序会得到若干局部有序结果。

微笑跳跃链表是一种随机化数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间),并且对并发算法友好。
跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的"快速跑道",这里在层 i 中的元素按某个固定的概率 p 出现在层 i+1 中。平均起来,每个元素都在 1/(1-p) 个列表中出现,而最高层的元素(通常是在跳跃列表前端的一个特殊的头元素)在 O(log1/pn) 个列表中出现。
查找的总体代价是 O(log1/p n/p).

微笑如果某系统15*4=112成立,则系统采用的是(6)进制。

答:设为x进制。由题得(x+5)*4=x*x+x+2,解得x=6.

微笑设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按二路归并方法对该序列进行一趟扫描后的结果,为?

答:D,Q,F,X,A,P,B,N,M,Y,C,W;

共12个元素,第一趟实现两两有序,共12/2=6对。

微笑关键码序列{Q,H,C,Y,Q,A,M,S,R,D,F,X},要求递增排序,若采用初始步长为4 的希尔排序,则一趟扫描的结果是?

若采用以第一个元素为基准的快速排序,则一趟排序的结果为?

答:Q,A,C,S,Q,D,F,X,R,H,M,Y;(1,5,10有序,2,6,11有序,...)

F,H,C,D,Q,A,M,Q,R,S,Y,X。(要细心)


目录
相关文章
|
2月前
|
算法 测试技术 项目管理
阿里十年总结之软件测试的价值
本文是作者十几年工作经验的总结,也对“软件测试的价值”做个探讨,希望有机会跟团队一起走出当前的周期。
|
人工智能 运维 监控
一线技术人的成长思考总结
作为长期奋战在一线的技术人,我深刻体会到几个思维能力对技术人成长的重要性,熟练运用这几种思维可以帮助我们快速的进入到新的领域,在分析、定位和解决问题上有很大帮助。作为长期奋战在一线的技术人,我深刻体会到几个思维能力对技术人成长的重要性,熟练运用这几种思维可以帮助我们快速的进入到新的领域,在分析、定位和解决问题上有很大帮助。
一线技术人的成长思考总结
|
SQL 存储 DataWorks
浅谈-大数据工程师面临的困境和要学习的技术
读书的时候,语文老师总会让同学看看作者的生平简介,谈谈作者为什么会写出这篇文章,文章诞生的背景是什么背景,一方面是让同学理解文章,另外一方面是让同学感同身受。 鄙人,不是大厂,也不算外包,算是靠在阿里系的一家创业公司的交付部门的小小大数据工程师,心比天高,命比纸薄。 当然,也和上学没有好好学习有关系,怨不得其他人。 回到正题,咋们先从我的个人经历聊一下大数据工程师现在面临的困境和我的一些解决思路。
282 0
|
存储 运维 监控
技术与业务同行:我是如何在业务中成长的?
勇于打破自己的边界,拓展自己的技术栈。
2891 1
技术与业务同行:我是如何在业务中成长的?
|
消息中间件 运维 架构师
架构师成长之路:如何提升技术掌控力?
在很多人眼里,架构师就犹如古代的将军一般,既能运筹帷幄决胜千里,又能独闯敌营取人首级,是所有士兵们崇拜的偶像...好了,其实我只是想说:能成为一名优秀的架构师,确实是所有工程师的梦想。那么,架构师应该具备什么能力呢?
2515 0
架构师成长之路:如何提升技术掌控力?
|
Web App开发 移动开发 供应链
铁军:保持成长动力,与技术、业务、团队共成长
对于前端的成长我认为首要的是自身成长的内在动力,其次是伴随技术业务团队共同成长,不忘初心、保持空杯、梦想前行。
铁军:保持成长动力,与技术、业务、团队共成长
|
分布式计算 运维 架构师
数据技术工程师成长之路
  最近或许有伙伴发现,写技术实现及细节的变少了,更多是经历以及思想、规范。莫非是道则道,非常道,你道我也道?然,并不是:)。   当入行四五年时,个人经历中,从14年开始实习工作到15年转正,各电信项目现场跑,开发、测试、产品部署及支持运维。
9663 0
|
机器学习/深度学习 人工智能 搜索推荐
这多年来我一直在钻研的技术
上次有人说,听说tinyfool看到AlphaGo火了,马上去赶时髦学机器学习,结果真的获益匪浅。
1572 0
|
分布式计算 Hadoop 大数据
|
应用服务中间件 nginx Python