美團2015校園招聘研發(fā)筆試題
一. 單項選擇題
美團有個傳統(tǒng)，就是公司各部門每月都要組織員工進行一次團建互動(team building，簡稱TB)，每個員工都可以帶家屬參加。活動內(nèi)容出了吃喝玩之外，還要做一些互動的游戲，需要從員工中隨機選出幾名組成一隊來完成游戲。一次TB活動，一共有20個人(含員工和家屬)參加。已知如果隨機選取3位員工以及該3位員工的家屬，一共有220組合。問如果每次隨機選取4個員工及該4位員工的家屬，會有多少組合?
A.405 B.455 C.495 D.505
二. 問答題
2. 一組隨機排列的字母數(shù)組。請編寫一個時間復(fù)雜度為O(n)的算法，使得這些字母按照字母從小到大順序排好。
說明：字母區(qū)分大小寫，相同的字母，排序后小寫排在大寫前
例如：R，B，B，b，W，W，B，R，B，w
排序為：b，B，B，B，B，R，R，w，W，W
1)描述思路(2分)
2)請用你熟悉的編程語言編碼實現(xiàn)(8分)
3. 給定整數(shù)x，定義函數(shù)A(n)=1+x+x2+x3+…+xn(n為整數(shù)且n>=0).已知乘運算的時間遠大于加運算，輸入x，n;如何盡可能快的求出A(n)?
要求：
1)描述思路(2分)
2)評估你的算法需要進行多少次乘法?(3分)3)請用你熟悉的編程語言編碼實現(xiàn)(5分)
4. 實現(xiàn)方法：print_rotate_matrix(int[] matrix, int n), 將一個n×n二維數(shù)組逆時針旋轉(zhuǎn)45度后打印，例如，下圖顯示一個3×3的二維數(shù)組及其旋轉(zhuǎn)后屏幕輸出的效果
5. 已知隊列(Queue)支持先進先出的操作add/remove，而棧(Stack)則支持先進后出的操作push/pop，請用兩個隊列實現(xiàn)棧先進后出的操作，希望該棧的push/pop時間復(fù)雜度盡量小。
1) 簡述思路(3分)
2) 已知這兩個隊列的容量為M,該棧的容量是多少(1分)
3) 假設(shè)隊列的每次Add/Remove操作時間復(fù)雜度O(1)，N代表存儲在棧里的'元素個數(shù)，請評估該棧的push/pop操作時間復(fù)雜度(1分)
4) 寫出push/pop的代碼，需要考慮棧溢出(stackoverflow)的情況(3分)
6. 任務(wù)務(wù)調(diào)度在分布式調(diào)度系統(tǒng)中是一個很復(fù)雜很有挑戰(zhàn)的問題。這里我們考慮一個簡化的場景：假設(shè)一個中央調(diào)度機，有n個相同的任務(wù)需要調(diào)度到m臺服務(wù)器上去執(zhí)行。由于每臺服務(wù)器的配置不一樣，因此服務(wù)器執(zhí)行一個任務(wù)所花費的時間也不同。現(xiàn)在假設(shè)第i個服務(wù)器執(zhí)行一個任務(wù)需要的時間為t[i]。
例如：有2個執(zhí)行機a, b. 執(zhí)行一個任務(wù)分別需要7min，10min，有6個任務(wù)待調(diào)度。如果平分這6個任務(wù)，即a，b各分三個任務(wù)，則最短需要30min執(zhí)行完所有。如果a分這4個任務(wù)，b分2個，則最短28min執(zhí)行完。
請設(shè)計調(diào)度算法，使得所有任務(wù)完成所需的時間最短
1) 簡述思路
2) 請用你熟悉的編程語言編碼實現(xiàn)以下方法，輸入為m臺服務(wù)器，每臺機器處理一個任務(wù)的時間為t[i]，完成n個任務(wù)，輸出n個任務(wù)在m臺服務(wù)器的分布：
int estimate_process_time(int[] t, int m, int n);
7. n個元素{1，2，……，n}有n!個不同的排列。將這n!個排列按字典序列排列。并編號為0，1，……，n!-1。每個排列的編號為其字典序的值。例如，當n=3是，其字典排序為：123，132，213，131，312，321，這6個數(shù)的字典序值分別為0,1,2,3,4,5�，F(xiàn)給定任意n，輸出字典序為k的排列(0<=k<=n!-1)7. n個元素{1，2，……，n}有n!個不同的排列。將這n!個排列按字典序列排列。并編號為0，1，……，n!-1。每個排列的編號為其字典序的值。例如，當n=3是，其字典排序為：123，132，213，131，312，321，這6個數(shù)的字典序值分別為0,1,2,3,4,5�，F(xiàn)給定任意n，輸出字典序為k的排列(0<=k<=n!-1)。
8. 給定N個磁盤，每個磁盤大小為D,i=0...N-1,現(xiàn)在要在這N個磁盤上"順序分配"M個分區(qū)，每個分區(qū)大小為P[j], j=0....M-1,順序分配的意思是：分配一個分區(qū)P[j]時，如果當前磁盤剩余空間足夠，則在當前磁盤分配;如果不夠，則 嘗試下一個磁盤，直到找到一個磁盤D[i+k]可以容納該分區(qū)，分配下一個分區(qū)P[j+1]時，則從當前磁盤D[i+k]的剩余 空間開始分配，不在使用D[i+k]之前磁盤末分配的空間，如果這M個分區(qū)不能在這N個磁盤完全分配，則認為分配失敗，請實現(xiàn)函數(shù)，is_allocable判斷給定N個磁盤(數(shù)組D)和M個分區(qū)(數(shù)組P)，是否會出現(xiàn)分配失敗的情況。 舉例：磁盤為[120,120,120],分區(qū)為[60,60,80,20,80]可分配 ，如果為[60,80,80,20,80]則分配失敗。
9. 實現(xiàn)一個監(jiān)聽load事件的接口window.load(callback):多次調(diào)用時保證執(zhí)行順序，先綁定的回調(diào)先執(zhí)行：如果load事件已觸發(fā)，調(diào)用時會直接執(zhí)行該回調(diào)
10. IOS系統(tǒng)提供了那些手勢?請選擇一個自己寫代碼實現(xiàn)
UITapGestureRecognizer敲擊手勢(單擊和雙擊)
UIPanGestureRecognizer(拖動手勢)
UIPinchGestureRecognizer(縮放手勢)
UISwipeGestureRecognizer(擦碰手勢)
UIRotationGestureRecognizer(旋轉(zhuǎn)手勢)
UILongPressGestureRecognizer(長按手勢
11. 下面是美團Andriod客戶端，團購列表中的一項團購，如果是你，你會怎么寫它的layout布局?(請用Andriod的基本控件，編寫layout xml實現(xiàn))
12. 某電商公司在做一個促銷活動，促銷商品共10000件，只限從手機客戶端購買，每個用戶&每個手機設(shè)備只限2件。商品原價M元(>10.0元)，促銷單價為N元(>10.0元，M>N)，活動時間為9月9日上午10:00開始，18:00結(jié)束，18:00前售完展示促銷商品售罄，非活動時間或促銷商品售罄后或超出購買限制，均可按原價購買;商品的支付方式可為網(wǎng)銀、代金券(面值5元，每單只限使用2張以內(nèi))，網(wǎng)銀、代金券支付方式可任意組合;促銷商品支持退貨，退貨時按購買金額退款，現(xiàn)金和/或代金券原路退回。請列出此活動的測試要點
13. 圖A是1MB容量的存儲器，圖B有兩個512KB容量的存儲器。如果使用兩個512KB容量的存儲器代替圖A1MB容量的存儲器，圖B中方框內(nèi)應(yīng)該是什么樣的電路?并說明原理。
【美團2015校園招聘研發(fā)筆試題】相關(guān)文章：
阿里校園招聘研發(fā)工程師筆試題07-26
去哪兒2015校園招聘產(chǎn)品經(jīng)理筆試題11-24
2015奇虎360校園招聘技術(shù)類筆試題目09-05
望�？敌叛邪l(fā)招聘筆試題目11-16
南方報業(yè)校園招聘筆試題07-26
2015阿里校招研發(fā)工程師筆試題08-13
美甲筆如何保養(yǎng)10-07