# 字節跳動的算法面試題是什么難度?
# 字節跳動的算法面試題是什么難度?
由于 lucifer 我是一個小前端, 最近也在準備寫一個《前端如何搞定算法面試》的專欄,因此最近沒少看各大公司的面試題。都說字節跳動算法題比較難,我就先拿 ta 下手,做了幾套 。這次我們就拿一套 `2018 年的前端校招(第四批)`來看下字節的算法筆試題的難度幾何。地址:<https://www.nowcoder.com/test/8536639/summary>
> 實際上,這套字節的前端崗位筆試題和后端以及算法崗位的筆試題也只有一道題目(紅包的設計題被換成了另外一個設計題)不一樣而已,因此也不需要擔心你不是前端,題目類型和難度和你的崗位不匹配。
這套題一共四道題, 兩道問答題, 兩道編程題。
其中一道問答題是 LeetCode 426 的原題,只不過題型變成了找茬(改錯)。可惜的是 LeetCode 的 426 題是一個會員題目,沒有會員的就看不來了。不過,劍指 Offer 正好也有這個題,并且力扣將劍指 Offer 全部的題目都 OJ 化了。 這道題大家可以去 <https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof> 提交答案。簡單說一下這個題目的思路,我們只需要中序遍歷即可得到一個有序的數列,同時在中序遍歷過程中將 pre 和 cur 節點通過指針串起來即可。
另一個問答是紅包題目,這里不多說了。我們重點看一下剩下兩個算法編程題。

