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