美團(tuán)網(wǎng)面試問(wèn)題

2014年9月25日星期四，上午10點(diǎn)去參加面試;面試地點(diǎn)是一個(gè)大教室，你坐在工程師右邊就行了;首先讓你做一個(gè)簡(jiǎn)單的自我介紹，他順便看一下簡(jiǎn)歷，然后就步入主題了。

開(kāi)門見(jiàn)山：(以下簡(jiǎn)稱A工程師和B 我)

題目一：

A 你面試的是android?恩，下面問(wèn)幾個(gè)簡(jiǎn)單問(wèn)題?

B 恩。

A android 里面的Intent 有什么作用?

B 用于Activity之間的跳轉(zhuǎn)，還有數(shù)據(jù)傳遞。

A 恩。那么還有什么作用?

B (還是坦白吧!不要不懂裝懂)其實(shí)android研究的不是很深，其實(shí)我用的最多的是算法?

A 志愿里面有一個(gè)算法工程師?為什么沒(méi)選?

B 我以為要求很高，所以沒(méi)敢填，所以寫在了第二志愿!!!囧

A 好吧，那我就問(wèn)一下的算法題，過(guò)了就把你轉(zhuǎn)到算法工程師那里去二面!

B 好

A那你主要研究的算法有哪些?

B 我平時(shí)研究的是dp和博弈。

A 博弈?

B 恩，主要是：背包問(wèn)題(01,完全，多重，二維費(fèi)用等)，威佐夫博奕，nim游戲，SG定理以及取走分割游戲。

A 我們來(lái)看一個(gè)問(wèn)題：n位的01串組成的集合S1(共個(gè))，找出一個(gè)母串的所有同構(gòu)串所組成集合S，S1屬于S.

有點(diǎn)抽象，看個(gè)栗子：

比如 n=2 所有的01串有：00 01 10 110110 的所有2位的循環(huán)同構(gòu)串有：01 11 10 00符合條件，不能找到更短的了，因?yàn)橹辽俚糜?個(gè)0和1.你分析一下如何找一個(gè)最短的母串!

B 然后想了一下，應(yīng)該這個(gè)串長(zhǎng)度最少應(yīng)該>=2n，大約想了5min，感覺(jué)沒(méi)什么思路!

A 你想一下，編程怎么解決?怎么找出這個(gè)串?

B 構(gòu)造?

A 不是，你把n位的所有01串全部列出來(lái)，再去選!

B 暴力!

A 恩

B 我說(shuō)：這樣的話復(fù)雜度是()階乘。

A 這個(gè)串肯定包含連續(xù)n個(gè)1和連續(xù)n個(gè)0的情況，可以去掉很多情況，復(fù)雜度可以降很多

B (無(wú)語(yǔ)，(!) 你這么點(diǎn)優(yōu)化，無(wú)語(yǔ))

A 下面，我們來(lái)討論簡(jiǎn)單點(diǎn)的問(wèn)題：

32位操作系統(tǒng)可識(shí)別的內(nèi)存多大?

B 理論值是4G。

A 為什么是4G?

B 因?yàn)?2位bit可編碼的地址空間是2^32 ，所以是4G。

A 那么你簡(jiǎn)單說(shuō)一下操作系統(tǒng)是如何分配內(nèi)存的?

B 從開(kāi)機(jī)開(kāi)始?

A 恩

B 首先，計(jì)算機(jī)加電，cpu直接將cs+ip置為BIOS第一行代碼的地址，讀取BIOS代碼…..直到啟動(dòng)桌面。

A 恩，那么下面說(shuō)一下32位int如何每一段如何劃分的?內(nèi)存分頁(yè)，最小的段是多少位?

B 好像是15位?

A 偏移位占幾位?

B 2位吧!

A 好吧，那么 ….

B (坦白吧!直接打斷他)這個(gè)我沒(méi)怎么研究過(guò)!

A 下面我們還是來(lái)做幾個(gè)題：

如何判斷一個(gè)單鏈表有環(huán)?

B 想了一下，Hash判重，每次查詢是O(1)效率是O(n)，如果訪問(wèn)過(guò)重復(fù)訪問(wèn)的點(diǎn)說(shuō)明有環(huán)，如果為NULL，說(shuō)明無(wú)環(huán)?

A 不錯(cuò)，那么輔助空間是多少?

