linux常问的面试题：linux后台开发精选面试题及答案

忙族 2023-01-29 05:56:58 776

linux常问的面试题：linux后台开发精选面试题及答案* Definition for singly-linked list./**定义另外一个长度为86400的整数数组intonline_num[86400]，每个整数对应这一秒的论坛在线人数。假设一天开始时论坛在线人数为0，则第1秒的人数online_num[0]=delta[0]。第n 1秒的人数online_num[n]=online_num[n-1] delta[n]。这样我们就获得了一天中任意时间的在线人数。

1、求一个论坛的在线人数，假设有一个论坛，其注册ID有两亿个，每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间，要求写一个算法统计一天中论坛的用户在线分布，取样粒度为秒。

一天总共有3600*24=86400秒。

定义一个长度为86400的整数数组intdelta[86400]，每个整数对应这一秒的人数变化值，可能为正也可能为负。开始时将数组元素都初始化为0。

然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加1，将与退出时间对应的整数值减1。

这样处理一遍后数组中存储了每秒中的人数变化情况。

定义另外一个长度为86400的整数数组intonline_num[86400]，每个整数对应这一秒的论坛在线人数。

假设一天开始时论坛在线人数为0，则第1秒的人数online_num[0]=delta[0]。第n 1秒的人数online_num[n]=online_num[n-1] delta[n]。

这样我们就获得了一天中任意时间的在线人数。

2、有序链表合并.

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x) next(NULL) {}

* };

class Solution {

public:

ListNode* mergeTwoLists(ListNode* l1 ListNode* l2) {

if (l1 == NULL) {

return l2;

} else if (l2 == NULL) {

return l1;

} else {

if (l1->val <= l2->val) {

l1->next = mergeTwoLists(l1->next l2);

return l1;

} else {

l2->next = mergeTwoLists(l1 l2->next);

return l2;

}

};

3、TCP三次握手的过程 accept发生在三次握手哪个阶段？

accept发生在三次握手之后。

第一次握手:客户端发送syn包(syn=j)到服务器。

第二次握手:服务器收到syn包必须确认客户的sY(ack=j 1) 同时自己也发送一个ASK包(ask=k)。

第三次握手:客户端收到服务器的SYN ACK包向服务器发送确认包ACK(ack=k 1)。

握手完成后客户端和服务器就建立了tcp连接。这时可以调用 accept函数获得此连接。

4、用UDP协议道讯时怎样得知目标机是否获得了数据包 ?

可以在每个数据包中插入一个唯一的ID 比如 timestamp或者递增的int。

发送方在发送数据时将此ID和发送时间记录在本地。

接收方在收到数据后将ID再发给发送方作为回应。

发送方如果收到回应则知道接收方已经收到相应的数据包;如果在指定时间内没有收到回应则数据包可能丢失需要重复上面的过程重新发送一次直到确定对方收到。

5、从10G个数中找到中数在一个文件中有10G个整数乱序排列要求找出中位数。内存限制为2G.

不妨假设10G个整数是64bit的。

2G内存可以存放256M个64bit整数。

我们可以将64bit的整数空间平均分成256M个取值范围用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后我们便知道中数在那个范围内出现以及这个范围内总共出现了多少个整数。

如果中数所在范围出现的整数比较少我们就可以对这个范围内的整数进行排序找到中数。如果这个范围还可以采用同样的方法将此范围再次分成多个更小的范围(256M-228 所以最多需要3次就可以将此范围缩小到1 也就找到了中数)

6、给40亿个不重复的 unsigned int的整数没排过序的然后再给几个数如何快速判断这几个数是否在那10亿个数当中?

unsigned int的取值范围是0到2^32-1。我们可以申请连续的232/8-512M的内存用每一个bit对应个 unsigned int数字。首先将51M内存都初始化为0 然后每处理一个数字就将其对应的bit设置为1。当需要查询时直接找到对应bit 看其值是0还是1即可。

7、如何输出源文件的标题和目前执行行的行数?

printf("The file name:%dn" __FILE__);

printf("The current line No: %d\n" __LINE__);

ANSI C标准预定义宏;

__LINE__

__FILE__

__DATE__

__TIME__

__STDC__ 当要求程序严格遵循ANSC标准时该标识符被赋值为1

__cplusplus__ 当编写C 程序时该标识符被定义

8、文腾讯服务器每秒有2W个QQ号同时上线找出5min内重新登入的qq号并打印出来。

如果空间足够大可以定义一个大的数组a[qq号] 初始为零然后.这个qq号登陆了

就a[qq号]

最后统计大于等于2的QQ号

这个用空间来代替时间

不成熟的想法

2w x 300s

所以用6000.000个桶。刪除超时的算法后面说所以平均桶的大小是1

假设qq号码一共有10^10个所以每个桶装的q号码是10^10/(6*10~6)个

这个是插入时候的最坏效率(插入同个桶的时候是顺序查找插入位置的)

qq的节点结构和上面大家讨论的基本一样增加一个指针指

向输出列表后面说

struct QQstruct {

num_type qqnum

timestamp last_logon_time

QQstruct *pre

QQstruct *next

OutPutlist *out //用于free节点的时候顺便更新下输出列表

}

另外增加两个指针列表

第一个大小300的循环链表自带一个指向 QQStruct的域循环存300秒内的qq指针。

时间一过就fee掉所以保证所有桶占用的空闾在2wX30以内.

第二个是输出列表就是存放题目需要输出的节点。

如果登陆的用户 5分钟内完全没有重复的话每秒free2w个节点

不过在free的时候要判断一下时间是不是真的超时因为把节点入桶的时候遇到重复的

会更新一下最后登陆的时间。当然啦这个时候要把这个q号码放到需要输出的列表里面

9、给一个奇数阶N幻方填入数字1 2 3.N^N 使得橫竖斜方向上的和都相同.

#inc1ude<iostream>

#include<iomanip>

#include<cmath>

usingnamespace std;

int main()

{

int n;

cin>>n;

int i;

int **Matr = new int *[n]; //动态分配二维数组

for(i=0;i<n; i)

Matr[i]=new int[n]: //动态分配二维

数组

//j=n/2代表首行中间数作为起点即1所在位置

int j=n/2 num=1: //初始值

i=0;

while(num!=n*n 1) {

//往右上角延升若超出则用%转移到左下角

Matr [(i%n n)%n][(j%n n)%n]=num;

//斜行的长度和n是相等的超出则转至下一写信.

if (num%n==0) {

i ;

} else {

i--;

j ;

}

num ;

}

for (i=0;i<n;i ) {

for (j=0;j<n; j) {

cout << setw((int)log10(n*n) 4)<<Matr[i][j]; //格式控制

cout <<endl<<endl;//格式控制

}

for (i=0; i<n; i) {

delete [] Matr[i];

}

return 1;

}

10、Redis的主从复制怎么做的?

Redis旧版复制功能只有同步和命令传播。新版复制功能加入了部分同步的功能。

1）同步：

2）命令传播：

当主服务器会将自己执行的写命令，也即是造成主从服务器不一致的那条写命令，发送给从服务器执行，当从服务器执行了相同的写命令之后，主从服务器将再次回到一致状态。

3）部分同步：（断线后重复制）

复制偏移量：通过对比主从服务器的复制偏移量，程序可以很容易地知道主从服务器是否处于一致状态。

复制积压缓冲区：主服务保存最近的写命令到复制积压缓冲区，是一个先进先出队列

服务器运行ID：从服务器记录上次同步的主服务器的Id。

11、程序什么时候应该使用线程，什么时候单线程效率高。

1 耗时的操作使用线程，提高应用程序响应

2 并行操作时使用线程，如C/S架构的服务器端并发线程响应用户的请求。

3 多CPU系统中，使用线程提高CPU利用率

4 改善程序结构。一个既长又复杂的进程可以考虑分为多个线程，成为几个独立或半独立的运行部分，这样的程序会利于理解和修改。

其他情况都使用单线程。

12、设计DNS服务器中cache的数据结构。

要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）

DNS服务器实现域名到IP地址的转换。

每个域名的平均长度为25个字节（估计值），每个IP为4个字节，所以Cache的每个条目需要大概30个字节。

总共50M个条目，所以需要1.5G个字节的空间。可以放置在内存中。（考虑到每秒5000次操作的限制，也只能放在内存中。）

可以考虑的数据结构包括hash_map，字典树，红黑树等等。

13、请描述C 的内存管理方式

在c 中内存主要分为5个存储区：

栈（Stack）：局部变量，函数参数等存储在该区，由编译器自动分配和释放.栈属于计算机系统的数据结构，进栈出栈有相应的计算机指令支持，而且分配专门的寄存器存储栈的地址，效率分高，内存空间是连续的，但栈的内存空间有限。

堆(Heap)：需要程序员手动分配和释放（new delete），属于动态分配方式。内存空间几乎没有限制，内存空间不连续，因此会产生内存碎片。操作系统有一个记录空间内存的链表，当收到内存申请时遍历链表，找到第一个空间大于申请空间的堆节点，将该节点分配给程序，并将该节点从链表中删除。一般，系统会在该内存空间的首地址处记录本次分配的内存大小，用于delete释放该内存空间。

全局/静态存储区:全局变量，静态变量分配到该区，到程序结束时自动释放，包括DATA段（全局初始化区）与BSS段（全局未初始化段）。其中，初始化的全局变量和静态变量存放在DATA段，未初始化的全局变量和静态变量存放在BSS段。BSS段特点：在程序执行前BSS段自动清零，所以未初始化的全局变量和静态变量在程序执行前已经成为0.

文字常量区：存放常量，而且不允许修改。程序结束后由系统释放。

程序代码区：存放程序的二进制代码

14、hash表如何rehash，怎么处理其中保存的资源.

先想想为什么需要rehash:

因为，当loadFactor（负载因子）<=1时，hash表查找的期望复杂度为O(1). 因此，每次往hash表中添加元素时，我们必须保证是在loadFactor <1的情况下，才能够添加。

模仿C 的vector扩容方式，Hash表中每次发现loadFactor==1时，就开辟一个原来桶数组的两倍空间（称为新桶数组），然后把原来的桶数组中元素全部转移过来到新的桶数组中。注意这里转移是需要元素一个个重新哈希到新桶中的。

15、strtok函数在使用上要注意什么问题。

这个问题我不知道能不能回答全面，因为实在是用的很少。这个函数的作用是分割字符串，但是要分割的字符串不能是常量，这是要注意的。比如先定义一个字符串：char array[]=”part1 part2″;，strtok的原形是char *strtok(char *string char *delim);，我们将” ”作为分隔符，先用pt=strtok(array ” ”);，得到的结果print出来就是”part1″，那后面的呢，要写成pt=strtok(NULL ” ”);，注意，要用NULL，如果被分割的字符串会被分成N段，那从第二次开始就一直要用NULL。总结起来，需要注意的是：被分割的字符串和分隔符都要使用变量;除第一次使用指向字符串的指针外，之后的都要使用NULL;注意使用这个函数的时候千万别把指针跟丢了，不然就全乱了。