2021年美團編程實習生面試題

小編:管理員 358閱讀 2021.06.25

第1題:


 1、美團有個傳統,就是公司各部門每月都要組織員工進行一次團建互動(team building,簡稱TB),每個員工都可以帶家屬參加;顒觾热莩隽顺院韧嬷,還要做一些互動的游戲,需要從員工中隨機選出幾名組成一隊來完成游戲。一次TB活動,一共有20個人(含員工和家屬)參加。已知如果隨機選取3位員工以及該3位員工的家屬,一共有220組合。問如果每次隨機選取4個員工及該4位員工的家屬,會有多少組合?


第2題:


 2、有一組隨機排列的字母數組。請編寫一個時間復雜度為O(n)的算法,使得這些字母按照字母從小到大順序排好。

說明:字母區分大小寫,相同的字母,排序后小寫排在大寫前。

例如:R,B,B,b,W,W,B,R,B,w

排序為:b,B,B,B,B,R,R,w,W,W

1)描述思路(2分)

2)請用你熟悉的編程語言編碼實現(8分)


第3題:


 3、給定N個磁盤,每個磁盤大小為D[i],i=0,…N-1,F要在這N個磁盤上“順序分配”M個分區。每個分區大小為P[j],j=0,…M-1。順序分配的意思是:分配一個分區P[j]時,如果當前磁盤剩余空間足夠,則在當前磁盤分配;如果不夠,則嘗試下一磁盤,直到找到一個磁盤D[i+k]可以容納該分區。分配下一個分區P[j+1]時,則從當前磁盤D[i+k]的剩余空間開始分配,不再使用D[i+k]之前磁盤的未分配空間。如果這M個分區不能在這N個磁盤完全分配。則認為分配失敗。請實現函數is_allocable 判斷給定N個磁盤(數組D)和M個分區(數組P),是否會出現分區分配失敗的情況。

舉例:磁盤為[120,120,120],分區為[60,60,80,20,80]可分配,如果為[60,80,80,20,80],則分配失敗。


第4題:


 4、給定整數x,定義函數A(n)=1+x+x2+x3+…+xn(n為整數且n>=0).已知乘運算的時間遠大于加運算,輸入x,n;如何盡可能快的求出A(n)?

要求:

1)描述思路(2分)

2)評估你的算法需要進行多少次乘法?(3分)

3)請用你熟悉的編程語言編碼實現(5分)


第5題:


 5、請實現方法:print_rotate_matrix(int[] matrix, int n), 將一個n×n二維數組逆時針旋轉45度后打印,例如,下圖顯示一個3×3的二維數組及其旋轉后屏幕輸出的效果。

  1      2      3                            3                                  3

  4      5      6                        2      6                              2   6

  7      8      9                    1      5      9                          1   5   9

                                            4      8                              4   8

                                                7                                  7

描述思路(2分)

請用你熟悉的語言編碼顯示(8分)


第6題:


 6、已知隊列(Queue)支持先進先出的操作add/remove,而棧(Stack)則支持先進后出的操作push/pop,請用兩個隊列實現棧先進后出的操作,希望該棧的push/pop時間復雜度盡量小。

1) 簡述思路(3分)

2) 已知這兩個隊列的容量為M,該棧的容量是多少(1分)

3) 假設隊列的每次Add/Remove操作時間復雜度O(1),N代表存儲在棧里的元素個數,請評估該棧的push/pop操作時間復雜度(1分)

4) 寫出push/pop的代碼,需要考慮棧溢出(stackoverflow)的情況(3分)


第7題:


 7、任務調度在分布式調度系統中是一個很復雜很有挑戰的問題。這里我們考慮一個簡化的場景:假設一個中央調度機,有n個相同的任務需要調度到m臺服務器上去執行。由于每臺服務器的配置不一樣,因此服務器執行一個任務所花費的時間也不同,F在假設第i個服務器執行一個任務需要的時間為t[i]。

例如:有2個執行機a, b. 執行一個任務分別需要7min,10min,有6個任務待調度。如果平分這6個任務,即a,b各分三個任務,則最短需要30min執行完所有。如果a分這4個任務,b分2個,則最短28min執行完。

請設計調度算法,使得所有任務完成所需的時間最短

1) 簡述思路(2分)

2) 請用你熟悉的編程語言編碼實現以下方法,輸入為m臺服務器,每臺機器處理一個任務的時間為t[i],完成n個任務,輸出n個任務在m臺服務器的分布(8分):

int estimate_process_time(int[] t, int m, int n);


第8題:


 8、n個元素{1,2,……,n}有n!個不同的排列。江浙n!個排列按字典序列排列。并編號為0,1,……,n!-1。每個排列的編號為其字典序的值。例如,當n=3是,其字典排序為:123,132,213,131,312,321,這6個數的字典序值分別為0,1,2,3,4,5,F給定任意n,輸出字典序為k的排列(0<=k<=n!-1)。


關聯標簽: