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

初面

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

二面

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

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

2019.3.28

Reeker

最新評論