字節(jié)跳動(dòng)2018校招算法方向第四批

《字節(jié)跳動(dòng)2018校招算法方向第四批》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

[問答題]題目描述以下函數(shù)用于將一顆二叉搜索樹轉(zhuǎn)換成一個(gè)有序的雙向鏈表。要求不能創(chuàng)建任何新的節(jié)點(diǎn)，只能調(diào)整樹種節(jié)點(diǎn)指針的指向。如輸入下圖中左邊的二叉搜索樹，則輸出轉(zhuǎn)換后的排序雙向鏈表：10/\614/\/\481216轉(zhuǎn)換成：4<=>6<=>8<=>10<=>12<=>14<=>16請(qǐng)指出程序代碼中錯(cuò)誤的地方（問題不止一處，請(qǐng)盡量找出所有你認(rèn)為錯(cuò)誤的地方）：1#include2usingnamespacestd;34structTreeNode{5intval;6TreeNode*left,*right;7};89TreeNode*Convert(TreeNode*root){10if(root==NULL)11returnroot;1213TreeNode*listHead=NULL;14TreeNode*listLastNode=NULL;15

116stacks;17while(root){18while(root){19root=root->left;20s.push(root);21}22root=s.top();23s.pop();24if(listHead==NULL){25listHead=root;26}else{27listLastNode->right=root;28}29listLastNode=root;30root=root->right;31}32returnlistHead;33}[問答題]題目描述對(duì)于廣告投放引擎，廣告庫索引服務(wù)是基礎(chǔ)服務(wù)，每次廣告請(qǐng)求會(huì)從廣告索引中找出匹配的廣告創(chuàng)意列表。假設(shè)每一次請(qǐng)求會(huì)攜帶地域、運(yùn)營(yíng)商、設(shè)備機(jī)型、網(wǎng)絡(luò)接入方式等信息，每個(gè)廣告策略都可以設(shè)置地域、運(yùn)營(yíng)商、設(shè)備機(jī)型、網(wǎng)絡(luò)接入方式的投放定向（即只能投放到定向匹配的請(qǐng)求，比如只投放特定地域）。每個(gè)廣告策略下包含N(N>=1)個(gè)廣告創(chuàng)意。設(shè)計(jì)一個(gè)廣告庫索引模塊，需要支持以下幾點(diǎn)：1.支持多線程廣告請(qǐng)求可以快速的找到匹配的所有廣告創(chuàng)意2.支持廣告庫數(shù)據(jù)的熱更新3.支持十萬級(jí)廣告策略，百萬級(jí)廣告創(chuàng)意4.支持高并發(fā)請(qǐng)求請(qǐng)給出廣告庫索引服務(wù)整體系統(tǒng)設(shè)計(jì)以及所使用到的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；

2[編程題]編程題1時(shí)間限制：2秒空間限制：65536K有三只球隊(duì)，每只球隊(duì)編號(hào)分別為球隊(duì)1，球隊(duì)2，球隊(duì)3，這三只球隊(duì)一共需要進(jìn)行n場(chǎng)比賽。現(xiàn)在已經(jīng)踢完了k場(chǎng)比賽，每場(chǎng)比賽不能打平，踢贏一場(chǎng)比賽得一分，輸了不得分不減分。已知球隊(duì)1和球隊(duì)2的比分相差d1分，球隊(duì)2和球隊(duì)3的比分相差d2分，每場(chǎng)比賽可以任意選擇兩只隊(duì)伍進(jìn)行。求如果打完最后的(n-k)場(chǎng)比賽，有沒有可能三只球隊(duì)的分?jǐn)?shù)打平。輸入描述:第一行包含一個(gè)數(shù)字t(1<=t<=10)接下來的t行每行包括四個(gè)數(shù)字n,k,d1,d2(1<=n<=10^12;0<=k<=n,0<=d1,d2<=k)輸出描述:每行的比分?jǐn)?shù)據(jù)，最終三只球隊(duì)若能夠打平，則輸出“yes”，否則輸出“no”輸入例子1:233003333輸出例子1:yes

3no例子說明1:case1:球隊(duì)1和球隊(duì)2差0分，球隊(duì)2和球隊(duì)3也差0分，所以可能的賽得分是三只球隊(duì)各得1分case2:球隊(duì)1和球隊(duì)2差3分，球隊(duì)2和球隊(duì)3差3分，所以可能的得分是球隊(duì)1得0分，球隊(duì)2得3分,球隊(duì)3得0分，比賽已經(jīng)全部結(jié)束因此最終不能打平。[編程題]編程題2時(shí)間限制：1秒空間限制：65536K有一個(gè)僅包含’a’和’b’兩種字符的字符串s，長(zhǎng)度為n，每次操作可以把一個(gè)字符做一次轉(zhuǎn)換（把一個(gè)’a’設(shè)置為’b’，或者把一個(gè)’b’置成’a’)；但是操作的次數(shù)有上限m，問在有限的操作數(shù)范圍內(nèi)，能夠得到最大連續(xù)的相同字符的子串的長(zhǎng)度是多少。輸入描述:第一行兩個(gè)整數(shù)n,m(1<=m<=n<=50000)，第二行為長(zhǎng)度為n且只包含’a’和’b’的字符串s。輸出描述:輸出在操作次數(shù)不超過m的情況下，能夠得到的最大連續(xù)全’a’子串或全’b’子串的長(zhǎng)度。輸入例子1:81aabaabaa

4輸出例子1:5例子說明1:把第一個(gè)'b'或者第二個(gè)'b'置成'a'，可得到長(zhǎng)度為5的全'a'子串。[編程題]附加題時(shí)間限制：1秒空間限制：65536K存在n+1個(gè)房間，每個(gè)房間依次為房間123...i，每個(gè)房間都存在一個(gè)傳送門，i房間的傳送門可以把人傳送到房間pi(1<=pi<=i),現(xiàn)在路人甲從房間1開始出發(fā)(當(dāng)前房間1即第一次訪問)，每次移動(dòng)他有兩種移動(dòng)策略：A.如果訪問過當(dāng)前房間i偶數(shù)次，那么下一次移動(dòng)到房間i+1；B.如果訪問過當(dāng)前房間i奇數(shù)次，那么移動(dòng)到房間pi；現(xiàn)在路人甲想知道移動(dòng)到房間n+1一共需要多少次移動(dòng)；輸入描述:第一行包括一個(gè)數(shù)字n(30%數(shù)據(jù)1<=n<=100，100%數(shù)據(jù)1<=n<=1000)，表示房間的數(shù)量，接下來一行存在n個(gè)數(shù)字pi(1<=pi<=i),pi表示從房間i可以傳送到房間pi。輸出描述:輸出一行數(shù)字，表示最終移動(dòng)的次數(shù)，最終結(jié)果需要對(duì)1000000007(10e9+7)取模。輸入例子1:

5212輸出例子1:4例子說明1:開始從房間1只訪問一次所以只能跳到p1即房間1，之后采用策略A跳到房間2，房間2這時(shí)訪問了一次因此采用策略B跳到房間2，之后采用策略A跳到房間3，因此到達(dá)房間3需要4步操作。