B O(n)

A 可不可以不用輔助空間呢?或者只用O(1)的輔助空間

B 讓我想想?

About 5min,.....

B 好像沒(méi)什么想法，因?yàn)槟愣纪�記了你自己走過(guò)的路!!好像不好搞耶!

/***后來(lái)google之(吐槽一下：自從前幾個(gè)月google加密搜索字段之后，有關(guān)部門墻了，修改本地host文件就行了)，發(fā)現(xiàn)google才是學(xué)術(shù)帝，龜兔算法!!(亦稱快慢指針)stackoverflow上有這樣的問(wèn)題!!還可以求環(huán)，效率O(n),突然發(fā)現(xiàn)優(yōu)化無(wú)止境。

***/

A 恩，那么我們來(lái)看下一個(gè)題!

給你一個(gè)嚴(yán)格遞增的序列，從中間某個(gè)未知的地方切成兩段，將前一段放到后面，求最大值?注意劃開(kāi)的位置你不知道!

B O(n)的遍歷可以，我覺(jué)得你是要更高效率的算法!

A 恩

B 在紙上簡(jiǎn)單畫了畫，大約兩分鐘thinking，發(fā)現(xiàn)可以二分搞!立馬給面試官講了思路!

A 恩，寫代碼實(shí)現(xiàn)一下。

B 下手就寫，寫完之后，發(fā)現(xiàn)L<r有點(diǎn)小問(wèn)題，沒(méi)去管!< p="">

A 面試官看了下，你的邊界是不是有問(wèn)題?

B (還真的看出來(lái)了!)想了1min，改成L+1<r返回的時(shí)候min(a[l],a[r])就沒(méi)事了.< p="">

A 恩，不錯(cuò)。

A 判斷一個(gè)二叉樹(shù)是否關(guān)于根節(jié)點(diǎn)左右對(duì)稱!

B 想了想，遍歷樹(shù)的方式，發(fā)現(xiàn)“左根右”==“右跟左”即可判斷是否“手性對(duì)稱”(這是高中在書(shū)上看到的一個(gè)詞)。

A 如果一個(gè)做孩子為空，一個(gè)右孩子為NULL，那就不對(duì)了。

B 我說(shuō)：加一個(gè)-1到遍歷序列。

A (面試官，又在紙上畫了畫)~~~你這個(gè)方法可以，但是你得保存遍歷序列，可不可以不要輔助空間?

B(好吧!原來(lái)優(yōu)化了時(shí)間，再想空間優(yōu)化，一般我只做前一個(gè))想了想，遍歷!

A 對(duì)!

B 哦，真的!(頓悟)遞歸實(shí)現(xiàn)，每次比較左右孩子即可!4種情況。

A 寫一下代碼。

B (好吧，習(xí)慣了!)下筆就開(kāi)始，發(fā)現(xiàn)自己沒(méi)寫好，又自己重寫了一次，大約花了7~8min，好了。

A 面試官看了看，行。

A 再看一個(gè)題：一個(gè)二叉樹(shù)，層次遍歷!寫一下代碼。如果你想記錄下來(lái)一起輸出也行。

B (搞的我好像很喜歡開(kāi)數(shù)組似的，還有沒(méi)有完!)BFS層次遍歷就行。

。。。寫完代碼

A 你先到外面等一下!

B 恩。

大約5min，通知進(jìn)去二面。

題目二：

A 做，先簡(jiǎn)單介紹一下!

B 恩我來(lái)自……(介紹完畢)

A 下面我們來(lái)討論一下CS.

B 不好意思，沒(méi)聽(tīng)太清CS是?

A Computer Science(不屑)

B 哦，計(jì)算機(jī)科學(xué)!(汗)

A 看了你的簡(jiǎn)歷，平時(shí)都研究哪方面的算法?

B (又重復(fù)了一遍。。。)

A 我們先看一個(gè)問(wèn)題：黑白棋盤，從左上角到右下角是否有路，只能訪問(wèn)上下左右4個(gè)位置，且為白色?問(wèn)是否可達(dá)?

B (心中竊喜，BFS尋路，簽到題)問(wèn)：用不用記錄步數(shù)?

A 不用!先看是否可達(dá)?

B 那就是BFS!

A 你寫一下代碼!

B 大約6min，寫完!最壞的情況下，復(fù)雜度O(n*m)

