关于算法:字节跳动的算法面试题是什么难度第二弹

因为 lucifer 我是一个小前端，最近也在筹备写一个《前端如何搞定算法面试》的专栏，因而最近没少看各大公司的面试题。都说字节跳动算法题比拟难，我就先拿 ta 下手，做了几套。这次咱们就拿一套 字节跳动 2017 秋招编程题汇总 来看下字节的算法口试题的难度几何。地址：https://www.nowcoder.com/test…

这套题一共 11 道题，三道编程题，八道问答题。本次给大家带来的就是这三道编程题。更多精彩内容，请期待我的搞定算法面试专栏。

其中有一道题《异或》我没有通过所有的测试用例，小伙伴能够找找茬，第一个找到并在公众号力扣加加留言的小伙伴处分现金红包 10 元。

1. 头条校招

题目形容

头条的 2017 校招开始了！为了这次校招，咱们组织了一个规模宏大的出题团队，每个出题人都出了一些乏味的题目，而咱们当初想把这些题目组合成若干场考试进去，在选题之前，咱们对题目进行了盲审，并定出了每道题的难度零碎。一场考试蕴含 3 道开放性题目，假如他们的难度从小到大别离为 a,b,c，咱们心愿这 3 道题能满足下列条件：a<=b<=c
b-a<=10
c-b<=10
所有出题人一共出了 n 道开放性题目。当初咱们想把这 n 道题散布到若干场考试中（1 场或多场，每道题都必须应用且只能用一次），然而因为上述条件的限度，可能有一些考试没法凑够 3 道题，因而出题人就须要多出一些适当难度的题目来让每场考试都达到要求，然而咱们出题曾经出得很累了，你能计算出咱们起码还须要再出几道题吗？输出形容:
输出的第一行蕴含一个整数 n，示意目前曾经出好的题目数量。第二行给出每道题目的难度系数 d1,d2,...,dn。数据范畴

对于 30% 的数据，1 ≤ n,di ≤ 5;

对于 100% 的数据，1 ≤ n ≤ 10^5,1 ≤ di ≤ 100。在样例中，一种可行的计划是增加 2 个难度别离为 20 和 50 的题目，这样能够组合成两场考试：（20 20 23）和（35,40,50）。输入形容:
输入只包含一行，即所求的答案。示例 1
输出
4
20 35 23 40
输入
2

思路

这道题看起来很简单，你须要思考很多的状况。，属于那种没有技术含量，然而考验编程能力的题目，须要思维足够紧密。这种 模仿的题目，就是题目让我干什么我干什么。相似之前写的囚徒房间问题，约瑟夫环也是模仿，只不过模仿之后须要你剪枝优化。

这道题的状况其实很多，咱们须要思考每一套题中的难度状况，而不须要思考不同套题的难度状况。题目要求咱们满足：a<=b<=c b-a<=10 c-b<=10，也就是题目难度从小到大排序之后，相邻的难度不能大于 10。

因而咱们的思路就是先排序，之后从小到大遍历，如果满足相邻的难度不大于 10，则持续。如果不满足，咱们就只能让字节的老师出一道题使得满足条件。

因为只须要比拟同一套题目的难度，因而我的想法就是 比拟同一套题目的第二个和第一个，以及第三个和第二个的 diff。

• 如果 diff 小于 10，什么都不做，持续。
• 如果 diff 大于 10，咱们必须补充题目。

这里有几个点须要留神。

对于第二题来说：

• 比方 1 30 40 这样的难度。我能够在 1，30 之间加一个 21，这样 1，21，30 就能够组成一一套。
• 比方 1 50 60 这样的难度。我能够在 1，50 之间加 21，41 才能够组成一套，本身（50）是无论如何都没方法组到这套题中的。

不难看出，第二道题的临界点是 diff = 20。小于等于 20 都能够将本身组到套题，减少一道即可，否则须要减少两个，并且本身不能组到以后套题。

对于第三题来说：

• 比方 1 20 40。我能够在 20，40 之间加一个 30，这样 1，20，30 就能够组成一一套，本身（40）是无奈组到这套题的。
• 比方 1 20 60。也是一样的，我能够在 20，60 之间加一个 30，本身（60）同样是没方法组到这套题中的。

不难看出，第三道题的临界点是 diff = 10。小于等于 10 都能够将本身组到套题，否则须要减少一个，并且本身不能组到以后套题。

这就是所有的状况了。

有的同学比拟好奇，我是怎么思考的。我是怎么 保障不重不漏 的。

实际上，这道题就是一个决策树，我画个决策树进去你就明确了。

图中红色边框示意本身能够组成套题的一部分，我也用文字进行了阐明。#2 代表第二题，#3 代表第三题。

从图中能够看出，我曾经思考了所有状况。如果你可能像我一样画出这个决策图，我想你也不会漏的。当然我的解法并不一定是最优的，不过的确是一个十分好用，具备普适性的思维框架。

须要特地留神的是，因为须要凑整，因而你须要使得题目的总数是 3 的倍数向上取整。

代码

n = int(input())
nums = list(map(int, input().split()))
cnt = 0
cur = 1
nums.sort()
for i in range(1, n):
    if cur == 3:
        cur = 1
        continue
    diff = nums[i] - nums[i - 1]
    if diff <= 10:
        cur += 1
    if 10 < diff <= 20:
        if cur == 1:
            cur = 3
        if cur == 2:
            cur = 1
        cnt += 1
    if diff > 20:
        if cur == 1:
            cnt += 2
        if cur == 2:
            cnt += 1
        cur = 1
print(cnt + 3 - cur)

复杂度剖析

• 工夫复杂度：因为应用了排序，因而工夫复杂度为 $O(NlogN)$。（假如应用了基于比拟的排序）
• 空间复杂度：$O(1)$

2. 异或

题目形容

给定整数 m 以及 n 各数字 A1,A2,..An，将数列 A 中所有元素两两异或，共能失去 n(n-1)/2 个后果，申请出这些后果中大于 m 的有多少个。输出形容:
第一行蕴含两个整数 n,m.

第二行给出 n 个整数 A1，A2，...，An。数据范畴

对于 30% 的数据，1 <= n, m <= 1000

对于 100% 的数据，1 <= n, m, Ai <= 10^5

输入形容:
输入仅包含一行，即所求的答案

输出例子 1:
3 10
6 5 10

输入例子 1:
2

前置常识

• 异或运算的性质
• 如何高效比拟两个数的大小（从高位到低位）

首先遍及一下前置常识。第一个是异或运算：

异或的性质：两个数字异或的后果 a^b 是将 a 和 b 的二进制每一位进行运算，得出的数字。运算的逻辑是如果同一位的数字雷同则为 0，不同则为 1

异或的法则：

1. 任何数和自身异或则为 0
2. 任何数和 0 异或是自身
3. 异或运算满足交换律，即：a ^ b ^ c = a ^ c ^ b

同时倡议大家去看下我总结的几道位运算的经典题目。位运算系列

其次要晓得一个常识，即比拟两个数的大小，咱们是从高位到低位比拟，这样才比拟高效。

比方：

123
456
1234

这三个数比拟大小，为了不便咱们先补 0，使得大家的位数保持一致。

0123
0456
1234

先比拟第一位，1 比拟 0 大，因而 1234 最大。再比拟第二位，4 比 1 大，因而 456 大于 123，前面位不须要比拟了。这其实就是剪枝的思维。

有了这两个前提，咱们来试下暴力法解决这道题。

思路

暴力法就是枚举 $N^2 / 2$ 中组合，让其两两按位异或，将失去的后果和 m 进行比拟，如果比 m 大，则计数器 + 1，最初返回计数器的值即可。

暴力的办法就如同题目形容的那样，复杂度为 $N^2$。肯定过不了所有的测试用例，不过大家切实没有好的解法的状况能够兜底。不论是牛客口试还是理论的面试都是可行的。

接下来，让咱们来 剖析一下暴力为什么低效，以及如何选取数据结构和算法可能使得这个过程变得高效。 记住这句话，简直所有的优化都是基于这种思维产生的，除非你开启了上帝模式，间接看了答案。只不过等你相熟了之后，这个思维过程会十分短，以至于变成条件反射，你感觉不到有这个过程，这就是 有了题感。

其实我方才说的第二个前置常识就是咱们优化的要害之一。

我举个例子，比方 3 和 5 按位异或。

3 的二进制是 011，5 的二进制是 101，

011
101

依照我后面讲的异或常识，不难得出其异或构造就是 110。

下面我进行了三次异或：

1. 第一次是最高位的 0 和 1 的异或，后果为 1。
2. 第二次是次高位的 1 和 0 的异或，后果为 1。
3. 第三次是最低位的 1 和 1 的异或，后果为 0。

那如何 m 是 1 呢？咱们有必要进行三次异或么？实际上进行第一次异或的时候曾经晓得了肯定比 m（m 是 1）大。因为第一次异或的构造导致其最高位为 1，也就是说其最小也不过是 100，也就是 4，肯定是大于 1 的。这就是 剪枝，这就是算法优化的要害。

看出我一步一步的思维过程了么？所有的算法优化都须要通过相似的过程。

因而我的算法就是从高位开始两两异或，并且异或的后果和 m 对应的二进制位比拟大小。

• 如果比 m 对应的二进制位大或者小，咱们提前退出即可。
• 如果相等，咱们持续往低位挪动反复这个过程。

这尽管曾经剪枝了，然而极其状况下，性能还是很差。比方：

m: 1111
a: 1010
b: 0101

a，b 示意两个数，咱们比拟到最初才发现，其异或的值和 m 相等。因而极其状况，算法效率没有失去改良。

这里我想到了一点，就是如果一个数 a 的前缀和另外一个数 b 的前缀是一样的，那么 c 和 a 或者 c 和 b 的异或的构造前缀局部肯定也是一样的。比方：

a: 111000
b: 111101
c: 101011

a 和 b 有独特的前缀 111，c 和 a 异或过了，当再次和 b 异或的时候，实际上前三位是没有必要进行的，这也是反复的局部。这就是算法能够优化的局部，这就是剪枝。

剖析算法，找到算法的瓶颈局部，而后选取适合的数据结构和算法来优化到。 这句话很重要，请务必记住。

在这里，咱们用的就是剪枝技术，对于剪枝，91 天学算法也有具体的介绍。

回到后面讲到的算法瓶颈，多个数是有独特前缀的，前缀局部就是咱们节约的运算次数，说到前缀大家应该能够想到前缀树。如果不相熟前缀树的话，看下我的这个前缀树专题，外面的题全副手写一遍就差不多了。

因而一种想法就是建设一个前缀树，树的根就是最高的位。因为题目要求异或，咱们晓得异或是二进制的位运算，因而这棵树要存二进制才比拟好。

反手看了一眼数据范畴：m, n<=10^5。10^5 = 2 ^ x，咱们的指标是求出 满足条件的 x 的 ceil（向上取整），因而 x 应该是 17。

树的每一个节点存储的是：n 个数中，从根节点到以后节点造成的前缀有多少个是一样的，即多少个数的前缀是一样的。这样能够剪枝，提前退出的时候，就间接取出来用了。比方异或的后果是 1，m 以后二进制位是 0，那么这个前缀有 10 个，我都不须要比拟了，计数器间接 + 10。

我用 17 间接简单度过高，目前仅仅通过了 70 % – 80 % 测试用例，心愿大家能够帮我找找故障，我猜想是语言的锅。

代码

class TreeNode:
    def __init__(self):
        self.cnt = 1
        self.children = [None] * 2
def solve(num, i, cur):
    if cur == None or i == -1: return 0
    bit = (num >> i) & 1
    mbit = (m >> i) & 1
    if bit == 0 and mbit == 0:
        return (cur.children[1].cnt if cur.children[1] else 0) + solve(num, i - 1, cur.children[0])
    if bit == 1 and mbit == 0:
        return (cur.children[0].cnt if cur.children[0] else 0) + solve(num, i - 1, cur.children[1])
    if bit == 0 and mbit == 1:
        return solve(num, i - 1, cur.children[1])
    if bit == 1 and mbit == 1:
        return solve(num, i - 1, cur.children[0])

def preprocess(nums, root):
    for num in nums:
        cur = root
        for i in range(16, -1, -1):
            bit = (num >> i) & 1
            if cur.children[bit]:
                cur.children[bit].cnt += 1
            else:
                cur.children[bit] = TreeNode()
            cur = cur.children[bit]

n, m = map(int, input().split())
nums = list(map(int, input().split()))
root = TreeNode()
preprocess(nums, root)
ans = 0
for num in nums:
    ans += solve(num, 16, root)
