算法岗笔试面试题


本材料是从阿里、腾讯、网易、美团大众点评、搜狐等企业的网络公开招聘题中进行精选,并附上详细解析和解答思路,适合算法岗应聘者进行学习。

1. 0 到 9999 这 1 万个数中有多少个数字 7 ?
解析:总共四位数,每个位置上的可能分别为 10 种,0-9,所以将出现 7 的情况分为四种,分别是个位、十位、百位、千位上出现,分别是 10*10*10=1000 种,故答案为:4*1000=4000 种
推广来说 1-9 数字的题目都是一个结论。

2. 春节期间小明使用微信收到很多个红包,非常开心。在查看领取红包记录时发现,某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现,要求算法尽可能高效给定一个红包的金额数组 gifts 及它的大小 n,请返回所求红包的金额。没找到,返回 0。
解析:这是典型的算法题,可以使用部分快速排序算法求解,通过反复调用 partition函数来实现。
先在数组中随机选取一个数字,而后通过 Partition 函数返回该数字在数组中的索引 index,1)如果 index 刚好等于 n/2,则这个数字便是数组的中位数,即是要求的数;2)如果 index 大于 n/2,则中位数肯定在 index 的左边,反之在右边,缩小搜寻区域,可以减少一半排序时间。时间复杂度来讲,最优情况下为 O(1),平均情下为 O(n),最坏的时间复杂度依然为 O(n^2),空间复杂度为 O(1)。

3. 如何实现一个随机播放音乐,要求能够方便查看上一首播放的是什么,方便交换即将播放的歌曲顺序
解析:实现随机播放音乐:先对每首歌曲附上编号,使用洗牌算法来打乱歌曲顺序,Python 的 random 库中,shuffle 函数可以实现洗牌算法,并记录歌曲编号。

4.不使用第三个数(临时变量)交换两个整形数
解析:
使用位运算求解:
a^=b
b^=a
a^=b

5. 假设淘宝一天有 5 亿条成交数据,求出销量最高的 100 个商品。
解析:
方法:采用 Hash 映射+Hash 统计+排序算法
先用哈希统计每个商品的成交次数,可以把 5 亿个数据分组存放,比如放在5000 个文件中。这样就可以分别在每个文件的 10^6 个数据中,用哈希+排序算法,求出每个区域内前 100 个频率最高的商品,最后求出所有记录中出现频率最高的前100 个商品。

6. 小 Q 最近遇到了一个难题:把一个字符串的大写字母放到字符串的后面,各个字符的相对位置不变,且不能申请额外的空间。你能帮帮小 Q 吗?
例如:OkhaoPingCeilXu 转换后 khaoingeiluOPCX

解析:
需要注意必须是 O(1)的空间复杂度,所以不能引入新列,思路是把大写字母移动到字符串末尾。
代码如下:

include <iostream>

include <algorithm>

include <string>

using namespace std;
//交换值的函数
void Swop(char& a,char& b){
char c=a;
a=b;
b=c;
}
int main(void) {
string s;
//判断是否是大写字母,是的话就进行两两交换,换到字符串末尾
while(cin>>s){
int len = s.length();
int End = len;
for(int i=0;i<End;i++){
if(s[i]>='A' && s[i]<='Z'){
for(int j=i;j<len-1;j++)
Swop(s[j],s[j+1]);
End--;
i--;
}
}
cout<<s<<endl;
}
return 0;
}
时间的复杂度为 O(n^2)
时间的复杂度为 O(n^2)

7. 假设支付宝红包口令支持 1 到 6 位的数字组合,即'0'、'1'、'003'和'999999'都是合法的红包口令,那么总共可以有多少个合法的红包口令______
解析:
由 题 目 可 知 , 0 、 00 、 000 算 是 不 同 的 口 令 , 那 么 答 案 为10+10^2+10^3+…+10^6=111110,这道题目的思路类似于题 1。

