人人 2021 研發崗面試題

?以下排序中時間復雜度最差的是

???

A? 歸并排序

B? 選擇排序

C? 希爾排序

D? 堆排序

?B

第2題：

?當參數*x==1, *y==1, *z==1時，下列不可能是函數add的返回值的( )?

int add(int *x, int *y, int *z){

????*x += *x;

??? *y += *x;

??? *z += *y;

??? return *z;

?}

??? ?

A? 4

B? 5

C? 6

D? 7

?D

開始不知道啥意思，后經?？途W的大神指點才知道這題要考慮的是，x，y，z三個參數是否指向同一地址（或者說調用該函數時是否實參相同），如：當a=b=c=1時，add(&a,&a,&a)，add(&a,&b,&c)。

通過寫程序測試得出結果，不可能得到答案7。

第3題：

?體育課的鈴聲響了，同學們都陸續地奔向操場，按老師的要求從高到矮站成一排。每個同學按順序來到操場時，都從排尾走向排頭，找到第一個比自己高的同學，并站到他的后面，這種站隊的方法類似下列哪種算法？

??

A? 快速排序

B? 插入排序

C? 冒泡排序

D? 歸并排序

?B

第4題：

?下面關于inode描述錯誤的是?

?

A? inode和文件是一一對應的

B? inode能描述文件占用的塊數

C? inode描述了文件大小和指向數據塊的指針

D? 通過inode實現文件的邏輯結構和物理結構的轉換

?A

第5題：

?設有一個棧，元素依次進棧的順序是A,B,C,D,E。下列不可能的出棧順序有?

?????????

A? ABCDE

B? BCDEA

C? EABCD

D? EDCBA

?C

進一個出一個的序列為A

AB進棧B出棧C進棧出棧D進棧出棧E進棧出棧A出棧的序列為B

全部進棧再出棧的序列為D，棧為先進后出的數據結構，無論如何都不會出現C的情況，故選C

第6題：

?某二叉樹結點的中序序列為A、B、C、D、E、F、G、H，后序序列為B、D、C、A、F、G、H、E。該二叉樹對應的樹林結點的層次次序序列為?

??

A? E、G、H、F、A、C、D、B

B? E、A、H、C、G、B、D、F

C? E、A、G、H、C、F、B、D

D? E、G、A、C、H、D、F、B

?B

由后序序列知E為根節點，再由中序遍歷知左子樹為ABCD，右子樹為FGH

由后序遍歷BDCA知，A為BDC父節點，BDC為右子樹，其中C為BD父節點，B為C的左孩子，D為C右孩子，該樹左半部分完成

由中序序列和后序序列知FGH序列不變，則H的左孩子為G，G的左孩子為F，H為E的右孩子，該樹可知其層次次序序列為EAHCGBDF,故選B

第7題：

?假設平均每個人人用戶有300個好友，則一個人人用戶的3跳好友數的數量級是?

???

A? 十萬級

B? 百萬級

C? 千萬級

D? 億級

?C

300的3次方，27000000，如果包含相互好友、共同好友的話還會比這個少。

第8題：

?下列哪些因素不會限制Linux服務器并發連接數?

?

A? 系統內存大小

B? 系統網卡數量

C? 系統最大文件句柄數量

D? 系統IP地址數量

?B

網卡數量。選擇B

第一個，就是ip地址數，系統ip數越多，建立連接數越多。

第二個，內存。從配置文件角度說吧

用vim打開配置文件：#vim ?/etc/sysctl.conf

net.ipv4.tcp_mem[0]:低于此值，TCP沒有內存壓力。

net.ipv4.tcp_mem[1]:在此值下，進入內存壓力階段。

net.ipv4.tcp_mem[2]:高于此值，TCP拒絕分配socket。

上述內存單位是頁，而不是字節。內存大小影響網絡 ?

第三個。其他，句柄最大數影響network 在vfs操作的上限。

最后。這么高大上的問題，我們先來看一個故事吧：

100萬并發連接服務器筆記之Erlang完成1M并發連接目標

100萬并發連接服務器筆記之1M并發連接目標達成

100萬并發連接服務器筆記之測試端就緒

100萬并發連接服務器筆記之處理端口數量受限問題

100萬并發連接服務器筆記之準備篇

第9題：

?二、填空題

在區間[-1, 1]隨意取兩個數，它們的和大于1的概率是_________。(分數表示)

?1/8

第10題：

?n從1開始，每個操作可以對n加1或加倍，如果要使n是2021，最少需要________ 個操作。

?18

int minimum_step(int n) {

??? vector dp(n + 1);

??? dp[1] = 0;

??? for (int i = 2; i <= 2021; i++) {

??? ? ? dp[i] = dp[i - 1] + 1;

??? ? ? if (i % 2 == 0) {

??? ? ? ? ? dp[i] = min(dp[i], dp[i / 2] + 1);

??? ? ? }

??? }

??? return dp[2021];

}

第11題：

?三、問答題

給出二叉樹接口為

class node

{

????node *get_left();

????node *get_right();

????int get_data();

}

? ?

找出值為val的最淺節點所在層數。

int find(node *root, int val).

?

int find(node * root, int val) {

??? int ret = 1;

?

??? if (root->get_data() == val) {

??? ? ? return ret;

??? } else {

??? ? ? int ?ret1 = 1 + find(root->get_left(), val);

??? ? ? int ?ret2 = 1 + find(root->get_right(), val);

??? ? ? if (ret1 > ret2)

??? ? ? ? ? ret = ret2;

??? ? ? else

??? ? ? ? ? ret = ret1;

?

??? ? ? return ret;

??? }

}

第12題：

?計算機中處理乘法的指令要比加法復雜的多， 因為在一些關鍵系統中我們常常會考慮如何盡可能減少乘法的運算。

現在有如下的表達式

y= anxn+an-1xn-1 +…..+a1x +a0

其中an, an-1, ….a1, a0是常數， 給一個x， 要求盡快算出y的值。請嘗試寫出這樣的一個函數。

?思路：?

F0=an;

F1=anx+an-1
Fn=xF(n-1)+an-1

代碼： ? ?

function sum(int a[], int n, int x){

????s=a[n]

????for(int i=1; i<=n; i++){

????????s += x*s + a[n-i]

????}

????return s;

}