簡歷是去年在騰訊招聘官網(wǎng)投的，都快忘記這事了，前一周突然來了面試邀請(qǐng)。一共面了兩輪，都是電面，現(xiàn)在在等結(jié)果。這算是我人生第一次面試工作，還是蠻有意義的，趁著還有印象+錄了一部分音，趕緊過來記錄一下。

初面

• 【～1:50】開始是慣例的自我介紹，說了一下專業(yè)、成績、個(gè)人特點(diǎn)，（面試官表示GPA有點(diǎn)東西，卻不知我就這點(diǎn)東西… my vegetable explodes）
• 【～7:40】面試官提出讓我選一個(gè)有代表性的項(xiàng)目介紹一下。針對(duì)選的項(xiàng)目，展開問了挺多——遇到了什么問題，怎么處理的，配置方面，分工方面等等。因?yàn)樽鲞^的項(xiàng)目都是些中規(guī)中矩的項(xiàng)目，沒有什么很炫酷的技術(shù)，所以也沒什么波瀾
• 【～9:00】針對(duì)簡歷上提到做過的游戲，進(jìn)行了一些簡單的提問，使用的開發(fā)引擎，使用的開發(fā)語言，有沒有用過Lua等腳本語言，對(duì)Python的了解程度如何。我除了C++比較系統(tǒng)的學(xué)習(xí)過，其他的都說只是有一定的了解，能用的程度……（流下了沒技術(shù)的淚水.jpg）
• 【～16:00】面試官聽我對(duì)C++還比較自信，比較細(xì)致的考察了一下各方面基礎(chǔ)內(nèi)容，下面用問答形式給出大致過程。
  • C++11新特性有過了解嗎，說一下都有哪些吧
  • 一個(gè)是比較好用的關(guān)鍵字auto，¥@#&*%……
  • 經(jīng)常跟它一起出現(xiàn)的關(guān)鍵字是什么？
  • 應(yīng)該是decltype吧？
  • 對(duì)，那智能指針了解嗎？
  • 就是shared_ptr嗎？
  • 對(duì)，為什么要用到智能指針呢？
  • 避免在忘記delete和發(fā)生異常時(shí)造成資源釋放的問題，比普通指針安全性高一些……&¥#@%……
  • new/delete和malloc/free有什么區(qū)別
  • 前面這一對(duì)是C++提供的關(guān)鍵字，malloc和free是C提供的庫函數(shù)，前面這個(gè)在用來創(chuàng)建類對(duì)象的時(shí)候會(huì)自動(dòng)調(diào)用構(gòu)造函數(shù)，后面的要自己手動(dòng)計(jì)算需要分配的空間大?。#¥%&*……
  • （小聲地）嗯…不完全正確……那其他的一些新特性呢
  • 還有l(wèi)ambda表達(dá)式比較常用
  • 你一般在什么時(shí)候用lambda表達(dá)式呢
  • 主要是在寫比較函數(shù)的時(shí)候，一些比較簡單的比較函數(shù)如果只用一次，就不太適合專門寫一個(gè)具名函數(shù)，容易污染命名空間，而且可讀性也不會(huì)更高
  • 那lambda表達(dá)式有什么優(yōu)缺點(diǎn)呢
  • 優(yōu)點(diǎn)比較明顯，寫起來方便，不會(huì)污染命名空間等等，缺點(diǎn)就是如果函數(shù)比較復(fù)雜的時(shí)候可讀性會(huì)比較低（用的比較少，一時(shí)也想不出很典型的優(yōu)缺點(diǎn)…）
  • 用過強(qiáng)枚舉類型嗎
  • （我也是之后查了才知道這方面的內(nèi)容，當(dāng)時(shí)完全不知道這個(gè)，瞎猜可能是變體數(shù)據(jù)類型，菜哭）是variant嗎？
  • （些許的尷尬…）那應(yīng)該我們說的不是一個(gè)東西
  • const關(guān)鍵字你一般在什么情況下會(huì)用
  • 修飾函數(shù)參數(shù)或者函數(shù)本身，保證傳入對(duì)象或者調(diào)用對(duì)象本身不會(huì)被修改，很多時(shí)候也用來代替某些宏定義，因?yàn)楹瓴惶峁┚幾g檢查，不夠安全……
  • 對(duì)C++編譯連接過程了解嗎？（這里我重復(fù)了一下問題內(nèi)容，可能語氣顯得有點(diǎn)不確定）對(duì)，就是gcc連接器這一類的，比較概念性的東西。我就是簡單問一下看看你了解的程度。（我估計(jì)這應(yīng)該就是看看個(gè)人對(duì)一項(xiàng)技術(shù)研究的深度吧）
  • （我簡單答了一下CSAPP講的那一套流程，沒有太深入，不復(fù)述了，面試官的意思是了解到這個(gè)程度就差不多了，然而我心里明白要是說的很深入肯定能加分就是了…）
  • 構(gòu)造函數(shù)可以是虛函數(shù)嗎
  • 不可以，（虛函數(shù)表原理那一套）。不過如果一個(gè)類有虛函數(shù)，析構(gòu)函數(shù)最好是虛函數(shù)
  • 初始化列表有哪些應(yīng)用情景
  • （簡單說了一下，初始化列表和構(gòu)造函數(shù)體里的不同，其實(shí)不是很確定）
  • 那什么時(shí)候必須用初始化列表
  • 調(diào)用父類構(gòu)造函數(shù)和const的成員變量的時(shí)候吧…（不確定…）