> 兩個問答題由于不能在線判題,我沒有做,只做了剩下兩個編程題。
## 球隊比賽
第一個編程題是一個球隊比賽的題目。
### 題目描述
有三只球隊,每只球隊編號分別為球隊 1,球隊 2,球隊 3,這三只球隊一共需要進行 n 場比賽。現在已經踢完了 k 場比賽,每場比賽不能打平,踢贏一場比賽得一分,輸了不得分不減分。已知球隊 1 和球隊 2 的比分相差 d1 分,球隊 2 和球隊 3 的比分相差 d2 分,每場比賽可以任意選擇兩只隊伍進行。求如果打完最后的 (n-k) 場比賽,有沒有可能三只球隊的分數打平。
### 思路
假設球隊 1,球隊 2,球隊 3 此時的勝利次數分別為 a,b,c,球隊 1,球隊 2,球隊 3 總的勝利次數分別為 n1,n2,n3。
我一開始的想法是只要保證 n1,n2,n3 相等且都小于等于 n / 3 即可。如果題目給了 n1,n2,n3 的值就直接:
```
<pre class="calibre18">```
print(n1 == n2 == n3 == n / 3)
```
```
可是不僅 n1,n2,n3 沒給, a,b,c 也沒有給。
實際上此時我們的信息僅僅是:
```
<pre class="calibre18">```
① a + b + c = k
② a - b = d1 or b - a = d1
③ b - c = d2 or c - b = d2
```
```
其中 k 和 d1,d2 是已知的。a ,b,c 是未知的。 也就是說我們需要枚舉所有的 a,b,c 可能性,解方程求出合法的 a,b,c,并且 合法的 a,b,c 都小于等于 n / 3 即可。
> 這個 a,b,c 的求解數學方程就是中學數學難度, 三個等式化簡一下即可,具體見下方代碼區域。
- a 只需要再次贏得 n / 3 - a 次
- b 只需要再次贏得 n / 3 - b 次
- c 只需要再次贏得 n / 3 - c 次
```
<pre class="calibre18">```
n1 = a + n / 3 - a = n / 3
n2 = b + (n / 3 - b) = n / 3
n3 = c + (n / 3 - c) = n / 3
```
```
### 代碼(Python)
> 牛客有點讓人不爽, 需要 print 而不是 return
```
<pre class="calibre18">```
t = int(input())
<span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(t):
n, k, d1, d2 = map(int, input().split(<span class="hljs-string">" "</span>))
<span class="hljs-keyword">if</span> n % <span class="hljs-params">3</span> != <span class="hljs-params">0</span>:
print(<span class="hljs-string">'no'</span>)
<span class="hljs-keyword">continue</span>
abcs = []
<span class="hljs-keyword">for</span> r1 <span class="hljs-keyword">in</span> [<span class="hljs-params">-1</span>, <span class="hljs-params">1</span>]:
<span class="hljs-keyword">for</span> r2 <span class="hljs-keyword">in</span> [<span class="hljs-params">-1</span>, <span class="hljs-params">1</span>]:
a = (k + <span class="hljs-params">2</span> * r1 * d1 + r2 * d2) / <span class="hljs-params">3</span>
b = (k + <span class="hljs-params">-1</span> * r1 * d1 + r2 * d2) / <span class="hljs-params">3</span>
c = (k + <span class="hljs-params">-1</span> * r1 * d1 + <span class="hljs-params">-2</span> * r2 * d2) / <span class="hljs-params">3</span>
a + r1
<span class="hljs-keyword">if</span> <span class="hljs-params">0</span> <= a <= k <span class="hljs-keyword">and</span> <span class="hljs-params">0</span> <= b <= k <span class="hljs-keyword">and</span> <span class="hljs-params">0</span> <= c <= k <span class="hljs-keyword">and</span> a.is_integer() <span class="hljs-keyword">and</span> b.is_integer() <span class="hljs-keyword">and</span> c.is_integer():
abcs.append([a, b, c])
flag = <span class="hljs-keyword">False</span>
<span class="hljs-keyword">for</span> abc <span class="hljs-keyword">in</span> abcs:
<span class="hljs-keyword">if</span> len(abc) > <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> max(abc) <= n / <span class="hljs-params">3</span>:
flag = <span class="hljs-keyword">True</span>
<span class="hljs-keyword">break</span>
<span class="hljs-keyword">if</span> flag:
print(<span class="hljs-string">'yes'</span>)
<span class="hljs-keyword">else</span>:
print(<span class="hljs-string">'no'</span>)
```
```
**復雜度分析**
- 時間復雜度:O(t)O(t)O(t)
- 空間復雜度:O(t)O(t)O(t)
### 小結
感覺這個難度也就是力扣中等水平吧,力扣也有一些數學等式轉換的題目, 比如 [494.target-sum](https://github.com/azl397985856/leetcode/blob/master/problems/494.target-sum.md "494.target-sum")
## 轉換字符串
### 題目描述
有一個僅包含’a’和’b’兩種字符的字符串 s,長度為 n,每次操作可以把一個字符做一次轉換(把一個’a’設置為’b’,或者把一個’b’置成’a’);但是操作的次數有上限 m,問在有限的操作數范圍內,能夠得到最大連續的相同字符的子串的長度是多少。
### 思路
看完題我就有種似曾相識的感覺。
> 每次對妹子說出這句話的時候,她們都會覺得好假 ^\_^
不過這次是真的。 ”哦,不!每次都是真的“。 這道題其實就是我之前寫的滑動窗口的一道題[【1004. 最大連續 1 的個數 III】滑動窗口(Python3)](https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/1004-zui-da-lian-xu-1de-ge-shu-iii-hua-dong-chuang/ "【1004. 最大連續 1 的個數 III】滑動窗口(Python3)")的換皮題。 專題地址:<https://github.com/azl397985856/leetcode/blob/master/thinkings/slide-window.md>
所以說,如果這道題你完全沒有思路的話。說明:
- 抽象能力不夠。
- 滑動窗口問題理解不到位。
第二個問題可以看我上面貼的地址,仔細讀讀,并完成課后練習即可解決。
第一個問題就比較困難了, 不過多看我的題解也可以慢慢提升的。比如:
- [《割繩子》](https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/ "《割繩子》") 實際上就是 [343. 整數拆分](https://lucifer.ren/blog/2020/05/16/343.integer-break/ "343. 整數拆分") 的換皮題。
- 力扣 230 和 力扣 645 就是換皮題,詳情參考[位運算專題](https://lucifer.ren/blog/2020/03/24/bit/ "位運算專題")
- 以及 [你的衣服我扒了 - 《最長公共子序列》](https://lucifer.ren/blog/2020/07/01/LCS/)
- 以及 [穿上衣服我就不認識你了?來聊聊最長上升子序列](https://lucifer.ren/blog/2020/06/20/LIS/)
- 以及 [一招吃遍力扣四道題,媽媽再也不用擔心我被套路啦~](https://lucifer.ren/blog/2020/06/13/%E5%88%A0%E9%99%A4%E9%97%AE%E9%A2%98/)
- 等等
回歸這道題。其實我們只需要稍微抽象一下, 就是一個純算法題。 抽象的另外一個好處則是將很多不同的題目返璞歸真,從而可以在茫茫題海中逃脫。這也是我開啟[《我是你的媽媽呀》](https://lucifer.ren/blog/2020/08/03/mother-01/) 的原因之一。
如果我們把 a 看成是 0 , b 看成是 1。或者將 b 看成 1, a 看成 0。不就抽象成了:
```
<pre class="calibre18">```
給定一個由若干 0 和 1 組成的數組 A,我們最多可以將 m 個值從 0 變成 1 。
返回僅包含 1 的最長(連續)子數組的長度。
```
```
這就是 力扣 [1004. 最大連續 1 的個數 III](https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/1004-zui-da-lian-xu-1de-ge-shu-iii-hua-dong-chuang/) 原題。
因此實際上我們要求的是上面兩種情況:
1. a 表示 0, b 表示 1
2. a 表示 1, b 表示 0
的較大值。
> lucifer 小提示: 其實我們也可以僅僅考慮一種情況,比如 a 看成是 0 , b 看成是 1。這個時候, 我們操作變成了兩種情況,0 變成 1 或者 1 變成 0,同時求解的也變成了最長連續 0 或者 最長連續 1 。 由于這種抽象操作起來更麻煩, 我們不考慮。
問題得到了抽象就好解決了。我們只需要記錄下加入窗口的是 0 還是 1:
- 如果是 1,我們什么都不用做
- 如果是 0,我們將 m 減 1
相應地,我們需要記錄移除窗口的是 0 還是 1:
- 如果是 1,我們什么都不做
- 如果是 0,說明加進來的時候就是 1,加進來的時候我們 m 減去了 1,這個時候我們再加 1。
> lucifer 小提示: 實際上題目中是求**連續** a 或者 b 的長度。看到連續,大家也應該有滑動窗口的敏感度, 別管行不行, 想到總該有的。
我們拿 A = \[1, 1, 0, 1, 0, 1\], m = 1 來說。看下算法的具體過程:
> lucifer 小提示: 左側的數字表示此時窗口大小,黃色格子表示修補的墻,黑色方框表示的是窗口。

這里我形象地將 0 看成是洞,1 看成是墻, 我們的目標就是補洞,使得連續的墻最長。

每次碰到一個洞,我們都去不加選擇地修補。由于 m 等于 1, 也就是說我們最多補一個洞。因此需要在修補超過一個洞的時候,我們需要調整窗口范圍,使得窗口內最多修補一個墻。由于窗口表示的就是連續的墻(已有的或者修補的),因此最終我們返回窗口的最大值即可。

> 由于下面的圖窗口內有兩個洞,這和”最多補一個洞“沖突, 我們需要收縮窗口使得滿足“最多補一個洞”的先決條件。

因此最大的窗口就是 max(2, 3, 4, ...) = 4。
> lucifer 小提示: 可以看出我們不加選擇地修補了所有的洞,并調整窗口,使得窗口內最多有 m 個修補的洞,因此窗口的最大值就是答案。然而實際上,我們并不需要真的”修補“(0 變成 1),而是僅僅修改 m 的值即可。
我們先來看下抽象之后的**其中一種情況**的代碼:
```
<pre class="calibre18">```
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestOnes</span><span class="hljs-params">(self, A: List[int], m: int)</span> -> int:</span>
i = <span class="hljs-params">0</span>
<span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(len(A)):
m -= <span class="hljs-params">1</span> - A[j]
<span class="hljs-keyword">if</span> m < <span class="hljs-params">0</span>:
m += <span class="hljs-params">1</span> - A[i]
i += <span class="hljs-params">1</span>
<span class="hljs-keyword">return</span> j - i + <span class="hljs-params">1</span>
```
```
因此**完整代碼**就是:
```
<pre class="calibre18">```
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestOnes</span><span class="hljs-params">(self, A: List[int], m: int)</span> -> int:</span>
i = <span class="hljs-params">0</span>
<span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(len(A)):
m -= <span class="hljs-params">1</span> - A[j]
<span class="hljs-keyword">if</span> m < <span class="hljs-params">0</span>:
m += <span class="hljs-params">1</span> - A[i]
i += <span class="hljs-params">1</span>
<span class="hljs-keyword">return</span> j - i + <span class="hljs-params">1</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestAorB</span><span class="hljs-params">(self, A:List[int], m: int)</span> -> int:</span>
<span class="hljs-keyword">return</span> max(self.longestOnes(map(<span class="hljs-keyword">lambda</span> x: <span class="hljs-params">0</span> <span class="hljs-keyword">if</span> x == <span class="hljs-string">'a'</span> <span class="hljs-keyword">else</span> <span class="hljs-params">1</span>, A) ,m), self.longestOnes(map(<span class="hljs-keyword">lambda</span> x: <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> x == <span class="hljs-string">'a'</span> <span class="hljs-keyword">else</span> <span class="hljs-params">0</span>, A),m))
```
```
這里的兩個 map 會生成兩個不同的數組。 我只是為了方便大家理解才新建的兩個數組, 實際上根本不需要,具體見后面的代碼.
### 代碼(Python)
```
<pre class="calibre18">```
i = <span class="hljs-params">0</span>
n, m = map(int, input().split(<span class="hljs-string">" "</span>))
s = input()
ans = <span class="hljs-params">0</span>
k = m <span class="hljs-title"># 存一下,后面也要用這個初始值</span>
<span class="hljs-title"># 修補 b</span>
<span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n):
m -= ord(s[j]) - ord(<span class="hljs-string">'a'</span>)
<span class="hljs-keyword">if</span> m < <span class="hljs-params">0</span>:
m += ord(s[i]) - ord(<span class="hljs-string">'a'</span>)
i += <span class="hljs-params">1</span>
ans = j - i + <span class="hljs-params">1</span>
i = <span class="hljs-params">0</span>
<span class="hljs-title"># 修補 a</span>
<span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n):
k += ord(s[j]) - ord(<span class="hljs-string">'b'</span>)
<span class="hljs-keyword">if</span> k < <span class="hljs-params">0</span>:
k -= ord(s[i]) - ord(<span class="hljs-string">'b'</span>)
i += <span class="hljs-params">1</span>
print(max(ans, j - i + <span class="hljs-params">1</span>))
```
```
**復雜度分析**
- 時間復雜度:O(N)O(N)O(N)
- 空間復雜度:O(1)O(1)O(1)
### 小結
這道題就是一道換了皮的力扣題,難度中等。如果你能將問題抽象,同時又懂得滑動窗口,那這道題就很容易。我看了題解區的參考答案, 內容比較混亂,不夠清晰。這也是我寫下這篇文章的原因之一。
## 總結
這一套字節跳動的題目一共四道,一道設計題,三道算法題。
其中三道算法題從難度上來說,基本都是中等難度。從內容來看,基本都是力扣的換皮題。但是如果我不說他們是換皮題, 你們能發現么? 如果你可以的話,說明你的抽象能力已經略有小成了。如果看不出來也沒有關系,關注我。 手把手扒皮給你們看,扒多了慢慢就會了。切記,不要盲目做題!如果你做了很多題, 這幾道題還是看不出套路,說明你該緩緩,改變下刷題方式了。
更多題解可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 36K+ star 啦。
關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。

- Introduction
- 第一章 - 算法專題
- 數據結構
- 基礎算法
- 二叉樹的遍歷
- 動態規劃
- 哈夫曼編碼和游程編碼
- 布隆過濾器
- 字符串問題
- 前綴樹專題
- 《貪婪策略》專題
- 《深度優先遍歷》專題
- 滑動窗口(思路 + 模板)
- 位運算
- 設計題
- 小島問題
- 最大公約數
- 并查集
- 前綴和
- 平衡二叉樹專題
- 第二章 - 91 天學算法
- 第一期講義-二分法
- 第一期講義-雙指針
- 第二期
- 第三章 - 精選題解
- 《日程安排》專題
- 《構造二叉樹》專題
- 字典序列刪除
- 百度的算法面試題 * 祖瑪游戲
- 西法的刷題秘籍】一次搞定前綴和
- 字節跳動的算法面試題是什么難度?
- 字節跳動的算法面試題是什么難度?(第二彈)
- 《我是你的媽媽呀》 * 第一期
- 一文帶你看懂二叉樹的序列化
- 穿上衣服我就不認識你了?來聊聊最長上升子序列
- 你的衣服我扒了 * 《最長公共子序列》
- 一文看懂《最大子序列和問題》
- 第四章 - 高頻考題(簡單)
- 面試題 17.12. BiNode
- 0001. 兩數之和
- 0020. 有效的括號
- 0021. 合并兩個有序鏈表
- 0026. 刪除排序數組中的重復項
- 0053. 最大子序和
- 0088. 合并兩個有序數組
- 0101. 對稱二叉樹
- 0104. 二叉樹的最大深度
- 0108. 將有序數組轉換為二叉搜索樹
- 0121. 買賣股票的最佳時機
- 0122. 買賣股票的最佳時機 II
- 0125. 驗證回文串
- 0136. 只出現一次的數字
- 0155. 最小棧
- 0167. 兩數之和 II * 輸入有序數組
- 0169. 多數元素
- 0172. 階乘后的零
- 0190. 顛倒二進制位
- 0191. 位1的個數
- 0198. 打家劫舍
- 0203. 移除鏈表元素
- 0206. 反轉鏈表
- 0219. 存在重復元素 II
- 0226. 翻轉二叉樹
- 0232. 用棧實現隊列
- 0263. 丑數
- 0283. 移動零
- 0342. 4的冪
- 0349. 兩個數組的交集
- 0371. 兩整數之和
- 0437. 路徑總和 III
- 0455. 分發餅干
- 0575. 分糖果
- 0874. 模擬行走機器人
- 1260. 二維網格遷移
- 1332. 刪除回文子序列
- 第五章 - 高頻考題(中等)
- 0002. 兩數相加
- 0003. 無重復字符的最長子串
- 0005. 最長回文子串
- 0011. 盛最多水的容器
- 0015. 三數之和
- 0017. 電話號碼的字母組合
- 0019. 刪除鏈表的倒數第N個節點
- 0022. 括號生成
- 0024. 兩兩交換鏈表中的節點
- 0029. 兩數相除
- 0031. 下一個排列
- 0033. 搜索旋轉排序數組
- 0039. 組合總和
- 0040. 組合總和 II
- 0046. 全排列
- 0047. 全排列 II
- 0048. 旋轉圖像
- 0049. 字母異位詞分組
- 0050. Pow(x, n)
- 0055. 跳躍游戲
- 0056. 合并區間
- 0060. 第k個排列
- 0062. 不同路徑
- 0073. 矩陣置零
- 0075. 顏色分類
- 0078. 子集
- 0079. 單詞搜索
- 0080. 刪除排序數組中的重復項 II
- 0086. 分隔鏈表
- 0090. 子集 II
- 0091. 解碼方法
- 0092. 反轉鏈表 II
- 0094. 二叉樹的中序遍歷
- 0095. 不同的二叉搜索樹 II
- 0096. 不同的二叉搜索樹
- 0098. 驗證二叉搜索樹
- 0102. 二叉樹的層序遍歷
- 0103. 二叉樹的鋸齒形層次遍歷
- 105. 從前序與中序遍歷序列構造二叉樹
- 0113. 路徑總和 II
- 0129. 求根到葉子節點數字之和
- 0130. 被圍繞的區域
- 0131. 分割回文串
- 0139. 單詞拆分
- 0144. 二叉樹的前序遍歷
- 0150. 逆波蘭表達式求值
- 0152. 乘積最大子數組
- 0199. 二叉樹的右視圖
- 0200. 島嶼數量
- 0201. 數字范圍按位與
- 0208. 實現 Trie (前綴樹)
- 0209. 長度最小的子數組
- 0211. 添加與搜索單詞 * 數據結構設計
- 0215. 數組中的第K個最大元素
- 0221. 最大正方形
- 0229. 求眾數 II
- 0230. 二叉搜索樹中第K小的元素
- 0236. 二叉樹的最近公共祖先
- 0238. 除自身以外數組的乘積
- 0240. 搜索二維矩陣 II
- 0279. 完全平方數
- 0309. 最佳買賣股票時機含冷凍期
- 0322. 零錢兌換
- 0328. 奇偶鏈表
- 0334. 遞增的三元子序列
- 0337. 打家劫舍 III
- 0343. 整數拆分
- 0365. 水壺問題
- 0378. 有序矩陣中第K小的元素
- 0380. 常數時間插入、刪除和獲取隨機元素
- 0416. 分割等和子集
- 0445. 兩數相加 II
- 0454. 四數相加 II
- 0494. 目標和
- 0516. 最長回文子序列
- 0518. 零錢兌換 II
- 0547. 朋友圈
- 0560. 和為K的子數組
- 0609. 在系統中查找重復文件
- 0611. 有效三角形的個數
- 0718. 最長重復子數組
- 0754. 到達終點數字
- 0785. 判斷二分圖
- 0820. 單詞的壓縮編碼
- 0875. 愛吃香蕉的珂珂
- 0877. 石子游戲
- 0886. 可能的二分法
- 0900. RLE 迭代器
- 0912. 排序數組
- 0935. 騎士撥號器
- 1011. 在 D 天內送達包裹的能力
- 1014. 最佳觀光組合
- 1015. 可被 K 整除的最小整數
- 1019. 鏈表中的下一個更大節點
- 1020. 飛地的數量
- 1023. 駝峰式匹配
- 1031. 兩個非重疊子數組的最大和
- 1104. 二叉樹尋路
- 1131.絕對值表達式的最大值
- 1186. 刪除一次得到子數組最大和
- 1218. 最長定差子序列
- 1227. 飛機座位分配概率
- 1261. 在受污染的二叉樹中查找元素
- 1262. 可被三整除的最大和
- 1297. 子串的最大出現次數
- 1310. 子數組異或查詢
- 1334. 閾值距離內鄰居最少的城市
- 1371.每個元音包含偶數次的最長子字符串
- 第六章 - 高頻考題(困難)
- 0004. 尋找兩個正序數組的中位數
- 0023. 合并K個升序鏈表
- 0025. K 個一組翻轉鏈表
- 0030. 串聯所有單詞的子串
- 0032. 最長有效括號
- 0042. 接雨水
- 0052. N皇后 II
- 0084. 柱狀圖中最大的矩形
- 0085. 最大矩形
- 0124. 二叉樹中的最大路徑和
- 0128. 最長連續序列
- 0145. 二叉樹的后序遍歷
- 0212. 單詞搜索 II
- 0239. 滑動窗口最大值
- 0295. 數據流的中位數
- 0301. 刪除無效的括號
- 0312. 戳氣球
- 0335. 路徑交叉
- 0460. LFU緩存
- 0472. 連接詞
- 0488. 祖瑪游戲
- 0493. 翻轉對
- 0887. 雞蛋掉落
- 0895. 最大頻率棧
- 1032. 字符流
- 1168. 水資源分配優化
- 1449. 數位成本和為目標值的最大數字
- 后序