拼多多 暑期實(shí)習(xí) 二面，總共用時(shí)1h 左右， 被面試官瘋狂拷打， 估計(jì)涼涼。

首先介紹項(xiàng)目， 對(duì)方完全不感興趣： 你做的這些和后端開(kāi)發(fā)有什么關(guān)系？
我簡(jiǎn)單介紹了下后端相關(guān)的，面試官可能覺(jué)得太簡(jiǎn)單了，沒(méi)有繼續(xù)問(wèn)。

然后就是痛苦的手撕拷打，持續(xù)50mins 左右。

問(wèn)題1： 給你兩個(gè)班級(jí)， 每個(gè)班級(jí)共有 k 個(gè)人，你是班主任，要從每個(gè)班級(jí)中挑出1個(gè)人，使得他們的身高差最小。

回答： 先排序， 然后遍歷A班級(jí)，二分查找B班級(jí)中的第一個(gè)大于等于（lower_bound）A班級(jí)里的那個(gè) 的位置，然后比較那個(gè)位置和前一個(gè)位置。

面試官和我不太同頻，問(wèn)我為什么要找第一個(gè)大于等于？二分查找不就是找一個(gè)位置嗎？ 面試官笑瞇瞇的問(wèn)我是第一次接觸二分搜索嗎？

然后計(jì)算時(shí)間復(fù)雜度。

感覺(jué)完全不同頻。

問(wèn)還有更優(yōu)解法嗎？

回答雙指針，還是固定遍歷A， 然后另一個(gè)指針從B開(kāi)始找比A大的，然后在和前一個(gè)也比較，取最小的。這樣就是O(n).

面試官提示一下，不要局限在當(dāng)前這個(gè)和前一個(gè)比較，換種思路。

然后我一直在思考，對(duì)方問(wèn)我雙指針要怎么初始化？  因?yàn)槲疫€沒(méi)想好，就沒(méi)回答。

面試官： 雙指針要怎么初始化？這你都不懂嗎。。。？ 怎么不回答我。

我說(shuō)新思路還沒(méi)想好，面試官表示剛才那種思路的雙指針要怎么初始化？ 答：都初始化在第一個(gè)位置。

問(wèn)題2： 兩個(gè)班級(jí)， 換成 N 個(gè)班級(jí)， 每個(gè)班級(jí)選1個(gè)人， 要求算出來(lái)的人里的 max - min 最小。

答沒(méi)思路， 面試官提示下多個(gè)指針？ 考慮下指針應(yīng)該如何移動(dòng)。

我想了想，移動(dòng)最小的那個(gè)指針，直到所有指針都走到末尾，每次移動(dòng)，從這個(gè)N個(gè)人里面取最大的，最小的，比較。

然后算時(shí)間復(fù)雜度：

n個(gè)班，每個(gè)班k個(gè)人，  我想整體的數(shù)據(jù)規(guī)模是 N = n*k ， 然后我用 N 去后續(xù)表示。

面試官：你為什要定義新的符號(hào)N？

算完時(shí)間復(fù)雜度，問(wèn)我“從這個(gè)N個(gè)人里面取最大的，最小的”這部分可以優(yōu)化嗎？

我回答可以使用 map （cpp里的），面試官表示你直接說(shuō)數(shù)據(jù)結(jié)構(gòu)，不要說(shuō)語(yǔ)言中的名字。
問(wèn)這個(gè)的時(shí)間復(fù)雜度，答logn

面試官：那你開(kāi)始寫(xiě)吧。

寫(xiě)了大概 3 分鐘。 他看了眼。

問(wèn)題3： ping 100ms  ， curl http://1.2.3.4:8080/hello  需要多少時(shí)間？

這里我考慮了4次揮手， 面試官：需要考慮這個(gè)嗎？

答 200ms. 

問(wèn)題4： 直播間，打賞金額最高的100個(gè)用戶？ 你應(yīng)該如何實(shí)現(xiàn)維護(hù)？

我回答使用 redis 的 zset ，  可以高效的獲取top 100.

面試官問(wèn)：這樣有什么問(wèn)題嗎？ 如果用戶特別多的情況。

我想了一會(huì)，也沒(méi)想出什么問(wèn)題，回答沒(méi)什么思路。
面試官：用戶太多了會(huì)有 大 key 問(wèn)題， zset 刪除的時(shí)候會(huì)阻塞幾秒。 （我不太理解）
面試官：你應(yīng)該考慮怎么優(yōu)化？

答： string 配合 zset 使用， string kv 中存 user, money,  而 zset 中只維護(hù) top 100 的。同時(shí)更新這倆。

最后， 反問(wèn)
部門(mén)業(yè)務(wù)：拼多多直播帶貨。
技術(shù)棧： 面試官看我的簡(jiǎn)歷里面，cpp 太底層了我們這邊不用，golang 也不用，主要是 java ， 然后 redis， mysql, kafka這些。

面試官問(wèn)我懂不懂二分， 我當(dāng)時(shí)多少有點(diǎn)生氣??， 不過(guò)總的來(lái)說(shuō)面試官人還不錯(cuò)，還算友善，給了很多引導(dǎo)。

#?？蛣?chuàng)作賞金賽#
#拼多多#