数极客首页

2013、2014年阿里巴巴算法工程师校招笔试试题整理

2013、2014年阿里巴巴算法工程师校招笔试试题整理2013、2014年阿里巴巴算法工程师校招笔试试题整理

选择题

1、一次内存访问,SSD硬盘访问和SATA硬盘随机访问的时间分别是()

A、几微秒,几毫秒,几十毫秒 B、几十纳秒,几十微秒,几十毫秒

C、几十纳秒,几十微秒,几十毫秒 D、几微秒,几十微秒,几十毫秒

解析:内存访问速度通常在50ns到80ns范围内,SSD硬盘的访问速度普通
是SATA硬盘的一千多倍,所以答案选C

2、8进制数256,转化成7进制数是(B)

A、356 B、336 C、338 D、346
解析:进制转换
八进制256转换为十进制:2*8*8 + 5*8 + 6*1 = 174
十进制174转换为七进制:336
答案:D

3、有一虚拟存储系统,若进程在内存中占3页(开端
时内存为空),若采用先进先出页面澹算法,当执行如下访页页号序列后1,2,3,4,1,2,5,1,2,3,4,5,会产生(?)次缺页?

解析:
输入:1,2,3,4,1,2,5,1,2,3,4,5
先进先出,就是保管
最近3个访问的记载
在内存中
, , <—1 中缀
1次
, ,1<—2 中缀
1次
, 1,2<—3 中缀
1次
1,2,3 <—4 中缀
1次
2,3,4 <—1 中缀
1次
3,4 ,1<—2 中缀
1次
4,1,2<—5 中缀
1次
1,2,5<—1 命中,不中缀

2,5,1 <—2 命中,不中缀

5,1,2<—3 中缀
1次
1,2,3 <—4 中缀
1次
2,3,4 <—5 中缀
1次
3,4,5
累计中缀
12次

延伸标题

在5个页框上运用
LRU页面交流

算法,当页框初始为空时,援用
序列为0、1、7、8、6、2、3、7、2、9、8、1、0、2,系统将发作
(C)次缺页
A、13 B、12 C、11 D、8
解析:
Least Recently Used 是指最近最少运用
的页面被先换出,因而

不是先进先出的机制,在淘宝面试标题
中也呈现

剖析

:缺页为:0、1、7、8、6、2、3、9、8、1、0,共11次
参考的链接:http://www.cnblogs.com/freeyiyi1993/archive/2013/05/18/3084956.html

4、有3个节点的二叉树可能有(A)种

A、5 B、13 C、12 D、15
解析:不思索
节点的排列组合
leetcode有一样的标题

5、从一副牌(52张,不含打小怪)里抽出两张牌,其中一红一黑的概率是(D)

A、25/51 B、1/3 C、1/2 D、26/51
解析: 52张牌从中抽两张,就是C522种状况

,一红一黑是C261* C261种状况

,概率P= C261 blog.sql fenxike.sql C261 /C522 =26/51
一定要留意
,第一次抽完牌之后,有个牌的数目曾经
减少了。

6、某网络的IP地址空间为192.168.5.0/24,采用定长子网划分,子网掩码为255.255.255.248,则该网络的最大子网个数、每个子网内最大可分配地址个数各位(C)

A、8,32 B、32,8 C、32,6 D、8,30
解析:
IP地址空间为192.168.5.0/24是一个c类IP地址块(其中的24表示子网掩码的前24位为1,255.255.255.0),其默许
子网掩码为255.255.255.0。若采用变长子网划分,子网掩码255.255.255.248的二进制表示为1111 1111.1111 1111.1111 1111.1111 1000,它是在255.255.255.0的基础

上,向原主机号借用了5个比特位作为新的子网号,因而

该网络的最大子网个数为2^5=32个,每个子网内的最大可分配地址个数=2^(32-29)-2=2^3-2=8-2=6 个,其中“-2“表示主机号全0的地址被保管

用于标志子网自身

,以及主机号全1的地址被保管

用作 该子网的广播

地址。

7、判别
有向图能否
存在回路,应用
(A)办法

