美團(tuán)2015校園招聘研發(fā)筆試題

　　一. 單項(xiàng)選擇題

　　美團(tuán)有個(gè)傳統(tǒng)，就是公司各部門(mén)每月都要組織員工進(jìn)行一次團(tuán)建互動(dòng)(team building，簡(jiǎn)稱(chēng)TB)，每個(gè)員工都可以帶家屬參加�；顒�(dòng)內(nèi)容出了吃喝玩之外，還要做一些互動(dòng)的游戲，需要從員工中隨機(jī)選出幾名組成一隊(duì)來(lái)完成游戲。一次TB活動(dòng)，一共有20個(gè)人(含員工和家屬)參加。已知如果隨機(jī)選取3位員工以及該3位員工的家屬，一共有220組合。問(wèn)如果每次隨機(jī)選取4個(gè)員工及該4位員工的家屬，會(huì)有多少組合?

　　A.405 B.455 C.495 D.505

　　二. 問(wèn)答題

　　2. 一組隨機(jī)排列的字母數(shù)組。請(qǐng)編寫(xiě)一個(gè)時(shí)間復(fù)雜度為O(n)的算法，使得這些字母按照字母從小到大順序排好。

　　說(shuō)明：字母區(qū)分大小寫(xiě)，相同的字母，排序后小寫(xiě)排在大寫(xiě)前

　　例如：R，B，B，b，W，W，B，R，B，w

　　排序?yàn)椋篵，B，B，B，B，R，R，w，W，W

　　1)描述思路(2分)

　　2)請(qǐng)用你熟悉的編程語(yǔ)言編碼實(shí)現(xiàn)(8分)

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

　　要求：

　　1)描述思路(2分)

　　2)評(píng)估你的算法需要進(jìn)行多少次乘法?(3分)3)請(qǐng)用你熟悉的編程語(yǔ)言編碼實(shí)現(xiàn)(5分)

　　4. 實(shí)現(xiàn)方法：print_rotate_matrix(int[] matrix, int n), 將一個(gè)n×n二維數(shù)組逆時(shí)針旋轉(zhuǎn)45度后打印，例如，下圖顯示一個(gè)3×3的二維數(shù)組及其旋轉(zhuǎn)后屏幕輸出的效果

　　5. 已知隊(duì)列(Queue)支持先進(jìn)先出的操作add/remove，而棧(Stack)則支持先進(jìn)后出的操作push/pop，請(qǐng)用兩個(gè)隊(duì)列實(shí)現(xiàn)棧先進(jìn)后出的操作，希望該棧的push/pop時(shí)間復(fù)雜度盡量小。

　　1) 簡(jiǎn)述思路(3分)

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

　　3) 假設(shè)隊(duì)列的每次Add/Remove操作時(shí)間復(fù)雜度O(1)，N代表存儲(chǔ)在棧里的'元素個(gè)數(shù)，請(qǐng)?jiān)u估該棧的push/pop操作時(shí)間復(fù)雜度(1分)

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

　　6. 任務(wù)務(wù)調(diào)度在分布式調(diào)度系統(tǒng)中是一個(gè)很復(fù)雜很有挑戰(zhàn)的問(wèn)題。這里我們考慮一個(gè)簡(jiǎn)化的場(chǎng)景：假設(shè)一個(gè)中央調(diào)度機(jī)，有n個(gè)相同的任務(wù)需要調(diào)度到m臺(tái)服務(wù)器上去執(zhí)行。由于每臺(tái)服務(wù)器的配置不一樣，因此服務(wù)器執(zhí)行一個(gè)任務(wù)所花費(fèi)的時(shí)間也不同�，F(xiàn)在假設(shè)第i個(gè)服務(wù)器執(zhí)行一個(gè)任務(wù)需要的時(shí)間為t[i]。

　　例如：有2個(gè)執(zhí)行機(jī)a, b. 執(zhí)行一個(gè)任務(wù)分別需要7min，10min，有6個(gè)任務(wù)待調(diào)度。如果平分這6個(gè)任務(wù)，即a，b各分三個(gè)任務(wù)，則最短需要30min執(zhí)行完所有。如果a分這4個(gè)任務(wù)，b分2個(gè)，則最短28min執(zhí)行完。

　　請(qǐng)?jiān)O(shè)計(jì)調(diào)度算法，使得所有任務(wù)完成所需的時(shí)間最短

　　1) 簡(jiǎn)述思路

　　2) 請(qǐng)用你熟悉的編程語(yǔ)言編碼實(shí)現(xiàn)以下方法，輸入為m臺(tái)服務(wù)器，每臺(tái)機(jī)器處理一個(gè)任務(wù)的時(shí)間為t[i]，完成n個(gè)任務(wù)，輸出n個(gè)任務(wù)在m臺(tái)服務(wù)器的分布：

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

　　7. n個(gè)元素{1，2，……，n}有n!個(gè)不同的排列。將這n!個(gè)排列按字典序列排列。并編號(hào)為0，1，……，n!-1。每個(gè)排列的編號(hào)為其字典序的值。例如，當(dāng)n=3是，其字典排序?yàn)椋?23，132，213，131，312，321，這6個(gè)數(shù)的字典序值分別為0,1,2,3,4,5�，F(xiàn)給定任意n，輸出字典序?yàn)閗的排列(0<=k<=n!-1)7. n個(gè)元素{1，2，……，n}有n!個(gè)不同的排列。將這n!個(gè)排列按字典序列排列。并編號(hào)為0，1，……，n!-1。每個(gè)排列的編號(hào)為其字典序的值。例如，當(dāng)n=3是，其字典排序?yàn)椋?23，132，213，131，312，321，這6個(gè)數(shù)的字典序值分別為0,1,2,3,4,5�，F(xiàn)給定任意n，輸出字典序?yàn)閗的排列(0<=k<=n!-1)。

　　8. 給定N個(gè)磁盤(pán)，每個(gè)磁盤(pán)大小為D,i=0...N-1,現(xiàn)在要在這N個(gè)磁盤(pán)上"順序分配"M個(gè)分區(qū)，每個(gè)分區(qū)大小為P[j], j=0....M-1,順序分配的意思是：分配一個(gè)分區(qū)P[j]時(shí)，如果當(dāng)前磁盤(pán)剩余空間足夠，則在當(dāng)前磁盤(pán)分配;如果不夠，則 嘗試下一個(gè)磁盤(pán)，直到找到一個(gè)磁盤(pán)D[i+k]可以容納該分區(qū)，分配下一個(gè)分區(qū)P[j+1]時(shí)，則從當(dāng)前磁盤(pán)D[i+k]的剩余 空間開(kāi)始分配，不在使用D[i+k]之前磁盤(pán)末分配的空間，如果這M個(gè)分區(qū)不能在這N個(gè)磁盤(pán)完全分配，則認(rèn)為分配失敗，請(qǐng)實(shí)現(xiàn)函數(shù)，is_allocable判斷給定N個(gè)磁盤(pán)(數(shù)組D)和M個(gè)分區(qū)(數(shù)組P)，是否會(huì)出現(xiàn)分配失敗的情況。 舉例：磁盤(pán)為[120,120,120],分區(qū)為[60,60,80,20,80]可分配 ，如果為[60,80,80,20,80]則分配失敗。

　　9. 實(shí)現(xiàn)一個(gè)監(jiān)聽(tīng)load事件的接口window.load(callback):多次調(diào)用時(shí)保證執(zhí)行順序，先綁定的回調(diào)先執(zhí)行：如果load事件已觸發(fā)，調(diào)用時(shí)會(huì)直接執(zhí)行該回調(diào)

　　10. IOS系統(tǒng)提供了那些手勢(shì)?請(qǐng)選擇一個(gè)自己寫(xiě)代碼實(shí)現(xiàn)

　　UITapGestureRecognizer敲擊手勢(shì)(單擊和雙擊)

　　UIPanGestureRecognizer(拖動(dòng)手勢(shì))

　　UIPinchGestureRecognizer(縮放手勢(shì))

　　UISwipeGestureRecognizer(擦碰手勢(shì))

　　UIRotationGestureRecognizer(旋轉(zhuǎn)手勢(shì))

　　UILongPressGestureRecognizer(長(zhǎng)按手勢(shì)

　　11. 下面是美團(tuán)Andriod客戶(hù)端，團(tuán)購(gòu)列表中的一項(xiàng)團(tuán)購(gòu)，如果是你，你會(huì)怎么寫(xiě)它的layout布局?(請(qǐng)用Andriod的基本控件，編寫(xiě)layout xml實(shí)現(xiàn))

　　12. 某電商公司在做一個(gè)促銷(xiāo)活動(dòng)，促銷(xiāo)商品共10000件，只限從手機(jī)客戶(hù)端購(gòu)買(mǎi)，每個(gè)用戶(hù)&每個(gè)手機(jī)設(shè)備只限2件。商品原價(jià)M元(>10.0元)，促銷(xiāo)單價(jià)為N元(>10.0元，M>N)，活動(dòng)時(shí)間為9月9日上午10:00開(kāi)始，18:00結(jié)束，18:00前售完展示促銷(xiāo)商品售罄，非活動(dòng)時(shí)間或促銷(xiāo)商品售罄后或超出購(gòu)買(mǎi)限制，均可按原價(jià)購(gòu)買(mǎi);商品的支付方式可為網(wǎng)銀、代金券(面值5元，每單只限使用2張以?xún)?nèi))，網(wǎng)銀、代金券支付方式可任意組合;促銷(xiāo)商品支持退貨，退貨時(shí)按購(gòu)買(mǎi)金額退款，現(xiàn)金和/或代金券原路退回。請(qǐng)列出此活動(dòng)的測(cè)試要點(diǎn)

　　13. 圖A是1MB容量的存儲(chǔ)器，圖B有兩個(gè)512KB容量的存儲(chǔ)器。如果使用兩個(gè)512KB容量的存儲(chǔ)器代替圖A1MB容量的存儲(chǔ)器，圖B中方框內(nèi)應(yīng)該是什么樣的電路?并說(shuō)明原理。

【美團(tuán)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

南方報(bào)業(yè)校園招聘筆試題07-26

2015阿里校招研發(fā)工程師筆試題08-13

美甲筆如何保養(yǎng)10-07