• 【～40:00】下一步轉(zhuǎn)戰(zhàn)代碼，加了面試官Q(mào)Q，發(fā)來一個(gè)騰訊文檔。（如果有不了解這個(gè)的，其實(shí)就是云同步的word文檔，沒有任何提示功能，你的每個(gè)按鍵操作對(duì)面都能同步看到）寫代碼過程中，面試官?zèng)]有在聽電話，只是在看你寫代碼（這種方式真特容易緊張導(dǎo)致大腦空白…）
  • 面試官口述了題目，輸入一個(gè)日期和一個(gè)天數(shù)，返回這個(gè)天數(shù)之后的日期。
  • 當(dāng)時(shí)第一感覺根本不像是個(gè)算法題，考察的就是各種臨界情況，超麻煩…做的過程中發(fā)現(xiàn)自己連閏年怎么判斷都忘了，還問的面試官，然后閏年的英語也不會(huì)寫，用拼音寫的，慚愧…
  • 代碼就不貼了，最后的代碼臨界條件應(yīng)該處理的還可以，但是當(dāng)時(shí)實(shí)現(xiàn)的整體思路是按從年往下判斷，導(dǎo)致處理完還要往回判斷一趟，只能實(shí)現(xiàn)的算一般情況吧…
  • ∆第一次面試有點(diǎn)緊張，其實(shí)申完題目應(yīng)該先說一下自己的理解和思路，看面試官給的反饋再做調(diào)整，既能側(cè)面體現(xiàn)溝通理解能力，也可以借機(jī)避免一些錯(cuò)誤的思路。但我是寫了一會(huì)才想起這事，然后示意面試官說了一下思路，略尷尬…
• 【～42:00】寫完代碼又回過頭來詢問關(guān)于數(shù)據(jù)結(jié)構(gòu)方面的內(nèi)容
  • 對(duì)數(shù)據(jù)結(jié)構(gòu)方面了解嗎
  • 基本的數(shù)據(jù)結(jié)構(gòu)比較熟悉，像紅黑樹這種就只了解概念和使用場(chǎng)景了……（我真坦率…）
  • 對(duì)STL了解嗎，STL是什么
  • 就是C++提供的一組比較高效的分別適用于各類場(chǎng)景的容器和容器適配器外加一組算法等等吧
  • 有那些容器
  • list vector deque map set multixx，在C11之后還有unordered map和set那幾個(gè)
  • vector是怎樣擴(kuò)容的
  • vector維護(hù)一個(gè)capacity，如果當(dāng)前size到了這個(gè)capacity的時(shí)候，就在內(nèi)存中重新開辟一塊是原來兩倍大的連續(xù)空間，然后把之前的內(nèi)容易到這邊來……
• 【～45:00】算法數(shù)據(jù)結(jié)構(gòu)等等基礎(chǔ)的內(nèi)容就到這里，之后聊了一下關(guān)于游戲引擎等等崗位相關(guān)的內(nèi)容
  • 你對(duì)unity游戲引擎了解到什么程度
  • （卑微而羞愧地）我現(xiàn)在覺得，就是用過的水平……（再次菜哭）
  • 嗯…那MonoBehaviour的生命周期是怎樣的
  • （試探性瞎說）%@#¥@&*@……比較陌生了，印象中有這些
  • 碰撞器和觸發(fā)器什么區(qū)別
  • （繼續(xù)瞎說）
  • unity的垃圾回收你知道嗎
  • （直接放棄）
  • （面試官聽出了我這塊知道的很少，開始轉(zhuǎn)移話題）那矩陣運(yùn)算你了解嗎
  • 線代學(xué)過一些，還有點(diǎn)印象
  • 正交矩陣的逆矩陣怎么求
  • 我說我只記得一般矩陣通用的那種求逆過程了…
  • 面試官思索了一下，可能是發(fā)現(xiàn)我這幾個(gè)方面都太菜了，沒啥好問的了，表示今天就到這里吧……
• 【～48:00】最后給了提問環(huán)節(jié)，我問了一個(gè)關(guān)于騰訊在市場(chǎng)導(dǎo)向方面的問題，其實(shí)也是因?yàn)閲鴥?nèi)和國外游戲市場(chǎng)的價(jià)值觀差距太大了，一直也挺想了解的
• P.S. 面完感覺已經(jīng)涼了…除了C++好像沒有答得上來的，顯得學(xué)習(xí)領(lǐng)域很沒有廣度，但是面完過了一會(huì)一查居然狀態(tài)是復(fù)試了……就當(dāng)是人品了

二面

• 二面除了開始簡單的交流一下基本情況和意向之外，就是硬核的兩道算法題，不貼代碼了
  • 第一個(gè)：給一個(gè)長len的數(shù)組，讓你刪除里面最大的N個(gè)數(shù)，重復(fù)的數(shù)字算一個(gè)。len很大，N不大
    • 我的實(shí)現(xiàn)思路就是用一個(gè)最大堆，遍歷一遍數(shù)組，都扔到堆里。然后從堆頂拿數(shù)，每拿出一個(gè)，都把后面跟著的重復(fù)的刪掉，直到拿出N個(gè)數(shù)，然后遍歷一遍數(shù)組把符合的刪掉，把后面的往前挪
    • 面完之后自己反思了一下思路，又跟大佬交流了一下，有這么幾個(gè)問題，最基本的至少應(yīng)該倒著掃描，這樣不會(huì)重復(fù)挪很多次后面的部分，其次堆應(yīng)該大小夠用就行，畢竟len很長，等于多了一份拷貝，空間效率不夠高
  • 第二個(gè)：n個(gè)桶n個(gè)球，序號(hào)都是1～n，每個(gè)桶只能放一個(gè)球，放的球的序號(hào)跟桶的序號(hào)不能一樣，一共有多少種放的方式
    • 稍一思考就能發(fā)現(xiàn)是個(gè)數(shù)學(xué)問題，找到通項(xiàng)就能很簡單寫出遞歸，至于能不能再改成循環(huán)來提高效率再另說
    • 但是尷尬的是我腦回路跟正常人有點(diǎn)不一樣，所以我的遞歸思路有點(diǎn)偏門，還挺繞。剛開始代碼寫了一段時(shí)間之后，面試官打字提示我我的遞歸參數(shù)有個(gè)沒有意義。其實(shí)那個(gè)參數(shù)在我的思路里是有意義的，但是面試官以為我是正常人的遞歸思路，所以好心給了一個(gè)提示。卻不知道這個(gè)提示讓我非?；?，思路整個(gè)都有點(diǎn)亂了……好在之后花了幾分鐘冷靜下來，還是按照自己的思路寫通了。最后給面試官講了一下，他可能也沒聽過這種思路，所以還挺感興趣的，而且至少能證明我是獨(dú)立思考出來的……就結(jié)果來說也算是中規(guī)中矩了