print(ans // 2)

复杂度剖析

• 工夫复杂度：$O(N)$
• 空间复杂度：$O(N)$

3. 字典序

题目形容

给定整数 n 和 m, 将 1 到 n 的这 n 个整数按字典序排列之后, 求其中的第 m 个数。对于 n=11, m=4, 按字典序排列顺次为 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 因而第 4 个数是 2.
对于 n=200, m=25, 按字典序排列顺次为 1 10 100 101 102 103 104 105 106 107 108 109 11 110 111 112 113 114 115 116 117 118 119 12 120 121 122 123 124 125 126 127 128 129 13 130 131 132 133 134 135 136 137 138 139 14 140 141 142 143 144 145 146 147 148 149 15 150 151 152 153 154 155 156 157 158 159 16 160 161 162 163 164 165 166 167 168 169 17 170 171 172 173 174 175 176 177 178 179 18 180 181 182 183 184 185 186 187 188 189 19 190 191 192 193 194 195 196 197 198 199 2 20 200 21 22 23 24 25 26 27 28 29 3 30 31 32 33 34 35 36 37 38 39 4 40 41 42 43 44 45 46 47 48 49 5 50 51 52 53 54 55 56 57 58 59 6 60 61 62 63 64 65 66 67 68 69 7 70 71 72 73 74 75 76 77 78 79 8 80 81 82 83 84 85 86 87 88 89 9 90 91 92 93 94 95 96 97 98 99 因而第 25 个数是 120…

输出形容:
输出仅蕴含两个整数 n 和 m。数据范畴:

对于 20% 的数据, 1 <= m <= n <= 5 ;

对于 80% 的数据, 1 <= m <= n <= 10^7 ;

对于 100% 的数据, 1 <= m <= n <= 10^18.

输入形容:
输入仅包含一行, 即所求排列中的第 m 个数字.
示例 1
输出
11 4
输入
2

前置常识

• 十叉树
• 齐全十叉树
• 计算齐全十叉树的节点个数
• 字典树

思路

和下面题目思路一样，先从暴力解法开始，尝试关上思路。

暴力兜底的思路是间接生成一个长度为 n 的数组，排序，选第 m 个即可。代码：

n, m = map(int, input().split())

nums  = [str(i) for i in range(1, n + 1)]
print(sorted(nums)[m - 1])

复杂度剖析

• 工夫复杂度：取决于排序算法，无妨认为是 $O(NlogN)$
• 空间复杂度: $O(N)$

这种算法能够 pass 50 % case。

下面算法低效的起因是开拓了 N 的空间，并对整 N 个 元素进行了排序。

一种简略的优化办法是将排序换成堆，利用堆的个性求第 k 大的数，这样工夫复杂度能够减低到 $mlogN$。

咱们持续优化。实际上，你如果把字典序的排序构造画进去，能够发现他实质就是一个十叉树，并且是一个齐全十叉树。

接下来，我带你持续剖析。

如图，红色示意根节点。节点示意一个十进制数，树的门路存储真正的数字，比方图上的 100，109 等。这不就是下面讲的前缀树么？

如图黄色局部，示意字典序的程序，留神箭头的方向。因而实质上，求字典序第 m 个数，就是求这棵树的前序遍历的第 m 个节点。

因而一种优化思路就是构建一颗这样的树，而后去遍历。构建的复杂度是 $O(N)$，遍历的复杂度是 $O(M)$。因而这种算法的复杂度能够达到 $O(max(m, n))$，因为 n >= m，因而就是 $O(N)$。

实际上，这样的优化算法仍然是无奈 AC 全副测试用例的，会超内存限度。因而咱们的思路只能是不应用 N 的空间去结构树。想想也晓得，因为 N 最大可能为 10^18，一个数依照 4 字节来算，那么这就有 400000000 字节，大概是 381 M，这是不能承受的。

下面提到这道题就是一个齐全十叉树的前序遍历，问题转化为求齐全十叉树的前序遍历的第 m 个数。

十叉树和二叉树没有实质不同，我在二叉树专题局部，也提到了 N 叉树都能够用二叉树来示意。

对于一个节点来说，第 m 个节点：

• 要么就是它自身
• 要么其孩子节点中
• 要么在其兄弟节点
• 要么在兄弟节点的孩子节点中

到底在下面的四个局部的哪，取决于其孩子节点的个数。

• count > m，m 在其孩子节点中，咱们须要深刻到子节点。
• count <= m，m 不在本身和孩子节点, 咱们应该跳过所有孩子节点，间接到兄弟节点。

这实质就是一个递归的过程。

须要留神的是，咱们并不会真正的在树上走，因而下面提到的 深刻到子节点 ，以及 跳过所有孩子节点，间接到兄弟节点 如何操作呢？

你仔细观察会发现：如果以后节点的前缀是 x，那么其第一个子节点（就是最小的子节点）是 x * 10，第二个就是 x * 10 + 1，以此类推。因而：

• 深刻到子节点就是 x * 10。
• 跳过所有孩子节点，间接到兄弟节点就是 x + 1。

ok，铺垫地差不多了。

接下来，咱们的重点是 如何计算给定节点的孩子节点的个数。

这个过程和齐全二叉树计算节点个数并无二致，这个算法的工夫复杂度应该是 $O(logN*logN)$。如果不会的同学，能够参考力扣原题：222. 齐全二叉树的节点个数，这是一个难度为中等的题目。

因而这道题自身被划分为 hard，一点都不为过。

这里简略说下，计算给定节点的孩子节点的个数的思路，我的 91 天学算法里出过这道题。

一种简略但非最优的思路是别离计算左右子树的深度。

• 如果以后节点的左右子树高度雷同，那么左子树是一个满二叉树，右子树是一个齐全二叉树。
• 否则（右边的高度大于左边），那么左子树是一个齐全二叉树，右子树是一个满二叉树。

如果是满二叉树，以后节点数 是 2 ^ depth，而对于齐全二叉树，咱们持续递归即可。

class Solution:
    def countNodes(self, root):
        if not root:
            return 0
        ld = self.getDepth(root.left)
        rd = self.getDepth(root.right)
        if ld == rd:
            return 2 ** ld + self.countNodes(root.right)
        else:
            return 2 ** rd + self.countNodes(root.left)

    def getDepth(self, root):
        if not root:
            return 0
        return 1 + self.getDepth(root.left)

复杂度剖析

• 工夫复杂度：$O(logN * log N)$
• 空间复杂度：$O(logN)$

而这道题，咱们能够更简略和高效。

比方咱们要计算 1 号节点的子节点个数。

• 它的孩子节点个数是。。。
• 它的孙子节点个数是。。。
• 。。。

全副加起来即可。

它的孩子节点个数是 20 - 10 = 10。也就是它的 左边的兄弟节点的第一个子节点 减去 它的 第一个子节点。

因为是齐全十叉树，而不是满十叉树。因而你须要思考边界状况，比方题目的 n 是 15。那么 1 的子节点个数就不是 20 – 10 = 10 了，而是 15 – 10 + 1 = 16。

其余也是相似的过程，咱们只有：

• Go deeper and do the same thing

或者：

• Move to next neighbor and do the same thing

一直反复，直到 m 升高到 0。

代码

def count(c1, c2, n):
    steps = 0
    while c1 <= n:
        steps += min(n + 1, c2) - c1
        c1 *= 10
        c2 *= 10
    return steps
def findKthNumber(n: int, k: int) -> int:
    cur = 1
    k = k - 1
    while k > 0:
        steps = count(cur, cur + 1, n)
        if steps <= k:
            cur += 1
            k -= steps
        else:
            cur *= 10
            k -= 1
    return cur
n, m = map(int, input().split())
print(findKthNumber(n, m))

复杂度剖析

• 工夫复杂度：$O(logM * log N)$
• 空间复杂度：$O(1)$

总结

其中三道算法题从难度上来说，根本都是艰难难度。从内容来看，根本都是力扣的换皮题，且都或多或少和树无关。如果大家一开始没有思路，倡议大家先给出暴力的解法兜底，再画图或举简略例子关上思路。

我也刷了很多字节的题了，还有一些难度比拟大的题。如果你第一次做，那么须要你思考比拟久能力想进去。加上面试缓和，很可能做不进去。这个时候就更须要你沉着剖析，先暴力打底，缓缓优化。有时候即便给不了最优解，让面试官看出你的思路也很重要。比方小兔的棋盘 想出最优解难度就不低，不过你能够先暴力 DFS 解决，再 DP 优化会缓缓帮你关上思路。有时候面试官也会疏导你，给你提醒，加上你方才“施展不错”，说不定一下子就做出最优解了，这个我深有体会。

另外要揭示大家的是，刷题要适量，不要贪多。要齐全理清一道题的前因后果。多问几个为什么。这道题暴力法怎么做？暴力法哪有问题？怎么优化？为什么选了这个算法就能够优化？为什么这种算法要用这种数据结构来实现？

更多题解能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858…。目前曾经 36K+ star 啦。

关注公众号力扣加加，致力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你辨认套路，高效刷题。