9. 8. 甲乙两个人比试射箭,两人射术水平一样,单次射中的概率都为 0.5。如果甲射了 101 箭,而乙射了 100 箭,求甲射中次数比乙射中次数多的概率是?
A、 1/4
B、 1/2
C、 3/4
D、 1/3
答案:B
解析:
前 100 次中,分为甲多(A)、甲乙一样多(B)、乙多(C)三种情况(三个事件互斥),因为水平一样,则事件 A、C 发生概率一样
P(甲射中次数多)=P(前 100 次甲射中次数多)+P(前 100 次一样多且最后一次甲射中)=[P(前 100 次甲多)+P(前 100 次乙多)]/2+P(前 100 次一样多)*P(最后一次甲射中)=P(A+B+C)/2=1/2

9.下列关于线性表,平衡二叉树,哈希表存储数据的优劣描述错误的是?
A、哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为 O(1);
B、线性表实现相对比较简单
C、平衡二叉树的各项操作的时间复杂度为 O(logn)
D、平衡二叉树的插入节点比较快
答案:D
解析:
在平衡二叉树中插入节点后需要保持整棵数的平衡性,所以还需要一次或者多次的树旋转来重新平衡这个树,其余选项为正确的,你可以进行记忆

10. 风口之下,猪都能飞。当今中国股市牛市,真可谓“错过等七年”。 给你一个回顾历史的机会,已知一支股票连续 n 天的价格走势,以长度为 n 的整数数组表示,
数组中第 i 个元素(prices[i])代表该股票第 i 天的股价。
假设你一开始没有股票,但有至多两次买入 1 股而后卖出 1 股的机会,并且买入前一定要先保证手上没有股票。若两次交易机会都放弃,收益为 0。 设法计算你能获得的最大收益。 输入数值范围:2<=n<=100,0<=prices[i]<=100

解析:
这是一道考察动态规划的问题:两次买卖机会,则一次出现在左边,一次出现在右边,利用动态规划的思想,首先从最左边开始从左往右扫描,求出最大收益,然后从最右边开始从右往左扫描求出右边的最大收益,然后再比较一次和的大小,就可以得出。
代码:
int calculateMax(vector<int> prices) {
int n=prices.size();
if(n<=1)
return 0;
vector<int>left(n,0);
vector<int>right(n,0);
int min=prices[0];
//分别从左右开始搜寻最大收益
for(int i=1;i<n;i++)
{
if(min>prices[i])
min=prices[i];
left[i]=max(prices[i]-min, left[i-1]);
}
int high=prices[n-1];
for(int i=n-2;i>=0;i--)
{
if(high<prices[i])
high=prices[i];
right[i]=max(high-prices[i],right[i+1]);
}
//比较收益和的大小,求出最大值
int result=0;
for(int i=0;i<n;i++)
{
if(right[i]+left[i]>result)
result=right[i]+left[i];
}
return result;
}

11. 一个具有 3 个节点的二叉树可以有几种形态。
答案:3 种
解析:
两层的有一种
三层的,第二层 2 种,第三层 2 种,一共 1*2*2=4 种
所以三个节点一共 5 种形态

12.N 个节点的二叉树有多少种形态?
解析:
12 题是 11 题的一个扩展,基本思路如上题,但是有个更快速的方法,用到Catalan 数,公式为:m=C(N,2N) /(N+1),Catalan 数是组合数学中一个常在计数问题中出现的数列,则一共有 m=C(N,2N) /(N+1)种形态

13. 给定一个整数 sum,从有 N 个有序元素的数组中寻找元素 a、b,使得 a+b 的结果最接近 sum,最快的平均时间复杂度是____。
A、O(N^2)
B、O(log N)
C、O(N)
D、O(N^3)
E、O(NLogN)
F、不确定
答案:C
解析:
设置两个指针,一个位于最小值,一个位于最大值,即链表的头尾;取指针指向数值,进行加总并和 sum 比较,和大于 sum 时:尾指针向前移动一位;和小于sum 时:首指针向后移动一位,直到差值最小为止,遍历一遍的时间复杂度为 O(N)