最佳

A、拓扑排序 B、求最短途径

C、求关键途径
D、广度优先遍历
学问
点:
拓扑排序
一个有向无环图(Directed Acyclic Graph简称DAG)G中止

拓扑排序,是将G中一切
顶点排成一个线性序列,使得图中恣意
一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出往常

v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个汇合

上的一个偏序得到该汇合

上的一个全序,这个操作称之为拓扑排序。

8、阿里巴巴有相距1500km的机房A和B,现有100GB数据需求
经过
一条FTP衔接
在100s的时间内从A传输到B。已知FTP衔接
树立
在TCP协议之上,而TCP协议经过
ACK来确认每个数据包能否
正确传送。网络信号传输速度2*108m/s,假定
机房间带宽足够高,那么A节点的发送缓冲区能够

设置为最小(A)

A、18M B、12M C、6M D、24M
解析:
TCP协议原理:TCP每发送一个报文段,就启动一个定时器,假定

在定时器超时之后还没有收到ACK确认,就重传该报文。

数据包由A的缓冲区发往B,B在收到数据包以后,回发一个ACK确认包给A,之后A将该数据包从缓冲区释放。因而

,该数据包会不时

缓存在A的缓冲区,直到一个ACK确以为
止。标题
央求

在100s内发送100GB数据,网络的传输速率至少是1G/s,某个数据包n在A中缓存的时间就是数据包n从A到B,再加上该数据包的ACK从B到A的时间:2*1500km/(2*108m/s)=1.5*10-2s,该段时间A中缓存的数据量至少是1G/s*1.5*10-2s约为15M

个人觉得
这种办法

不是十分

精确

,由于
TCP衔接
有滑动窗口机制,能够

在未收到ACK的时分
继续发送数据,所以极端状况

下A节点的发送缓冲区能够

再减少一半,即在7.5M左右。不过标题
里并没有说到滑动窗口机制,而是说经过
ACK来确认每个数据报能否
正确传送,所以应该不思索
这种极端状况

9、假定
有每个网络结点,两两之间树立
相互

通讯
之后能够

记载
(保管
)对方的全部信息,

往常

一个网络有17个结点,要使每个结点都保管
其它一切
结点的全部信息,至少要树立
多少次通讯

解析:
假定
有n个节点,直观的依照

1-2-···-(-1)-n传播次第
,最终
n-1和n取得

了一切
节点的信息,然后取其中任一节点与1、2、···、-2这些节点交流
信息,即可让一切
节点取得

一切
信息,这样通讯次数=-1+-2=2n-3;

假定

分红
两个组呢,假定
两个组的节点个数分别为n1和n2,则每个组第一
需求
按序传播信息N1=n1-1+n2-1,然后第一组最终
两个节点和第二组的最终
两个节点就取得

了各自组的一切
信息,这四个节点两两交流
信息,需求
N2=2次,则这四个节点取得

了两个组一切
节点信息,然后取任一节点与每个组剩下的节点(分别是n1-2,n2-2)交流
信息N3=n1-2+n2-2,则通讯任务完成,总共通讯次数N=N1+N2+N3=2n1-3+2n2-3+2=2(n1+n2)-4=2n-4;

假定

分红
三个组,同样的剖析

N=2n1-3+2n2-3+2n3-3+6=2n-3,其中6表示三个组的最终
两个节点交流
信息需求
6次;

那假定

分的组数更多呢,假定
分为g组(g>=4),同上剖析

N=2n-3g+M,其中M表示g个组的最终
两个节点交流
信息所需求
的最少次数。假定
把这些点的通讯依照

两个组的方式

来处置
,则M=2*(2g-4),N=2n+g-8>=2n-4。假定
按三个组的方式

来处置
,则M=2*(2g-3),N=2n+g-6>=2n-2,可见它们都是大于等于2n-4,而且随着g的变大通讯次数也会增加

所以最优的状况

就是在分红
两个组或者四个组的时分
取到,最优状况

下通讯次数为2n-4.

10(多选)、有朋自远方来,他乘火车,轮船,汽车,飞机来的概率分别是0.3,0.2,0.1,0.4,坐各交通工具迟到的概率分别是1/4,1/3,1/12,0,下列语句中正确的是(CD)

A、假定

他准点,那么乘飞机的概率大于等于0.5
B、坐陆路(火车,汽车)交通工具准点机遇

比坐水路(轮船)要低
C、假定

他迟到,乘火车的概率是0.5
D、假定

他准点,坐轮船或汽车的概率等于坐火车的概率
解析:
设A1={坐火车},A2={坐轮船},A3={坐汽车},A4={坐飞机},B={迟到}
P(A1)=0.3
P (A2) =0.2
P (A3)=0.1
P (A4)=0.4
P(B|A1)=1/4
P(B|A2)=1/3
P(B|A3)=1/12
P(B|A4)=0
用全概公式得:
P(B)=0.3*1/4+0.2*1/3+0.1*1/12+0.4*0=3/20
乘火车来的概率用逆概公式得:
P(A1|B)=P(A1)*P(B|A1)/P(B)=1/2

11、有个苦逼的上班族,他每天遗忘
定闹钟的概率为0.2,上班堵车的概率为0.5,假定

他既没定闹钟上班又堵车那他迟到的概率为1.0,假定

他定了闹钟但是上班堵车那他迟到的概率为0.9,假定

他没定闹钟但是上班不堵车他迟到的概率为0.8,假定

他既定了闹钟上班又不堵车那他迟到的概率为0.0,那么求出他在60天里上班迟到的希冀

解析:
定闹钟概率0.8 未定闹钟概率0.2 堵车概率0.5 不堵车概率0.5
迟到概率 定闹钟 未定闹钟
堵车 0.9 1
不堵车 0 0.8
定闹钟迟到次数希冀
=0.8*(0.5*0.9+0.5*0)=0.8*0.5*0.9=0.36
不定闹钟迟到次数希冀
=0.2*(0.5*1+0.5*0.8)=0.18
所以迟到次数希冀
=0.36+0.18=0.54
60天迟到次数希冀
=60*0.54=32.4

12、有一堆石子共100枚,甲乙轮番
从该堆中取石子,每次可取2、4或6枚,若取得

最终
的石子的玩家为赢,若甲先取,则(C)

A、谁都无法取胜 B、乙必胜 C、甲必胜 D、不肯定

剖析


先取的人只需求
保证最终
剩8枚就胜了。而要保证最终
剩8枚,则必需求

保证每一个回合内取的数是一个可控的固定数,显然这个数字是8,所以只需求
保证第一次取完后,剩下的数字是8的倍数,就一定能胜。100除以8余数为4,故而,甲先取4枚,之后每一个回合所取数与上一个回合乙所取数之和为8,就能保证必胜。

13、假定一个二维数组的定义语句为“int a[3][4]={{3,4},{2,8,6}};”,则元素a[1][2]的值为(A)

A、6 B、4 C、2 D、8

14、下列有关图的遍历说法中,不正确的是(C)

A、有向图和无向图都能够

中止

遍历操作
B、基本

遍历算法两种:深度遍历和广度遍历
C、图的遍历必需
用递归完成

D、图的遍历算法能够

执行在有回路的图中

解析:
C肯定是不正确的,用队列辅助的话,能够

不用
运用
递归完成

A对的,B对的,遍历并没有显现
能否
是有向,
D应该是对的,只需求
对访问过的节点中止

标志
,也就不用思索
能否
有回路,或者说,无向图自身

就不用思索
能否
有回路
学问
点:图的深度遍历和广度遍历的递归和非递归完成

15、在16位机器上跑下列foo函数的结果是(B)

void foo() { int i = 65536; cout << i<<”,”; i = 65535; cout << i; }

A、-1,65535 B、0,-1 C、-1,-1 D、0,65535

解析:
16位机器的int型变量为16位
16位int的表示范围:-32768到32767
65536(十进制) = 10000000000000000(二进制)
65535(十进制) = 1111111111111111 (二进制)
上面是原码表示
转换为补码,除了最高位,其它位取反,加一
补码表示:分别为0和-1

16、有一段年代久远

的C++代码,内部逻辑复杂,往常

需求
应用
其完成
一个新的需求,假定有以下可行的计划

,应当优先选择(D)

A、修正
老代码的接口,满足新的需求
B、将老代码丢弃
,自己

重新完成
相似

的逻辑
C、修正
老代码的内部逻辑,满足新的需求
D、在这段代码之外写一段代码,调用该代码的一些模块,完成新功用
需求

17、设某文件经内排序后得到100个初始归并段(初始顺串),若运用
多路归并排序算法,且央求

三趟归并完成排序,问归并路数最少为(D)

A、8 B、7 C、6 D、5
**剖析

:**m个元素k路归并的归并趟数s=logk(m),代入数据:logk(100)≦3

18、一个优化的程序能够

生成一n个元素汇合

的一切
子集,那么该程序的时间复杂度是(B)

A、O(!) B、O(2 ) C、O( 2 ) D、O(nlog )

19、2-3树是一种特殊的树,它满足两个条件:

(1)每个内部节点有两个或三个子节点;
(2)一切
的叶节点到根的途径
长度相同;
假定

一颗2-3树有9个叶节点,下列数据量
个非叶节点的2-3树可能存在的有(BE)
A、8 B、7 C、6 D、5 E、4

剖析

依据

条件(2),叶节点只能在同一层,依据

条件(1),上一层的父节点只能是3个或4个,只能是如下图所示的两种结果
2013、2014年阿里巴巴算法工程师校招笔试试题整理

20、下列有关进程的说法中,错误的是(ABC)

A、进程与程序是一亿对应的 B、进程与作业时逐一

对应的
C、进程是静态的 D、进程是动态的过程

21、下列函数定义中,有语法错误的是(D)

A、void fun(int x, int y){x = *y;}
B、int blog.sql fenxike.sql fun(int *x, int y){return x += y;}
C、void fun(int *x, int y){*x += y;}
D、void fun(int x, int y){*x = *y;}

解答题:

1、有一个算法,查找n个元素的的数组的最大值和最小值,要比较

2n次;请写一个最高效的算法,并阐明

他要比较

的次数。请留意
复杂度的常数 (不用写代码,阐明

步骤和过程即可,要定出比较

的次数,没写不给分)

解析:
剖析

:已知的比较

2n次的办法

,显然是将每个元素和最大值、最小值各比一次,要减少比较

次数,能够

有多种优化办法

办法

一:一个元素先和最大值比较

,假定

比最大值大,就不用再和最小值比较

(或者先和最小值比较

,假定

比最小值小,就不用再和最大值比较

),普通
状况

下,这种优化后的比较

次数一定会少于2n

办法

二:把数组两两一对分组,假定

数组元素个数为奇数,就最终
单独分一个,然后分别对每一组的两个数比较

,把小的放在左边,大的放在右边,这样遍历下来,总共比较

的次数是 N/2 次;在前面分组的基础

上,那么能够

得到结论,最小值一定在每一组的左边部分

找,最大值一定在数组的右边部分

找,最大值和最小值的查找分别需求
比较

N/2 次和N/2 次;这样就能够

找到最大值和最小值了,比较

的次数为N/2 blog.sql fenxike.sql 3 = (3N)/2 次

2、有三个非递加
序列的数组a[l]、b[m]、c[],求他们之间的最小距离

。已知距离

的定义如下:distance = max(|a[i]-b[j]|, |a[i]-c[k]|, |b[j]-c[k]|)

解析:
这道标题
有两个关键点:

第一个关键点:
max{|x1-x2|,|y1-y2|} =(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 –公式(1)
我们假定
x1=a[ i ],x2=b[ j ],x3=c[ k ],则
Distance = max(|x1 – x2|, |x1 – x3|, |x2 – x3|) = max( max(|x1 – x2|, |x1 – x3|) , |x2 – x3|) –公式(2)
依据

公式(1),max(|x1 – x2|, |x1 – x3|) = 1/2 ( |2×1 – x2– x3| + |x2 – x3|),带入公式(2),得到
Distance = max( 1/2 ( |2×1 – x2– x3| + |x2 – x3|) , |x2 – x3| )
=1/2 blog.sql fenxike.sql max( |2×1 – x2– x3| , |x2 – x3| ) + 1/2*|x2 – x3| //把相同部分

1/2*|x2 – x3|分别

出来
=1/2 blog.sql fenxike.sql max( |2×1 – (x2 + x3)| , |x2 – x3| ) + 1/2*|x2 – x3| //把(x2 + x3)看成一个整体,运用
公式(1)
=1/2 blog.sql fenxike.sql 1/2 ((|2×1 – 2×2| + |2×1 – 2×3|) + 1/2|x2 – x3|
=1/2 |x1 – x2| + 1/2 |x1 – x3| + 1/2*|x2 – x3|
=1/2 *(|x1 – x2| + |x1 – x3| + |x2 – x3|) //求出来了等价公式,终了

第二个关键点:
怎样
找到(|x1 – x2| + |x1 – x3| + |x2 – x3|) 的最小值,x1,x2,x3,分别是三个数组中的恣意
一个数,算法思想是:
用三个指针分别指向a,b,c中最小的数,计算一次他们最大距离

的Distance ,然后在移动

三个数中较小的数组指针,再计算一次,每次移动

一个,直到其中一个数组终了

为止,最慢(l+ m + )次,复杂度为O(l+ m + ).

3、在黑板上写下50个数字:1至50。在接下来的49轮操作中,每次做如下动作:选取两个黑板上的数字a和b檫去,在黑板上写|b-a|。请问最终
一次动作之后剩下数字可能是什么?为什么?

解析:
第一步:奇偶剖析

,证明结果不可能为偶数
有以下三种操作:
1. | 奇 – 偶 | = 奇
2. | 偶 – 偶 | = 偶
3. | 奇 – 奇 | = 偶
也就是说每次操作减少0个或者2个奇数。
而原有 1,3,5,…,49 共25个奇数
所以以上操作知道

剩余一个数时,此数必为奇数

第二步:结构

一切
奇数的解
第一
留意
到关于
a, a+1, b, b+1 四个数,在操作
| (a+1) – a | = 1
| (b+1) – b | = 1
| 1 – 1 | = 0
后,化为了0
而0与恣意
数k执行以上操作 | k – 0 | = k,无影响。
总结为自然言语
就是“两个连续整数对,能够

直接疏忽

”。
更进一步总结为“偶数个连续整数对,能够

直接疏忽

”。
然后开端
结构

了:
需求
得到结果2k-1,其中k=1,…,25
我们就先把1和2k拿出来,
则余下了 2,3,4,…,2k-1, 2k+1,…50
一共24个连续整数对,
依据

我们刚才

的结论,这是能够

直接疏忽

的。
所以,得到了 | 2k – 1 | = 2k-1

4、(4分)已知如下代码,并在两个线程中同时执行f1和f2,待两个函数都返回后,a的一切
可能值是哪些?

int a = 2, b = 0, c = 0; void f1() void f2() { { a = a blog.sql fenxike.sql 2; c = a + 11; a = b; a = c; } } 

剖析


思索
四行代码的执行次第
即可
(1)b=a*2,c=a+11,a=c,a=b a=4
(2)b=a*2,c=a+11,a=b,a=c a=13
(3)b=a*2,a=b,c=a+11,a=c a=15
(4)c=a+11,a=c,b=a*2,a=b a=26

5、文件分配表FAT是管理磁盘空间的一种数据结构

,用在以链接方式存储文件的系统中记载
磁盘分配和追踪空白磁盘块,整个磁盘仅设一张FAT表,其结构

如下所示,假定

文件块号为2,查找FAT序号为2的内容得知物理块2的后继物理块是5,再查FAT序号为5的内容得知物理块5的后继物理块是7,接着继续查FAT序号为7的内容为“Λ”,即该文件终了

标志,

2013、2014年阿里巴巴算法工程师校招笔试试题整理

剖析


(1)磁盘块大小为1KB,540MB的硬盘能够

分红
540MB/1KB=5.4*105个磁盘块,因而

至少需求
5.4*105<220个编号,需求
20BIt存储空间
(2)同理,1.2G至少需求
1.2*106<221个编号,为21BI,由于FAT序号以4BIts为单位向上扩展

,因而

需求
24BIt存储空间

6、有一个怪物流落到一个荒岛上,荒岛上有n条鳄鱼。每条鳄鱼都有实力单独吃掉怪物。但是吃掉怪物是有风险的,会构成

膂力
值降落
,然后会有可能被掉其他鳄鱼吃。问,最终
那个怪物是风险
的还是安全

的?

解析:
F()表示n条鳄鱼时,怪物的安全

状态。1表示安全

,0表示不安全


鳄鱼吃掉怪物后,变成怪物。
=1时,怪物不安全

,F(1)=0
=2时,第一条鳄鱼吃掉怪物后,会被另一条吃掉。所怪物是安全

的。F(2)=1
=3时,第一条鳄鱼吃掉怪物后,另外两条都不敢吃第一条鳄鱼。F(3)=0

由上面的推导可见,若F(-1)为安全

状态,那么一条鳄鱼能够

肆无忌惮地吃掉怪物;假定

F(-1)为不安全

状态,那么就没有鳄鱼敢吃怪物。
F()= 1 if F(-1)=0
F()=0 if F(-1)=1
再由初始F(1)=0,F(2)=1能够

得到:
n为奇数是不安全

,n为偶数时安全

7、有N-1个大众

和1个明星,一切
的大众

都认识该明星,但明星不认识任何一个大众

,大众

之间是招认

识未知。假定

你是一个机器人,具有讯问
一个人是招认

识另外一个人的功用
,请设计一个最佳算法,在这N个人中最快地找到该明星。

解析:
其实解法很简单,假定
有1,2,3,4,5个人
从1开端
,问1是招认

识2
假定

认识,留下2,淘汰1
假定

不认识,留下1,淘汰2
之后留下的继续讯问
3…….
最终剩下的那个就是所谓的明星。
这种解法应用
的是减小数据范围
的思绪
,不时
将问题的解汇合

减少
,最终得到解。和从n个数中找到呈现
次数大于n/2的那个问题很相似

void findmin(int *a,int ) { int i,find=0; for(i=1;i<;i++) { if(a[find]>a[i]) { find=i; } } printf("%dn",find+1); }

8、这道题的大意是:有一个淘宝商户,在某城市有n个仓库,每个仓库的储货量不同,往常

要经过
货物运输,将每次仓库的储货质变
成分歧
的,n个仓库之间的运输线路围城一个圈,即1->2->3->4->…->->1->…,货物只能经过
衔接
的仓库运输,设计最小的运送本钱
(运货量*路途
)抵达

淘宝商户的央求

,并写出代码。

解析:
http://blog.csdn.net/l_f0rm4t3d/article/details/23967995
假定
n个仓库的初始储货量分别为warehouse[1],warehouse[2],…,warehouse[]
计算平均

储货量
average = (warehouse[1]+warehouse[2]+…+warehouse[])/
就算出来了最终的结果中,每个仓库应该有的存量
第一
,从仓库1向仓库n运送k;
然后,从1到n-1,依次向下运送某一特定值,使得每一个仓库的余量都为average,剩下的问题就是求总代价的最小值了。
设第0步从1仓库向n仓库(留意
由于
是圆圈,所以途径
长度是1)运出k存量,k能够

为负,假定

为负数,意味着从n向1运输|k|存量,然后从循环,从(1到n-1),从i仓库向i+1仓库运输,运输的量需求
保证i仓库在运输终了
后等于average
第0步(从仓库1向仓库n运送k):破费

代价为 |k|,
第1步(确保仓库1的余量为average):需求
破费

代价为|warehouse[1]-average-k|,也就是从1向2伙从2向1运输
第2步(确保仓库2的余量为average):代价为 |warehouse[2]+warehouse[1]-average-k-average|=|warehouse[1]+warehouse[2]-2*average-k|
…-1.
第n-1步:代价为|warehouse[1]+warehouse[2]+…+warehouse[-1]-(-1)*average-k|,此时,仓库n剩下的货物量:
(warehouse[]+k)+warehouse[1]+warehouse[2]+…+warehouse[-1]-(-1)*average-k=(warehouse[1]+warehouse[2]+…+warehouse[])-(-1)*average=average

刚好也满足,其实这里不用推导,由于
平均

值是算好的,所以最胡一定是刚好完成的。
总的代价为:
无妨
令sum[i] = warehouse[1]+warehouse[2]+…+warehouse[i]-i*average
则,总代价可表示为:|k|+|sum[1]-k|+|sum[2]-k|+…+|sum[-1]-k|
这个式子能够

看成在水平

数轴上寻觅
一个点k,使得点k到点0,sum[1],sum[2],sum[3],…,sum[-1]的距离

之和最小,显然k应该取这n个数的中位数。至此问题处置

9、战场上不同的位置有N个战士(>4),每个战士知道

当前的一些战况,往常

需求
这n个战士经过
通话交流,相互

传达自己

知道

的战况信息,每次通话,能够

让通话的双方知道

对方的一切
情报,设计算法,运用
最少的通话次数,使得战场上的n个战士

知道

一切
的战况信息,不需求
写程序代码,得出最少的通话次数。

和选择题第9题一是一样的。

10、补全反转数组的代码,如A{1,2,3,4}反转之后A{4,3,2,1}

void f(int *A,int )
{
int i,temp;
for(i=0;i

算法工程师 附加题】

请设计一个算法,在满足质因数仅为3,5,7或其组合的数中,找出第K大的数。比如

K=1,2,3时,分别应返回3,5,7。央求

算法时间复杂度最优。
解析:
我们能够

用3个队列来维护这些数。第1个队列担任
乘以3,第2个队列担任
乘以5, 第3个队列担任
乘以7。算法描画

如下:
1. 初始化结果res=1和队列q3,q5,q7
2. 分别往q3,q5,q7插入1*3,1*5,1*7
3. 求出三个队列的队头元素中最小的那个x,更新结果res=x
4. 假定

x在:
q3中,那么从q3中移除x,并向q3,q5,q7插入3*x,5*x,7*x
q5中,那么从q5中移除x,并向q5,q7插入5*x,7*x
q7中,那么从q7中移除x,并向q7插入7*x
5. 重复

步骤3-5,直到找到第k个满足条件的数
留意
,当x出往常

q5中,我们没往q3中插入3*x,那是由于
这个数在q5中曾经
插入过了。

最优解:
其实当我们第一次看到这个题,都会想到K是不是一个能够

求解的数。
但马上艰难

就呈现
了,我们不知道

怎样
为3^x,5^y,7^z排序。
对数学较敏锐的人会马上想出办法


5^y=3^(log3(5)*y)
7^z=3^(log3(7)*z)
这样一来:
a()=3^x*5^y*7^z=3^(x+log3(5)*y+log3(7)*z)
就只需求
对x+log3(5)*y+log3(7)*z的第K大的数中止

求解。
由于
这里x,y,z之间是固定比例,很容易做。

【附加题】淘宝上每天都产生大量的用户行为,比如

搜索、珍藏

、置办

等等,设计一个计划

,依据

这些历史用户行为,来推断用户的性别。

参考:

http://blog.csdn.net/thebestdavid/article/details/11975809
http://blog.163.com/yichangjun1989yichangjun1989yichangjun1989@126/blog/static/1319720282014518222755/
http://www.sjsjw.com/kf_www/article/023165ABA015253.asp
http://www.cnblogs.com/ksedz/p/3346294.html

作者:jimmybao0730

链接:http://blog.csdn.net/linglun3/article/details/44835223

发表评论

评论已关闭。

相关文章