你猜他通過了嗎
一面2020/12/20/14：00-14：50
1、自我介紹（2分鐘）
2、你說你讀過 redis 原始碼，那說一下常用的資料結構，
字串、跳表、字典、壓縮串列、鏈表
3、介紹一下跳表：
它在初始化的時候會分配一個頭，它也是和鏈表一樣鏈起來一個表嘛，它會給每個節點隨機分配一個層，然后它從它的頭部給每個節點進行每一層的連接，它的層數越高，它就會直接連到后面去，中間低的層就不連了，包括它的遍歷也是一樣，從高到低來找哪個數，這樣它就可以跳著遍歷了，
4、查找的時間復雜度是多少：log(n)
5、空間占用呢，相對于鏈表多了什么：主要是多出了那個層嘛，它每個節點的層數是不一樣的，如果層都是1，也就退化成鏈表了，
6、vector push_back 擴容：2倍擴容，實際上可能更復雜一點
7、擴容以后，它的記憶體地址會變化嘛：會變化，以前的話，它是會把原來的元素重新復制過去，開辟一個新空間，復制過去，再把它之前的空間 free 掉，但是現在的話，是通過移動語意 move 來的
8、說一說 move 語意：相對于以前的復制來說，是把元素復制一遍，再把之前的銷毀掉，現在的 move 相當于是把它直接搬走了，也就是，我再想一種說法，也就是延長了它的生命周期，然后把新的指標直到原先的那個位置去，然后把原先的指標賦為空，差不多這樣，
9、move 底層的實作：emm，我看到了有 static_cast ，但是具體的，沒有完全了解過
10、右值參考：把那種臨時的變數，或者說馬上就要消亡，那個叫將亡值，把它的生命周期給延長，變成左值，
11、什么時候被釋放：我的理解是它相當于一個左值了（意思和左值一樣）
12、怎么把 vector 里面存資料的所有記憶體空間都釋放掉：先說的 resize ，后面改說是另一個函式，不記得名字了
13、說一下虛函式：子類對父類的函式進行一個重寫，
14、舉個例子詳細說一下吧：舉例說了動物（父類）吃東西，其他子類吃的動作不一樣，這個時候對吃這個函式使用虛函式，
15、虛函式和函式重寫有什么區別呢：（亂七八糟猜了一同）我這樣猜的
16、再具體說說：但是我不知道這樣猜的對不對
17、那換個問題吧，說說參考和指標：1. 記憶體占用；2. 初始化；3. 可修改指向
18、還有嘛：沒了
19、參考可以銷毀嘛：不知道了
20、智能指標了解過嘛，說說怎么實作的：增加了一個參考計數
21、具體說說：不同的智能指標指向同一個物件，有一個指標指向，它的參考計數就+1，最后變為0的時候，它就自動的銷毀了，
22、多執行緒中可以使用智能指標嘛：不同執行緒里面的智能指標都是指向同一個物件嘛？是的：我覺得應該是適用的吧
23、你不知道是吧，確實是適用的，你是怎么想的呢：它不同的執行緒是共享資源的吧，所以它們是可以指到同一個物件上的吧
24、會有讀寫沖突嘛：會有的
25、怎么解決：應該通過加鎖來解決
手撕
1. 中序遍歷（迭代）
給定二叉樹的，構造一個中序遍歷的迭代器，對應的功能是回傳二叉樹上的下一個元素，class Iterator { public: TreeNode* next(); }
1.1 思路討論（6分鐘左右）
我：在實作的程序中，需要把中序遍歷給記錄下來嘛
面：你具體說說
我：比如說，我在初始化的時候直接把它的中序遍歷存在 vector 中，直接用 next 這樣來訪問
面：說說有什么優點和缺點
我：優點就是在呼叫 next 的時候復雜度是 O(1)，缺點就是在初始化的時候要把它完全遍歷一遍，空間復雜度是O(n)
面：你可以試試其他方法
我：是不用額外的空間嘛
面：也不是不用，但是比 O(n) 小點，比如 O(logn) 就行了，
我：哦哦，那就是用一個堆疊，記錄它balabala....
面：那你開始寫吧
面：你先定義一個TreeNode
我：需要定義Tree嘛
面：這個不用
我：這個需要運行嘛
面：先不需要
1.2中途代碼撰寫（八分鐘左右）
面：根節點從建構式傳入
#include <iostream> #include <stack> using namespace std; struct TreeNode { int val; TreeNode* left, *right; }; class Iterator { public: stack<TreeNode*> s; Iterator(TreeNode* root) { // s.push(root); TreeNode* t = root; while (t) { s.push(t); t = root->left; } } TreeNode* next() { if (s.empty()) return nullptr; // 面試官后面提醒 TreeNode* ret = s.top(); TreeNode* t = ret; if (t&&t->right) { t = t->right; while (t) { s.push(t); t = t->left; } } else { TreeNode* tRight = t; s.pop(); if (s.empty()) return ret; // 面試官后面提醒 t = s.top(); while (t->right == tRight) { s.pop(); if (s.empty()) return ret; // 面試官后面提醒 tRight = t; t = s.top(); } } return ret; } }
1.3 代碼解釋（4分鐘）
寫完之后，讓我解釋代碼，并指出幾個沒有加特殊情況的位置，
2. 全排列
給定一個陣列，列印它的全排列
[1,2]
-> [1,2] [2,1]2.1 說思路（2分鐘）
- 面：說不太清，你覺得沒問題就直接寫吧
2.2 代碼（7分鐘）
#include <iostream> #include <vector> using namespace std; vector<vector<int>> ans; void sol(vector<int>& v, vector<int> ret, vector<bool> flag) { if (ret.size() == v.size()) ans.push_back(ret); for (int i = 0; i < v.size(); ++ i) { if (flag[i]) { ret.push_back(v[i]); flag[i] = false; sol(v, ret, flag); flag[i] = true; ret.pop_back(); } } } int main() { vector<int> v; for (int i = 1; i <= 3; ++ i) v.push_back(i); vector<int> ret; vector<bool> flag(v.size(), true); sol(v, ret, flag); for (int i = 0; i < ans.size(); ++ i) { for (int j = 0; j < ans[i].size(); ++ j) cout << ans[i][j] << ' '; cout << endl; } }
反問
- 我：你覺得我還有什么需要加強的地方嘛
- 面：你的廣度還行，但是深度不夠，比如虛函式和智能指標
二面2020/12/21/14：05-15：05
自我介紹
簡歷有寫c++，接受其他語言嘛：具體什么語言
golang，python：可以接受，只是偏向c++
實習時間：沒有其他問題，可以實習到轉正
說明轉正時間（提醒我時間很長）：沒特殊情況，希望實習到轉正
base上海？：是的
闡述實習的作業（3分鐘）
說說行程、執行緒、協程：說了行程是資源調度單位，執行緒是cpu調度單位，協程有個通道可以傳輸資料，粒度上：行程 > 執行緒 > 協程
可以試著說說它們的優缺點：行程切換的缺點，時間開銷；其他的我可能不太了解，就說這么多吧
說說行程、執行緒的通信：行程：通道（口誤把管道說成了通道，，）、信號，socket也算吧；執行緒用信號比較多吧，
演算法題
說一說lru，快取大小為K，怎么設計數據結構：用鏈表保存快取資料，說了訪問的程序；繼續說鏈表查找上的缺點，時間復雜度為O(n)，所以用哈希來查找，時間復雜度可以降為O(1)，（2分鐘）
如果加上過期時間呢：在鏈表節點中加一個更新時間，在訪問資料的時候，判斷一下時間有沒有過期，就行了吧，（3分鐘）
寫一下吧：
（剛開始的時候自己實作的 list 來寫的，挺麻煩的，我突然反應過來之前是用stl的，這時候已經過了15分鐘）我：我可以改成用stl么，，，，
面：可以的，你改
（15分鐘后，寫完了）
#include <iostream> #include <unordered_map> #include <list> #include <pair> using namespace std; struct ListNode { int val; ListNode* next, *pri; double update; }; class lru { // ListNode* head, *tail; list<pair<int, double>> l; unordered_map<int, list<pair<int, double>>::iterator > m; int K; int nums; double T; lru(int k, double t) { K = k; nums = 0; T = t; } void set(int x) { if (m.find(x) == m.end()) { auto p = make_pair(x, time()); l.push_back(p); m[x] = l.rbegin(); nums ++; } else { auto p = m[x]; p->first = x; p->second = time(); l.erase(p); l.push_back(*p); m[x] = l.rbegin(); } if (nums > K) { l.pop_front(); nums --; } } int get(int x) { if (m.find(x) == m.end()) { return 0; } else { auto p = m[x]; if (time() - p->second >= T) { m.erase(x); l.erase(p); return 0; } else { p->second = time(); l.erase(p); l.push_back(*p); m[x] = l.rbegin(); return x; } } } }
如果是多執行緒里面會出錯嘛：會出錯
那怎么解決呢：在對資料結構內部進行修改的時候加鎖
具體點：
// 這里加寫鎖 l.erase(p); l.push_back(*p); m[x] = l.rbegin();
mysql 的索引資料結構：B+樹
說說為什么用 B+ 樹：說了范圍查找的優點
說說 git merge 和 git rebase 哪個好：rebase
說說有什么優點：不太清楚
反問
看原始碼和做專案，從面試和自我提升的角度哪個更好：都很重要，后者重要一點
面的哪個組：廣告創意
面試官介紹了4分鐘：感徑訓挺有意思的
三面2020/12/24/14：00-14：55
自我介紹（2分鐘）
實習介紹（12分鐘）
redis常用資料結構：字串、字典、鏈表、跳表、壓縮串列、集合、有序集合
有序集合的實作方式：跳表和壓縮串列
具體說說：壓縮串列用于資料量小的情況，存盤方式是線性的；資料量大的時候會自動轉換為跳表，跳表和鏈表一樣，由一個一個節點鏈起來，但是它的節點和鏈表不一樣，它的節點會被隨機分配一個層數，相同的層數鏈接起來，
跳表查詢的時間復雜度：log(n)
有序集合中有查詢時間復雜度為O(1)的實作嗎：有序集合應該是沒有的，
redis 的過期策略：有好幾種吧，常見的lru
不是說這種，redis里面不是有好多不同的鍵、值，它們的過期策略：哦，在時間事件里面，會對過期的東西直接刪掉，另外，訪問到的時候，如果它過期了，也會進行洗掉
之前用的資料庫是什么：mysql
引擎是什么：innodb
隔離級別是：可重復讀
怎么實作的可重復讀：MVCC
使用的樂觀鎖還是悲觀鎖：樂觀鎖
MVCC的實作：增加了版本號，有個版本鏈，每次事務開始的時候有一個快照，其他事務讀取的時候，讀取那個快照，事務內部修改的時候有一個日志，日志會記錄事務內部對這一行的修改，會用于事務的回滾，
binlog、redolog(也可能是undo log)聽說過嗎：聽說過，但是沒深入了解過
innodb的索引資料結構是什么：B+樹
主鍵和非主鍵的索引呢：它一開始只會對主鍵建索引吧
非主鍵呢：不清楚
B+樹的葉子節點存放的什么：整體的資料，包括索引，都在里面
瀏覽器輸入一個url，回傳了一個error，怎么找出錯的地方：通過狀態碼
沒有狀態碼，只有一個error：啥都沒有嗎，，，
dns的回傳標志：那可能是dns上的錯誤，可能不存在這個域名
但是我輸入的toutiao.com，我知道是存在的：是的，那可能是dns查詢的時候出現了錯誤，那可以一步一步的查，它剛出去的時候訪問的那個dns服務器（應該都是有的，小聲bb），可能最近的那個路由器或者電腦里面沒有配dns，有沒有可能（強訊訓笑）
你怎么知道最近的呢：查詢dns的路徑，好像是有一個命令的
什么命令呢：這命令名字我不記得了，，，
linux怎么查看系統的狀態呢：top
top出來顯示什么：cpu占用率，記憶體占用率、一些行程的資訊
實習中，python后端，是怎么實作的http連接，是django嗎：emm，是通過webpy的api直接呼叫的，，，，
你的request，post，具體實作是什么：emmm，我可以從c++方面來說嗎
嗯：它要創建一個套接字，給套接字分配一個埠，等待連接的到來，連接來了之后，像redis的話，它收到連接，會復制一個socket，分配一個新埠，把這個連接分配給新socket，原先的socket繼續listen，連接之后，讀取socket里面緩沖區的內容，再內部進行處理，再通過socket傳輸出去，
socket監聽是哪個層：tcp
之前問的是http，這方面是不是不太了解：嗯
還有什么領域沒問你的嗎：作業系統，計算機網路，你們應該用golang，python比較多吧
也有用c++的：那還有c++這些，了解的多一些
段頁式存盤執行的時候會訪問幾次記憶體：訪問記憶體會通過頁的級數也有關系，如果它是一級頁表的話，它取頁號一次，取物理地址一次，如果沒有在記憶體中的話，還會訪問磁盤
我問的段頁式：段頁式先取它的段內偏移量，然后再訪問物理地址，是兩次
行程的存盤分布：堆疊、堆、資料區、代碼區、共享庫
代碼放在哪：代碼區
變數放在哪：靜態變數放在靜態的變數區，區域變數會放在堆疊中
指標呢：指標也是有靜態的吧（小聲（不確定）），直接宣告的會放在堆疊中
指標指向的地址分配的空間呢，malloc的：放在堆中
演算法
做題吧，我先看看你之前做的什么題
求s1中包含s2中字符（不用考慮順序）的最小子串（長度最小） s1 = "abcedeabd" s2 = "abe"
思路
滑動視窗：
可以先找到第一個包含s2字符的字串，比如例子中的abce，然后往右移，把a提出去，找到右邊第一個提出去的a，這就是下一個子串，把所有子串找出來，再找最短的，
面：你這個會有問題，你先寫代碼吧，
#include <iostream> #include <unordered_map> #include <unordered_set> #include <vector> #include <string> using namespace std; int main() { unordered_map<char, int> um1, um2; unordered_set<char> us; string s1 = "abcedeabd"; string s2 = "abe"; vector<string> ans; int left, right; left = right = 0; int sum = 0; for (int i = 0; i < s2.length(); ++ i) { us.insert(s2[i]); um1[s2[i]] ++; sum ++; } string s; um2 = um1; int i = 0; while (i < s1.length() && um2[s1[i]] == 0) i ++; while (sum > 0) { if (um2[s1[i]]) { um2[s1[i]] --; sum --; } s += s1[i]; i ++; } ans.push_back(s); for (; i < s1.length(); ++ i) { char ch = s[0]; int cnt = 1; // 找到截取的地方 if (um1[s[0]] == 1) { while (us.find(s[cnt]) == us.end()) { // TODO } } while (s[cnt] ) s = s.strsub(1, s.length() -1); while () if (sum == 0){ ans.push_back(s); um2 = um1; } } cout << "Hello World!" << endl; }
（17分鐘后）
面：沒什么時間了，說說代碼吧
我：（對著代碼）先找到第一個符合條件的子串，然后移除掉第一個字符s[0]，這里需要把s中，非s2字符的其他字符也移除掉，這里就有問題了，如果后面的s[cnt]（已經是s[cnt] in s2了），正好是移除掉的s[0]，這里有兩種情況，如果s2中只有一個s[0]，那么這個時候right不用右移，如果s2有多個s[0]，則與其他字符做同樣的處理，感覺后面還有挺多要寫的，，，
面：還有更好的解法，你可以之后去想一想，
反問
問：推薦一本書
面：這種主觀的推薦我們是規定不能說的哈
問：上下班時間
面：10105.5，你們應該都知道
我：不同組也有差異吧哈哈
面：那你想要多呢還是少呢（笑）
以上都是面試程序中的回答，沒有加其他東西，也沒有修改錯誤，有錯誤的地方歡迎大家糾正！
三面沒過，換了個組繼續加面兩輪
文章來源：https://www.nowcoder.com/discuss/583059
如果你不知道如何讓自己在面試中脫穎而出，十多年編程經驗的大牛可以給你一點建議，進群還可以領取學習資料噢~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/240797.html
標籤：其他
下一篇：KVM虛擬化基礎