2021年騰訊面試題(后臺開發崗位)

小編:管理員 451閱讀 2021.06.09

第1題:


一、不定項選擇

將一組無序的數據重新排列成有序序列,其方法有()

 

A  拓撲排序

B  快速排序

C  堆排序

D  基數排序



答案:BCD

解析:在圖論中,由一個有向無環圖的頂點組成的序列,當且僅當滿足下列條件時,稱為該圖的一個拓撲排序(英語:Topological sorting)。

每個頂點出現且只出現一次;
若A在序列中排在B的前面,則在圖中不存在從B到A的路徑。
也可以定義為:拓撲排序是對有向無環圖的頂點的一種排序,它使得如果存在一條從頂點A到頂點B的路徑,那么在排序中B出現在A的后面


第2題:


 某服務請求經負載均衡設備分配到集群A、B、C、D進行處理響應的概率分別是10%、20%、30%和40%。已知測試集群所得的穩定性指標分別是90%、95%、99%和99.9%,F在該服務器請求處理失敗,且已排除穩定性以外的問題,那么最有可能在處理該服務請求的集群是________。

A、A

B、B

C、C

D、D



答案:A B

解析:選中該集群,并且處理失敗了的概率為:10%*10%、20%*5%、30%*1%、40%*0.1%。A與B的概率最高。


第3題:


下列說法正確的有( )

 

A  環境變量可在編譯source code時指定

B  在編譯程序時,所能指定的環境變量不包括class path

C  javac一次可同時編譯數個Java源文件

D  javac.exe能指定編譯結果要置于哪個目錄(directory)


答案:A C D


第4題:


下列說法錯誤的有( )

         

A  數組是一種對象

B  數組屬于一種原生類

C  int number=[]={31,23,33,43,35,63}

D  數組的大小可以任意改變



答案: B C D

解答:Java把數組當作一個java類來處理

java是純面向對象的語言,他的數組也是一個對象。


第5題:


下列說法錯誤的有( )

         

A  能被java.exe成功運行的java class文件必須有main()方法

B  J2SDK就是Java API

C  Appletviewer.exe可利用jar選項運行.jar文件

D  能被Appletviewer成功運行的java class文件必須有main()方法



答案:B C D

解析如下:

B選項中J2SDK是編程工具,不是API.

C選項中      Appletviewer.exe   就是用來解釋執行java       applet應用程序的,簡單理解就是沒有main函數的繼承applet類的java類。

D選項中      能被Appletviewer成功運行的java class文件沒有main()方法


第6題:


 卡方分布的方差為2倍的自由度為?

     

A  n

B  1

C  2n

D  4n



答案:C

注解: 分布的均值為自由度 n,記為 E() = n。

分布的方差為2倍的自由度(2n),記為 D() = 2n。


第7題:


如何減少換頁錯誤?

  

A  進程傾向于占用CPU

B  訪問局部性(locality of reference)滿足進程要求

C  進程傾向于占用I/O

D  使用基于最短剩余時間(shortest remaining time)的調度機制



答案: B

解析如下:

換頁錯誤又稱缺頁錯誤,當一個程序試圖訪問沒有映射到物理內存的地方時,就會出現缺頁錯誤,   這時操作系統就要去虛擬內存中加載這塊內存頁。

百度了一下,減少換頁錯誤的方法,即降低缺頁中斷率:      
1、內存頁框數。增加作業分得的內存塊數。      
2、頁面大小。頁面劃分越大,中斷率越低。      
3、替換算法的優劣影響缺頁中斷次數      
4、程序局部性。程序局部性好可減少缺頁中斷(為什么?)。      
 

那么B是對的,而對于D,最短剩余時間調度是CPU調度就緒進程的方式,與頁面置換算法無關,不要搞混淆了。  


第8題:


 Please choose the right statement about constusage:
 

A  const int a; //const integer

B  int const a; //const integer

C  int const *a; //a pointer which point to const integer

D  const int *a; //a const pointer which point to integer

E  int const *a; // a const pointer which point to integer



答案:ABC

解析如下:

對于A和B,int const 和 const int 可以顛倒位置,意義不變

CDE都表示指向const int 的指針,而int *const a 才表示指向int的const指針


第9題:


下列定義語句中,錯誤的是

 

A  int px*;

B  char*acp[10];

C  char(*pac)[10];

D  int(*p)();


答案: A


第10題:

對類成員訪問權限的控制,是通過設置成員的訪問控制屬性實現的,下列不是訪問控制屬性的是(    )

 

A  公有類型

B  私有類型

C  保護類型

D  友元類型


答案:D

解析如下:

C++中有三種權限控制類型,分別是共有類型public,私有類型private,保護類型protected.

友元是聲明一個類外的方法具有類方法同樣的訪問權限,目的是讓類外的方法可以訪問類內部的屬性,不是訪問控制屬性。


第11題:


給出以下定義,下列哪些操作是合法的?
 

const char *p1 = “hello”;

char *const p2 = “world”;

    

A  p1++;

B  p1[2] = ‘w’;

C  p2[2] = ‘l’;

D  p2++;



答案:A

解析如下:

p1是指向字符常量的指針,p1本身不是常量,所以p1++合法,A正確。

p2本身是指針常量,可以指向非常量的字符。但是"hello"這樣聲明的字符串是存儲在只讀存儲區的,不可修改,所以B,C,D都錯誤。


第12題:

以下集合對象中哪幾個是線程安全的?(       )

 

A  ArrayList

B  Vector

C  Hashtable

D  Stack


答案: BCD  

解析如下:

在集合框架中,有些類是線程安全的,這些都是jdk1.1中的出現的。在jdk1.2之后,就出現許許多多非線程安全的類。  下面是這些線程安全的同步的類:

vector:就比arraylist多了個同步化機制(線程安全),因為效率較低,現在已經不太建議使用。在web應用中,特別是前臺頁面,往往效率(頁面響應速度)是優先考慮的。

statck:堆棧類,先進后出

hashtable:就比hashmap多了個線程安全

enumeration:枚舉,相當于迭代器

除了這些之外,其他的都是非線程安全的類和接口。


第13題:

若下列所用變量均已經正確定義,一下表達式中不合法的是

 

A  x>>3

B  +++j

C  a=x>y?x:y

D  x%=4


答案:B

解析如下:

A ,x右移三位

B,++j是j自增1,+++j是不合法的,編譯出錯

C,這是一個三目運算符,(exp1)?(exp2):(exp3)

   當exp1為true時個表達式結果為exp2

   當exp1為false時整個表達式結果為exp3

D,取余運算,等價于x=x%4


第14題:

test.c文件中包括如下語句:

#define INT_PTR int*

typedef int* int_ptr;

INT_PTR a,b;

int_ptr c,d;    

文件中定義的四個變量中,哪個變量類型不是指針類型?

A  a

B  b

C  c

D  d

E  都是指針

F  都不是指針



答案:B

解析如下:
#define INT_PTR int* 這是宏定義,編譯預處理階段要進行宏替換,INT_PTR a,b會變成 int* a,b 所以b不是指針類型
typedef int* int_ptr; 這是自定義類型,也就是把int_ptr定義為 int型指針,編譯階段會把c,d都識別為指針


第15題:

不屬于馮諾依曼體系結構必要組成部分是:

 A  CPU

B  Cache

C  RAM

D  ROM


答案:B


第16題:


 二、問答題

有1000億條記錄,每條記錄由url,ip,時間組成,設計一個系統能夠快速查詢以下內容
1.給定url和時間段(精確到分鐘)統計url的訪問次數
2.給定ip和時間段(精確到分鐘)統計ip的訪問次數



 答:首先,1000億條記錄全部放到內存肯定不夠,那就是分成小文件了,然后整合;
公共的時間段,因為精確到分鐘,我們把這每一分鐘建成一個小文件,每個小文件肯定會有許多重復的ip,url;
現在統計每個小的文件中url的訪問量和ip的訪問次數,方法就是建立索引;
(建立索引的目的是為了減少查詢次數,但是隨著索引級數增多也會造成花更多的時間在建立索引上);
建立url的索引,假如是www.nowcoder.com/question,可以分別給www.nowcoder.com和question建立索引,那么來了一條url,先看一級索引是不是匹配,匹配再看二級索引,相同的話就是我們要的url目標;
ip的索引也是一樣,ip分成4段建立索引;
所以這里影響效率的就是在索引建立這塊,索引建立好那就是查詢的事了的,就會變得非?。
假定給定了某個時間段,找出url的訪問量,那么先找到給定的時間段,對應著剛開始分割的小的文件(每一個分鐘)中搜索,通過索引找到相同的url之后,開始統計,直到搜索完所有的給定時間段內的所有的小的文件;
求ip的訪問次數也是一樣,按照給定的時間段,找到對應的小的文件,通過索引找到相同的ip后統計,直到搜索完了給定時間段內的所有的小的文件。


第17題:


 實現一個簡化的搜索提示系統。給定一個包含了用戶query的日志文件,對于輸入的任意一個字符串s,輸出以s為前綴的在日志中出現頻率最高的前10條query。

由于是分布式系統,假設至少有26臺機器,每個機器存儲以26個字母開頭的query日志文件(如機器1存的是a字母開頭的,機器2存的是以b字母開頭的……)

每個機器上維護著一張哈希表,對于每條query, 在哈希表表中存放其地址(哈希地址為鏈式的),并對其進行排序,按頻率由高到低進行排序。