14. 下列算法中,没有使用贪心策略的是()
A、 Prim 算法
B、 Kruskal 算法
C、 Dijkstra 算法
D、 KMP 算法
答案:D
解析:
贪心策略是在对问题求解时,总是做出在当前看来是最好的选择,且缺少约束条件。也就是说,贪心策略不从整体最优上加以考虑,在某种意义上求得的是局部最优解。
Prim 算法属于贪心策略,先任意选择一个初始起点,构造顶点集,寻找与顶点集相邻权值最小的边和另一顶点,从而扩充顶点集,最后构造出最小生成树
Kruskal 算法通过合并顶点所在的子集合,选择边上权值最小的顶点集合进行联合,直到涵盖所有的顶点,生成最小生成树
Dijkstra 算法是解单源最短路径的贪心算法,通过扩充顶点集,不断做贪心选择来进行扩充
KMP 算法是一种改进的字符串匹配算法,时间复杂度是 O(m+n),主要使用的是递推的方法,没有涉及贪心策略

15. 某一系统功能,需要一次性加载 N(N 在 1000 左右)个随机数,后续只对该集合进行遍历.最宜采用哪种结构存放?
A、Hash 表
B、链表
C、图
答案:B
解析:
1.Hash 表不适合遍历,利用 Hash 算法来决定存储位置,
2.链表适合遍历但是不适合随机访问
3.图用于表示物件与物件之间关系的数学对象,但是不强调数据之间的关系,遍历效率不如链表

16. 判断有向图是否存在回路,利用( )方法最佳 。
A、拓扑排序
B、求最短路径
C、求关键路径
D、广度优先遍历
答案:A
解析:
拓扑排序主要是对有向无环图进行排序,步骤是
1.选择入度为 0 的顶点并输出;
2.从网中删除此顶点及所有出边。循环执行这两个步骤,直到不存在入度为 0 的顶点为止。
拓扑排序每次选的点都是入度为 0 的点,如果没有这样的点,就不能构成拓扑排序,则可以判断是存在回路的。

17. 体育课的铃声响了,同学们都陆续地奔向操场,按老师的要求从高到矮站成一排。每个同学按顺序来到操场时,都从排尾走向排头,找到第一个比自己高的同学,并站到他的后面,这种站队的方法类似下列哪种算法?
A、快速排序
B、插入排序
C、冒泡排序
D、归并排序
答案:B
解析:
插入排序:将数据插入到已经排好序的序列中去,基本思想是:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中的适当位置上,直到全部放入位置。

18.设有一个栈,元素依次进栈的顺序是 A,B,C,D,E。下列不可能的出栈顺序有?
A、A,B,C,D,E
B、B,C,D,E,A
C、E,A,B,C,D
D、E,D,C,B,A
答案:C
解析:
堆栈遵循先进后出原则,若进栈顺序是 ABCDE,则每个选项的可能性为:
1. A,B,C,D,E:先放入 A,取出 A,再放入 B,取出 B 依此类推
2. B,C,D,E,A:先放入 A,再放入 B,取出 B,再放入 C,取 C,放入 D,取 D,放入 E,取 E,最后取出 A
3. E,A,B,C,D:要想取出 E,则必须 ABCDE 都放入,取出 E 后不能直接取 A,所以是错误的
4. E,D,C,B,A:放入 ABCDE,再依次取出 ABCDE

19. 大整数 845678992357836701 转化成 16 进制表示,最后两位字符是?
A、AB
B、EF
C、8B
D、9D
答案:D
解析:
方法一:
将 10 进制转化为 2 进制,再转化为 16 进制;10 进制转化成 2 进制采用取余的方法,因为是倒着取余,所以只需计算后 8 位,为 10011101,转化为 16 进制时,注意2 进制转化 16 进制可以每四位进行切分,对应以下转换表可得,1001——9,;1101——D,所以末尾两位为 9D
转换表:
0001——1
0010——2
0011——3
0100——4
0101——5
0110——6
0111——7
1000——8
1001——9
1010——A
1011——B
1100——C
1101——D
1110——E
1111——F
方法二:
使用排除法,利用同余关系进行,845678992357836701 除以 4 余数为 1,16 进制数中决定除以 4 后余数的只有最后一位,选项中只有 D(十进制中的 13)除以 4 余数是 1,所以选择 D
看到这么长串的数字,应该依靠一些技巧进行解题

20. C 市现在要转移一批罪犯到 D 市,C 市有 n 名罪犯,按照入狱时间有顺序,另外每个罪犯有一个罪行值,值越大罪越重。现在为了方便管理,市长决定转移入狱时间连续的 c 名犯人,同时要求转移犯人的罪行值之和不超过 t,问有多少种选择的方式?
输入描述:
第一行数据三个整数:n,t,c(1≤n≤2e5,0≤t≤1e9,1≤c≤n),第二行按入狱时间给出每个犯人的罪行值 ai(0≤ai≤1e9)
输出描述:
一行输出答案。
输入例子:
3 100 2
1 2 3
输出例子:
2
解析:
这是一道动态规划的问题,确定头尾的位置,每一次循环都往后移动一位,并进行判断
Python 程序:
n=int(input("共多少罪犯:"))
t=int(input("最大上限制"))
c=int(input("转移罪犯数"))
a=eval(input("输入罪行值"))
num=0
for i in range(n+1-c):
if sum(a[i:(i+c)])<t:
num+=1
print("hehe",i)
else:

continue
print(num)

21.对数列 (25,84,21,47,15,27,68,35,20) 进行排序,元素序列的变化情况如下:
(1)25,84,21,47,15,27,68,35,20
(2)20,15,21,25,47,27,68,35,84
(3)15,20,21,25,35,27,47,68,84
(4)15,20,21,25,27,35,47,68,84
则该排序方法为()
A.快速排序
B.简单选择排序
C.希尔排序
D.归并排序
答案:A
解析:
从(1)到(2):取第一个数 25,放到它应该在的位置,25 左边的数都比 25小,右边的都比 25 大;
从(2)到(3):对 25 左边的数列和 25 右边的数列{20,15,21},{47,27,68,35,84}分别进行快速排序,同样先取各数列的第一个数 20 和 47,使其分别放到应该在的位置,即左边的数都比它小,右边的都比它大;
从(3)到(4):对{15},{21},{35,27},{68,84}四个子序列进行排序,最终排序完成;
从整个过程分析,是一个快速排序的过程。

22.(多选)使下列算法的时间复杂度描述错误的有?
A.冒泡排序:O(n*n)
B.选择排序: O(n*n)
C.插入排序: O(n*n*n)
D.快速排序: O(nlogn)
E.堆排序: O(nlogn)
F.归并排序:O(n * n)
答案:C, F
解析:
下图列出了若干排序算法复杂度的对比,请进行理解和记忆

23.下列算法段中,时间复杂度为()
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
x=0;
for(k=1;k<=n;k++)
x+=a*b;
}
}
A.O(n^2)
B.O(n^2*(n+1))
C.O(n*(n+1))
D.O(n^3)
答案:D
解析:
三重循环,实际循环次数为(1+2+3+...+n)*n,O 计算时间复杂度忽略常数系数,且只保留最高项.。三层循环,每层最多都是 n,所以一共的时间复杂度为n^3。

24.序列{2,1,4,9,8,10,6,20}是某排序算法第二轮排序的结果,则该算法只能是
A.快速排序
B.冒泡排序
C.选择排序
D.插入排序
答案:A
解析:
排除法
冒泡排序特征第一趟排序之后最大值会在最后面,第二趟排序会在次后面
选择排序特征第一趟排序之后最小值会在最前面,第二趟排序会在次前面
插入排序特征第一趟排序范围 0~1,前一个数比后一个数小,第二趟排序范围0~2,前三个数小大排列
快速排序以一个值为分界点