• 二面完之后還給我留了一道題，可能是覺得我這兩道題做的還可以，想進(jìn)一步考察一下。
  • 題目是考官自己出的概念，叫格式化樹，反正我之后查是沒有查到相關(guān)概念了。具體的定義我也記不太清了，大概有這么幾點(diǎn)：格式化樹是用來輸出顯示的，是對(duì)普通的樹進(jìn)行一系列規(guī)整得到的，同一節(jié)點(diǎn)的子節(jié)點(diǎn)之間的距離要相同，父節(jié)點(diǎn)要在所有子節(jié)點(diǎn)的中間，相同深度的節(jié)點(diǎn)所在的高度要相同，要求整個(gè)樹所占面積盡量小。
  • 題目的需求不是特別明確，要求也很open，面試官的意思是盡量寫，當(dāng)天晚上之前把代碼發(fā)過去，什么程度不做要求。
  • 我根據(jù)自己的理解限制了一下需求，盡可能簡單，但還是只能做到局部最優(yōu)解，而且還采用了暴力枚舉等等效率比較低的做法……只能說這類題目上下限確實(shí)很高，跟OJ那些有明確解和思路的算法題不一樣，還是需要以后重點(diǎn)關(guān)注一下的
  • 貼一下代碼吧，大概寫了4個(gè)小時(shí)（可見水平很菜了……），可能參考意義不大，我甚至都沒有測(cè)試過……

typedef struct {
	int id;
	//other data...
	vector<Node*> children; //the order of the sub nodes is exactly the shown order in picture
} Node;

class Tree {
private:
	Node* root;
	void format();
	//other functions...
};

