Hulu2022校招 | 笔试真题及解法揭秘
2022秋季校招
筆試真題+解析
Hulu2022校招筆試順利結(jié)束
無(wú)論你是直通面試
還是遺憾止步筆試環(huán)節(jié)
希望你們都能從中有所收獲
這不，Hulu大方地把真題分享給大家
并附上大佬們的詳細(xì)解析
Let's check it out～
第一題：天使粒子
問(wèn)題描述：
在一個(gè)線性管道里有一組粒子，它們位置互不重合，有著相同的運(yùn)動(dòng)速度，但有些粒子只能向左移動(dòng)，有些粒子只能向右移動(dòng)。這些粒子可以相互穿過(guò)且不會(huì)干擾粒子的運(yùn)動(dòng)（意味著粒子在同一時(shí)刻可以重合），因此所有粒子都會(huì)相對(duì)較快地離開(kāi)管道。
現(xiàn)在我們將給定一組粒子，包含它們的類型和在管道中初始的位置，同時(shí)我們將給定粒子的運(yùn)動(dòng)速度，我們希望獲得一個(gè)例子運(yùn)動(dòng)過(guò)程的動(dòng)畫(huà)。具體來(lái)說(shuō)，在每個(gè)時(shí)間點(diǎn)我們都需要輸出一個(gè)字符串，表示當(dāng)前管道中粒子所占的位置
輸入描述：
輸入分為兩行：
第一行為一個(gè)整數(shù)v，代表粒子的速度。
第二行為一個(gè)字符串s，代表時(shí)刻0時(shí)管道中粒子的狀態(tài)，其中只可能有三種字符'L', 'R', '.'
'L'代表一個(gè)會(huì)向左移動(dòng)的粒子；
'R'代表一個(gè)會(huì)向右移動(dòng)的粒子；
'.'代表這個(gè)位置現(xiàn)在沒(méi)有粒子。
1 <= v <= 10, 1 <= s的長(zhǎng)度 <= 50
輸出描述：
輸出為若干行，每行都是一個(gè)字符串，第一行字符串代表時(shí)刻0時(shí)管道中粒子所占的位置，第二行字符串代表時(shí)刻1時(shí)管道中粒子所占的位置，以此類推。
輸出的字符串只能包含兩種字符'X'和'.'
其中'X'代表這個(gè)位置有粒子(可以有多個(gè)粒子)；
'.'代表這個(gè)位置沒(méi)有粒子。
輸出的最后一行是一個(gè)全部由'.'構(gòu)成的字符串，
代表此時(shí)刻粒子已經(jīng)全部離開(kāi)了管道，輸出結(jié)束。
輸入樣例：
2
..R....
輸出樣例：
..X....
....X..
......X
.......
提示：
輸入樣例中有一個(gè)向右移動(dòng)，速度為2，初始位置在管道左數(shù)第3個(gè)位置的粒子。之后移動(dòng)到了第5、第7個(gè)位置，最后移動(dòng)出管道，輸出結(jié)束。
更復(fù)雜的輸入會(huì)像這樣：
4
RRL..LR..L.
題目解答：
這道題是一道比較簡(jiǎn)單的模擬題，解題思路比較直觀。
我們可以構(gòu)造一個(gè)粒子類Particle，并開(kāi)一個(gè)數(shù)組存儲(chǔ)題目給定的粒子。
Class Particle {int position; // 存儲(chǔ)粒子當(dāng)前的位置，可以為負(fù)數(shù)
int direction; // 存儲(chǔ)粒子的運(yùn)動(dòng)方向，1代表向右移動(dòng)，-1代表向左移動(dòng)}
然后維護(hù)一個(gè)boolean類型的數(shù)組hasParticle[n]，存儲(chǔ)每個(gè)位置是否有粒子。對(duì)于某一時(shí)間點(diǎn)，我們首先把boolean數(shù)組全初始化為false。假設(shè)速度為v，則每個(gè)時(shí)間點(diǎn)我們都可以模擬粒子的運(yùn)動(dòng)，更新粒子的位置（position = position + direction * v），并且如果position在數(shù)組hasParticle下標(biāo)內(nèi)的話，更新一下hasParticle[position] = true。最后根據(jù)數(shù)組hasParticle的值輸出（false就輸出‘.’，true就輸出’X’），如果沒(méi)有粒子在范圍內(nèi)了就終止程序。
偽代碼：
Class Particle?
{int position;
int direction;}
List<Particle>particles=initialize particles
List<Boolean>hasParticles=initialize array with particles.size
int v = initialize speed
while(true)?
{for each hasParticle, hasParticle = false
for each particle, if 0 <= position < hasParticles.
size, hasParticles[position] = true
print one line by hasParticles
if all hasParticles are false, return
for each particle, position = position + direction * v}
第二題：人間“雨人”
問(wèn)題描述：
傳說(shuō)中 Hulu 有位 Hulugan 被譽(yù)為「Hulu 雨人」，Ta 有著驚人的數(shù)字能力，可以秒算出指定范圍內(nèi)符合某些常見(jiàn)性質(zhì)的數(shù)的個(gè)數(shù)。
可是，時(shí)代變了，現(xiàn)在是信息時(shí)代，為什么不問(wèn)問(wèn)神奇的計(jì)算機(jī)呢？
Sophie 定義，如果一個(gè)數(shù)的每一位之和模 N 為 0，則稱它為 Sophie-N 數(shù)。
現(xiàn)在 Sophie 想讓你設(shè)計(jì)一個(gè)程序，可以快速計(jì)算出整數(shù)閉區(qū)間 [A, B] 的 Sophie-N 數(shù)的個(gè)數(shù)。
輸入描述：
三個(gè)正整數(shù) N、A、B
輸出描述：
一個(gè)整數(shù)，代表整數(shù)閉區(qū)間 [A, B] 的 Sophie-N 數(shù)的個(gè)數(shù)
輸入樣例：
62 19260817 20210817
輸出樣例：
21
提示：
對(duì)于 10% 的數(shù)據(jù)，1 ≤ N ≤ 100，1 ≤ A ≤ B ≤ 108
對(duì)于 30% 的數(shù)據(jù)，1 ≤ N ≤ 100，1 ≤ A ≤ B ≤ 109
對(duì)于 60% 的數(shù)據(jù)，1 ≤ N ≤ 100，1 ≤ A ≤ B ≤ 1010
對(duì)于 100% 的數(shù)據(jù)，1 ≤ N ≤ 100，1 ≤ A ≤ B ≤ 1011
題目解答：
可以想到計(jì)算 [A, B] 區(qū)間的 Sophie-N 數(shù)的個(gè)數(shù)可以轉(zhuǎn)換成計(jì)算 [1, B] 區(qū)間 - [1, A - 1] 區(qū)間中 Sophie-N 數(shù)的個(gè)數(shù)。
所以問(wèn)題可以抽象成如何寫(xiě)出函數(shù) f(m)，函數(shù) f(m) 代表計(jì)算 [1, m] 區(qū)間 Sophie-N 數(shù)的個(gè)數(shù)，由于 m 數(shù)字大小可以高達(dá) 1e11，我們可以自然地想到按位進(jìn)行計(jì)算，即數(shù)位 DP。
令 f[i][j] 表示不超過(guò) m 的情況下，前 i 位數(shù)的和模 N 為 j 的數(shù)的個(gè)數(shù)，從 0 到 9 枚舉第 i 位數(shù) cur，則：f[i][j] = sum(f[i - 1][((j - cur) % N + N) % N])。
進(jìn)行狀態(tài)轉(zhuǎn)移即可，時(shí)間復(fù)雜度 O(NlogB)，空間復(fù)雜度 O(NlogB)。
第三題：輕松職場(chǎng)
問(wèn)題描述：
Hulu準(zhǔn)備在辦公室的某一個(gè)區(qū)域內(nèi)舉辦一個(gè)大型活動(dòng)，舉辦活動(dòng)的設(shè)想之一就是希望找到一個(gè)區(qū)域讓大家最方便到達(dá)。
Hulu辦公室的布局非常簡(jiǎn)單高效。辦公室存在N個(gè)區(qū)域（編號(hào)從1到N），區(qū)域里原本坐著一些組包含一定數(shù)量的人。辦公室布局總共有N-1條道路方便相互通行，每條道路連接兩個(gè)不同的區(qū)域，區(qū)域之間最多存在一條道路。布局還能保證兩兩區(qū)域之間都能相互到達(dá)，并且有且僅有一條路徑，任何區(qū)域均可以被選擇為活動(dòng)點(diǎn)。
那么我們需要你幫助Hulu設(shè)計(jì)一個(gè)算法，為Hulu找到一個(gè)最便捷的活動(dòng)點(diǎn)，并輸出它的代價(jià)。我們定義代價(jià)為所有人到達(dá)活動(dòng)點(diǎn)的距離的總和，那么你找到的活動(dòng)點(diǎn)即為所有區(qū)域中代價(jià)最小的區(qū)域。
如果存在多個(gè)選擇，任意一個(gè)均可。
輸入描述：
第1行: 一個(gè)整數(shù)N?
第2 .. N+1行: 對(duì)于每個(gè)第i+1行, 一個(gè)整數(shù) Zi 表示編號(hào)為i的區(qū)域的人數(shù)
接下來(lái)N-1行: 對(duì)于每一行，三個(gè)整數(shù)A, B, C （以空格隔開(kāi)）表示區(qū)域A到區(qū)域B有一條長(zhǎng)為C的道路
(1<=N<=100,000，0<=Zi<=1000，1<=Ai,Bi<=N, 1<=Ci<=1000)
輸出描述：
一個(gè)整數(shù)，表示最小可能的代價(jià)
輸入樣例：
5
1
1
0
0
2
1 3 1
4 3 3
3 2 2
4 5 3
輸出樣例：
15
題目解答：
閱讀題目時(shí)我們很容易分析出這是在一張圖里找一個(gè)中心點(diǎn)，所有點(diǎn)到它的加權(quán)距離和最小。
那么一個(gè)樸素的算法則是：
-計(jì)算兩兩頂點(diǎn)之間最短路（頂點(diǎn)i，j之間的路徑長(zhǎng)度，不妨記為Di,j)
-枚舉每個(gè)活動(dòng)點(diǎn)，計(jì)算代價(jià)
-輸出其中最小值。
也即：
題目條件隱藏了一個(gè)要點(diǎn)：布局本質(zhì)上是一棵樹(shù)（雖然我們可以自定義其根）。相互到達(dá)表示連通圖，無(wú)重邊且邊數(shù)為頂點(diǎn)個(gè)數(shù)減一將圖降級(jí)為樹(shù)。這樣能簡(jiǎn)化一些最短路的計(jì)算，但是并沒(méi)有降低求代價(jià)的復(fù)雜度。這也是優(yōu)化的重點(diǎn)。
我們考慮已經(jīng)計(jì)算完成了以頂點(diǎn)x為活動(dòng)點(diǎn)的代價(jià)（記為Fx），相鄰的頂點(diǎn)y的代價(jià) Fy 如何利用這次計(jì)算的結(jié)果：
我們以Ex,y 作為分界，將圖分成兩個(gè)子樹(shù)，不難看出，Fx和Fy的差值即轉(zhuǎn)移活動(dòng)點(diǎn)后，左側(cè)子樹(shù)所有的人要多走Dx,y的距離，而右側(cè)子樹(shù)的人要少走Dx,y的距離：
雖然求代價(jià)變得簡(jiǎn)單了，但是求子樹(shù)總?cè)藬?shù)變得棘手起來(lái)，因?yàn)樗苤朴谵D(zhuǎn)移的方向（從哪個(gè)相鄰的頂點(diǎn)轉(zhuǎn)移到此頂點(diǎn)）。如果每次遍歷到再計(jì)算，時(shí)間復(fù)雜度并不會(huì)優(yōu)化太多。這時(shí)候樹(shù)的結(jié)構(gòu)優(yōu)勢(shì)便體現(xiàn)出來(lái)。我們不妨約定遍歷的順序?yàn)閺母饺~，即頂點(diǎn)x為頂點(diǎn)y的雙親，再加上我們知道總?cè)藬?shù)：
所以，
也就僅僅需要知道子樹(shù)的總?cè)藬?shù)即可。
那么題目的算法則變成：
-約定圖中某個(gè)頂點(diǎn)為根，利用DFS遍歷圖，在回溯過(guò)程中：
? ? ? ? ?-求得每個(gè)子樹(shù)的總?cè)藬?shù)；
? ? ? ? ?-求得以根為活動(dòng)點(diǎn)的代價(jià)；
-代價(jià)計(jì)為當(dāng)前最小值，從根往葉子節(jié)點(diǎn)開(kāi)始遍歷（BFS 或 DFS）
-每遍歷到一個(gè)頂點(diǎn)，利用其雙親的代價(jià)，帶入上述公式，求得自己的代價(jià)；
-每次遍歷更新當(dāng)前最小值
-輸出最小值
這樣時(shí)間復(fù)雜度和空間復(fù)雜度均為線性，能夠完全勝任題目的數(shù)據(jù)范圍。另外值得一提的是，拋去平凡的邊界情況，數(shù)據(jù)說(shuō)明了有些區(qū)域人數(shù)可能為0，所以有一些情況是有一點(diǎn)優(yōu)化空間的。比如，在數(shù)據(jù)規(guī)模達(dá)到上限的情況下，僅有一個(gè)區(qū)域有人和僅有兩個(gè)區(qū)域有人。
第四題：魔鬼迷宮
問(wèn)題描述：
有一個(gè)矩形迷宮，包含m行和n列，可以用一個(gè)二維字符數(shù)組來(lái)表示這個(gè)迷宮，數(shù)組的每個(gè)元素可以是這些字符之一：'0' / '1' / '2' / 's' / 'e' / 'd'. (只會(huì)有一個(gè) 's', 一個(gè) 'e', 和一個(gè) 'd')
'0' 表示空，你可以達(dá)到這個(gè)位置；
'1' 表示這是一個(gè)惡魔士兵，你和魔鬼都不能到達(dá)這個(gè)位置，但是魔鬼可以穿過(guò)這個(gè)位置而你不行；
'2' 表示這是一個(gè)己方士兵，你和魔鬼都不能到達(dá)這個(gè)位置，但是你可以穿過(guò)這個(gè)位置而魔鬼不行；
's' 表示迷宮唯一的起點(diǎn)；
'e' 表示迷宮唯一的終點(diǎn)；
'd' 表示這里有一個(gè)魔鬼并且它足夠聰明
(魔鬼會(huì)盡可能的阻止你穿越迷宮)。
你需要從起點(diǎn)開(kāi)始，想辦法到達(dá)終點(diǎn)，但是魔鬼也是可以移動(dòng)的（雙方士兵不能移動(dòng)），你每次移動(dòng)一次之后，魔鬼都可以移動(dòng)一次，你和魔鬼輪流移動(dòng)，從你先開(kāi)始。
如何定義一次移動(dòng)：每次移動(dòng)只能選一個(gè)方向或者可以選擇不移動(dòng)。你每次可以往上下左右四個(gè)方向走s1步（0<=s1<=yourSteps）, 魔鬼每次可以往上下左右四個(gè)方向走s2步（0<=s2<=devilSteps），相鄰的兩個(gè)格子定義為1步的距離，你雖然不能穿過(guò)魔鬼士兵，但是你可以穿過(guò)魔鬼，但是如果你和魔鬼在同一點(diǎn)（包括終點(diǎn)）你就會(huì)被魔鬼抓住。
在移動(dòng)次數(shù)小于1000的情況下，請(qǐng)問(wèn)你能不能走出迷宮（走到終點(diǎn)）并且不被魔鬼抓住，輸出你從起點(diǎn)到終點(diǎn)需要移動(dòng)的次數(shù) （不能走出迷宮或者被魔鬼抓住都輸出-1）
Constraints:
0 < m < 10
0 < n < 10
0 < yourSteps < 10
0 < devilSteps < 10
輸入描述：
第1行：yourSteps,你每次移動(dòng)最多可以走多少步；
第2行：devilSteps,魔鬼每次移動(dòng)最多可以走多少步；
第3行：m,迷宮有多少行 (每行的長(zhǎng)度相等)；
第4 ~ m+3行：迷宮數(shù)組的每一行，包含n個(gè)字符
輸出描述：
在移動(dòng)次數(shù)小于1000的情況下，你至少需要移動(dòng)多少次才能走出迷宮（從起點(diǎn)到終點(diǎn)），不能走出迷宮或者被魔鬼抓住都輸出-1
輸入樣例：
3
2
5
0s000
00100
10001
d0200
0002e
輸出樣例：
4
題目解答：
其實(shí)這題乍一看是一個(gè)BFS搜索，但是唯一的問(wèn)題是你如果移動(dòng)的步子足夠大是可以跨過(guò)魔鬼移動(dòng)到一個(gè)新的位置，這種情況下BFS是處理不了的。
考慮到這個(gè)迷宮本身的狀態(tài)信息（士兵、出口）不會(huì)發(fā)生變化，唯一有變化的是你的位置和魔鬼的位置，所以可以考慮用DFS來(lái)模擬雙方的每一次移動(dòng)，為了避免重復(fù)計(jì)算（可能不同的移動(dòng)步驟可以達(dá)到相同的狀態(tài)）可以添加一個(gè)全局的緩存，緩存的key就是你的位置和魔鬼的位置。但是有一點(diǎn)需要考慮的是DFS如果迭代的太深了可能會(huì)超時(shí)，雖然題目里邊給的是移動(dòng)次數(shù)1000以內(nèi)能否走出迷宮，但是其實(shí)最壞的情況可能也用不了1000次，其實(shí)你和魔鬼的移動(dòng)次數(shù)加起來(lái)最多不超多92次，你如果能贏，92次之內(nèi)就能贏，所以可以限制DFS迭代的深度最多92次。
迭代的過(guò)程不能剪枝，因?yàn)槟阈枰玫阶钌俚囊苿?dòng)次數(shù)走出迷宮，魔鬼就算是輸，也會(huì)讓你已更多的移動(dòng)次數(shù)來(lái)贏。
魔鬼可以選擇不移動(dòng)，但是你必須得選擇移動(dòng)。（不然肯定就走不到出口了）
有些情況是你可以比魔鬼率先到達(dá)出口并且不用跨過(guò)魔鬼移動(dòng)，這些都可以用BFS來(lái)做一個(gè)優(yōu)化，畢竟DFS時(shí)間長(zhǎng)。
DFS pseudo-code
第五題：地獄三角形
問(wèn)題描述：
在直角坐標(biāo)系的 Y 軸上有兩個(gè)點(diǎn) A(0,1) B(0,-1)，記為底邊 AB。在第一和第四象限分布著 N 個(gè)點(diǎn)C1,C2,...,Cn.這 N+2 個(gè)點(diǎn)沒(méi)有任何三點(diǎn)共線，需要從 N 個(gè)點(diǎn)中選出最多的點(diǎn),使得他們作為頂點(diǎn)和 AB底邊構(gòu)成的三角形共 AB 這個(gè)底邊并且相互只包含,不相交。(相交的定義為兩個(gè)三角形的另外兩邊都不相交)
輸出被選出的點(diǎn)的集合的大小
如圖中,三角形 ABC3,ABC1,ABC4,ABC5 相互只包含不相交，而三角形 ABC1 與 ABC2 相交，三角形 ABC6 與其他每一個(gè)三角形都相交。
輸入描述：
第一行是一個(gè)整數(shù) N
第二行是 2N? 個(gè)用空格分隔的高精度浮點(diǎn)數(shù),表示每個(gè)點(diǎn)的橫坐標(biāo)和縱坐標(biāo)
輸出描述：
輸出被選出的點(diǎn)的集合的大小
輸入樣例：
6
1 0.2 1.6 -0.6 0.6 0 2 -0.2 3 -0.5 0.2 1.05
輸出樣例：
4
題目解答：
將 N個(gè)頂點(diǎn)按照 ACi的斜率從小到大排序, 得到 N 個(gè)頂點(diǎn)的一個(gè)序列。如樣例的數(shù)據(jù),會(huì)得到 C3,C2,C1,C4,C5,C6; 然后按 BCi 的斜率從大到小排序,得到序列C6,C3,C1,C4,C2,C5。任意兩個(gè)點(diǎn) Ci Cj,如果在兩個(gè)序列中出現(xiàn)的順序相同,那么以他們?yōu)轫旤c(diǎn)構(gòu)成的三角形相互包含;如果順序不同,那么三角形相交。
所以這兩個(gè)序列的最大公共子序列(以樣例為例,最大公共子序列為C3,C1,C4,C5)即為最大的 N 個(gè)頂點(diǎn)的子集。
怎樣以 O(n^2)時(shí)間求最長(zhǎng)公共子序列,不在這里詳述了,不知道怎么做的同學(xué)可以搜索相關(guān)資料。
最長(zhǎng)公共子序列的時(shí)間復(fù)雜度為 O(n^2),但是這道題要拿到滿分,需要的時(shí)間復(fù)雜度為 O(nlogn)。實(shí)際上如果兩個(gè)序列中有一個(gè)序列中每個(gè)元素都只出現(xiàn)了一次,那么這個(gè)最長(zhǎng)公共子序列問(wèn)題可以轉(zhuǎn)換成最長(zhǎng)遞增子序列問(wèn)題,而最長(zhǎng)遞增子序列問(wèn)題有 O(nlogn)時(shí)間復(fù)雜度的實(shí)現(xiàn)。
轉(zhuǎn)換的方法為:首先選每個(gè)元素都只出現(xiàn)了一次的序列,以這個(gè)序列里元素出現(xiàn)的順序?qū)γ總€(gè)元素從 1 到 n 編號(hào)，然后對(duì)第二個(gè)序列把每個(gè)元素轉(zhuǎn)變成對(duì)應(yīng)的編號(hào)。
(樣例中C3,C2,C1,C4,C5,C6依次編號(hào)為 1,2,3,4,5,6。那么C6,C3,C1,C4,C2,C5可以轉(zhuǎn)化為 6,1,3,4,2,5) 然后對(duì)這個(gè)編號(hào)后的序列求最長(zhǎng)遞增子序列,該子序列對(duì)應(yīng)的元素即為原來(lái)兩序列的最長(zhǎng)公共子序列。(1,3,4,5 為最長(zhǎng)遞增子序列,對(duì)應(yīng)回元素即為 C3,C1,C4,C5)。
為什么重新編號(hào)后的序列的最長(zhǎng)遞增子序列即為原來(lái)兩序列的最長(zhǎng)公共子序列?原因也很簡(jiǎn)單，重新編號(hào)實(shí)際上保留了第一個(gè)序列的順序信息,對(duì)第二個(gè)序列做編號(hào)的轉(zhuǎn)換后,新序列里的所有遞增子序列描述了原來(lái)兩個(gè)序列的所有公共子序列，所以最長(zhǎng)的那個(gè)遞增子序列即為所求。
怎樣以 O(nlogn)時(shí)間求最長(zhǎng)遞增子序列,不在這里詳述了,不知道怎么做的同學(xué)可以搜索相關(guān)資料。
另外,這道題特意將A和B點(diǎn)放在了y軸上,這樣是為了簡(jiǎn)化代碼實(shí)現(xiàn)難度,有筆試者可能上過(guò)鄧?yán)蠋煹挠?jì)算幾何課程,或者有一定的計(jì)算幾何基礎(chǔ),實(shí)現(xiàn)了一個(gè)toLeft測(cè)試函數(shù),在這道題目上實(shí)際上是不需要的。
長(zhǎng)按關(guān)注Hulu
了解更多校招動(dòng)態(tài)
總結(jié)
以上是生活随笔為你收集整理的Hulu2022校招 | 笔试真题及解法揭秘的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： hulu面试经验
- 下一篇： 国外常用免费博客平台