25. 13.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素 0 之后,其结果是()
A.[3,2,5,7,4,6,8]
B.[2,3,5,7,4,6,8]
C.[2,3,4,5,7,8,6]
D.[2,3,4,5,6,7,8]
答案:C
解析:
根据堆的删除规则,删除操作只能在堆顶进行,也就是删除 0 元素。然后让最后一个节点放在堆顶,做向下调整工作,让剩下的数组依然满足最小堆。
删除 0 后用 8 填充 0 的位置,为[8,3,2,5,7,4,6]
然后 8 和其子节点 3,2 比较,结果 2 最小,将 2 和 8 交换,为:[2,3,8,5,7,4,6]
然后 8 的下标为 2,其两个孩子节点下标分别为 2*2+1=5,2*2+2=6
也就是 4 和 6 两个元素,经比较,4 最小,将 8 与 4 交换,为[2,3,4,5,7,8,6]
这时候 8 已经没有孩子节点了,调整完成。

26.下面说法错误的是()
(1)算法原地工作的含义是指不需要任何额外的辅助空间
(2)在相同的规模 n 下,复杂度 O(n)的算法在时间上总是优于复杂度 O(2n )的算法
(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
(4)同一个算法,实现语言的级别越高,执行效率就越低
A.1
B.1,2
C.1,4
D.3
答案:A
解析:
算法原地工作的含义是指不需要任何额外的辅助,算法所需要的辅助空间不随着问题的规模而变化,是一个确定的值。所以 A 不正确。

27.若有 18 个元素的有序表存放在一维数组 A[19]中,第一个元素放 A[1]中,现进行二分查找,则查找 A[3]的比较序列的下标依次为()
A.1,2,3
B.9,5,3
C.9,5,2,3
D.9,4,2,3
答案:D
解析:
注意第一个元素是放在 A【1】,一共 18 个元素,也就是 A【1】~A[18]。
第一次: low=1,high=18 ,mid=9(9.5 向下取整)。A【3】和 A【9】比较。然后把 A【9】右面的包括 A【9】全部抛弃掉。
第二次:A[1]~A [8]. mid=4(向下取整)。然后把 A【4】右面的包括 A【4】全部抛弃掉
第三次:A【1】~A【3】。mid=2。然后把 A【2】左面的包括 A【2】全部抛弃掉。
第四次;A【3】和A【3】比较。

28.某二叉树的中序遍历序列为 CBADE ,后序遍历序列为 CBADE ,则前序遍历序列为( )
A.E,D,A,B,C
B.C,B,E,D,A
C.C,B,A,D,E
D.E,D,C,B,A
答案:A
解析:
二叉树遍历可以分为 3 种:前序遍历(访问根结点在访问左子树和访问右子树之前)、中序遍历(访问根结点在访问左子树和访问右子树两者之间)、后序遍历(访问根结点在访问左子树和访问右子树之后)。二叉树的中序遍历序列为 CBADE ,后序遍历序列为 CBADE ,可知该树只有左子树结点,没有右子树结点, E 为根结点。中序遍历序列与后序遍历序列相同说明该树只有左子树没有右子树,因此该树有 5 层,从顶向下依次为 EDABC 。

29.线性表的顺序存储结构是一种()
A.随机存取的存储结构
B.顺序存取的存储结构
C.索引存取的存储结构
D.Hash 存取的存储结构
答案:A
解析:
线性表有两种存储结构:
1.顺序存储结构---顺序表。顺序表以数组形式出现,可以取任意下标访问,所以是一种随机存取的存储结构。
2.链式存储结构---链表。链表以链表的形式出现,必须从头开始访问,所以是一种顺序存取的存储结构。

30.n 个结点的完全有向图含有边的数目()
A.n*n
B.n(n+1)
C.n/2
D.n*(n-1)
答案:D
解析:
有向完全图:图中各边都有方向,且每两个顶点之间都有两条方向相反的边连接的图。
有向图:n*(n-1)
无向图:n*(n-1)/2
已邀请:

MLfintach

赞同来自:


赞小编!继续多多提供算法题!

要回复问题请先登录注册

返回顶部