A 他一行一行看了代碼!好像沒(méi)發(fā)現(xiàn)什么問(wèn)題，說(shuō)怎么沒(méi)輸出路徑!!

B (暈!你不早說(shuō)!)拿回代碼，改之，開(kāi)了一個(gè)標(biāo)記數(shù)組，存儲(chǔ)方向!到達(dá)終點(diǎn)，從終點(diǎn)回溯輸出即可!

B 可不可以不回溯!你這多了一重循環(huán)!復(fù)雜度最多是(n*m+n+m)只是增加了O(n+m)，時(shí)間復(fù)雜度!總的時(shí)間復(fù)雜度根本沒(méi)增加!!(真感覺(jué)，太沒(méi)風(fēng)度了，能不能找個(gè)心服口服的理由)!

A 不一樣，能不能不開(kāi)標(biāo)記數(shù)組!能不能不要那重循環(huán)找路!

B 那就遞歸DFS，我寫的是BFS!

A 能不能不用遞歸!

B 那就將遞歸DFS改成非遞歸DFS，那也得開(kāi)數(shù)組記錄狀態(tài)啊!

A 能不能不開(kāi)數(shù)組!

B 非遞歸，不開(kāi)數(shù)組怎么保存狀態(tài)!(我感覺(jué)，越來(lái)越…..)(聲音好大，別人還以為我們吵起來(lái)了)

A 那么我們來(lái)?yè)Q一個(gè)題：

現(xiàn)在，我們的服務(wù)器上有一個(gè)APK文件，你知道就是一個(gè)ZIP包，對(duì)于每一個(gè)用戶請(qǐng)求，先建立連接，然后判斷請(qǐng)求來(lái)源，把a(bǔ)pk解包，在manifest后追加來(lái)源信息，再打包成apk，發(fā)給請(qǐng)求方。

問(wèn)：1.如果多個(gè)用戶同時(shí)請(qǐng)求，沒(méi)有時(shí)差，怎么解決沖突?

2 .如何提高數(shù)據(jù)的發(fā)送效率?

B 單例模式?

A 單例模式解決不了。

B 如果多用戶同時(shí)請(qǐng)求，可以建立一個(gè)請(qǐng)求隊(duì)列，然后判斷請(qǐng)求隊(duì)列是否為空，不為空，則循環(huán)取隊(duì)列中的請(qǐng)求建立連接!

A 如果兩個(gè)用戶的請(qǐng)求同時(shí)到達(dá)!

B 對(duì)文件加鎖!!

A 如果兩個(gè)請(qǐng)求同時(shí)請(qǐng)求加鎖?

B 這個(gè)….我不是很清楚!

A 那么看第二個(gè)問(wèn)題，如何提高數(shù)據(jù)的發(fā)送效率?

B 得先找瓶頸段，看哪段效率最低?我覺(jué)得的瓶頸段應(yīng)該在節(jié)點(diǎn)的轉(zhuǎn)發(fā)上!spfa尋最短路!

A 不是!!

B 哦，數(shù)據(jù)到公網(wǎng)上就不受發(fā)送者控制了!那就是服務(wù)器端，數(shù)據(jù)包分組發(fā)送?

A 那怎么分組?

B 這個(gè)不是默認(rèn)就分好的嗎!

A 你可以控制!

B 好吧!這個(gè)不是太懂!

A 那今天就到這里吧!你先回去吧!

B (估計(jì)沒(méi)戲!回去好好學(xué)習(xí)吧!)

[美團(tuán)網(wǎng)面試問(wèn)題]

【美團(tuán)網(wǎng)面試問(wèn)題】相關(guān)文章：

美團(tuán)網(wǎng)面試問(wèn)題及答案08-09

大學(xué)生團(tuán)的面試問(wèn)題08-13

淘寶網(wǎng)客服面試問(wèn)題09-11

網(wǎng)銀在線校園招聘面試問(wèn)題及答案10-05

網(wǎng)銀在線校園招聘面試問(wèn)題及答案07-08

美團(tuán)的企業(yè)管理分析09-26

美團(tuán)總裁王興的創(chuàng)業(yè)故事09-04

面試經(jīng)典問(wèn)題08-01

MBA面試經(jīng)典的面試問(wèn)題10-23

騰訊面試的面試問(wèn)題07-11