當用戶進行搜索時,可以很快定位到某臺機器,并根據哈希表,返回出現頻率最高的前10條query。

提示:

1、可以預處理日志

2、假設query不超過10億條,每個query不超過50字節。

3、考慮在大查詢量的情況下如何實現分布式服務



  系統前臺:

用JS監控input輸入框的內容變化,用戶輸入或者刪除字符(輸入串的發生變化)就觸發異步Javascript提交輸入內容到后臺,引發后臺查詢。然后再講查詢結果出現頻率最高的前10條query展現給用戶提示。


系統后臺:

首先有26臺服務器分別存儲26個字母開頭的query。所以首先要設計一個接收用戶請求的服務器,這臺服務器可以根據用戶請求的首字母將查詢請求分發給對應26臺服務器中的一個(相當于查詢請求的路由功能)。

然后就是這26臺查詢服務器如何設計的問題了。

假設query不超過10億條,每個query不超過50字節。也就是query文件不超過50G,分在26臺機器上也就是每臺機器上的query文件不超過2G。

每個機器上維護著一張哈希表,對于每條query,   在哈希表表中存放其地址。收到每個query做hash運算可以找到query對應的地址。對應每個query存儲兩項信息,即query本身和被查詢次數,也就是類似query:times這樣的存儲格式。

下面做預處理:26臺機器都對自身存儲的query進行遍歷,分別找出a到z開頭query出現頻率最高的top10,這樣的查詢一次遍歷就能找到,時間復雜度為O(N)。然后對找到的top10在內存中構建一個最小堆。其他非top10的query無需做排序處理。到這里預處理完成。

然后說查詢過程,查詢分為兩類,

1,以給出搜索提示的異步Javascript提交的查詢,這種查詢直接返回最小堆中的10個query詞條即可。

2,用戶最終提交的查詢(即用戶輸入完畢點擊搜索按鈕提交的查詢),這種查詢的query是用戶最終查詢的詞條,這樣的查詢應該引起后臺存儲的對應query頻率的變化。當一個query到達的時候,先用hash運算找到他的位置和對應的頻率,hash操作時間復雜度是O(1),然后對應的次數+1,然后用這個+1的次數與最小堆中首個元素比較,如果大于最小堆首個元素,與最小堆中首個元素交換,然后最小堆做更新操作,保證最小堆的特性。否則不操作。這樣最小堆中維護的10個query始終是這臺機器上頻率最高的,查詢時返回這10個query詞條即可。


第18題:


 小米公司內部每個員工都會有一個專屬的工作郵箱,郵箱的前綴是員工姓名的拼音全拼,例如張強的郵箱是zhangqiang@xiaomi.com,但同時公司里有很多同名的人,為了避免大家相互之間發錯郵件,工程師們想了個規則來解決這個問題,即在這些同命人中,入職最早的郵箱前綴為姓名的拼音全拼,第二個入職的郵箱前綴為姓名的拼音全拼后面加“_a”,第三個入職的為姓名的拼音全拼后面加“_b”,以次類推,請按這個規則,如果公司里同時有3位名叫張強的員工,則他們的郵箱分別是zhangqiang@xiaomi.com,zhangqiang_a@xiaomi.com,zhangqiang_b@xiaomi.com...郵箱前綴是員工在公司里的重要標識之一,問題來了:現在小米要舉行一次全員野外拉練活動,要求所有員工必須排成一隊出去,并且,有的員工要求他必須排在某人的前面或后面,作為組織者的你,收到這樣的需求之后,如何給出一個讓每個人都滿意的排隊方式呢?
Java:


class RequestItem

{

    public String member;

    public boolean standFront; //true表示要排在這個人的前面,false表示要排在這個人的后面

}

class Request

{

    public String owner;    //那個人提出的要求

    List<RequestItem> requestItems;    //他要排在哪些人的前面,哪些人的后面

}

List<String> getValidOrder(List<String>allMembers, List<Request> requests);

   

allMembers就是所有員工的郵箱前綴,requests是一些人的排隊要求。小米公司現有幾千名員工,每個人最多有10個排隊要求(要排在一個人的前面或者后面算一個排隊要求),也有人沒有什么要求,F在你的任務是完成上面的getValidOrder函數,如果有合法的排隊序列,那么返回其中任何一個。否則返回null。




 假設有n個員工。

選用數據結構,map[n][n]。

1、其中map[i][j]=1代表i在j的前面,=0代表前后位置,=-1帶表在后面。若出現已經=-1的情況下,在后面又要求=1,會形成環,則返回null。。

2、這樣就形成了一個圖,然后進行拓撲排序即可。先找出所有入度為0的點,放在前面,然后去掉這些點和相應的邊.如此得到最終結果。


關聯標簽: