簡歷是去年在騰訊招聘官網(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)比較熟悉，像紅黑樹這種就只了解概念和使用場景了……（我真坦率…）
  • 對(duì)STL了解嗎，STL是什么
  • 就是C++提供的一組比較高效的分別適用于各類場景的容器和容器適配器外加一組算法等等吧
  • 有那些容器
  • 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)于騰訊在市場導(dǎo)向方面的問題，其實(shí)也是因?yàn)閲鴥?nèi)和國外游戲市場的價(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í)（可見水平很菜了……），可能參考意義不大，我甚至都沒有測試過……

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

最新評(píng)論