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