面試崗位

后端開發(fā)

一面 (2021.0816）

臨陣抱佛腳準備了一下八股榄审，結(jié)果就問了三個算法題巾遭。

算法題

1. 加密若河，給一個映射表饱亿，讓把文本加密成密文
   答：簡單映射

2. 兩個字符串蚜退，找到最長公共字符串。
   答： 的做

3. 給一個 Unix 風格路徑如 /home/app/../a/./..彪笼，做簡化
   答：原題是這個《71.簡化路徑》钻注，思路是搞一個棧然后每次push進去

   • 3 這里擴展問了幾個問題：

     1. 如果加入一個 throw，在異常時拋出配猫，需要在哪些地方加幅恋？
        答：① 已經(jīng)到達根目錄，還要通過..回退到上一目錄時
        ② 出現(xiàn)非法字符時
        ③ 字符串開頭不為 / 或字符串為空時

     2. 兩個斜杠表示什么 //
        答：和一個斜杠 / 一個意思

     3. 由于我一開始實現(xiàn)時泵肄，最后合并結(jié)果是循環(huán)執(zhí)行 ans = s.top() + ans; 所以他問我這一步可以優(yōu)化嗎
        答：可以優(yōu)化捆交，兩種形式，一種是再搞一個棧/數(shù)組腐巢，把整個棧中的元素都反轉(zhuǎn)一下品追，然后用 ans += s.top()，還有一種辦法就是 ans += 反轉(zhuǎn)的s.top()冯丙，最后再做一次反轉(zhuǎn)肉瓦。并解釋自己是圖省事兒沒有做這步優(yōu)化，（自己其實知道）每次在stirng頭部加內(nèi)容性能很慢胃惜。

     4. 追問：如果有 個字符串泞莉，每個字符串長度都是 ，通過頭部累加的形式合并成一串船殉，那么復雜度是多少鲫趁？
        答：每次拼接時都會把以拼接部分拼接到新的字符后面，整個過程是 的利虫。

一面 (2021.0820)

可能是該部門那個組沒有名額了挨厚，把我推薦給了同部門另一個組重新面試堡僻。這次面試時間是晚上 點，能看出來小哥是真的渴望下班

基礎(chǔ)題

1. 如果有一個很大的數(shù)據(jù)流疫剃，想知道里面 top-k 的最大值苦始，該怎么辦？
   答：搞一個大小為 的堆

2. 堆排序的一次查找過程時間復雜度多少慌申？
   答：

3. 堆排序時間復雜度多少，怎么算的理郑？
   答：蹄溉，遍歷是 ，建堆/調(diào)整堆都是

4. 有其他 復雜度的排序算法嗎您炉，他們分別是怎么算的柒爵？
   答：歸并：每次合并是 的，二分過程是 的
   快排：每次按照基礎(chǔ)元素排序是 的赚爵，二分是 的

5. 內(nèi)核態(tài)和用戶態(tài)了解嗎棉胀，是什么？
   答：為了減少有限資源的訪問和使用沖突冀膝，對不同的操作賦予不同的執(zhí)行等級唁奢，就是所謂特權(quán)的概念。簡單說就是有多大能力做多大的事窝剖，與系統(tǒng)相關(guān)的一些特別關(guān)鍵的操作必須由最高特權(quán)的程序來完成麻掸。Linux操作系統(tǒng)中主要采用了0和3兩個特權(quán)級，分別對應的就是內(nèi)核態(tài)和用戶態(tài)赐纱。內(nèi)核態(tài)切換到用戶態(tài)的情況通常有系統(tǒng)調(diào)用脊奋、中斷、和外圍設(shè)備異常疙描。

6. 線程和進程區(qū)別诚隙？
   答：……（此處太長省略）

7. 進程間通信方式有哪些？
   答：PIPE起胰、有名管道久又、消息隊列、信號量待错、信號籽孙、共享內(nèi)存、套接字火俄。

8. 長連接短連接知道嗎犯建？

算法題

1. 最長上升子序列
   答：維護一個長度為 的數(shù)組

二面（2021.0824）

又臨陣抱佛腳了一下八股，結(jié)果還是沒問

基礎(chǔ)題

1. 說要實現(xiàn)一個發(fā)紅包的算法怎么實現(xiàn)瓜客，比如 個人适瓦， 元錢竿开。
   答：可以搞一個 范圍的隨機數(shù)，然后每次從當前所有錢中計算拿到多少玻熙，剩下的繼續(xù)下一輪否彩，最后一個人拿走所有。（但這一步我不會證明是否是公平的）

2. 如果春節(jié)期間嗦随，好多人都在搶紅包發(fā)紅包怎么辦列荔？
   答：降級、削峰枚尼、限流贴浙。

   • 降級指的是服務降級，這里指的是通過沒那么高級的服務署恍，來緩解瞬時壓力崎溃。比方說可以不用上面的隨機數(shù)，預先計算幾千組隨機序列盯质，發(fā)紅包時直接去套已有的隨機序列模板袁串，減少隨機數(shù)生成計算等過程；更進一步的呼巷，可以把如 這種吉利數(shù)字作為紅包隨機值囱修，增加用戶體驗，試想誰大年三十搶到一個吉利數(shù)紅包不開心呢朵逝。
   • 削峰指的是把瞬時流量拉長蔚袍，比如增加紅包動畫，或者增加復核操作等配名，讓用戶盡可能錯峰的完成發(fā)紅包搶紅包這個過程啤咽。
   • 限流是為了保護后臺服務器不被沖爆，可以搞一個消息隊列渠脉，把所有的請求放進去宇整，按照服務器水平來取用。甚至可以提前做好備案芋膘，根據(jù)需求臨時擴容服務器鳞青，等到需求回落了再把服務器縮減回去。

3. 如果有人發(fā)現(xiàn)为朋，自己發(fā)不了紅包臂拓，你該怎么看是哪里出了問題。
   答：這里我答的不好习寸，因為我其實懂得不太透徹 K8S 那一套胶惰，所以我開始胡扯。我說可以把行為分段霞溪，即用戶段孵滞，消息隊列段中捆，后臺服務器段，以及數(shù)據(jù)庫段坊饶。

   • 用戶段可以看是局部現(xiàn)象泄伪，還是一個全局現(xiàn)象，如果僅是某臺用戶設(shè)備匿级，也說不定是網(wǎng)絡不良蟋滴；如果涉及到某一地區(qū)，分析是否是區(qū)域供電問題痘绎。
   • 消息隊列段脓杉，如果用戶請求正確到達消息隊列，說明用戶行為沒錯简逮，核實消息隊列是否正確分發(fā)，是否異常丟失尿赚。
   • 后臺服務器段散庶，如果消息隊列正常分發(fā)，查看是否是某臺服務器斷線凌净，比如與主機斷連悲龟，或由于異常導致的無法服務等。這一步可以從主機查看從機狀態(tài)冰寻，也可以使用如 Habor 等工具查看任務狀態(tài)须教。
   • 數(shù)據(jù)庫段，如果后臺服務器正常請求斩芭，并根據(jù)請求開始操作數(shù)據(jù)庫（交易/轉(zhuǎn)賬等）轻腺，檢查數(shù)據(jù)庫后臺Log信息是否有誤。

4. 如果此時我們發(fā)現(xiàn)100臺服務器划乖，就其中的99號機器贬养，所有分發(fā)到這臺設(shè)備上的搶紅包任務，都沒有正常服務琴庵，我們該怎么做误算？
   答：把主機上的所有任務重新放回到消息隊列中，把他從主機上斷連迷殿，先確保之后不會再出現(xiàn)未服務儿礼。然后 ping 一下測試是否有連接，這里我接著回答的是可以去看 日志庆寺，是否有異常報錯蚊夫，在本地執(zhí)行模擬任務，定位問題止邮，不知道有沒有更好的回答方式这橙。

算法題

1. 這里的算法題我忘了奏窑，放一個八月初阿里的面試算法題好了。說有一個字符串 A 屈扎，你每次可以把其中一個字符埃唯，拿出來放到字符串末尾，問想轉(zhuǎn)換成字符串 B,最少需要移動幾次（保證 A 和 B 構(gòu)成元素相同）
   答：用 A 中所有元素鹰晨，去和 B 的前綴找到最大公共子序列墨叛。

int deal(string a, string b){
  int index = 0;
  for(auto p : a){
    if(b[index] == p){
      index++;
    }
  }
  return a.length() - index;
}

三面（2021.0830）

基礎(chǔ)題

1. 項目介紹
2. K8S 調(diào)優(yōu)接觸過嗎？
   答：沒……
3. 項目中系統(tǒng)如何實現(xiàn)用戶的高并發(fā)模蜡？
   答：讓他們在消息隊列里等著漠趁。做了一些用戶等待交互。
4. 我看到你項目里用到了 Django忍疾，有設(shè)計哪些表嗎闯传？
   答：最基礎(chǔ)的有用戶表、任務表和算法表卤妒，然后他們之間分別有一對多關(guān)系甥绿，以及還有一些補充表，比方說用戶昵稱表這些與 User 相關(guān)的则披。
5. 一個 Django 請求共缕，是怎么發(fā)送給后端的？
   答：我這里回答的是 HTTP 怎么發(fā)到后端士复，結(jié)果面試官說他想聽的是图谷，Django 是怎么接收請求的，問我知道 WSGI 做了什么嗎阱洪？我回答不會便贵。胡亂說了一些 MVC 的東西。
6. 其他的忘了冗荸，但也不是八股的內(nèi)容嫉沽，屬于兩眼一抹黑，悶頭就是吹的狀態(tài)俏竞。

算法題

1. 有一棵二叉搜索樹绸硕，有一個范圍 [a, b]，顯式 的把不在該范圍的節(jié)點刪除魂毁，返回刪除后二叉搜索樹玻佩。
   答：這里我的做法是:

void delete_TreeNode(TreeNode* root){
  if(root == NULL) return;
  // 遞歸刪除所有子樹
  delete_TreeNode(root->left);
  delete_TreeNode(root->right);
  // 這里我是后來百度的才知道該這樣刪除
  delete root;
  root = NULL;
}
TreeNode* deal(TreeNode* root, int a, int b){
  // 判空
  if(root == NULL) return NULL;
  // root在左邊界以左，則root及其左子樹需全部刪除
  if(root->val < a){
    delete_TreeNode(root->left);
    TreeNode* tmp = root->right;
    delete root;
    root = NULL;
    return deal(tmp, a, b);
  }
  // 同理root在右邊界以右席楚，則root及其右子樹需全部刪除
  if(root->val > b){
    delete_TreeNode(root->right);
    TreeNode* tmp = root->left;
    delete root;
    root = NULL;
    return deal(tmp, a, b);
  }
  // root在范圍內(nèi)咬崔，則遞歸清理兩子樹
  root->left = deal(root->left, a, b);
  root->right = deal(root->right, a, b);
}