/*
* this implementation can only find local optimal solutions, assuming each step has no aftereffect (actually not)
* format the tree from the lowest level
* for each node, mapping to a deque,  which stores a pair of displacements relative to the node for the most left and right sub nodes for each sub level
* after formating all sub nodes of a node, use brutal force to compute the possible minimal gap with the deques of the sub nodes
* during the process, maintain the optimal permutation, after enumerate all the cases, compute the deque of the current node
* suppose :
* 1. nodes with the same depth must have the same y
* 2. the sub nodes of different nodes cannot be interlaced 
* 3. the distance of every two sub nodes  of a single node must be the same
*/
void Tree::format()
{
	if (root == nullptr)
		return;

	//post order traversal of the tree
	stack< pair<Node*, int> > stackOfNodes; //int element is used to record the times of encountering the node
	unordered_map<Node*, deque<pair<int, int>>> subLevelDis; //the pair of two ints records the left and the right displacement * 2 of the level relative to its parent
	stackOfNodes.push(make_pair(root, 1));
	while (!stackOfNodes.empty())
	{
		Node* curNode = stackOfNodes.top().first;
		int cnt = stackOfNodes.top().second;
		switch (cnt)
		{
		case 1:
			//the sub nodes of the current node havent been formatted yet
			stackOfNodes.top().second = 2;
			//push the sub nodes to stack in the reverse node such that the first child is on the top
			for (auto it = curNode->children.rbegin(); it != curNode->children.rend(); ++it)
			{
				stackOfNodes.push(make_pair(*it, 1));
			}
			break; //end case1
		case 2:
			//the sub nodes of the current node have been formatted
			stackOfNodes.pop();
			//format the order of sub nodes of the current node
			vector<Node*>& childrens = curNode->children;
			if (!childrens.empty())
			{
				int cntOfChildren = childrens.size();
				vector<int> permutation(cntOfChildren); //the permutation of the index of the sub nodes
				for (int i = 0; i < cntOfChildren; ++i)
					permutation[i] = i;
				int minMaxGap = INT_MAX;
				vector<int> minMaxPermutation(cntOfChildren);
				//use brutal force to check each permutation
				//for each permutation, find the max gap
				do
				{
					int maxGap = 0;
					//compute the gap between each two adjacent node
					for (int i = 0; i < cntOfChildren - 1; ++i)
					{
						int tempMaxGap = 0;
						auto& deque1 = subLevelDis[childrens[permutation[i]]];
						auto& deque2 = subLevelDis[childrens[permutation[i+1]]];
						int minLen = min(deque1.size(), deque2.size());
						auto it1 = deque1.begin(), it2 = deque2.begin();
						for (int i = 0; i < minLen; ++i, ++it1, ++it2)
						{
							tempMaxGap = it1->second - it2->first;
							maxGap = max(maxGap, tempMaxGap);
						}
					}

					if (maxGap < minMaxGap)
					{
						minMaxGap = maxGap;
						minMaxPermutation.assign(permutation.begin(), permutation.end());
					}

				} while (next_permutation(permutation.begin(), permutation.end()));

				//reorder the subnodes according to the indice in minMaxPermutation
				vector<Node*> tempChildrens(childrens.begin(), childrens.end());
				for (int i = 0; i < cntOfChildren; ++i)
				{
					childrens[i] = tempChildrens[minMaxPermutation[i]];
				}

				//compute the level displacements of the current node and bind to the node
				vector<int> maxLens(cntOfChildren);
				int maxLen = 0;
				for (int i = 0; i < cntOfChildren; ++i)
				{
					maxLens[i] = subLevelDis[childrens[i]].size();
					maxLen = max(maxLen, maxLens[i]);
				}
				//for each level, find the index of the most left and right node, then compute the displacement
				deque<pair<int, int>> dis;
				//if all the sub nodes of current node 
				if (dis.empty())
					dis.push_back(make_pair(-cntOfChildren * minMaxGap, cntOfChildren * minMaxGap));
				//otherwise
				for (int i = 0; i < maxLen; ++i)
				{
					int left = 0, right = cntOfChildren;
					while (maxLens[left] < i)
						++left;
					while (maxLens[right] < i)
						--right;
					int leftDis = subLevelDis[childrens[left]][i].first * 2 + (left * 2 - cntOfChildren) * minMaxGap;
					int rightDis = subLevelDis[childrens[right]][i].second * 2 + (right * 2 - cntOfChildren) * minMaxGap;
					dis.push_back(make_pair(leftDis, rightDis));
				}
				subLevelDis[curNode] = dis;

				//free the memory space for level displacements of the sub nodes
				for (int i = 0; i < cntOfChildren; ++i)
					subLevelDis.erase(childrens[i]);
			}
			break; //end case2
		} //end switch
	}
}

后記

• 盡管到現(xiàn)在還沒有出結(jié)果，但是面試過程中暴露的問題已經(jīng)足夠有意義了。下一步，大方向上還是按照自己原本規(guī)劃的推進(jìn)，具體執(zhí)行過程就需要根據(jù)這些問題加以側(cè)重了。
• 這學(xué)期到現(xiàn)在為止都沒有投過簡歷了，大四之前可能也不再投了，先看看這次面試的結(jié)果吧。
• 愿大家都能拿到喜歡的學(xué)?；蚬镜腛ffer！

2019.3.28

Reeker