- 美團(tuán)網(wǎng)面試問題及答案 推薦度：
- 相關(guān)推薦
美團(tuán)網(wǎng)面試問題
2014年9月25日星期四，上午10點(diǎn)去參加面試;面試地點(diǎn)是一個大教室，你坐在工程師右邊就行了;首先讓你做一個簡單的自我介紹，他順便看一下簡歷，然后就步入主題了。
開門見山：(以下簡稱A工程師和B 我)
題目一：
A 你面試的是android?恩，下面問幾個簡單問題?
B 恩。
A android 里面的Intent 有什么作用?
B 用于Activity之間的跳轉(zhuǎn)，還有數(shù)據(jù)傳遞。
A 恩。那么還有什么作用?
B (還是坦白吧!不要不懂裝懂)其實(shí)android研究的不是很深，其實(shí)我用的最多的是算法?
A 志愿里面有一個算法工程師?為什么沒選?
B 我以為要求很高，所以沒敢填，所以寫在了第二志愿!!!囧
A 好吧，那我就問一下的算法題，過了就把你轉(zhuǎn)到算法工程師那里去二面!
B 好
A那你主要研究的算法有哪些?
B 我平時研究的是dp和博弈。
A 博弈?
B 恩，主要是：背包問題(01,完全，多重，二維費(fèi)用等)，威佐夫博奕，nim游戲，SG定理以及取走分割游戲。
A 我們來看一個問題：n位的01串組成的集合S1(共個)，找出一個母串的所有同構(gòu)串所組成集合S，S1屬于S.
有點(diǎn)抽象，看個栗子：
比如 n=2 所有的01串有：00 01 10 110110 的所有2位的循環(huán)同構(gòu)串有：01 11 10 00符合條件，不能找到更短的了，因?yàn)橹辽俚糜?個0和1.你分析一下如何找一個最短的母串!
B 然后想了一下，應(yīng)該這個串長度最少應(yīng)該>=2n，大約想了5min，感覺沒什么思路!
A 你想一下，編程怎么解決?怎么找出這個串?
B 構(gòu)造?
A 不是，你把n位的所有01串全部列出來，再去選!
B 暴力!
A 恩
B 我說：這樣的話復(fù)雜度是()階乘。
A 這個串肯定包含連續(xù)n個1和連續(xù)n個0的情況，可以去掉很多情況，復(fù)雜度可以降很多
B (無語，(!) 你這么點(diǎn)優(yōu)化，無語)
A 下面，我們來討論簡單點(diǎn)的問題：
32位操作系統(tǒng)可識別的內(nèi)存多大?
B 理論值是4G。
A 為什么是4G?
B 因?yàn)?2位bit可編碼的地址空間是2^32 ，所以是4G。
A 那么你簡單說一下操作系統(tǒng)是如何分配內(nèi)存的?
B 從開機(jī)開始?
A 恩
B 首先，計算機(jī)加電，cpu直接將cs+ip置為BIOS第一行代碼的地址，讀取BIOS代碼…..直到啟動桌面。
A 恩，那么下面說一下32位int如何每一段如何劃分的?內(nèi)存分頁，最小的段是多少位?
B 好像是15位?
A 偏移位占幾位?
B 2位吧!
A 好吧，那么 ….
B (坦白吧!直接打斷他)這個我沒怎么研究過!
A 下面我們還是來做幾個題：
如何判斷一個單鏈表有環(huán)?
B 想了一下，Hash判重，每次查詢是O(1)效率是O(n)，如果訪問過重復(fù)訪問的點(diǎn)說明有環(huán)，如果為NULL，說明無環(huán)?
A 不錯，那么輔助空間是多少?
B O(n)
A 可不可以不用輔助空間呢?或者只用O(1)的輔助空間
B 讓我想想?
About 5min,.....
B 好像沒什么想法，因?yàn)槟愣纪浟四阕约鹤哌^的路!!好像不好搞耶!
/***后來google之(吐槽一下：自從前幾個月google加密搜索字段之后，有關(guān)部門墻了，修改本地host文件就行了)，發(fā)現(xiàn)google才是學(xué)術(shù)帝，龜兔算法!!(亦稱快慢指針)stackoverflow上有這樣的問題!!還可以求環(huán)，效率O(n),突然發(fā)現(xiàn)優(yōu)化無止境。
***/
A 恩，那么我們來看下一個題!
給你一個嚴(yán)格遞增的序列，從中間某個未知的地方切成兩段，將前一段放到后面，求最大值?注意劃開的位置你不知道!
B O(n)的遍歷可以，我覺得你是要更高效率的算法!
A 恩
B 在紙上簡單畫了畫，大約兩分鐘thinking，發(fā)現(xiàn)可以二分搞!立馬給面試官講了思路!
A 恩，寫代碼實(shí)現(xiàn)一下。
B 下手就寫，寫完之后，發(fā)現(xiàn)L<r有點(diǎn)小問題，沒去管!< p="">
A 面試官看了下，你的邊界是不是有問題?
B (還真的看出來了!)想了1min，改成L+1<r返回的時候min(a[l],a[r])就沒事了.< p="">
A 恩，不錯。
A 判斷一個二叉樹是否關(guān)于根節(jié)點(diǎn)左右對稱!
B 想了想，遍歷樹的方式，發(fā)現(xiàn)“左根右”==“右跟左”即可判斷是否“手性對稱”(這是高中在書上看到的一個詞)。
A 如果一個做孩子為空，一個右孩子為NULL，那就不對了。
B 我說：加一個-1到遍歷序列。
A (面試官，又在紙上畫了畫)~~~你這個方法可以，但是你得保存遍歷序列，可不可以不要輔助空間?
B(好吧!原來優(yōu)化了時間，再想空間優(yōu)化，一般我只做前一個)想了想，遍歷!
A 對!
B 哦，真的!(頓悟)遞歸實(shí)現(xiàn)，每次比較左右孩子即可!4種情況。
A 寫一下代碼。
B (好吧，習(xí)慣了!)下筆就開始，發(fā)現(xiàn)自己沒寫好，又自己重寫了一次，大約花了7~8min，好了。
A 面試官看了看，行。
A 再看一個題：一個二叉樹，層次遍歷!寫一下代碼。如果你想記錄下來一起輸出也行。
B (搞的我好像很喜歡開數(shù)組似的，還有沒有完!)BFS層次遍歷就行。
。。。寫完代碼
A 你先到外面等一下!
B 恩。
大約5min，通知進(jìn)去二面。
題目二：
A 做，先簡單介紹一下!
B 恩我來自……(介紹完畢)
A 下面我們來討論一下CS.
B 不好意思，沒聽太清CS是?
A Computer Science(不屑)
B 哦，計算機(jī)科學(xué)!(汗)
A 看了你的簡歷，平時都研究哪方面的算法?
B (又重復(fù)了一遍。。。)
A 我們先看一個問題：黑白棋盤，從左上角到右下角是否有路，只能訪問上下左右4個位置，且為白色?問是否可達(dá)?
B (心中竊喜，BFS尋路，簽到題)問：用不用記錄步數(shù)?
A 不用!先看是否可達(dá)?
B 那就是BFS!
A 你寫一下代碼!
B 大約6min，寫完!最壞的情況下，復(fù)雜度O(n*m)
A 他一行一行看了代碼!好像沒發(fā)現(xiàn)什么問題，說怎么沒輸出路徑!!
B (暈!你不早說!)拿回代碼，改之，開了一個標(biāo)記數(shù)組，存儲方向!到達(dá)終點(diǎn)，從終點(diǎn)回溯輸出即可!
B 可不可以不回溯!你這多了一重循環(huán)!復(fù)雜度最多是(n*m+n+m)只是增加了O(n+m)，時間復(fù)雜度!總的時間復(fù)雜度根本沒增加!!(真感覺，太沒風(fēng)度了，能不能找個心服口服的理由)!
A 不一樣，能不能不開標(biāo)記數(shù)組!能不能不要那重循環(huán)找路!
B 那就遞歸DFS，我寫的是BFS!
A 能不能不用遞歸!
B 那就將遞歸DFS改成非遞歸DFS，那也得開數(shù)組記錄狀態(tài)啊!
A 能不能不開數(shù)組!
B 非遞歸，不開數(shù)組怎么保存狀態(tài)!(我感覺，越來越…..)(聲音好大，別人還以為我們吵起來了)
A 那么我們來換一個題：
現(xiàn)在，我們的服務(wù)器上有一個APK文件，你知道就是一個ZIP包，對于每一個用戶請求，先建立連接，然后判斷請求來源，把a(bǔ)pk解包，在manifest后追加來源信息，再打包成apk，發(fā)給請求方。
問：1.如果多個用戶同時請求，沒有時差，怎么解決沖突?
2 .如何提高數(shù)據(jù)的發(fā)送效率?
B 單例模式?
A 單例模式解決不了。
B 如果多用戶同時請求，可以建立一個請求隊列，然后判斷請求隊列是否為空，不為空，則循環(huán)取隊列中的請求建立連接!
A 如果兩個用戶的請求同時到達(dá)!
B 對文件加鎖!!
A 如果兩個請求同時請求加鎖?
B 這個….我不是很清楚!
A 那么看第二個問題，如何提高數(shù)據(jù)的發(fā)送效率?
B 得先找瓶頸段，看哪段效率最低?我覺得的瓶頸段應(yīng)該在節(jié)點(diǎn)的轉(zhuǎn)發(fā)上!spfa尋最短路!
A 不是!!
B 哦，數(shù)據(jù)到公網(wǎng)上就不受發(fā)送者控制了!那就是服務(wù)器端，數(shù)據(jù)包分組發(fā)送?
A 那怎么分組?
B 這個不是默認(rèn)就分好的嗎!
A 你可以控制!
B 好吧!這個不是太懂!
A 那今天就到這里吧!你先回去吧!
B (估計沒戲!回去好好學(xué)習(xí)吧!)
[美團(tuán)網(wǎng)面試問題]
【美團(tuán)網(wǎng)面試問題】相關(guān)文章：
大學(xué)生團(tuán)的面試問題08-13
淘寶網(wǎng)客服面試問題09-11
美團(tuán)的企業(yè)管理分析09-26
美團(tuán)總裁王興的創(chuàng)業(yè)故事09-04
面試經(jīng)典問題08-01
MBA面試經(jīng)典的面試問題10-23
騰訊面試的面試問題07-11