Peiqin Lin's Homepage

Interview

Math

Linear Algebra

  1. 计算三个稠密矩阵 A,B,C 的乘积 ABC ,假设三个矩阵的尺寸分别为 m∗n，n∗p，p∗q，且 m <n < p < q，计算顺序效率最高的是 (AB)C 还是 A(BC)？

    答：在 (AB)C 中，m∗n 的矩阵 A 和 n∗p 的矩阵 B 的乘积，得到 m∗p 的矩阵 AB ，而 A∗B 的每个元素需要 n 次乘法和 n-1 次加法，忽略加法，共需要 m∗n∗p 次乘法运算。同样情况分析 AB 之后再乘以 C 时的情况，共需要 m∗p∗q 次乘法运算。因此， (AB)C 需要的乘法次数是 m∗n∗p+m∗p∗q 。同理分析 C 选项 A (BC) 需要的乘法次数是 n∗p∗q+m∗n∗q。

  2. 给一个3*3的矩阵，求 row-wise cosine similarity

    答：

     import numpy as np
    
 X = np.random.randn(3, 3)
    
 norms = np.linalg.norm(X, axis=1, keepdims=True) + 1e-8  # shape (3,1)
    
 # 归一化矩阵，使每行向量单位化
 X_normalized = X / norms
    
 # 计算行向量之间的余弦相似度（相当于点积）
 cosine_sim = X_normalized @ X_normalized.T

Probability and Statistics

  1. 给一枚硬币，但扔出正反的概率未知，如何得到等概率的二元随机数？

    答：扔两次，00、11 时无输出重扔，01 输出 0，10 输出 1。

  2. 抛的硬币直到连续出现两次正面为止，平均要扔多少次？

    答：用马尔可夫链，可做图求解递归方程。

    假定扔出正面 (H) 的概率为 p，扔出反面 (T) 的概率为 1 - p。我们需要扔出连续 2 个 H。在整个过程有这么几种状态：

    a. 当前连续 0 个正面（0H）；

    b. 当前连续 1 个正面（1H）；

    c. 当前连续 2 个正面（2H）。

    如果当前是 0H，那么 p 的概率，下一个状态是 1H；1 - p 的概率维持在 0H。

    如果当前是 1H，那么 p 的概率，下一个状态为 2H（达到条件，任务完成）；1 - p 的概率回到 0H。

    假设期望 x 次后，得到 2H，则有 \(x = (1 − p)(1 + x) + p^2 × 2 + p(1 − p)(2 + x)\)，可解得 x = 6。

  3. 一枚不均匀硬币，抛了 100 次，有 70 次朝上，第 101 次朝上的概率是多少，公式是如何推导？

    答：7/10。二项分布的极大似然估计，可参考此链接。

  4. 两个人轮流抛硬币，规定第一个抛出正面的人可以吃到苹果，请问先抛的人能吃到苹果的概率多大？

    答：先抛的人吃到苹果的概率：\(1/2 + 1/2^3 + 1/2^5 + ...\)，求得结果为 \(2/3\)。另一种解法是设先抛先吃的概率为 \(p_1\)， 后抛先吃的概率为 \(p_2\)，有：\(p_1 = 1/2 + 1/2 * p_2\) 且 \(p_1 + p_2 = 1\)，解方程可得，\(p_1 = 2/3\)。如果题目说是只抛一次的话，则概率为 \(1/2\)。

  5. 如何用一个骰子等概率地生成 1 到 7 的随机数？

    答：将一个筛子扔两次可以得到 36 种组合（进制思维），每五种组合代表一个数字，剩下的一种表示重扔。

  6. 一个骰子，6 面，1 个面是 1， 2 个面是 2， 3 个面是 3， 问平均掷多少次能使 1、2、3 都至少出现一次？

    答：链接

  7. 假设有某种病毒，每个病毒每秒钟会以 1/3 的概率分裂成两个病毒，1/3 的概率不分裂（还是一个），1/3 的概率消亡（变成 0 个）。在最初时刻，玻璃罩中有一个病毒，那么最终玻璃罩内没有活着的病毒概率是多大？

    答：链接

  8. 一米长的绳子，随机剪两刀，最长的一段有多长？

    答：假设三段的长度从小到大依次为 a，a + b，a + b + c，并且满足 a + a + b + a + b + c = 3a + 2b + c = 1 以及 a > 0，b ≥ 0，c ≥ 0。

    则可以得到 a ≤ 1/3，b ≤ 1/2，c ≤ 1，不妨可以认为 a ∼ U(0, 2k)，b ∼ U(0, 3k)，c∼U(0, 6k)。

    绳子最长的一段的期望为 k + 1.5k + 3k = 5.5k，绳子长度的期望为 3k + 3k + 3k = 9k。因为 9k = 1，所以 5.5k = 11/18 = 0.61111。

  9. 一根绳子切成三段，组成三角形的几率是多少？

    答：链接

  10. 假设一段公路上，1 小时内有汽车经过的概率为96%，那么，30分钟内有汽车经过的概率为？

    答：一小时有车的概率 = 1 - 一小时没车的概率 = 1 - 两个半小时都没车的概率 = 1 - (1 - 半小时有车的概率)^2。

  11. 4个人，52张扑克牌，红桃 A 和黑桃 A 同时被一个人拿到的概率？

    答：解法一：C(1,4) * C(11,50) / C(13,52)，C(1,4) = 从四个人中任选 1 人为红桃 A + 黑桃 A，C(11,50) = 从剩余 50 张牌中抽取 11 张给指定人，C(13,52) = 从 52 张牌中随机抽取 13 张；

    解法二：对于抓到红桃 A 的人，再抓黑桃 A 的概率就是 12/51 = 4/17。

  12. 假设有一副被打乱的扑克牌，52 张，其中 13 张黑桃，一个人从这副牌里随机的抽牌，每次抽一张，并且不放回，假设在第X次抽牌的时候，第一次抽到黑桃。请问 X 的数学期望是多少?

    答：链接

  13. 三个人告诉你深圳下雨了，每个人说谎概率是1/3，那么深圳下雨概率是多少?

    答：8/9。

  14. 幼儿园 10 个小朋友排成一列，其中 3 个小朋友是女孩，求女孩排在一起的概率？

    答：所有人排列是 10!，三个小女孩看做整体排列是 8!，三个小女孩排列是 3!，最后结果就是 (8! * 3!) / 10! = 1/15。

  15. 村长带着 4 对父子参加爸爸去哪儿第三季第二站某村庄的拍摄。村里为了保护小孩不被拐走有个前年的规矩，那就是吃饭的时候小孩左右只能是其他小孩或者自己的父母。那么 4 对父子在圆桌上共有几种坐法？

    答：链接

  16. 一个点用偶数步从原点出发回到原点有几种走法？

    答：链接

  17. 频率派概率和贝叶斯概率有什么区别？

    答：频率派概率是最大似然估计，贝叶斯概率是最大后验估计。频率派从自然角度出发，直接为事件建模，即事件 A 在独立重复试验中发生的频率趋于概率 p。贝叶斯派则认为概率是不确定的，需要结合先验概率和似然概率来得到后验概率。随着数据量的增加，参数分布会向数据靠拢，先验的影响越来越小。

  18. 先验概率是什么？后验概率是什么？

    答：\(p(\theta \| x)=\frac{p(x \| \theta)p(\theta)}{p(x)}\)。\(x\) 为观察得到的数据（结果），\(\theta\) 为决定数据分布的参数（原因），\(p(\theta \| x)\) 为后验分布，\(p(\theta)\) 为先验分布，\(p(x \| \theta)\) 为似然。

  19. 高维空间下的点有什么特点？

    答：

    • 随着维度升高，点的分布会变得稀疏，任意两点的距离会变大。
    • 距离会变得差不多。距离的相对方差为 1/d，d 为维度，随着维度升高，方差趋于 0。
    • 集中在表面。从低维推到高维空间，体积会越来越由表面附近区域贡献。
    • 几乎正交

  20. 为什么样本方差（sample variance）的分母（denominator）是 \(n - 1\)？

    答：如果期望已知，分母就是 \(n\)，如果未知，分母是 \(n - 1\) 是为了保证方差的估计是无偏的（unbiased）。如果直接使用 \(n\) 为分母作为估计，那么会倾向于低估方差（可用数学方法证明），所以为了正确的估计方差，所以可以把原先的估计值稍微放大一点，即把分母 \(n\) 改为 \(n - 1\)。

    这里也可以用自由度（随机变量中可以同时自由随机变化的变量数目，Degree of Freedom）的角度进行分析。对于 \(n\) 个样本，由于已经根据这些样本估计了样本均值，因此只剩下 \(n - 1\) 个样本的值是可以变化的。换句话说，样本中原有的 \(n\) 个自由度，有一个被分配给计算样本均值，剩下自由度即为 \(n - 1\)，所以用 \(n - 1\) 作为分母来计算样本方差。

  21. 给定一个 0 到 1 的均匀分布，如何近似地生成一个标准正态分布。即用 numpy.random.uniform() 这个函数， 得到 numpy.random.normal()？

    答：本题考点为中心极限定理（Central Limit Theorems）和均匀分布。中心极限定理即一组相互独立的随机变量的均值符合正态分布。

    np.random.uniform()生成的是 (0, 1) 之间均匀分布的随机数，则2 * np.random.uniform() - 1生成的是 (-1, 1) 之间均匀分布的随机数。

    已知 U(a, b) 方差是 (a - b)^2 / 12，则含有 n 个样本的样本均值的方差是 (a - b)^2 / 12 / n。代码如下：

    import numpy as np
normal_rv = 30 * np.mean(2 * np.random.uniform(size=300) - 1)

    具体步骤是先产生 300 个 (-1, 1) 随机变量，它们的均值的标准差是 1 / 30，要得到标准正态分布，所以要乘以 30。

  22. 请解释协方差矩阵的含义

    答：协方差矩阵描述多变量间的线性关系，矩阵的每个元素代表两个变量的协方差。

  23. 什么是点估计，什么是区间估计？

    答：点估计是预测参数的值，区间估计是预测参数所处的区间。

  24. 什么是置信区间，什么是置信水平/置信度？

    答：置信区间是一个带着置信度的估计区间。若置信区间为 \([a, b]\)，则置信水平 Y% 表示 \(P(a < \mu < b) = Y%\)。常见的置信度为 95%（\(2\sigma\)），95% 置信度表示的是 100 次区间估计，其中约有 95 次区间估计得到的区间结果包含正确的参数值。

    根据大数定律和中心极限定律，样本均值 \(M \sim N(\mu, \sigma^2/n)\)，其中 \(\mu\) 为抽样总体分布期望，\(\sigma^2\) 为抽样总体分布方差，\(n\) 为样本数目。

    求置信区间的方式是先计算抽样样本的均值和方差，然后再根据设置的置信区间查表就可以得到置信区间的上下界。

  25. 什么是卡方检验？

    答：卡方检验就是统计样本的实际观测值与理论推断值之间的偏离程度，实际观测值与理论推断值之间的偏离程度就决定卡方值的大小，如果卡方值越大，二者偏差程度越大；反之，二者偏差越小；若两个值完全相等时，卡方值就为0，表明理论值完全符合。

  26. 蒲丰投针问题

    答：链接

  27. 中餐馆过程

    答：链接

Calculus and Optimization

  1. 一阶优化和二阶优化对应的矩阵？

    一阶对应 Jacobian 矩阵，二阶对应 Hessian 矩阵。当矩阵正定（positive definite），梯度为 0 处为极小值。

  2. 深度学习为什么不用二阶优化？

    答：有些方法可用，但总体不适用。原因：计算量大，训练慢；求导复杂；深度学习不需要高精度解；稳定性差。

  3. 什么是 Jensen 不等式？

    答：链接

Information Theory

  1. 互信息是什么？

    答：\(I(X; Y) = \sum_{y \in Y}\sum_{x \in X} {p(x,y)log{\frac{p(x,y)}{p(x)p(y)}}}\)。当变量相互独立时，互信息为 0。

  2. KL 散度和交叉熵的区别？

    答：自信息（一个事件的信息量）：\(I(x)=-logP(x)\)；

    信息熵（一个分布的信息量）：\(H(x)=E_{X \sim P}[I(x)]=-E_{X \sim P}[P(x)]\)；

    交叉熵（在给定的真实分布下，使用非真实分布所指定的策略需要的代价）：\(-\sum_{k=1}^N{p_klog_2{q_k}}\)；

    交叉熵越低，策略越好，当交叉熵 = 信息熵，表示使用了真实分布；

    相对熵 / KL 散度（两个分布之间的差异）：\(KL(f(x) \| g(x))=\sum_{x \in X} {f(x) * log_2{\frac{f(x)}{g(x)}}}\)；

    相对熵 = 交叉熵 - 信息熵。

  3. 为什么 KL 散度不对称？

    答：KL 散度（Kullback–Leibler Divergence）不对称的根本原因在于其定义中的对数函数位置（分子分母位置）的非对称性。它本质上是一个“相对熵”：衡量一个分布在用另一个分布进行近似时，所造成的信息损失。

Discrete Mathematics

  1. 有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？

    答：可以用二进制编码的思维来解决。先对 1000 个瓶子以二进制数的形式进行编号，则至少需要十位的二进制数进行表示。再用这10只小白鼠分别对应二进制数的 10 个数位，让每只小白鼠喝下编号对应数位值为 1 的瓶子。最后根据小白鼠的死亡情况得到一个十位二进制数，编号与其相等的瓶子里面有毒药。

  2. 1000 桶水，其中一桶有毒，猪喝毒水后会在 15 分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？

    答：由于一只猪总共有五种状态，所以可以用五进制的方法解决，将 1000桶水表示成五进制至少需要 5 位，所以至少需要五头猪。

  3. 1000 桶水中两桶有毒，猪喝毒水后会在 15 分钟内死去，想用一个小时找到毒水，至少需要几只猪？如何实现？

    答：从理论上来讲，1000 桶水两桶有毒，有 499500 种状态，而一头猪有 5 种状态，求解 5^l > 499500，求得 l > 8.15，所以 9 只猪就可以找到毒水：

    a. 我们先把1000桶水分为10组，每只猪试验一组，一组空白；

    b. 如果只有一只猪死，那么说明两桶毒水都在那 100 桶水中，再把这 100 桶水分为 10 组，剩下的 9 只猪试验 9 组，另外 10 桶不实验，这样问题可一步一步缩小；

    c. 如果有两只猪死，则说明有两组 100 桶水各有一桶毒水，每组用 3 头猪即可实验。

  4. 一个村子里有很多户人家，每家都养了一条狗。现在发现村子里面出现了 n 只疯狗，村里规定，谁要是发现了自己的狗是疯狗，就要将自己的狗枪毙。但问题是，村子里面的人只能看出别人家的狗是不是疯狗，而不能看出自己的狗是不是疯的，如果看出别人家的狗是疯狗，也不能告诉别人。于是大家开始观察，第一天晚上，没有枪声，第二天晚上，没有枪声，直到第 n 天晚上，这 n 只狗才被同时枪毙，请问这是为什么？

    答：具体分析流程如下：

    a. 首先从只有一条疯狗分析起，如果只有一条疯狗，那么疯狗的主人在第 1 天就会发现其他家庭一只疯狗都没有，从而枪毙自己家的狗；

    b. 如果有两条疯狗，那么拥有疯狗的家庭在第一天由于看到别人家有疯狗，就不会枪毙自己家的狗，但发现第一晚没人枪毙自己的狗后，他会知道村子里有两条疯狗，其中一条就是自己的。实际上，整个村子的人都会在第一晚没人枪毙自己的狗后，知道整个村子至少有两条疯狗；

    c. 继续分析，如果第二晚还没有枪声，那说明拥有疯狗的人都看到了至少两条疯狗，所以他不会认为自己拥有疯狗，但经过没有枪声的第二晚后，全村人便达成了村子至少有三条疯狗的事实；

    d. 同理可得，拥有疯狗的家庭由于能看到 n - 1 条狗，他需要 n 天才能判断村子里至少有 n 条疯狗，其中一条就是自己家的狗，从而在第 n 天晚上枪毙自己家的狗。

  5. 五个同事决定计算他们的平均工资，在大家互相不告诉薪水的情况下，如何才能做到这一点？

    答：这道题的方法有很多，比如有：

    a. 每个人把自己的工资随意拆成四个数的和，分别把四个数字告诉自己以外的四个人；每个人手里收到四个数字，加起来，报出；五个人的数字相加，即可得到五个人的总收入，除以5得到平均工资；

    b. 找个计算器，叫第一个人输入一个巨大的不规则的数，然后把自己的收入加上去，之后依次传给其他人，每人都把自己的收入加上之前的数。最后传回第一个人。第一个人再把最后的总和减去他选中的那个不规则数，然后除以人数，即可得到大家的平均。

  6. 圆桌上有 1 到 1000 号，1 号右手边是 2 号，左手边是 1000 号。1 号开枪打死 2 号，把枪交给 3 号，3 号打死 4 号交给5号。。999 号打死 1000 号后把枪交给 1 号，继续循环。最后留下来的是几号？

    答：约瑟夫环问题，套公式 \(f(n) = 2(n - 2^{log_2n}) + 1\) 直接得到结果为 977。

  7. 一幢 200 层的大楼，给你两个鸡蛋。如果在第 n 层扔下鸡蛋，鸡蛋不碎，那么从前 n-1 层扔鸡蛋都不碎。这两只鸡蛋一模一样，不碎的话可以扔无数次。已知鸡蛋在 0 层扔不会碎。提出一个策略，要保证能测出鸡蛋恰好会碎的楼层，并使此策略在最坏情况下所扔次数最少？

    答：这是一道非常经典的面试题，我们用两种方法来解决：

    a. 分析法：对于每一次扔鸡蛋，都可以看作是一次决策，所以最终扔的方案应该是构成一棵决策树，问题就可以转换成求最矮决策树的高度。假设第一次扔的楼层是第 k 层楼，则碎子树的高度为 k - 1，如果第一次扔鸡蛋没碎，则设第二次扔的高度为 m，则对于 m 来讲，其碎子树高度为 m - k - 1，相对根节点高度则为 m - k。由于要尽可能保证子树的高度一致，所以得 m - k = k - 1，故可得第二次扔的高度要比前一次高 k - 1 层。从而得到方程 k(k + 1) / 2 = 200，从而解得高度为 14；

    b. 动态规划法：这道题是很经典的动态规划问题，设楼层次数为 n，我们可以得到状态转移方程f(n) = min(max(k-1, f(n - k))) + 1 (0 < k <= n)，如果我们再加入鸡蛋数目变量 m，则状态转移方程为f(n, m) = min(max(f(k - 1, m - 1), f(n - k, m))) + 1 (0 < k <= n)。

  8. 16 个硬币，A 和 B 轮流拿走一些，每次拿走的个数只能是 1，2，4 中的一个数。谁最后拿硬币谁输。请问：A 或 B 有无策略保证自己赢？

    答：B 可以保证自己赢。 如果 A 拿 1 个，则 B 拿2个； 如果 A 拿 2 个，则 B 拿 1 个； 如果 A拿 4 个，则 B 拿 2 个。这样每次 AB 加起来都是 3 或者 6，所以最后会剩下 1 个或 4 个。 如果是 1 个则 A 直接输了； 如果剩下 4 个，A 全拿则输了，如果不全拿，B继续采取上面的策略，最后还是剩下 1 个，还是 A 输。

  9. Nim 问题?

    答：必败态当且仅当所有堆硬币的数量都异或起来结果为 0。

  10. 海盗博弈

    答：链接1、链接2、链接3

  11. 五个囚犯先后从100颗绿豆中抓绿豆。抓得最多和最少的人将被处死，不能交流，可以摸出剩下绿豆的数量，谁的存活几率最大？

    答：链接

  12. 三个极度嫉妒的人分一个蛋糕，采用什么策略，能让三人都觉得公平？

    答：链接

  13. 有 5 个直线排列的洞，兔子每天换一个相邻的洞，每天插一次，怎样做一定能找到兔子，次数不限。

    答：第一天，守住第二个洞，没有的话，第二天还守住第二个洞，还没有的话，一二洞可排除，兔子前两天一定不会在一二两个洞，第三天检查第三个洞，如果没有，此时，兔子只可能在第二四五三个洞，第四天检查第四个洞，如果还没有，说明只可能在一三五三个洞，第五天还检查第四个洞，如果没有的话，说明兔子不可能在第四五个洞，也不可能在第一三个洞，只可能在第二个洞，第六天检查第三个洞，如果没有，第七天一定可以在第二个洞里抓到它的。

  14. 64 匹马，8 个赛道，找出跑得最快的 4 匹马，至少比赛几场？

    答：链接

  15. 有 8 个台球，其中一个比其他的 7 个都要重一些。如果仅仅是使用天平而不称出具体的重量，请问最少几次能找出那个最重的台球？

    答：2 次。把所有的球分成 3 组，其中 2 组是 3 个球，最后一组是两个球。首先，把 3 个球的两组放在天平上。如果其中一方比较重，把偏重的那一组球任意拿出来两个放在天平上。如果两组球一样重，那就把剩下的 2 个球放在天平上称重。

  16. 有 n 名球员参加比赛，第一轮抽签两两对决，如果 n 为奇数，则剩下一人轮空，后面的轮次采取类似做法。问总共有几场比赛？

    答：因为总共要淘汰 n - 1 人，所以比赛场数为 n - 1 场。

  17. 一瓶可乐两元钱，喝完后两个空瓶可以换一瓶可乐，假设你有40块，请问你最多可以喝到几瓶汽水？

    答：此题与上题类似，每一次换可乐之后都会损失一个瓶盖，所以 20 瓶可乐可以换到 19 瓶可乐，因此总共可以可以喝到 39 瓶可乐。如果开放借瓶盖的话，由于最后我们只剩一个瓶盖，所以最多只能借一个，而且只有当可乐数不是 2 的幂的时候借，因此，如果可以借的话总共可以喝 40 瓶可乐。

  18. 0， 6， 24，60， 120，（）?

    答：0=0*1*2；6=1*2*3；24=2*3*4；60=3*4*5；120=4*5*6；210=5*6*7。

  19. 黑色硬币问题

    答：链接

  20. 难铺的瓷砖

    答：链接

  21. 共 10 瓶药丸。（1）其中一瓶每颗超重 10 毫克；（2）其中多瓶每颗超重 10 毫克。用最少称重数目给出错误的瓶号。

    答：（1）从 1 到 10 瓶，每瓶拿出 1、2、3、…、10 颗；（2） 从 1 到 10 瓶，每瓶各拿出 1、2、4、…、1024 颗。

  22. 捡麦穗问题

    答：链接

  23. 鹰鸽博弈

    答：链接

Algorithm

  1. KSum

    答：KSum 问题

    Two Sum：使用哈希表记录已访问数字及其索引，遍历过程中查找 target - nums[i] 是否存在，时间复杂度 O(n)。

    Three Sum：对数组排序，固定一个数，剩余部分用双指针从两端逼近，跳过重复项，时间复杂度 O(n²)。

    Three Sum Closest：类似 3Sum，固定一个数后使用双指针，记录当前和与 target 的最小差值，更新最接近值。

    Three Sum Smaller：排序后，固定一个数，对剩余部分用双指针统计满足和小于 target 的组合数量。

    Four Sum：排序后，固定两个数，对剩余数组使用双指针。可看作 2Sum 在外面套两层循环，时间复杂度 O(n³)。

    General K-Sum：排序 + 递归：固定一个数，将 KSum 降维为 (K-1)Sum，最终降为 2Sum 使用双指针，时间复杂度 O(n^(k-1))。

    K-Sum Count（如 4Sum II）：利用哈希表预存前两数组的和，再在后两数组中查找 target - sum 是否存在，时间复杂度可降为 O(n²)。

    K-Sum II（输出所有组合）：不要求去重时，可使用回溯（DFS）遍历所有长度为 K 的组合，判断其和是否等于目标，适合小规模数据。

    K-Sum with Constraints（带上下界或特定索引）：
    在递归或双指针基础上加入条件判断或跳过无效值，需特别注意剪枝。

    K-Sum Variant in Interview（求组合数 / 有多少组）：
    可以用记忆化递归或多维动态规划（DP[k][i][j]），适合计数问题而非列出所有组合。

  2. 双指针

    答：一、对撞型双指针（Two Pointers Opposite Direction）

    • KSum
    • Container With Most Water：双指针从两端向内收缩，面积取决于较短的那条边，移动短板。时间复杂度：O(n)
    • Valid Palindrome：双指针从两端向中间检查字符是否匹配，跳过非字母数字字符。可扩展为“最多删一个字符”场景。

    二、滑动窗口型双指针（Same Direction）

    • Longest Substring Without Repeating Characters：右指针滑动加入字符，左指针缩小窗口直到无重复，哈希表记录字符位置。
    • Minimum Window Substring：右指针扩展直到满足条件，左指针缩小窗口以求最小子串，哈希计数维护需求。
    • Longest Subarray with Sum ≤ K（子数组和）：滑动窗口维护当前和，超过 K 就移动左指针。
    • Fruit Into Baskets（最多两个不同元素的最长子数组）：滑动窗口 + 哈希表记录窗口内元素类型，超过两种时左指针前移。

    三、快慢指针（Fast and Slow Pointers）

    • Linked List Cycle Detection（环检测）：快慢指针在链表上移动，相遇即有环。环入口可通过重新遍历得到。
    • Middle of Linked List：快指针一次两步，慢指针一步，快指针到末尾时，慢指针即为中点。
    • Remove N-th Node From End of List：快指针先走 n 步，然后快慢指针同时移动，快到末尾时慢指向待删除前一节点。

    四、区间类问题

    • Merge Intervals：先按起点排序，双指针或遍历合并重叠区间。
    • Subarray Sum Equals K：滑动窗口只适用于所有数为正；否则使用前缀和 + 哈希表。
    • Minimum Size Subarray Sum（连续和 ≥ S 的最短子数组）：滑动窗口右移扩展，左移收缩直到窗口内和 ≥ target，记录最短长度。

  3. 子数组

    答：一、固定功能类

    • 最大子数组和（Maximum Subarray）：Kadane 算法，维护当前最大和和全局最大和。
    • 最小子数组和：与最大子数组类似，取 min。
    • 最大子数组乘积（Maximum Product Subarray）：动态维护最大和最小乘积，因为负负得正。
    • 和为 K 的子数组数量（Subarray Sum Equals K）：前缀和 + 哈希表，记录前缀和出现次数。
    • 和为 K 的最长子数组：同样使用前缀和 + 哈希表，记录每个前缀和第一次出现的位置。

    二、滑动窗口类

    • 长度为 K 的最大平均值子数组：固定长度滑动窗口，维护当前窗口总和。
    • 不超过 K 的最大子数组和：前缀和 + 有序集合（如 TreeSet）维护前缀和，查找满足条件的最小前缀和。
    • 最多包含 K 个不同元素的最长子数组：变长滑动窗口 + 哈希表统计窗口内字符种类。
    • 最多有两个不同字符的最长子字符串：滑动窗口 + 哈希表记录字符频次。

    三、计数类

    • 和为 K 的连续子数组个数：前缀和 + 哈希表统计出现次数。
    • 等差子数组个数：枚举子数组判断是否等差，可使用 dp 优化。
    • 子数组最大值 - 最小值 ≤ K 的个数：单调队列维护区间最大最小值，变长滑动窗口。

    四、其他性质类

    • 最大升序子数组长度：一次遍历，记录连续严格递增序列长度。
    • 子数组最大和（二维扩展）：压缩二维子数组为一维，使用 Kadane 算法。
    • 最长山形子数组：从左到右和从右到左分别统计连续上升/下降序列，结合判断中心。
    • 最长平衡子数组（0 和 1 个数相同）：将 0 转为 -1，问题转为和为 0 的最长子数组，使用前缀和+哈希。

  4. 区间问题

    答：一、基础区间合并与排序

    • 合并区间（Merge Intervals）：将区间按起点排序，依次比较是否重叠并合并。
    • 插入区间（Insert Interval）：按位置插入新区间，遍历合并重叠部分。
    • 区间交集（Interval Intersection）：双指针遍历两个有序区间列表，找重叠区间。
    • 最少区间合并次数 / 合并后区间个数：排序 + 贪心合并，统计合并操作或最终区间数。

    二、覆盖与选择类

    • 用最少数量的区间覆盖整段区间：按起点排序，使用贪心策略选择右端最大值。
    • 用最少区间覆盖点集 / 时间段：按右端排序，每次选择能覆盖最多未覆盖点的区间。
    • 判断是否能用区间完全覆盖目标区间：贪心扫描，判断最大可达右端是否覆盖到终点。

    三、区间动态操作类

    • 区间更新 + 区间查询（如数值加减、最大最小值等）：线段树 / 树状数组 / 差分数组。
    • 区间加法，单点查询：使用前缀和或差分数组优化区间操作。
    • 区间异或 / 取反操作 + 查询：线段树支持 lazy propagation 或位运算。

    四、区间重叠与冲突检测类

    • 判断是否存在重叠区间：按起点排序，检查当前起点是否小于上一个区间的终点。
    • 会议室问题（最多需要几个会议室）：扫描线 / 最小堆维护当前会议的结束时间。
    • 区间调度问题（最多安排多少个互不重叠的区间）：贪心，按结束时间排序，每次选择最早结束的非重叠区间。
    • 最少区间移除使所有区间不重叠：贪心选择最多不重叠的区间，剩下的就是需要移除的。

    五、其他综合变种

    • 区间染色、区间合并维护颜色段数：线段树 + 标记合并逻辑。
    • 二维区间合并 / 查询（如矩形区域）：扫描线 + 树状数组/线段树 + 离散化。
    • 区间差值或重叠个数统计：差分数组 + 前缀和 或 扫描线算法。
    • 区间最长连续可用时间段：对不可用区间排序合并，剩余为可用时间段。

  5. 前缀和

    答：一维前缀和

    • 区间和快速查询（如 Leetcode 303）：构建前缀和数组 prefix[i+1] = sum(nums[0..i])，任意区间和为 prefix[r+1] - prefix[l]。
    • 固定大小窗口的最小/最大和：用前缀和快速计算任意长度为 k 的区间和，再遍历或滑动窗口取最小/最大。
    • 子数组和为 k 的个数（Leetcode 560）：前缀和 + 哈希表统计 prefix[j] - prefix[i] == k 的出现次数。
    • 判断是否存在和为 k 的连续子数组（Leetcode 523）：计算前缀和并对 k 取模，若同一余数出现两次，则存在满足条件的子数组。
    • 最长和为 k 的子数组长度（Leetcode 325）：记录前缀和第一次出现的位置，遇到相同前缀和时计算长度取最大。

    二维前缀和（矩阵）

    • 矩阵区域和查询（Leetcode 304）：预处理二维前缀和 prefix[i][j]，查询时用 inclusion-exclusion 公式快速获取矩形和。
    • 最大子矩阵和（Leetcode 363）：枚举上下边界，将列压缩为一维数组，转化为一维最大子数组和问题 + 前缀和。
    • 统计满足条件的子矩阵个数：将二维压缩为一维后，用前缀和 + 哈希/树状数组处理子数组和满足条件的数量。

    前缀和与频率/计数统计

    • 区间内某值出现的次数：对每个字符/数值构建出现次数的前缀和数组，查询时用 cnt[r+1] - cnt[l] 获取某值出现频率。
    • 最多变 k 次后使所有数相等（Leetcode 1838）：排序 + 前缀和 + 双指针，维护区间和与最大值的关系判断是否满足变化次数。
    • 子数组的平均值比较：用前缀和计算子数组和避免重复计算平均值，再转为乘法避免浮点误差。

    特殊技巧：差分、异或前缀和

    • 差分数组（Leetcode 370）：通过差分数组只更新区间端点，最后用前缀和还原整体变化。
    • 异或前缀和（Leetcode 1310）：异或满足结合律，使用 prefix[i] = A[0]^...^A[i]，子数组异或为 prefix[r] ^ prefix[l-1]。
    • 字符串中子串统计：构建每个字符的出现次数前缀和，查询区间内特定字符频率。

    综合技巧与高难度题

    • 子矩阵和为目标的个数（Leetcode 1074）：枚举行区间压缩为一维数组，然后用子数组前缀和 + 哈希统计目标值出现次数。
    • 最大连续 1 的数量（允许翻转 k 个 0）：用前缀和记录 0 的累计个数，滑动窗口找到最多翻转 k 次后的最长区间。
    • 滑动窗口平均值/中位数优化：前缀和用于快速计算平均值，配合单调队列或多重集合求中位数。

  6. 并查集

    答：

    • 省份数量：并查集判断连通块数。
    • 岛屿数量：并查集合并相邻陆地格子。
    • 冗余连接：并查集找成环的边。
    • 连通网络的操作次数：统计冗余边与连通块数量。
    • 等式方程的可满足性：合并等式再判断不等式是否冲突。
    • 除法求值：带权并查集维护比值。
    • 账户合并：邮箱为节点并查集合并账户。
    • 交换字符串中的元素：归并交换块后排序。
    • 寻找图中是否存在路径：并查集判断是否连通。
    • 字典序最小等效字符串：并查集维护字典序最小根。
    • 最长连续序列：连续数归为同一集合。
    • 相似字符串组：相似字符串构图归类。
    • 冗余连接 II：有向图中判断成树条件。
    • 由斜杠划分区域：每格四块并查集合并内部与相邻块。
    • 最小时间传递信息：Kruskal 过程判断连通。

  7. 链表

    答：一、基础操作类

    • 反转链表（Reverse Linked List）：迭代/递归反转指针方向，常见面试题。
    • 合并两个有序链表：双指针逐节点比较；递归也可实现。
    • 给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该节点：如果待删节点不是尾节点，可以通过将待删节点的下一个节点的值和指针复制过来，然后删除下一个节点来实现 O(1) 删除。如果待删节点是尾节点，且只有头指针，不知道前驱节点，无法在 O(1) 时间内删除该节点。只能遍历找到前驱，时间是 O(n)。
    • 删除链表中的节点（如删除倒数第 n 个节点）：快慢指针找到待删节点的前一个节点。
    • 删除排序链表中的重复元素（只保留一个）：遍历有序链表，当前节点与下一个节点值相同则跳过下一个节点，保留第一个重复节点。
    • 删除排序链表中的所有重复元素（重复节点全部删除）：遍历有序链表，遇到重复节点全部跳过，只保留不重复的节点。
    • 删除无序链表中的重复元素：使用哈希集合记录出现过的值，遍历链表时删除已经出现过的节点。
    • 删除无序链表中所有重复元素（只保留无重复元素的节点）：先遍历统计每个元素出现次数，再遍历链表删除所有出现次数大于1的节点。
    • 删除链表中指定值的所有节点：遍历链表，删除值等于目标值的节点。
    • 删除链表中重复的连续节点（保留第一个节点）：只删除连续重复的后续节点，保留第一个出现节点。
    • 删除环形链表中的重复元素：先检测环，确定环入口，再处理环内重复元素。
    • 递归删除排序链表中的重复元素：使用递归方法实现有序链表中重复元素的删除。
    • 双指针法删除排序链表重复元素：快慢指针遍历，慢指针记录唯一节点，快指针跳过重复节点。
    • 删除链表重复元素后保持链表结构的稳定性：确保删除过程中链表链接正确，避免断链或遗漏节点。
    • 查找链表中点：快慢指针，快走两步、慢走一步。

    二、循环与判断类

    • 链表是否有环：可以使用快慢指针（Floyd判圈算法），慢指针每次走一步，快指针每次走两步，如果链表有环，那么当快慢指针同时进入环的时候，每次快指针都会在慢指针后追一步，所以如果环长为 r，最多 r - 1次，两者就会相遇。时间复杂度为 O(n)，空间复杂度为 O(1)。
    • 链表环的入口节点：设链表从头到环入口的长度为 a；环入口到相遇点的距离为 b；环的总长度为 r；k 为快指针多走的圈数。在它们相遇时，快指针走的总路程是慢指针的两倍：快指针走的距离 = 慢指针走的距离 + n 圈环长（n 是正整数） 2(a + b) = a + b + k * r ⇒ a + b = k * r。所以：a = k * r - b。相遇后一指针回头从头出发走 a 步，另一指针从相遇点出发，同样速度，则会弥补 r - b 到入口，并绕 k - 1 圈，因此再次相遇点即入口。
    • 判断两个链表是否相交：尾节点是否相同；或长度对齐后同时遍历。
    • 找到两个链表的交点：双指针分别遍历两链表，尾对接。

    三、翻转与重排类

    • k 个一组翻转链表：递归或迭代，每次翻转 k 个节点。
    • 按奇偶位置重排链表：奇偶指针分别连接各自序列，最后拼接。
    • 重排链表（L0→Ln→L1→Ln-1→…）：中点+反转后半+合并两个链表。

    四、复杂结构类

    • 复制带随机指针的链表：三步法（原节点后插拷贝 → 建 random → 拆分）。
    • 多级双向链表扁平化：递归处理 child 指针，调整 prev/next。

    五、排序与划分类

    • 链表排序（归并排序）：快慢指针找中点 + 递归归并。
    • 分隔链表（小于 x 放前面）：构造两个链表（小于和不小于），最后拼接。

    六、数字处理类

    • 两个链表表示的数字相加：从低位往高位逐位相加，处理进位。
    • 链表相加 II（高位在前）：用栈反转顺序或递归模拟。

    七、其他技巧类

    • LRU 缓存机制（链表 + 哈希表）：使用双向链表 + 哈希表快速定位和移动节点。
    • 将二叉搜索树转为排序双向链表：中序遍历 + 链接节点。
    • 设计单链表/双链表数据结构（LeetCode 707）：实现基本的 add/delete/get 接口，注意边界处理。

  8. 栈

    答：

    • 有效的括号：利用栈匹配左右括号，检测括号是否成对出现且顺序正确。
    • 最小栈：设计一个支持 push、pop、top 操作，并能在O(1)时间内检索到最小元素的栈。
    • 用栈实现队列：用两个栈模拟队列的先进先出行为。
    • 逆波兰表达式求值：使用栈计算后缀表达式的值。（前缀、中缀、后缀表达式相关）
    • 接雨水：用栈记录边界，计算能接多少雨水。
    • 滑动窗口最大值：用双端队列（特殊栈）维护滑动窗口最大元素。
    • 基本计算器：用栈处理带括号的表达式计算。
    • 栈排序：只用一个额外栈实现对栈元素排序。
     stack = []
    
 # 入栈
 stack.append(1)
 stack.append(2)
    
 # 出栈
 top = stack.pop()
    
 # 查看栈顶元素（不弹出）
 top_peek = stack[-1]
    
 # 判断栈是否为空
 is_empty = len(stack) == 0

  9. 单调栈

    答：栈内保持单调（递增 / 递减）；入栈前，弹出不满足单调性的元素；栈顶元素就是当前元素的最近更小（或更大）元素。应用例子：柱状图中最大的矩形面积：用单调栈维护高度，计算最大矩形面积。

     def monotonic_stack(nums):
     stack = []  # 栈里存索引
     res = [-1] * len(nums)  # 记录每个元素左边最近小于它的元素索引

     for i, num in enumerate(nums):
         while stack and nums[stack[-1]] >= num:
             stack.pop()
         if stack:
             res[i] = stack[-1]  # 栈顶就是左边最近更小的元素索引
         stack.append(i)  # 当前元素入栈
     return res

  10. 队列

    答：

    • 用栈实现队列：用两个栈模拟队列的入队和出队操作，stact_in 负责入队，stack_out 负责出队。入队：直接压入 stact_in，出队：如果 stack_out 为空，就把 stack_in 所有元素弹出并压入 stack_out（反转顺序），然后从 stack_out 弹出或读取元素。
    • 滑动窗口最大值：用双端队列维护当前窗口的最大元素，实现高效查询。
    • 循环队列设计：实现固定大小的循环队列，支持入队、出队及满/空状态判断。
    • 最近请求次数（计数器设计）：用队列记录请求时间，统计指定时间窗口内的请求数。
    • 数据流中的中位数：使用两个堆模拟双端队列，支持动态维护中位数。
    • 课程表 BFS 拓扑排序：用队列实现广度优先搜索，检测是否有环。
    • 短est路径（BFS）：在无权图中用队列实现最短路径搜索。
    • 滑动窗口平均值：用队列维护窗口元素，实现动态均值计算。
    • 聊天室限流器：用队列控制单位时间内的请求频率。
    • 猫狗队列：用两个队列分别存储猫和狗，实现按顺序取出最早进入的宠物。
    from collections import deque
    
queue = deque()
    
# 入队
queue.append('a')
queue.append('b')
    
# 出队
first = queue.popleft()  # 'a'
    
# 查看队首元素
peek = queue[0]
    
# 判断是否为空
empty = not queue

    用 list 实现出队first = queue.pop(0)时间复杂度为 O(n)，因此不推荐。 优先队列用 heapq 实现

  11. 树

    答：

    • 二叉树的前序、中序、后序遍历：用递归/迭代/栈实现节点访问顺序。
    • 二叉树的层序遍历（BFS）：用队列实现按层访问所有节点。
    • 判断二叉树是否是平衡二叉树：递归计算子树高度并判断平衡性。
    • 找到二叉树的最近公共祖先（LCA）：递归或借助父指针寻找公共祖先。
    • 二叉搜索树（BST）插入和查找：利用BST性质快速定位节点。
    • 树的最大深度和最小深度计算：递归遍历叶节点计算深度。
    • N叉树的遍历：扩展二叉树遍历思路，适应多子节点结构。
    • 求树中两个节点的距离：利用LCA和深度信息计算距离。
    • 判断一棵树是否是子树：递归比较结构和节点值。
    • 树的序列化与反序列化：将树结构转为字符串及还原树形结构。

  12. 堆

    答：堆只保证父子节点的局部有序，不保证整个树有序。

    删除节点 O(logn)：先将最后一个元素移到堆顶，再从堆顶开始，将该节点与其左右子节点中较小（大）的一个进行比较交换,直到满足最小（大）堆的性质

    用 Python 的 heapq 库实现，默认为小顶堆；实现最大堆时可将数值取负。

    import heapq
    
heap = []
heapq.heapify(heap)  # 将列表转为堆结构（可省略，空列表即堆）
heapq.heappush(heap, item) # 往堆中插入一个元素，时间复杂度：O(log N)
min_item = heapq.heappop(heap) #弹出并返回最小元素，时间复杂度：O(log N)
min_item = heap[0] # O(1) 时间获取最小元素
heapq.nsmallest(k, iterable) # 获取最小的 K 个元素
heapq.nlargest(k, iterable) # 获取最大的 K 个元素
    • 前 K 个高频元素：使用小顶堆（优先队列）维护出现频率最高的 K 个元素。
    • 合并 K 个有序链表：使用小顶堆维护每个链表的头节点，实现逐步合并。
    • 数组中第 K 大的元素：使用大小为 K 的小顶堆，维护当前最大的 K 个元素。
    • 数据流中的中位数：使用最大堆和最小堆分别存储数据流的左右两半，动态维护中位数。
    • 滑动窗口最大值：可用单调队列实现，但也可用最大堆维护当前窗口最大值（需处理过期元素）。
    • 寻找和最小的 K 对数字：在两个有序数组中，使用最小堆生成最小的 K 个数对。
    • 接雨水 II（二维）：使用最小堆从边界向内扩展，维护当前高度边界。
    • 区间合并类问题（如会议室问题）**：使用最小堆维护当前会议室的结束时间。
    • 石头碰撞问题：使用最大堆模拟石头之间的碰撞过程，取出最大两块进行处理。
    • 构建哈夫曼编码树：使用最小堆每次合并频率最小的两个节点，构建最优前缀树。

  13. Trie

    答：

    • 实现 Trie（前缀树）：使用字典或数组构建多叉树，支持 insert, search, startsWith 操作。
    • 替换词根（Leetcode 648）：将句子中的词替换为其词根；利用 Trie 存储所有词根，遍历句子中每个词，查找最短匹配词根。
    • 单词搜索 II（Leetcode 212）：在二维字符网格中找多个单词；构建 Trie 存储单词表，然后结合 DFS 和 Trie 剪枝遍历。
    • 添加与搜索单词（Leetcode 211）：支持通配符 ‘.’ 的词典查询；在 Trie 上做 DFS，遇到 ‘.’ 时递归尝试所有子节点。
    • 最大异或对（Leetcode 421）：给定整数数组，找最大异或值；用 Trie 按位（高到低）存储每个数字的二进制表示，寻找最大异或路径。
    • 回文对（Leetcode 336）：寻找两个单词拼接后为回文的组合；Trie 结合字符串反转和回文判定处理。
    • 前缀和统计（Leetcode 677）：实现 MapSum 类，支持 insert(key, val) 和 sum(prefix)；Trie 节点记录每个前缀的值和子树和。
    • 统计单词出现频率（面试类问题）：构造 Trie 并在每个叶节点或终止节点记录出现次数，实现高效统计。
    • 敏感词过滤器：构建 Trie 存储敏感词集合，配合 AC 自动机或双指针，进行文本过滤与替换。
    • DNA 序列查重（变种问题）：构建 Trie 存储基因序列（A/C/G/T），检测是否存在重复序列（如长度为 10 的重复子串）。

  14. 完全二叉树是什么？

    答：除了最后一层，所有层都必须被填满，且最后一层节点必须尽量靠左排列（因此二叉平衡树不一定是完全二叉树）。

  15. 二叉搜索树是什么？

    答：每个节点的值都满足：左子树 < 根节点 < 右子树。其中序遍历单调递增。

  16. 二叉平衡树是什么？

    答：二叉平衡树（Balanced Binary Tree）是对普通二叉搜索树（BST）的优化，目的是解决 BST 在极端情况下可能退化为链表（如连续插入有序数列）的问题，从而保证查找、插入、删除等操作的时间复杂度维持在 O(log n)。二叉平衡树要求任意节点的左右子树高度差控制在一定范围内（如 AVL 树是 ≤1，红黑树是最多两倍）。

  17. AVL 树是什么？

    答：AVL 树是一种自平衡的二叉搜索树（Binary Search Tree，BST），它在插入和删除节点时，能自动调整自身结构以保持树的“平衡”，从而保证查找、插入、删除操作的时间复杂度始终为 O(log n)。

  18. 红黑树是什么？

    答：红黑树性能要好于平衡二叉树。

    红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

    性质1. 节点是红色或黑色。

    性质2. 根节点是黑色。

    性质3 每个叶节点（NIL节点，空节点）是黑色的。

    性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

    性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

  19. B/B- 树是什么？

    答：B 树是一种自平衡的多路搜索树，是对二叉搜索树的推广，适合磁盘或大规模数据存储系统中高效读取。

    • 每个节点可以有多个键值（key）和子树指针
    • 所有键值按顺序排列
    • 每个节点的子树数在一个范围内（阶的约束）
    • 所有叶子节点在同一层
    • 查找路径短，I/O 次数少

    查找过程类似多路查找：从根节点开始，依次判断键值大小，决定走哪个子树，直到叶子或命中。

  20. B+ 树是什么？

    答：B+ 树是在 B 树基础上演化而来的，数据库系统中应用最广泛的索引结构。

    • 所有值只存在于叶子节点
    • 内部节点（非叶子）只存键，不存数据

    • 所有叶子节点之间用链表连接，天然支持范围查询

    • 更高的扇出（fan-out），因为内部节点更“轻”，树更矮 → 减少磁盘访问
    • 范围查找特别高效，只需找到区间起点，后续通过链表遍历即可

  21. 图的表示方法

    答：邻接表：每个节点维护一个列表，存储它所有相邻的节点。邻接矩阵：二维数组。

  22. 判断图存在环？

    答：无向图：深度遍历；并查集。 有向图：深度遍历；广度遍历/拓扑排序：时间复杂度为 O(n＋e)。

  23. 最短路径算法及复杂度？

    答：Dijkstra 算法，是贪心算法，时间复杂度为 O(V^2)，如果是稀疏图，可用堆进行优化，时间复杂度为 O((V + E) lgV)；Floyd 算法，时间复杂度为 O(V^3)。

  24. 无向图最小生成树算法及复杂度？

    答：Prim 算法，是贪心算法，每一步从当前生成树出发，选择权值最小的边，并且这条边连接的是树内节点和树外节点，逐步扩展生成树，直到包含所有节点。时间复杂度 O(V^2)；Kruskal 算法，时间复杂度 O(ElgE)。

  25. KMP 算法

    答：KMP 算法

    1. 构建部分匹配表（next 数组）：next[i] 记录每个位置之前 pattern[0:i] 的前缀后缀最长公共长度。

    2. 主串匹配时使用 next 数组跳过重复匹配。

    时间复杂度为 O(m + n)

  26. Edit Distance

    答：Edit Distance

  27. 正则表达式

  28. 了解 Hamming 距离吗？

    答：两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

  29. 如何求两个数的二进制表示的 Hamming 距离？

    答：先求两个数的异或结果 res，再依次求 res 每一位与 1 与操作的结果，不为 0，则 Hamming 距离加一；每判断完一位，res 右移一位继续判断下一位。

  30. 哈希冲突

    答：开放地址法（当当前位置被占用时，寻找下一个可用位置；容易产生聚集现象，负载因子高时效率下降）：线性探测（从当前位置开始，逐个向后找）；二次探测（间隔逐步增大，避免连续冲突）；双重哈希（使用第二个哈希函数计算偏移。

    链地址法：每个哈希桶（地址）用一个链表（或其它结构）存储所有哈希到该地址的元素。需要额外的链表或结构，内存碎片。

    再哈希：当负载因子过高时，扩大哈希表，重新计算所有元素的哈希值。扩容代价较高。

  31. 排序

    答：冒泡排序：时间复杂度 O(n^2)，稳定

    插入排序：时间复杂度 O(n^2)，稳定

    选择排序：时间复杂度 O(n^2)，不稳定

    归并排序：时间复杂度 O(nlogn)，稳定

    基数排序：按位排序，从低位到高位依次进行分配和收集；稳定

    快速排序：时间复杂度 O(nlogn)，空间复杂度最好情况是 O(logn)，最坏情况可能达到 O(n),但平均情况是 O(logn)，不稳定

    希尔排序：插入排序的改进版本，其核心思想是先将整个待排序序列分割成若干个子序列分别进行直接插入排序,待整个序列基本有序时,再对全体记录进行一次直接插入排序。不稳定

    堆排序：堆排序包含两个主要步骤：建堆和排序。建堆过程：从最后一个非叶子节点开始，自上而下进行堆化。排序过程：每次将堆顶元素与末尾元素交换，并重新对剩余元素进行堆化。需要执行 n-1 次，每次堆化的时间复杂度为 O(logn)，因此排序阶段总的时间复杂度为 O(nlogn)。空间复杂度 O(1)，可原地排序，不稳定

    桶排序：时间复杂度 O(n)

  32. 原地排序与非原地排序？

    答：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。非原地排序就是要利用额外的数组。

  33. 数组最大最小值最优算法？

    答：链接

  34. 无序整数数组中找第 k 大的数？

    答：方法一：最小堆：建一个大小为 k 的最小堆。遍历数组，将元素加入堆中，如果堆大小超过 k，就弹出堆顶（最小元素）。最终堆顶就是第 k 大的数。时间复杂度：O(nlogk)，空间复杂度：O(k)

    方法二：快速选择（Quickselect），类似快速排序的分区思想（partition）；每次将数组划分为两个区间，选择一边递归；平均时间复杂度 O(n)，最坏 O(n²)。

    方法三：内置排序

  35. 从一个几乎排序好的数组中找出第 k 小的元素，时间复杂度尽量低。

    答：利用“插入排序”特性，数组接近有序，插入排序接近线性。也可以用快速选择算法，平均 O(n)。

  36. 在 n 个数中取最大的 k 个数，时间复杂度是？

    答：nlogk。堆的大小为 k，总共要调整 n 次。

  37. 有 10 个排好序的数据库，那么我要找整个的中位数，怎么找？

    答：最简单的思路是合并数据库，然后再定位长度，时间复杂度为 O(n)，空间复杂度是 O(n)；但实际上只需要借鉴这个合并的过程，当合并到中位数的时候输出中位数即可，时间复杂度为 O(n)，空间复杂度是 O(1)。这思路十分简单，但并不是最佳算法，有序数组让我们想到的会是二分查找，因此我们可以利用二分查找来使复杂度降至 O(logn)，具体可参考：

    a. https://www.douban.com/note/177571938/

    b. https://stackoverflow.com/questions/6182488/median-of-5-sorted-arrays

  38. 海量数据处理

    答：海量数据处理

  39. 汉诺塔时间复杂度？

    答：假设移动 n 个圆盘需要 f(n) 次移动

    首先考虑一个圆盘，只需一步就可以了 f(1) = 1 …… ①

    现在考虑 n 个圆盘，假设开始圆盘在 A 柱，可以先把 A 柱的上面 n - 1个圆盘移到 B，再将 A 剩下的一个移到 C，最后将 B 的 n - 1 个移到 C。总共需要 f(n) = 2f(n- 1) + 1 …… ②

    根据 ①② 两式，可求出 f(n) = 2^n - 1 所以 O(n) = 2^n

  40. 尾递归（Tail Call）有什么危害，如何避免？

    答：栈溢出（Stack Overflow）。尾递归事实上和循环是等价的。

  41. 背包问题

    答：01 背包问题

    完全背包问题

    物品冲突问题

  42. 农夫过河问题？

    答：链接

  43. 不用库函数求一个数的立方根？

    答：链接

  44. 二进制中 1 的个数？

    答：把一个整数减去 1，再和原整数做与运算，会把该整数最右边的 1 变成 0。那么一个整数的二进制表示中有多少个 1，就可以进行多少次这样的操作。具体解题思路可参见《剑指 Offer》。

  45. 数值的整数次方？

    答：链接

  46. 有两个未知整数，你可以不断询问某个数与这两个数的大小关系（每次询问一个数），该如何查找这两个数？

    答：链接

  47. 一群木板，一开始有一条线把它们固定在一条水平线上，现在抽掉这条线，有的木板往下掉落，有的木板位置上升，问怎么移动才能使移动距离最小，让它们继续在一条水平线上？

    答：中位数。

  48. 给定两个数，求他们无限次相加中第 k 小的数？

    答：链接

  49. 什么是水塘抽样？

    答：一种在数据量未知或数据流形式下，以等概率从 n 个元素中采样 k 个的算法，适用于内存受限的场景。

  50. 如何从数据流中以等概率选取一个元素（k=1）？

    答：初始化：result = None，遍历第 i 个元素时，以 1/i 的概率替换 result，所有元素最终被选中的概率都是 1/n。

  51. 如何扩展到选取 k 个元素？

    答：初始化：前 k 个元素入 reservoir，对第 i (>k) 个元素：以 k/i 的概率随机替换 reservoir 中的一个元素。

  52. 链表中如何随机返回一个节点？（单次遍历，O(1) 空间）

    答：遍历链表，对第 i 个节点，以 1/i 的概率更新当前候选节点，最终返回的节点是等概率选中的。

Computer Science

  1. 为什么要用时间复杂度来描述算法，而不是运行时间？

    答：操作系统调度，所以运行时间不一定相同。

  2. 死锁的条件

    答：a.互斥：某种资源一次只允许一个进程访问，即该资源一旦分配给某个进程，其他进程就不能再访问，直到该进程访问结束。 b.占有且等待：一个进程本身占有资源（一种或多种），同时还有资源未得到满足，正在等待其他进程释放该资源

    c.不可抢占：别人已经占有了某项资源，你不能因为自己也需要该资源，就去把别人的资源抢过来。

    d.循环等待：存在一个进程链，使得每个进程都占有下一个进程所需的至少一种资源。

  3. 死锁避免方法

    答：产生死锁需要四个条件，那么，只要这四个条件中至少有一个条件得不到满足，就不可能发生死锁了。

  4. 银行家算法

    答：链接

  5. 集线器和交换机有什么区别？

    答：集线器在物理层，所有端口是一个冲突域，交换机在数据链路层，每个端口是一个冲突域。

  6. 三次握手是怎样的？

    答：第一次握手：建立连接时，客户端发送 syn 包（syn = j）到服务器，并进入 SYN_SENT 状态，等服务器确认；

    第二次握手：服务器收到 syn 包，必须确认客户的 SYN（ack = j + 1），同时自己也发送一个 SYN 包（syn = k），即 SYN + ACK 包，此时服务器进入 SYN_RECV 状态；

    第三次握手：客户端收到服务器的 SYN + ACK 包，向服务器发送确认包 ACK (ack = k + 1），此包发送完毕，客户端和服务器进入 ESTABLISHED（TCP 连接成功）状态，完成三次握手。

  7. 四次挥手是怎样的？

    答：TCP 客户端发送一个 FIN，用来关闭客户到服务器的数据传送。

    服务器收到这个 FIN，它发回一个 ACK，确认序号为收到的序号加 1。和 SYN 一样，一个FIN 将占用一个序号。

    服务器关闭客户端的连接，发送一个 FIN 给客户端。

    客户端发回 ACK 报文确认，并将确认序号设置为收到序号加 1。

  8. 8 位二进制整型补码表示取值范围是？

    答：-2^32 到 2^32 - 1。补码中正负 0 统一用正 0 表示，所以负数多出一个数。

  9. count(1)、count(*) 和 count(列名) 的区别？

    答：链接

  10. 数据库的三级模式是什么？

    答：数据库领域公认的标准结构是三级模式结构，包括外模式、概念模式、内模式。

    用户级对应外模式。它是某个或某几个用户所看到的数据库的数据视图，是与某一应用有关的数据的逻辑表示。

    概念级对应概念模式（又称逻辑模式），反映了数据库的整体观。它是由数据库设计者综合所有用户的数据，按照统一的观点构造的全局逻辑结构，是对数据库中全部数据的逻辑结构和特征的总体描述，是所有用户的公共数据视图。

    物理级对应内模式（又称存储模式），反映了数据库的存储观。它是数据库中全体数据的内部表示或底层描述，它描述了数据在存储介质上的存储方式和物理结构，对应着实际存储在外存储介质上的数据库。

  11. 数据库三范式？

    答：链接

Programming

C/C++

  1. 字节对齐？

    答：先看以下程序：

    struct A{
    int    a;
    char   b;
    short  c;
};
struct B{
    char   b;
    int    a;
    short  c;
};

    已知 32 位机器上各数据类型的长度为：char 为 1 字节、short 为 2 字节、int 为 4 字节、long 为 4 字节、float 为 4 字节、double 为 8 字节。那么上面两个结构体大小如何呢？

    结果是：sizeof(strcut A) 值为 8；sizeof(struct B) 的值却是 12。

    结构体 A 中包含一个 4 字节的 int 数据，一个 1 字节 char 数据和一个 2 字节 short 数据；B 也一样。按理说 A 和 B大小应该都是 7 字节。之所以出现上述结果，就是因为编译器要对数据成员在空间上进行对齐。

    a.数据类型自身的对齐值：char 型数据自身对齐值为 1 字节，short 型数据为 2 字节，int / float 型为 4 字节，double 型为 8 字节。

    b.结构体或类的自身对齐值：其成员中自身对齐值最大的那个值。

    c.指定对齐值：#pragma pack (value) 时的指定对齐值 value。

    d.数据成员、结构体和类的有效对齐值：自身对齐值和指定对齐值中较小者，即有效对齐值 = min{自身对齐值，当前指定的 pack 值}。

  2. 面对对象的三大特性是什么？

    答：封装、继承和多态。

  3. 定义一个空类时，C++ 到底会默默为我们编写哪些函数？

    答：4 个函数：一个 default 构造函数、一个析构函数、一个 copy 构造函数、一个等号 “=” 重构函数。

  4. C++ 的构造函数可以是虚的嘛？析构函数呢？

    答：构造函数不能为虚函数，而析构函数可以且常常是虚函数。

  5. C++ 中的抽象类是什么？

    答：定义了纯虚函数的类称为抽象类，抽象类不能被实例化，抽象方法只能声明于抽象类中，且不包含任何实现，派生类必须覆盖它们。抽象类也可派生自一个抽象类。

  6. C++ 中的虚函数是什么？

    答：C++ 的多态性是通过虚函数实现的，虚函数必须存在于继承环境下。虚函数是重载的一种表现形式。只有类的普通成员函数可以定义为虚函数，全局函数及静态成员函数（类拥有）不能声明为虚函数。

  7. C++ 中的纯虚函数是什么？

    答：virtual 函数类型 函数名（形参表列）= 0。抽象类中定义的，为了派生类中的使用而声明定义的。

  8. C++ 中的抽象类和接口有什么区别？

    答：一个类一次可以实现若干个接口，但是只能扩展一个父类。

  9. C++ 中的 public、private 和 protected 是什么？

    答：a. 公有（public）成员可以在类外访问。

    b. 私有（private）成员只能被该类的成员函数访问。

    c. 保护（protected）成员只能被该类的成员函数或派生类的成员函数访问。

Python

  1. Python 中的 *args 和 **kwargs 是什么意思？

    答：*args 表示可变参数（variadic arguments），它允许你传入 0 个或任意个无名参数，这些参数在函数调用时自动组装为一个 tuple； **kwargs 表示关键字参数（keyword arguments），它允许你传入 0 个或任意个含参数名的参数，这些关键字参数在函数内部自动组装为一个 dict。同时使用 *args 和 **kwargs 的时候，必须保证 *args 在 **kwargs 之前。 *args 是变量 list，**kwargs 是指针 list。

  2. __new__ 了解吗？

    答：__init__ 作用是类实例进行初始化，第一个参数为 self，代表对象本身，可以没有返回值。__new__ 则是返回一个新的类的实例，第一个参数是 cls 代表该类本身，必须有返回值。__new__ 先执行，然后再 __init__，实际上，只要 __new__ 返回的是类本身的实例，它会自动调用 __init__ 进行初始化。但是有例外，如果 __new__ 返回的是其他类的实例，则它不会调用当前类的 __init__。

  3. __name__ 的值怎么确定？

    答：链接

  4. map() 返回的对象是什么？

    答：map() 函数返回的是一个迭代器，并对返回结果使用了 yield，所以其返回结果只能使用一次，这样做在于节省内存。

  5. [[1, 2], [3, 4], [5, 6]] 一行代码展开该列表，得出 [1, 2, 3, 4, 5, 6]

    答：[j for i in [[1,2],[3,4],[5,6]] for j in i]

  6. Python 中怎么转换 ascii 码和字符？

    答：chr(65)和ord('A')。

  7. len('中文')和len('中文'.encode('utf-8'))的输出分别是多少？

    答：2 和 6，Python 默认是 Unicode 编码，转换成 UTF-8 编码，中文通常占用三个字符，英文一个。

  8. 一行代码将字符串 “->” 插入到 “abcdefg” 中每个字符的中间

    答："->".join("abcdef")

  9. 如何判断一个字符串是否是另一个字符串的子串

    答：in；s.find()可以放回 index，如果返回 -1 则说明查询不到；s.index()，类似s.find()，找不到会抛出异常。

  10. 字符串常用函数

    答：大小写转换：lower(), upper(), capitalize(), title(), swapcase() 查找与判断：find(), index(), count(), startswith(), endswith(), in 空白与格式清理：strip(), lstrip(), rstrip(), replace() 分割与拼接：split(), join() 字符判断：isdigit(), isalpha(), islower(), isupper()

  11. list

    答：增 lst = [1, 2, 3] lst.append(4) # 加到末尾 lst.insert(1, 10) # 插入到索引 1 位置 lst.extend([5, 6]) # 扩展多个元素 删 lst.remove(2) # 删除指定元素（找不到会报错） del lst[0] # 按索引删除 lst.pop() # 删除并返回最后一个元素 lst.clear() # 清空列表 改 lst[0] = 100 # 修改指定索引值 查 print(lst[0]) # 按索引访问 print(len(lst)) # 长度 print(10 in lst) # 是否包含 for item in lst: # 遍历 print(item)

  12. set

    答：增 s = {1, 2, 3} s.add(4) s.update([5, 6]) # 添加多个元素 删 s.remove(2) # 删除元素（不存在会报错） s.discard(10) # 安全删除（不存在不报错） s.pop() # 随机删除一个元素 s.clear() # 清空集合 改：集合不能直接修改元素，但可以删除后添加新值。 查 print(3 in s) for item in s: print(item)

  13. dict

    答：增 d = {‘a’: 1, ‘b’: 2} d[‘c’] = 3 # 新增键值对 d.update({‘d’: 4}) # 批量添加/更新 删 del d[‘a’] # 删除键 d.pop(‘b’) # 删除键并返回值 d.clear() # 清空字典 改 d[‘c’] = 10 # 修改键对应的值 查 print(d[‘c’]) # 获取值（键必须存在） print(d.get(‘x’)) # 安全获取，不存在返回 None print(‘c’ in d) # 是否包含键 for k, v in d.items(): print(k, v)

  14. tuple

    答：增/删/改：都不支持 t = (1, 2, 3) t = t + (4,) # 创建新元组，实现“添加”效果 查 print(t[0]) # 访问索引 print(len(t)) # 长度 print(3 in t) # 是否包含 for item in t: print(item)

  15. Python 的可变对象和不可变对象

    答：可变对象：可以在原地修改其内容，不改变对象的 id（地址）。不可变对象：一旦创建，内容就不能被改变。修改操作会创建新的对象。

    可变对象有 list, dict, set 不可变对象有 str, tuple, int, float, bool

    不可变对象例子：字符串

    s = "hello"
print(id(s))  # 比如 123456
s = s + " world"
print(id(s))  # 改变了（新对象）

    可变对象例子：列表

    lst = [1, 2, 3]
print(id(lst))  # 比如 789123
lst.append(4)
print(id(lst))  # 没变（原地修改）

    可变对象在函数中修改，会影响原对象；不可变对象修改，会创建新对象。 作为字典键或集合元素，必须是不可变对象（如字符串、整数、元组）。

  16. 自定义排序

    答：sorted_data = sorted(data, key=lambda x: (x[0], x[1])) data.sort(key=lambda x: (x[0], x[1])) 可以加 reverse=True 或 reverse=False

    或

    from functools import cmp_to_key
    
def my_cmp(x, y):
    # 先比较a字段升序
    if x[0] < y[0]:
        return -1
    elif x[0] > y[0]:
        return 1
    else:
        # a相等时，b字段降序
        if x[1] > y[1]:
            return -1
        elif x[1] < y[1]:
            return 1
        else:
            return 0
	
lst = [(2, 3), (1, 4), (2, 1), (1, 5)]
lst.sort(key=cmp_to_key(my_cmp))
print(lst)

  17. Python 的匿名函数是什么

    答：就是 lambda 函数，一般用来实现简单的功能，如加法 (lambda x, y: x + y)(3, 4)。

  18. @staticmethod 和 @classmethod 的作用与区别

    答：链接

  19. Python 的 getter 和 setter 是什么？

    答：@property 和 @name.setter。

  20. Python 参数传递

    答：链接

  21. Python 赋值、浅拷贝和深拷贝

    答：链接

  22. 装饰器的意义和使用？

    答：用来实现代码复用，增强代码可读性。

          def deco(func):
          def warpper(*args, **kwargs):
              print('start')
              func(*args, **kwargs)
              print('end')
          return warpper
          
      @deco
      def myfunc(parameter):
          print("run with %s" % parameter)
          myfunc("something")

  23. 解释一下多态？

    答：多态的好处就是，当我们需要传入Dog、Cat、Tortoise……时，我们只需要接收Animal类型就可以了，因为Dog、Cat、Tortoise都是Animal类型，然后，按照Animal类型进行操作即可。由于Animal类型有run()方法，因此，传入的任意类型，只要是Animal类或子类，就会自动调用实际类型的run()方法，这就是多态的意思：

    对于一个变量，我们只需要知道它是Animal类型，无需确切地知道它的子类型，就可以放心地调用run()方法，而具体调用的run()方法是作用在Animal、Dog、Cat还是Tortoise对象上，由运行时该对象的确切类型决定，这就是多态真正的威力：调用方只管调用，不管细节，而当我们新增一种Animal的子类时，只要确保run()方法编写正确，不用管原来的代码是如何调用的。

  24. 鸭子类型是什么？

    答：对于 Python 这样的动态语言，则不一定需要传入Animal类型。我们只需要保证传入的对象有一个run()方法就可以了：这就是动态语言的“鸭子类型”，它并不要求严格的继承体系，一个对象只要“看起来像鸭子，走起路来像鸭子”，那它就可以被看做是鸭子。

  25. Counter 与运算和或运算

    答：与和或操作分别返回两个 Counter 各元素的最小值和最大值。得到的 Counter 对象将删除小于 1 的元素。

  26. Python 多线程？

    答：对于 CPU 密集型，由于全局解释器锁（GIL）的存在，GIL 保证在任何时刻只有一个线程执行 Python 字节码，所以线程是线性执行的；对于 I/O 密集型，由于线程在等待 I/O 操作时会释放全局解释器锁，所以这时多线程有体现作用。

Linux

  1. 程序如何后台运行？

    答：链接

  2. 查看当前训练进程占用的内存和 CPU 资源

    答：top, htop, ps aux 找到进程

  3. 查看当前训练进程占用的 GPU 资源

    答：nvidia-smi

Machine Learning

Basic

  1. 解释一下奥卡姆剃刀原理？

    答：如果两个模型的预测能力差不多，就选简单的。原因有二，简单模型往往解释性更好；复杂的模型更有可能过拟合。

  2. 解释一下没有免费的午餐原理？

    答：A 算法在某些数据集或任务上表现比 B 算法好，则一定存在一些数据集或任务，B 算法表现比 A 算法好。这告诉我们具体问题具体分析。

  3. L1 和 L2 的联系和区别？

    答：都是正则化系数，L1（Lasso）得到稀疏的权值，用于特征选择，L2（Ridge）得到平滑的权值。

  4. 为什么 L1 更容易得到稀疏解？

    答：因为损失函数的等高线易与 L1 正则的坐标轴上的点相切。第一象限与正方形相切的圆的中心只能是在第一象限正方形边的垂直区域内，而第一象限的圆都可以与中心点的圆相切。

    The question can be answered in a geometric view. L1 loss can be represented as a diamond, while L2 loss can be represented as a circle. Therefore, the loss is likely to intersect with the diamond on only one point, which is in axises.

  5. 结构风险和经验风险分别是什么？

    答：经验风险就是使所有训练样本的损失平均值最小，结构风险其实就是加多一个正则项。

  6. 什么是生成模型，什么是判别模型？

    答：生成模型：学习得到联合概率分布 P(x, y)，即特征 x 和标记 y 共同出现的概率，然后求条件概率分布。能够学习到数据生成的机制。

    判别模型：学习得到条件概率分布 P(y | x)，即在特征 x 出现的情况下标记 y 出现的概率。

    数据要求：生成模型需要的数据量比较大，能够较好地估计概率密度；而判别模型对数据样本量的要求没有那么多。

  7. 什么是参数模型，什么是非参数模型？

    答：参数模型假设总体服从某分布，该分布由一些参数确定；非参数模型对于总体分布不做任何假设，只有在给定一些样本的条件下，能够依据非参数统计的方法进行推断。

  8. 拉普拉斯平滑是什么？

    答：为了解决零概率问题：如果某个量 x，在训练集中没有出现过，会导致概率结果是 0。这是不合理的，不能因为一个事件没有观察到就武断的认为该事件的概率是 0。拉普拉斯平滑即加法平滑。假定训练样本很大时，每个分量 x 的计数加 1 造成的估计概率变化可以忽略不计，但可以方便有效的避免零概率问题。

  9. bias 和 variance 的含义是什么？

    答：bias 要求让 Error(train) 尽可能小，variance 要求让 Error(train) 尽可能等于 Error(test)。bias 体现了模型的精确度，variance 体现了模型的泛化能力。两个值都是希望越小越好。

  10. map，mrr 是什么？

    答：链接

  11. 宏平均 F1 和 微平均 F1 的区别？

    答：宏平均 F1 对每个类求 F1 之后取平均，微平均 F1 针对整体求 F1。

Regression

  1. 线性回归的基本假设是？

    答：线性性；独立性；同方差性；正态性；无多重共线性。

  2. 线性回归中特征不小心重复会有影响吗？

    答：会，导致矩阵不可逆。

  3. 最小二乘法为什么可以解决线性回归问题？

    答：残差满足均值为 0 的同方差正态分布时，用最大似然估计法可以证明最小二乘法是合理的。

  4. 描述一下最小二乘法的几何意义？

    答：最小二乘法中的几何意义是高维空间中的一个向量在低维子空间的投影。\(WX\) 实际上是当前样本形成的线性组合空间 \(S\)，最小化的过程是找到一个合适的 \(W\)，使得不在 \(S\) 上的 \(Y\) 到 \(S\) 的投影距离最小。

  5. 正规方程是什么？它有什么作用？

    答：\((X^TX)^{-1}X^Ty\)。可以一次运算得出结果，但特征数目过多时不适用。

  6. 用最小二乘法实现线性回归

    答：

     import numpy as np
 # 1. 生成数据（y = 2x + 3 + noise）
 np.random.seed(42)
 X = np.random.rand(100, 1)  # 100 个样本，1 个特征
 y = 2 * X[:, 0] + 3 + np.random.randn(100) * 0.1  # 添加噪声
	
 # 2. 添加偏置项 x0 = 1（扩展 X 为 [x, 1]）
 X_b = np.c_[X, np.ones((X.shape[0], 1))]  # shape: [100, 2]
	
 # 3. 正规方程解：theta = (X^T X)^(-1) X^T y
 theta = np.linalg.inv(X_b.T @ X_b) @ X_b.T @ y
	
 print("权重和偏置（w, b）：", theta)

  7. 用梯度下降实现线性回归

    答：

     # 初始化
 w = np.random.randn()
 b = np.random.randn()
 lr = 0.1
	
 for epoch in range(1000):
     y_pred = w * X[:, 0] + b
     error = y_pred - y
     loss = (error ** 2).mean()
	
     # 手动计算梯度
     grad_w = 2 * (error * X[:, 0]).mean()
     grad_b = 2 * error.mean()
	
     # 更新参数
     w -= lr * grad_w
     b -= lr * grad_b
	
     if epoch % 100 == 0:
         print(f"Epoch {epoch}: loss={loss:.4f}, w={w:.4f}, b={b:.4f}")

Classification

  1. 逻辑斯特回归（Logistic Regression，LR）为什么不能用均方误差计算损失函数？

    答：链接。

  2. LR 为什么用交叉熵计算损失函数（二分类）？

    答：假设有训练样本 \((x_i, y_i)\)，其中 \(y_i\) 是标签，取值为 0 或 1。

    逻辑回归模型对正类的预测概率为：

    \[\hat{y}_i = 1 / (1 + exp(-w·x_i))\]

    负类概率为：

    \[1 - \hat{y}_i\]

    极大似然估计的目标是最大化所有样本的联合概率：

    \[L(w) = ∏_{i=1}^n P(y_i | x_i; w)\]

    因为 \(y_i\) 只有 0 或 1，服从伯努利分布（二分类），可以写成：

    \[L(w) = ∏_{i=1}^n (\hat{y}_i)^{y_i} * (1 - \hat{y}_i)^{1 - y_i}\]

    取对数似然：

    \[log L(w) = ∑_{i=1}^n [y_i * log(\hat{y}_i) + (1 - y_i) * log(1 - \hat{y}_i)]\]

    最大化对数似然等价于最小化负对数似然，即交叉熵损失：

    \[Loss = - ∑_{i=1}^n [y_i * log(\hat{y}_i) + (1 - y_i) * log(1 - \hat{y}_i)]\]

    因此，逻辑回归的极大似然估计目标函数就是交叉熵损失函数。

  3. LR 为什么用交叉熵计算损失函数（多分类）？

    答：假设有样本 \((x_i, y_i)\)，标签 \(y_i\) 属于类别集合 {1, 2, …, K}。

    逻辑回归的多分类模型预测第 k 类的概率为：

    \[p_{i,k} = exp(w_k · x_i) / ∑_{j=1}^K exp(w_j · x_i)\]

    对所有样本的联合概率：

    \[L(W) = ∏_{i=1}^n P(y_i | x_i; W) = ∏_{i=1}^n p_{i, y_i}\]

    取对数似然，并因为数据服从多项式分布（多分类）：

    \[log L(W) = ∑_{i=1}^n log p_{i, y_i} = ∑_{i=1}^n log [ exp(w_{y_i} · x_i) / ∑_{j=1}^K exp(w_j · x_i) ]\]

    展开：

    \[log L(W) = ∑_{i=1}^n [ w_{y_i} · x_i - log ∑_{j=1}^K exp(w_j · x_i) ]\]

    最大化对数似然等价于最小化负对数似然，即交叉熵损失：

    \[Loss = - ∑_{i=1}^n log p_{i, y_i} = - ∑_{i=1}^n [ w_{y_i} · x_i - log ∑_{j=1}^K exp(w_j · x_i) ]\]

    换一种形式，用 one-hot 标签 \(y_i^k\)：

    \[Loss = - ∑_{i=1}^n ∑_{k=1}^K y_i^k * log p_{i,k}\]

  4. LR 梯度

    答：Logistic Regression 的预测概率定义为：

    \[\hat{y}_i = 1 / (1 + exp(-z_i))，其中 z_i = w · x_i + b\]

    损失函数（单样本）是交叉熵：

    \[L_i = - [ y_i * log(\hat{y}_i) + (1 - y_i) * log(1 - \hat{y}_i) ]\]

    求损失对参数 w 的梯度：

    \[∂L_i/∂w = (\hat{y}_i - y_i) * x_i\]

    求损失对偏置 b 的梯度：

    \[∂L_i/∂b = \hat{y}_i - y_i\]

    推导要点：

    1. 先对损失函数关于预测概率 \(\hat{y}_i\) 求导：
    \[∂L_i/∂\hat{y}_i = - y_i / \hat{y}_i + (1 - y_i) / (1 - \hat{y}_i)\]
    1. 再对预测概率 \(\hat{y}_i\) 关于 z_i$$ 求导：
    \[∂\hat{y}_i/∂z_i = \hat{y}_i * (1 - \hat{y}_i)\]
    1. 最后对 $$z_i 关于参数 w 求导：
    \[∂z_i/∂w = x_i\]
    1. 通过链式法则合并以上导数，简化得到：
    \[∂L_i/∂w = (\hat{y}_i - y_i) * x_i\]

    同理偏置 b 的梯度为：

    \[∂L_i/∂b = \hat{y}_i - y_i\]

  5. LR 为什么用 sigmoid 函数？

    答：链接

  6. 从贝叶斯的角度解释 LR

    答：LR 可以从贝叶斯角度理解为最大后验估计（MAP）。贝叶斯公式如下： 后验概率 P(θ|D) ∝ 似然 P(D|θ) × 先验 P(θ)

    其中 D 是观测数据；θ 是模型参数；P(D θ) 表示在参数 θ 下，数据 D 出现的可能性，即似然函数；P(θ) 是对参数 θ 的先验知识；P(θ D) 是给定数据 D 后，参数 θ 的后验分布。
    训练 Logistic Regression 的目标就是找到使后验概率 P(θ D) 最大的参数 θ，这就是最大后验估计（MAP）：θ_MAP = argmax P(D θ) × P(θ)

    不同情况下有不同的结果：

    • 如果不加先验（即 P(θ) 为常数），那么最大后验就变成了最大似然估计（MLE）。这对应标准的逻辑回归训练目标，即最小化交叉熵损失。
    • 如果 P(θ) 是高斯分布（exp(−θ² / 2σ²)），那么 MAP 对应在最大似然的基础上加入 L2 正则项（Ridge Regression 形式），防止过拟合。
    • 如果 P(θ) 是拉普拉斯分布（exp(− θ / b)），则 MAP 对应于最大似然 + L1 正则项（Lasso Regression 形式），这会导致部分参数为 0，实现特征选择的效果。

  7. LR 为什么要对特征进行离散化？

    答：模型是使用离散特征还是连续特征，其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型，也可以用连续特征加深度学习。

    a. 离散特征的增加和减少都很容易，易于模型的快速迭代；

    b. 稀疏向量内积乘法运算速度快；

    c. 离散化后的特征对异常数据有很强的鲁棒性：比如一个特征是年龄 >30 是 1，否则 0。如果特征没有离散化，一个异常数据“年龄 300 岁”会给模型造成很大的干扰；

    d. 变量离散化为相当于为模型引入了非线性，能够提升模型表达能力，加大拟合；

    e. 特征离散化后，模型会更稳定，比如如果对用户年龄离散化，20 - 30 作为一个区间，不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反，所以怎么划分区间是门学问；

    f. 特征离散化以后，起到了简化了逻辑回归模型的作用，降低了模型过拟合的风险。

  8. 给一个有 m 个样本，n 维特征的数据集，如果用 LR 算法，那么梯度是几维？

    答：n 维。

  9. 如何用机器学习算法计算特征重要性？

    答：LR 后看系数。

  10. 单层感知机为什么不能解决异或问题？

    答：因为异或操作需要两条线来划分边界，而单层感知机可以理解为一个线性分类器，只能解决与、或、非问题。

  11. 如何对单层感知机进行改进，使其能够解决异或问题？

    答：多层感知机，或在进入激活函数前加一个多项式模块，从而添加非线性成分。

  12. 怎么判断分类器是线性分类器还是非线性分类器？

    答：根据决策面是否是线性的。

  13. KNN 的训练损失是多少？

    答：KNN 实际上不算训练，损失为 0。

  14. KNN 算法的 k 值应该如何选择？

    答：k 值太小，模型复杂度较高，容易过拟合；k 值太大，模型复杂度不够，较远的点也可能影响分类结果，分类模糊，导致分类结果不理想。当 k 取训练集大小时，分类结果都为训练集中最多的类。k 值一般选取较小的值，且要低于训练样本数的平方根，可以使用交叉验证法选取。

  15. KNN 怎么更快地找到最近邻点？

    答：KD 树和 ball 树，KD 树根据样本构建，但训练样例远大于特征维度时才适用。

  16. KNN 算法可以根据距离加权吗？

    答：可以用反函数或高斯函数进行距离加权，前者为近邻样本赋予较大权重，稍远的会衰减地很快，因此对噪声数据比较敏感，后者能解决这个问题，但比较复杂。

  17. 常见的距离度量方法有哪些？

    答：\(L_p\) 距离 / Minkowski 距离 / 闵式距离是最常规的距离度量方式，其公式为 \((\|x-y\|^p)^{1/p}\)。当 \(p = 1\) 时为曼哈顿距离，\(p = 2\) 时为欧式距离，\(p\) 为无穷大时为各个坐标距离的最大值，即切比雪夫距离。

  18. 衡量相似度的方法？

    答：欧式距离，Jaccard 相似度（两集合交集大小 / 并集大小），余弦相似度，皮尔逊相关系数（数值归一化后计算余弦相似度），汉明距离。

  19. 什么是支持向量机？

    答：支持向量机就是构造一个的超平面，使得距离超平面最近的那些点，即支持向量与超平面之间的 margin 最大，从而将两个集合分开。

  20. LR 和 SVM 的联系与区别？

    答：链接

    联系：都可以处理分类问题（一般为线性二分类）；都可以增加不同正则化项。两种算法性能接近；两个方法都增加对分类影响较大的数据点的权重，SVM 是只考虑 support vectors，LR 是通过非线性映射，减小了离分类平面较远的点的权重。

    区别：LR 是参数模型，SVM 是非参数模型；从目标函数来看，LR 采用的是 log loss，SVM 采用的是 hinge loss。

  21. 当数据线性可分、接近线性可分以及线性不可分时，分别使用什么 SVM？

    答：硬间隔最大化、软间隔最大化以及核技巧。

  22. SVM 为什么采用间隔最大化？

    答：当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。

  23. 手推 SVM

    答：

    SVM

    超平面：\(y=w^TX+b\)；

    样本点 \(P(x_i, y_i)\) 到超平面的几何距离：\(\frac{\|w^Tx_i+b\|}{\|w\|}\)；

    样本点 \(P(x_i, y_i)\) 到超平面的几何间隔：\(y_i\frac{w^Tx_i+b}{\|w\|} \geq 0\)；

    SVM 解决问题：\(\max_{w,b}{\min_{x_i}y_i\frac{w^Tx_i+b}{\|w\|}}\)；

    由于 \(w, b\) 可缩放，所以令最近点满足 \(y_i(w^Tx_i+b)=1\)，问题转换为 \(\max_{w}{\frac{1}{\|w\|}} \ \ s.t. \ \ y_i(w^Tx_i + b) \geq 1\)；

    定义拉格朗日函数：\(L(w, b, \alpha) = \frac{1}{2} \|w\|^2 + \sum_{i = 1}^m{\alpha_i(1 - y_i(w^Tx_i + b))}\)；

    转换为拉格朗日的极小极大问题：\(\min_{w, b}\max_{\alpha}L(w, b, \alpha)\)，即先求拉格朗日的上界，再最小化上界；

    可进一步转换为极大极小问题，即对偶问题：\(\max_{\alpha}\min_{w, b}L(w, b, \alpha)\)；

    先求极小问题，对 \(w, b\) 求导，令导数为 0，求解 \(w = \sum_{i=1}^m{\alpha_iy_ix_i}, 0=\sum_{i=1}^m{\alpha_iy_i}\)；

    代回拉格朗日函数，得对偶问题：\(\max_\alpha-{\frac{1}{2}\sum_{i=1}^m{\sum_{j=1}^m{\alpha_i\alpha_jy_iy_jx_i^Tx_j}} + \sum_{i=1}^m\alpha_i} \ \ s.t. \ \ \sum_{i=1}^m{\alpha_iy_i=0,\alpha_i \geq 0}\)；

    求解问题，解出 \(\alpha\)，从而解得 \(w, b\)，\(\alpha_i > 0\) 对应的样本即为支持向量。

  24. 为什么要将求解 SVM 的原始问题转换为其对偶问题？

    答：一是对偶问题往往更易求解。二是可以自然引入核函数，进而推广到非线性分类问题。

  25. 为什么 SVM 对缺失数据敏感？

    答：缺失数据是指缺失某些特征数据，向量数据不完整。SVM 没有处理缺失值的策略。而 SVM 希望样本在特征空间中线性可分，所以特征空间的好坏对 SVM 的性能很重要。缺失特征数据将影响训练结果的好坏。

  26. 什么是几何间隔，什么是函数间隔？

    答：几何间隔 \(y_i\frac{w^Tx_i+b}{\|w\|}\)，函数间隔 \(y_i(w^Tx_i+b)\)。函数间隔可以无限大，几何间隔不可以。

  27. 支持向量机的训练在本质上是在最优化哪个值？

    答：w。w 得到 b 自然可以得到。

  28. 如何用支持向量机实现深度学习？

    答：可以用支持向量机作为网络的最后一层，进行分类。

  29. 给一组数据，问决策树、LR、NB 以及 SVM 等算法学出来是什么样子的？

    答：链接

  30. 什么是基于核的机器学习算法？

    答：判别式模型需要把正负样本区分开，那势必会遇到区分不开的情形，这时要用到核函数，所以可认为判别式模型都要用核函数的。

  31. SVM 有哪些核函数？

    答：线性核和高斯核，即线性核与 RBF（径向基）核。 线性核：主要用于线性可分，参数少，速度快，对于一般数据，分类效果已经很理想了。 RBF 核：主要用于线性不可分，参数多，分类结果非常依赖于参数。 如果 Feature 数量跟样本数量差不多，应选用线性核的 SVM。 如果 Feature 数量比较小，样本数量一般，选用高斯核的 SVM。其他的核函数包括幂指数核、拉普拉斯核以及 Sigmoid 核等等。

  32. 高斯核为什么有效？

    答：链接

  33. 支持向量机可以用来做回归吗？

    答：支持向量机分类是使两类的点在各自的支持向量外，而支持向量机回归是把所有的点都看成一类，并要求在支持向量内。

  34. SVM 和 softmax 的区别？

    答：SVM 具有附加稳定性，当样例满足边界条件时，该样例不会影响损失函数；而 softmax 将考虑所有的样例。

  35. 感知机和 SVM 有什么区别？

    答：链接

  36. One-class SVM？

    答：只要针对异常检测问题。

  37. 朴素贝叶斯为何如此朴素？

    答：对条件概率分布作了条件独立性（conditional independence）的假设。

  38. 朴素贝叶斯中特征不小心重复会有影响吗？

    答：会，破坏了原本的独立性假设。

  39. 用 numpy 实现 cross entropy loss

    答：

    import numpy as np
    
def softmax(logits):
    """
    计算 softmax 概率，确保数值稳定。
    logits: 形状为 (N, C)，N 是样本数，C 是类别数
    """
    shifted = logits - np.max(logits, axis=1, keepdims=True)
    exps = np.exp(shifted)
    return exps / np.sum(exps, axis=1, keepdims=True)
	
def cross_entropy_loss(probs, labels):
    """
    计算平均交叉熵损失。
    probs: softmax 后的概率，形状为 (N, C)
    labels: 每个样本的真实类别索引，形状为 (N,)
    """
    N = probs.shape[0]
    # 取出每个样本对应真实类别的概率，防止 log(0) 加个小常数
    log_likelihood = -np.log(probs[np.arange(N), labels] + 1e-15)
    return np.sum(log_likelihood) / N
	
# 示例数据
logits = np.array([
    [2.0, 1.0, 0.1],
    [0.5, 2.5, 0.3],
    [1.2, 0.7, 3.0]
])
labels = np.array([0, 1, 2])  # 每个样本的真实标签
	
# 计算 softmax 概率
probs = softmax(logits)
	
# 计算交叉熵损失
loss = cross_entropy_loss(probs, labels)
	
# 打印结果
print("Softmax probabilities:\n", probs)
print("\nCross-entropy loss:", loss)

  40. You are given a data set on cancer detection. You’ve build a classification model and achieved an accuracy of 96%. Why shouldn’t you be happy with your model performance? What can you do about it?

    答：If you have worked on enough data sets, you should deduce that cancer detection results in imbalanced data. In an imbalanced data set, accuracy should not be used as a measure of performance because 96% (as given) might only be predicting majority class correctly, but our class of interest is minority class (4%) which is the people who actually got diagnosed with cancer. Hence, in order to evaluate model performance, we should use Sensitivity (True Positive Rate), Specificity (True Negative Rate), F measure to determine class wise performance of the classifier. If the minority class performance is found to to be poor, we can undertake the following steps:

    a. We can use undersampling, oversampling or SMOTE to make the data balanced.

    b. We can alter the prediction threshold value by doing probability caliberation and finding a optimal threshold using AUC-ROC curve.

    c. We can assign weight to classes such that the minority classes gets larger weight.

    d. We can also use anomaly detection.

    Know more: Imbalanced Classification

  41. 多分类问题如何转二分类方法？

    答：a. 一对多法（one-versus-rest）。把某类样本归为一类，其他归为另一类，k 个类别的样本就构造出了 k 个 SVM；

    b. 一对一法（one-versus-one）。在任意两类样本间设计一个 SVM，k 个类别需要 k(k - 1) / 2 个 SVM；

    c. 层次支持向量机（H-SVMs）。先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环。

  42. 上溢（overflow）和下溢（underflow）是什么，softmax 函数会出现哪种情况，该怎么解决？

    答：上溢即大量级的数被近似为正负无穷时，发生上溢。发生上溢后，这些数值会变为非数值。下溢即有些逼近零的数，如零除或者对零取对数时，得到负无穷，如果对负无穷进一步运算，则会得到非数字。softmax 函数中有指数运算，如果要运算的数过小或过大，则会下溢或上溢。解决上溢的方式是让每一个值都减去最大分量的值，由于这样做之后分母有一项为 1，所以不会出现下溢。同样对于取对数，可以让所有数都加 1。

Clustering

  1. 手撕 KMeans

    答：

     import numpy as np
    
 class KMeans:
     def __init__(self, n_clusters=3, max_iter=100, tol=1e-4, random_state=None):
         self.n_clusters = n_clusters
         self.max_iter = max_iter
         self.tol = tol
         self.random_state = random_state
	
     def fit(self, X):
         np.random.seed(self.random_state)
         n_samples, _ = X.shape
	
         # Step 1: 初始化质心（随机选择 K 个样本）
         initial_idxs = np.random.choice(n_samples, self.n_clusters, replace=False)
         self.centroids = X[initial_idxs]
	
         for i in range(self.max_iter):
             # Step 2: 分配每个样本到最近的质心
             distances = self._compute_distances(X)
             labels = np.argmin(distances, axis=1)
	
             # Step 3: 更新质心
             new_centroids = np.array([
                 X[labels == j].mean(axis=0) if np.any(labels == j) else self.centroids[j]
                 for j in range(self.n_clusters)
             ])
	
             # Step 4: 判断收敛（质心移动小于 tol）
             shift = np.linalg.norm(new_centroids - self.centroids)
             self.centroids = new_centroids
             if shift < self.tol:
                 break
	
         self.labels_ = labels  # 保存训练标签
	
     def predict(self, X):
         # 计算每个点到所有质心的距离，返回最近质心的索引
         distances = self._compute_distances(X)
         return np.argmin(distances, axis=1)
	
     def _compute_distances(self, X):
         # 返回 (n_samples, n_clusters) 的距离矩阵
         return np.linalg.norm(X[:, np.newaxis] - self.centroids, axis=2)

  2. KMeans 将 m 条 n 维数据进行聚类，一共迭代了 t 次，其中簇的数目为 K，计算时间复杂度和空间复杂度

    答：使用 KMeans 算法的时候，需要对 m 条数据每一维都与 K 个中心进行计算，一共迭代 t次，即一共是 O(mntK) 的时间复杂度，同时每个维度有 K 个聚类中心，要存 m 个 n 维向量，因此空间复杂度为 O(n(m + K))，选A。

  3. KMeans 聚类数目选择方法

    答：肘部法则（Elbow Method）：通过绘制聚类数目与目标函数（通常是簇内平方和）的关系图，寻找图像呈肘状的拐点，该拐点对应的聚类数目被认为是合适的选择。

    轮廓系数法（Silhouette Method）：通过计算每个样本的轮廓系数，绘制轮廓系数与聚类数目的关系图，选择轮廓系数最大的聚类数目。

    Gap统计量（Gap Statistic）：比较聚类结果与随机数据集的差异，选择Gap统计量最大的聚类数目。

  4. KMeans 中我想聚成 100 类 结果发现只能聚成 98 类，为什么？

    答：因为聚类过程中可能会产生空簇，可见例子。

  5. 为什么在高维空间中聚类效果会变差？如何应对？

    答：高维导致“距离集中”，影响距离度量有效性（维度灾难）。可先进行降维（如 PCA、t-SNE、UMAP）再聚类。

  6. 讲一下 EM 算法，E 步和 M 步的具体步骤，E 中的期望是什么？

    答：初始化参数 \(\theta^{old}\)；E 步：估计 \(p(Z\|X, \theta^{old})\)，求得样本的后验期望值；M 步：根据极大似然估计求得 \(\theta^{new}\)；根据 \(\theta\)，迭代至收敛。

  7. KMeans 和 EM 有什么关系，和 GMM 有什么关系？

    答：KMeans 的目标函数（整个数据集点到各自聚类中心的距离的平方和）可以用 EM 算法求解。K-Means 算法归类为 GMM 的 EM 解法的一个特例。

  8. DBSCAN

  9. IVF（Inverted File Index，倒排文件索引）

    答：将整个向量空间划分为多个“簇（clusters）”，并构建倒排表（inverted list），从而减少实际要比较的向量数量。

Decision Tree

  1. id3 是什么？

    答：利用信息增益（大的特征优选）的决策多叉树。

  2. c4.5 是什么？

    答：信息增益容易倾向选择取值多的属性，所以 c4.5 是利用信息增益比（大的特征优选）的决策多叉树。

  3. cart 是什么？

    答：利用基尼系数（从数据集 D 中随机抽取两个样本，类别标志不一样概率，小的优选）的决策二叉树，可为回归树，也可为分类树。

  4. 决策树中的特征选择方法有哪些？

    答：分类：信息增益、信息增益比和基尼系数；回归：误差（一般取叶子结点数值的方差和）。

  5. 决策树容易过拟合的原因是什么？如何缓解？

    答：训练数据中噪声或特征太多，树可以完美拟合训练集。

    缓解方法：剪枝；设置最大深度、最小叶子节点数；使用集成方法（如随机森林）

Dimension Reducing

  1. SVD 算法是什么？

    答：\(A=U \sum V^T\)。把一个矩阵分解为正交矩阵 \(U\)（经过 \(A\) 变换后的新标准正交基），对角矩阵 \(\sum\) （\(V\) 中向量与 \(U\) 中对应向量之间的比例关系，\(\sum\) 中的每个 \(\sigma\) 会从大到小排序，值越大代表该维度重要性越高）和正交矩阵 \(V\)（原始域的标准正交基）。

  2. PCA，SVD 和 LDA 有什么区别？

    答：PCA 和 SVD 是无监督算法，不需要类别信息，他们都可以将数据投影到低维空间，以最大程度保留原始数据的方差信息。PCA 基本思想：找到数据方差最大的方向，将高维数据投影到这些方向上以实现降维。主要步骤：中心化 → 计算协方差矩阵 → 特征值分解 → 选择前 k 个主成分 → 投影。LDA 是有监督算法，需要类别信息，他在降维的同时让类间距离尽可能大，类内距离尽可能小。

  3. 特征标准化有什么意义？怎么做？

    答：消除不同指标量纲的影响。归一化，正态化。

  4. 什么是白化？

    答：输入数据分布变换到 0 均值，单位方差的正态分布。但计算代价大，很少用于神经网络。

Emsemble Learning

  1. ensemble method 中哪种方法降低 bias，哪种方法降低 variance

    答：bagging 降低 variance，boosting 既能降低 bias，又能降低 variance。

    根据中心极限定理：样本平均值将会约等于其所在总体的平均值，取样次数越多，结果就越接近正态分布；而且样本大小越大，样本平均值分布的标准差就越小。

    在 bagging 中，可以把建立每一个分类器的过程都看作给定数据集下的随机变量，把分类器的组合看作样本，很明显分类器越多，预测结果的 variance 就越小。

    boosting 的每一轮迭代都是基于前面的残差，不断的去学习残差，从而使模型一步步去逼近真实值，整个过程都在优化 loss function，很明显随着迭代次数增加，预测结果的 bias 就越小。另外，boosting 也属于集成学习，是由若干个若分类器组成的一个强分类器，但由于各阶段分类器之间相关性较强，若把 boosting 也看成一次抽样，变量之间并不相互独立，也不是完全相关，存在一定的互相依赖关系，因此方差降低得较少。

  2. 集成方法的个体学习器有什么要求？

    答：好而不同。

  3. 集成方法分为什么？有哪些方法？

    答：个体学习器不存在强依赖关系，可同时生成，有 Bagging、Random Forest；个体学习器存在强依赖关系，须串行生成，有 Boosting，AdaBoost，GBDT。

  4. 强可学习和弱可学习是什么？

    答：对于存在一个多项式的学习算法，若正确率很高，则是强可学习的，若仅比随机猜测略好，则是弱可学习的。

  5. Bagging 的工作机制是什么？

    答：利用自助采样法得到多套数据集，然后通过多个基分类器分类。

  6. Boosting 的工作机制是什么？

    答：通过基学习器的表现对训练样本分布进行调整，使得分错样本得到更多关注。

  7. Random Forest 是什么？

    答：随机森林是 Bagging 的变种，其以决策树为基学习器，并在决策树的训练过程中加入了随机属性选择。其可以处理离散特征，又可以处理连续特征。

  8. 随机森林相比普通的 bagging 的改进是什么？

    答：不仅对样本随机选择，还对特征随机选择。

  9. bagging 的自动校验是什么？

    答：包外估计。

  10. GBDT 相对于随机森林的改进是什么？

    答：随机森林中每棵决策树是独立的，而在 GBDT 中，每棵树都是以前一棵树的残差（真实值跟预测值的差值，刚好是平方损失函数的负梯度）为学习目标去拟合。基于残差的 GBDT 对异常值敏感，可以用绝对损失或 huber 损失来代替平方损失函数。

  11. 随机森林和 GBDT 的联系和区别？

    答：相同点：都是由多棵树组成；最终的结果都是由多棵树一起决定

    不同点：组成随机森林的树可以分类树也可以是回归树，而 GBDT 只由回归树组成；组成随机森林的树可以并行生成，而 GBDT 是串行生成；随机森林的结果是多数表决表决的，而 GBDT 则是多棵树累加之和；随机森林对异常值不敏感，而 GBDT 对异常值比较敏感；随机森林是通过减少模型的方差来提高性能，而 GBDT 是减少模型的偏差来提高性能的；随机森林不需要进行数据预处理，即特征归一化。而 GBDT 则需要进行特征归一化

  12. AdaBoost 是什么？

    答：此方法通过提高前一轮弱分类器错误分类样本权值来提高集成学习效果，它在预测时采用加权多数表决的方法，即加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值。

  13. GBDT 和 XgBoost 区别？

    答：GBDT 用一阶梯度（如残差），一般仅限MSE等简单损失函数，且无正则项；XgBoost 用一阶 + 二阶梯度（加快收敛，提高稳定性），支持任意可导损失函数（通过泰勒展开），支持 L1、L2 正则，防止过拟合。XgBoost 将树模型的复杂度（叶节点的数量和叶节点的得分越高，树就越复杂）作为正则项加在优化目标上，公式推导中用到了二阶导数信息，支持并行操作。

  14. 提升树是什么？

    答：如果用于分类，那就是特殊的 AdaBoost，基分类器都为决策树，回归则情况有所不同。

Deep Learning

  1. 权重初始化方法？

    答：链接

    零初始化，常量初始化，高斯/均匀随机初始化，Xavier 初始化，He 初始化，正交初始化。

  2. 为什么不能零初始化或常量初始化？

    答：if the neurons start with the same weights, then all the neurons will follow the same gradient, and will always end up doing the same thing as one another.

  3. Xavier / He 初始化的目的是什么？

    答：使每一层输出方差为 1。

  4. RNN 系列为什么要正交初始化？

    答：RNN 的反向传播本质是权值矩阵连乘，如果矩阵所有特征值绝对值小于 1，则梯度消失，大于 1，则梯度爆炸。

  5. 怎么得到正交初始化？

    答：QR 分解或 SVD。

  6. 有哪些激活函数？

    答：sigmoid，softmax，tanh，ReLU，PReLU，Leakly ReLU，Maxout。

  7. 激活函数如何选择？

    答：除了 gate 之类的地方，尽量不要用 sigmoid，可以用 tanh 或者 relu 之类的激活函数。

  8. 为什么在 CNN 等结构中将原先的 sigmoid、tanh 换成 ReLU 可以取得比较好的效果？

    答：解决了梯度消失问题。Sigmoid 导数在两端趋近于 0，容易导致梯度消失；ReLU 在正区间梯度恒为 1，不会出现梯度爆炸/消失问题，支持更深网络训练。

  9. RNN 中只能采用 tanh 而不是 ReLU 作为激活函数么？

    答：ReLU 能解决梯度消失，但对 CNN 有效，对 RNN 无效。因为CNN 每一层使用独立的参数不同，原始的 RNN 在每个阶段都共享一个参数。如果直接把 RNN 的激活函数换成 ReLU 会导致非常大的输出值。

  10. RELU 在 0 点的导数是多少？

    答：链接

  11. dying relu？

    答：链接

  12. 为什么 softmax 包含 “soft”？

    答：“soft”表示 softmax 函数是连续可导的，以保证梯度下降可以用来优化损失函数。

    “soft” means that the softmax function is continuous and differentiable so that the gradient descent can be used to optimize the loss function.

  13. 怎么得到一个 soft 版本的 argmax？

    答：用 softmax 的结果与 index 的倒置相乘。

  14. Dropout

    答：以一定的概率随机地使一部分神经元节点失效。应用 Dropout 之后，前向传播生成网络结构的过程可以看做服从的分布是伯努利分布。

  15. 矩阵计算：AB=C，y=f(C)，y 对 C 的偏导为 P，求 y 对 A 和 B的偏导。

    答：\(PB^T\) 和 \(A^TP\)。

  16. 挑一种激活函数推导梯度下降的过程?

    答：链接

  17. softmax 求导？

    The derivation of the softmax function?

    答：链接。\(softmax'(z)=softmax(z)(y_i-softmax(z))\)，其中\(y_i\)为标签。如果表示为 Jacobian 矩阵可为\(J_{softmax}=Diag(p)-pp^T\)，其中\(p=softmax(z)\)，而\(Diag(p)\)是以p为对角线的矩阵。

  18. argmax 不可导怎么办？

    答：gumbel softmax。

  19. sgd、momentum、rmsprop、adam 区别与联系

    答：都是梯度下降，SGD 没动量，Momentum 是一阶动量，RMSProp 是二阶动量，Adam 是一阶动量 + 二阶动量。

  20. 神经网络为什么会产生梯度消失现象？

    答：两种情况下梯度消失经常出现，一是在深层网络中，二是采用了不合适的损失函数，比如 sigmoid（导数范围从 0 到 0.25）。前者是因为根据链式法则，如果每一层神经元对上一层的输出的偏导乘上权重结果都小于 1 的话，多次链乘之后会接近为 0，如果都大于 0 的话，多次链乘之后会接近正无穷。sigmoid 中心部位和两侧的梯度差别太大，如果权重初始化得太大或太小，激活值基本都在 sigmoid 两侧，两侧梯度几乎为 0，传播几层就没有梯度了。

  21. 如何避免梯度消失或梯度爆炸？

    答：权重合理初始化，梯度剪切（梯度爆炸），门机制，batch normalization。

  22. 如何调参？

    答：for 循环；贝叶斯优化。

  23. 多任务如何学习？

    答：链接

  24. CNN 在卷积和池化过程中，输入特征和输出特征的关系是怎样的？

    答：输出尺寸 = (输入尺寸 - filter + 2 * padding）/ stride + 1。计算尺寸不被整除，卷积向下取整，池化向上取整。

  25. LSTM 是什么？

    答：遗忘门：\(f_t=\sigma(W_f[h_{t-1}, x_t] + b_f)\)，输出 [0, 1]，来表示信息保留程度。

    输入门：\(i_t=\sigma(W_i[h_{t-1}, x_t] + b_i)\)，输出 [0, 1]，来表示信息更新程度。

    输入转换为初步输出：\(\tilde{C_t}=\sigma(W_C[h_{t-1}, x_t] + b_C)\)。

    使用遗忘门和输入门：\(C_t=f_t*C_{t-1}+i_t*\tilde{C_t}\)。

    输出门：\(o_t=\sigma(W_o[h_{t-1}, x_t] + b_o)\)，输出 [0, 1]，来表示信息输出程度。

    得到最终输出：\(h_t=o_t*tanh(C_t)\)。

  26. GRU 是什么？

    答：LSTM 的变种，将遗忘门和输入门合在一起，输入门 = 1 - 遗忘门。

  27. LSTM 和 GRU 的联系和区别？

    答：都是通过使梯度的乘法变成加法，来解决 RNN 由于梯度消失而不能对长期依赖建模的问题。前者三个门，后者两个门，所以前者计算更耗时。

  28. 门机制为什么能解决梯度消失或爆炸问题？

    答：链接

  29. TensorFlow 和 Pytorch 如何在不同层使用不同的学习率？

    答：链接

  30. TensorFlow 和 Pytorch 如何固定参数和 fine-tune？

    答：链接

  31. TensorFlow 怎么实现 learning rate decay？

    答：链接

  32. Pytorch 怎么实现 learning rate decay？

    答：链接

  33. TensorFlow 内部求导机制？

    答：符号求导。先提供每一个op求导的数学实现，然后使用链式法则求出整个表达式的导数。

  34. TensorFlow 创建变量的方式有哪些，有什么区别？

    答：tf.Variable()和tf.get_variable()。前者一律创建新的变量，遇到同名变量，会在后面加后缀 1，2；后者如果遇到同名变量，则使用之前创建的变量，但要求这个变量一定在 variable_scope 中，且有 reuse 选项。

  35. Pytorch 如何切换训练和测试模式？

    答：model.train()和model.eval()

  36. Pytorch 的 view 和 reshape 有什么区别？

    答：view 只能用于连续内存的张量；只改变视图，不复制数据（如果张量是连续的）；如果张量不是连续的，会报错；更快（不涉及数据复制）；在对张量做完 .contiguous() 后更常用。reshape 可以用于非连续张量（会自动创建副本）；自动处理非连续张量，可能复制数据；自动处理，返回新的张量；稍慢（可能需要复制内存）；更通用，适用于任何张量。

  37. GPU 利用率低怎么办？

    答：dataset API 可以支持以 streaming 的方式读取数据。

Natural Language Processing

Traditional Methods

  1. TF-IDF 是什么？

    答：词频（TF）为词在当前文档中出现的频率，逆向文件频率（IDF）由总文件数目除以包含该词的文件数目，再将得到的商取以 10 为底得到。

  2. 手动加权或自主学习权重哪个好？

    答：手动加权相当于引入特征，更为合理，自主学习权重相当于学习特征，能够学到隐含信息。

  3. 自然语言处理数据增强的方法？

    答：a、加噪，如随机扔词或调整语序；b、同义词替换；c、回译；d、文档裁剪；e、生成对抗网络。

  4. HMM 的两个假设是什么？

    答：齐次马尔可夫性假设（当前时刻状态只跟上一状态相关）和观测独立性假设（当前观测只跟当前状态相关）。

  5. CRF 是什么？

    答：给定一组输入随机变量，另一组输出随机变量的条件概率分布模型，输出随机变量构成马尔可夫随机场。

  6. HMM 和 CRF 的联系与区别

    答：a.HMM 是生成模型，CRF 是判别模型

    b.HMM 是概率有向图，CRF 是概率无向图

    c.HMM 求解过程可能是局部最优，CRF 可以全局最优

    d.CRF 概率归一化较合理，HMM 则会导致 label bias 问题

Word2Vec + Neural Networks

  1. 为什么不能用 one-hot 表示词？

    答：维度灾难和语义鸿沟。

  2. 分布式假设是什么

    答：相同上下文语境的词有类似含义。

  3. 了解哪些词向量方法？

    答：固定表征（word2vec，Glove，FastText）和动态表征（cove，elmo，GPT，bert）。

  4. word2vec 的原理？

    答：word2vec 有两种模型 CBOW 和 Skip-Gram，前者是在已知上下文的情况下，预测当前词，后者是在已知当前词的情况下，预测上下文。

  5. word2vec 的两个模型哪个对小数据集和非词典词比较友好？

    答：CBOW 每个词在进入模型后，都相当于进行了均值处理，所以非词典词在进行加权平均后，也容易被忽视。

    Skip-Gram 每个词都会被单独得训练，较少受其他高频的干扰。所以对于 Skip-Gram 在小数据集和非词典词上占优。

  6. word2vec 中的 hierarchical softmax 是什么？

    答：将一次分类分解为多次分类，从而把分类的时间复杂度从 O(N) 降低到 O(logN)，从而提高运算效率。word2vec 根据词频构建了一棵 Huffman 树，来实现 hierarchical softmax。

  7. word2vec 中的 negative sampling 是什么？

    答：负采样即在词汇表中采样一定数目的词作为负例，与原先的正例一起做多次二分类（而不是全词表多分类），从而提高模型训练速度。负采样受到词频影响，词频越高的词越可能被采样到。

  8. LSA 是什么？

    答：潜在语义分析，先构建一个单词-标题（或文章）矩阵成，然后再用 SVD 算法等进行处理。

  9. Glove 的原理？

    答：通过构建词向量和共现矩阵之间的近似关系，来进行训练

  10. Glove 和 LSA 有什么联系或区别？

    答：LSA 采用计算复杂度高的 SVD 算法，Glove 可看作是对 LSA 的一种优化。

  11. Glove 和 word2vec 有什么联系或区别？

    答：word2vec 是局部语料库训练的，其特征提取是基于滑窗的；而 Glove 的滑窗是为了构建共现矩阵，是基于全局语料的，因此，word2vec 可以进行在线学习，glove 不能。word2vec 是无监督学习；Glove 通常被认为是无监督学习，但实际上 Glove还是有 label 的，即共现次数。word2vec 损失函数是带权重的交叉熵，权重固定；glove的损失函数是最小平方损失函数，权重可做映射变换。总体来看，Glove 可看作是换了目标函数和权重函数的全局 word2vec。

  12. FastText 的原理？

    答：FastText 建立在 word2vec 基础上，其用 subword 来对非词典词进行处理，用 n-gram 来考虑词序。

  13. elmo 的原理？

    答：基于语言模型的动态词向量。采用 1 层静态向量 + 2 层 LSTM 提取特征，然后将两个方向得到的向量进行拼接。

  14. cove 和 elmo 的联系和区别

    答：都用了 LSTM 编码，但前者的输入单位是词，后者是字符。

  15. CNN 在文本分类上一般怎么应用？

    答：卷积核宽度为词向量的维度（词向量交换维度并不会起影响，所以没必要在词向量维度做卷积），长度为关注窗口的大小，通道数可为所用词向量。

Large Language Models

  1. Raw data 数据收集和质量控制

    答：Minhash 模糊去重，使用小模型打 PPL，数据配比。在评估大模型数据集质量时，可以从以下几个核心维度进行分析：

    • 覆盖度：主要关注数据是否覆盖足够的任务类型、是否具备样本多样性，以及领域分布是否均衡。典型的评估方法包括统计分析和多任务映射。
    • 真实性：关注数据中的信息是否真实、是否符合客观事实。常用的检测方法包括与知识图谱进行对比以及基于语言模型的自动事实核查（fact-check）。
    • 干净程度：检查数据是否存在拼写错误、乱码或无意义的文本。可以通过文本清洗技术和噪声检测方法进行处理。
    • 毒性安全性：关注数据中是否存在有害内容或带有偏见的文本。通常使用有害内容检测模型和关键词扫描工具进行识别。
    • 语言质量：判断文本是否通顺、流畅且语言丰富。可以通过语言模型打分、句法结构检测等方式进行评估。
    • 任务相关性：验证样本是否与目标任务或目标领域高度相关。可采用 Embedding 相似度匹配或由领域专家进行标注确认。
    • 知识时效性：检查数据中的信息是否已经过时，通常通过与最新的数据库或时间戳进行对齐来判断。

  2. Instruction data 数据收集和质量控制

    答：基于 dataset，人工标注。

  3. 数据生成和质量控制

    答：GPT-based 质量评分器。

  4. Transformer 的原理？

    答：Transformer 的总体架构是 encoder-decoder，它的主要部分是利用 multi-head attention 去计算词与词之间的相似度。此外，为了融入位置信息，它还提出了 position embedding。

  5. multi-head attention 的公式是怎样的？

    答：\(Attention(Q,K,V) = softmax({QK^T\over {\sqrt {d_k}}})V\)。

  6. multi-head attention 实现

    答：

     import torch
 import torch.nn as nn
 import torch.nn.functional as F
     
 class MultiHeadAttention(nn.Module):
    def __init__(self, embed_dim, num_heads):
        super(MultiHeadAttention, self).__init__()
        assert embed_dim % num_heads == 0, "Embedding dimension must be divisible by number of heads"
	
        self.embed_dim = embed_dim
        self.num_heads = num_heads
        self.head_dim = embed_dim // num_heads
	
        # Linear layers to project input to Q, K, V
        self.q_proj = nn.Linear(embed_dim, embed_dim)
        self.k_proj = nn.Linear(embed_dim, embed_dim)
        self.v_proj = nn.Linear(embed_dim, embed_dim)
	
        # Final output projection
        self.out_proj = nn.Linear(embed_dim, embed_dim)
	
    def forward(self, x):
        B, T, E = x.size()
	
        # Linear projections
        Q = self.q_proj(x)  # (B, T, E)
        K = self.k_proj(x)
        V = self.v_proj(x)
	
        # Split into multiple heads: (B, num_heads, T, head_dim)
        Q = Q.view(B, T, self.num_heads, self.head_dim).transpose(1, 2)
        K = K.view(B, T, self.num_heads, self.head_dim).transpose(1, 2)
        V = V.view(B, T, self.num_heads, self.head_dim).transpose(1, 2)
	
        # Scaled dot-product attention
        scores = torch.matmul(Q, K.transpose(-2, -1)) / (self.head_dim ** 0.5)  # (B, num_heads, T, T)
        weights = F.softmax(scores, dim=-1)
        attended = torch.matmul(weights, V)  # (B, num_heads, T, head_dim)
	
        # Concatenate heads: (B, T, E)
        attended = attended.transpose(1, 2).contiguous().view(B, T, E)
	
        # Final linear projection
        output = self.out_proj(attended)
        return output

  7. multi-head attention 时间复杂度

    答：\(O(d * seq\_len * seq\_len)\)。

  8. Transformer 使用的时候，制约显存的最关键因素是什么？

    答：序列长度。

  9. grouped-query attention 实现

    答：grouped-query attention 中，query 使用比 key/value 更多的 heads。因为在推理阶段，Q 是即时计算的，而 K/V 是缓存的。

    import torch
import torch.nn as nn
import torch.nn.functional as F
     
class GroupedQueryAttention(nn.Module):
    def __init__(self, embed_dim, num_query_heads, num_kv_heads):
        super(GroupedQueryAttention, self).__init__()
        assert embed_dim % num_query_heads == 0, "embed_dim must be divisible by num_query_heads"
        assert embed_dim % num_kv_heads == 0, "embed_dim must be divisible by num_kv_heads"
	
        self.embed_dim = embed_dim
        self.num_query_heads = num_query_heads
        self.num_kv_heads = num_kv_heads
        self.q_head_dim = embed_dim // num_query_heads
        self.kv_head_dim = embed_dim // num_kv_heads
	
        # Projection layers
        self.q_proj = nn.Linear(embed_dim, embed_dim)
        self.k_proj = nn.Linear(embed_dim, embed_dim)
        self.v_proj = nn.Linear(embed_dim, embed_dim)
        self.out_proj = nn.Linear(embed_dim, embed_dim)
	
    def forward(self, x):
        B, T, E = x.shape
	
        # Project inputs
        Q = self.q_proj(x).view(B, T, self.num_query_heads, self.q_head_dim).transpose(1, 2)  # (B, QH, T, Dq)
        K = self.k_proj(x).view(B, T, self.num_kv_heads, self.kv_head_dim).transpose(1, 2)     # (B, KVH, T, Dk)
        V = self.v_proj(x).view(B, T, self.num_kv_heads, self.kv_head_dim).transpose(1, 2)     # (B, KVH, T, Dv)
	
        # Expand K/V to match query heads if needed
        if self.num_query_heads != self.num_kv_heads:
            repeat_factor = self.num_query_heads // self.num_kv_heads
            K = K.repeat_interleave(repeat_factor, dim=1)  # (B, QH, T, Dk)
            V = V.repeat_interleave(repeat_factor, dim=1)  # (B, QH, T, Dv)
	
        # Scaled dot-product attention
        scores = torch.matmul(Q, K.transpose(-2, -1)) / (self.q_head_dim ** 0.5)  # (B, QH, T, T)
        attn_weights = F.softmax(scores, dim=-1)
        context = torch.matmul(attn_weights, V)  # (B, QH, T, Dv)
	
        # Combine heads
        context = context.transpose(1, 2).contiguous().view(B, T, E)  # (B, T, E)
        output = self.out_proj(context)  # Final linear projection
	
        return output

  10. multi-head attention + kv cache 实现

    答：query 必须每步重算，而 key/value 是过去的记忆，可以缓存。

    import torch
import torch.nn as nn
import torch.nn.functional as F
class SelfAttentionWithKVCache(nn.Module):
    def __init__(self, embed_dim, num_heads, max_seq_len):
        super().__init__()
        assert embed_dim % num_heads == 0
        self.embed_dim = embed_dim
        self.num_heads = num_heads
        self.head_dim = embed_dim // num_heads
	
        self.q_proj = nn.Linear(embed_dim, embed_dim)
        self.k_proj = nn.Linear(embed_dim, embed_dim)
        self.v_proj = nn.Linear(embed_dim, embed_dim)
        self.out_proj = nn.Linear(embed_dim, embed_dim)
	
        # 初始化 KV Cache（支持最多 max_seq_len 步）
        self.register_buffer("key_cache", torch.zeros(1, num_heads, max_seq_len, self.head_dim))
        self.register_buffer("value_cache", torch.zeros(1, num_heads, max_seq_len, self.head_dim))
        self.max_seq_len = max_seq_len
	
    def forward(self, x, start_pos):
        """
        x: [B, 1, E] - 当前一步的 token 表示
        start_pos: int - 当前 token 在生成序列中的位置
        """
        B, T, E = x.shape  # T == 1 during generation
	
        # QKV projection
        Q = self.q_proj(x).view(B, T, self.num_heads, self.head_dim).transpose(1, 2)  # [B, H, 1, D]
        K = self.k_proj(x).view(B, T, self.num_heads, self.head_dim).transpose(1, 2)
        V = self.v_proj(x).view(B, T, self.num_heads, self.head_dim).transpose(1, 2)
	
        # 更新 KV cache
        self.key_cache[:, :, start_pos:start_pos+1, :] = K
        self.value_cache[:, :, start_pos:start_pos+1, :] = V
	
        # 从 0 到当前 step，取所有 KV
        K_cached = self.key_cache[:, :, :start_pos+1, :]   # [B, H, T_cache, D]
        V_cached = self.value_cache[:, :, :start_pos+1, :] # [B, H, T_cache, D]
	
        # 注意力计算
        scores = torch.matmul(Q, K_cached.transpose(-2, -1)) / (self.head_dim ** 0.5)  # [B, H, 1, T_cache]
        attn_weights = F.softmax(scores, dim=-1)
        out = torch.matmul(attn_weights, V_cached)  # [B, H, 1, D]
	
        out = out.transpose(1, 2).contiguous().view(B, T, E)  # [B, 1, E]
        return self.out_proj(out)

  11. FlashAttention

    答：FlashAttention 基于以下几点：

    1. 块分割 (blocking) 将 Q, K, V 按块划分，分块计算 Attention。每次只加载当前块，节省内存。

    2. 在线计算 softmax（online-softmax） 传统 softmax 需要先计算全部 QK^T，然后减 max 值再求 exp，最后归一化。而 FlashAttention 在线计算 softmax，避免存储整个矩阵。

    3. 单遍扫描（one-pass）计算
      通过巧妙算法实现只需遍历一次 Q,K,V 即可计算 Attention 输出，避免多次加载。

  12. Multi-head Latent Attention (MLA)

    答：MLA 把 keys 和 values 低秩联合压缩成 latents，从而把 self attention 变成 latents cross-attend inputs，时间复杂度从 \(O(d * seq\_len * seq\_len)\) 降至 \(O(d * seq\_len * latent\_len)\)。

  13. 为什么要 multi-head

    答：多头注意力允许模型在不同的表示子空间中学习信息，这样可以让模型同时关注不同的信息维度。每个头学习到的信息可以独立地编码输入序列的不同方面，然后将这些信息综合起来，得到更丰富的表示。

  14. Transformer 的 Q 和 K 为什么使用不同的权重矩阵生成？如果强行让 Q=K 会发生什么？

    答：注意力将退化为自相似匹配，容易捕捉到 trivial 信息（如位置对称性）；表达能力显著下降，模型性能变差；实际论文实验证明，共用 Q/K/V 权重会损害性能

  15. Transformer 为什么是 Q * K^T，而不是 Q + K？

    答：点积是最自然的相似度度量，而加法并不能提供一个明确的匹配度分数，它只是两个向量的混合，没有“匹配程度”的含义。

  16. Transformer 为什么是点积，而不是 cosine？

    答：cosine 会归一化，损失模长信息，而且计算复杂度更高。

  17. 为什么要除以 \(\sqrt {d_k}\)

    答：可以防止内积过大导致softmax函数梯度变得非常小，这有助于数值稳定性，使得学习过程更加稳定。此外，它还可以看作是一种缩放因子，帮助模型在不同维度上保持一致的性能。

  18. multi-head attention 的 embed 会不会有低秩的问题，怎么解决？

    答：是的，可能因 head 冗余、聚合退化等原因呈现低秩结构，从而降低表达能力。可以通过正则化（在多头 projection 矩阵上加正交约束）、架构设计、训练策略等方法缓解，并可用奇异值分析评估问题严重程度。

  19. 为什么大模型要使用 left padding

    答：left padding KV Cache 在右侧连续生长，无需移动缓存，支持高效批量并发生成，动态 KV Cache 底层优化都支持左填充。right padding KV Cache 在不同位置，难以对齐，难以批量对齐，增加显存开销，很少支持右填充。

  20. BPE，WordPiece 和 Unigram 的区别是？

    答：BPE 是基于贪心的频率合并。初始时将文本拆成最小单位（单字符），然后反复合并出现频率最高的连续字符对，直到达到预定词表大小。WordPiece（BERT 使用）跟 BPE 类似，不过是根据最大似然估计进行合并。Unigram 基于概率模型，先初始化大量子词候选，然后用 EM 算法估计每个子词的概率，迭代优化删除低概率子词，最终得到固定大小词表。

  21. 传统中文分词

    答：前向匹配（Forward Maximum Matching）+ 动态规划（如 Viterbi 算法）

  22. Position Embedding

    答：绝对位置编码，分为 Sinusoidal（无需学习参数，偶数位置，使用正弦编码，在奇数位置，使用余弦编码。任意位置的 \(PE_{pos+k}\) 都可以被 \(PE_{pos}\) 的线性函数表示）和 Learnable Embedding。

    相对位置编码（可针对长序列），分为 RoPE（对 Query 和 Key 的每个向量维度用旋转变换编码位置信息）和 ALiBi（通过为 Attention 权重加上线性位置偏置来编码位置信息）。

  23. 外推性

    答：测试时要接收处理比训练时更长的上下文。

  24. 如何提升外推能力

    答：位置编码外推：ALiBi 长度泛化技术：动态调整 RoPE 的旋转角 推理策略增强：CoT，Self- Consistency

  25. LLM 常用的激活函数有？

    答：ReLU：f(x) = max(0, x)

    GeLU：f(x) ≈ x * Φ(x)，Φ是标准正态分布的累积分布函数。

    GLU：GLU(a,b)=a×σ(b)，其中，输入被分成两部分 a 和 b，σ 是 sigmoid 函数。

    SwiGLU：SwiGLU = 线性 × SwiSH 激活。Swish 函数代替了原始 GLU 中的 Sigmoid 激活。

    ReLU，GeLU 不能门控，GLU，SwiGLU 能门控。

  26. Batch Normalization (BN)

    答：BN 就是在深度神经网络训练过程中使得每一层神经网络的输入保持相同分布的。

    对于深度学习这种包含很多隐层的网络结构，在训练过程中，因为各层参数不停变化，所以每个隐层都面临 covariate shift 的问题，输入分布老是变来变去，这就是 Internal Covariate Shift，Internal 指的是深层网络隐层，发生在网络内部。BatchNorm 的基本思想是让每个隐层节点的激活输入分布固定下来，避免 Internal Covariate Shift 问题。

    经过 BN 后，大部分 Activation 的值落入非线性函数的线性区内，对应导数远离导数饱和区，加速训练收敛过程。

    BN 为了保证非线性的获得，对变换后的 x 又进行了 scale 加上 shift 操作：y = scale * x + shift。

  27. Batch Normalization (BN) vs Layer Normalization (LN) vs RMSNorm

    答：BN 是跨样本跨 token 统计的，会泄漏信息，所以 LN 更适合变长序列和单样本推理，RMSNorm 参数量（d，缩放因子）为 LN （2d，缩放因子和偏移因子） 一半，更高效和稳定，并表现与 LN 相似。

    输入是形状为 (batch_size, seq_len, hidden_dim) 的张量，BN 通常对 batch 和 seq_len 两个维度联合计算均值和方差，也就是对每个 hidden_dim 维度独立归一化。LN/RMSNorm 对每个样本每个 token 的 hidden_dim 维度做归一化，即对 seq_len 中的每个位置独立归一化，计算均值和方差都在 hidden_dim 上。

  28. 实现 LayerNorm

    答：

    import torch
import torch.nn as nn
	
class LayerNorm(nn.Module):
    def __init__(self, dim, eps=1e-5):
        super(LayerNorm, self).__init__()
        self.eps = eps
        self.gamma = nn.Parameter(torch.ones(dim))  # 缩放因子
        self.beta = nn.Parameter(torch.zeros(dim))  # 偏移因子
	
    def forward(self, x):
        mean = x.mean(dim=-1, keepdim=True)
        var = x.var(dim=-1, unbiased=False, keepdim=True)
        x_norm = (x - mean) / torch.sqrt(var + self.eps)
        return self.gamma * x_norm + self.beta

  29. 实现 RMSNorm

    答：RMSNorm 不减去均值，只用输入的均方根（RMS）来进行归一化。它更轻量，计算更快，没有 mean 操作。

    import torch
import torch.nn as nn
	
class RMSNorm(nn.Module):
    def __init__(self, dim, eps=1e-8):
        super(RMSNorm, self).__init__()
        self.eps = eps
        self.scale = nn.Parameter(torch.ones(dim))  # 可学习缩放因子
	
    def forward(self, x):
        # 计算 RMS
        rms = x.pow(2).mean(dim=-1, keepdim=True).add(self.eps).sqrt()
        x_norm = x / rms
        return self.scale * x_norm

  30. Pre Norm 和 Post Norm 有什么区别？

    答：Pre Norm 在子层（Self-Attn / FFN）之前，Post Norm 在子层（Self-Attn / FFN）之后。Pre Norm 更常用，因为其更稳定，更容易收敛。

  31. Top-k/Top-p

    答：采样，增加生成多样性。

  32. speculative decoding

    答：使用一个小型辅助模型（称为“提议模型”或“draft model”）先快速生成多个候选token序列（草稿）。主模型（大型语言模型）随后只对这些候选进行验证和纠正，而不是每一步都全量生成和计算概率。这种方式能显著减少主模型的计算成本，提高生成速度。

  33. 为什么 LLM 流行 MoE？

    答：MoE 能显著提高模型容量而不成比例地增加计算成本

  34. 手撕 MoE

    答：

    import torch
import torch.nn as nn
import torch.nn.functional as F
	
class SimpleMoE(nn.Module):
    def __init__(self, input_dim, output_dim, num_experts):
        super().__init__()
        self.num_experts = num_experts
        self.experts = nn.ModuleList([nn.Linear(input_dim, output_dim) for _ in range(num_experts)])
        self.gate = nn.Linear(input_dim, num_experts)

    def forward(self, x):
        gate_probs = F.softmax(self.gate(x), dim=1)  # [batch, num_experts]
        expert_outputs = torch.stack([expert(x) for expert in self.experts], dim=1)  # [batch, num_experts, output_dim]
        gate_probs = gate_probs.unsqueeze(-1)  # [batch, num_experts, 1]
        return torch.sum(gate_probs * expert_outputs, dim=1)  # [batch, output_dim]

  35. Prefix LM 和 Causal LM 区别是什么？

    答：Causal LM 是单向的，只看左边上下文；Prefix LM 是半双向的，可以看整个 prefix 的信息（左侧上下文），预测后缀。

  36. 为什么大部分 LLM 是 decoder-only？

    答：生成范式的统一性；任务更难；双向 attention 的注意力矩阵容易退化成低秩状态，而 causal attention 的注意力矩阵是下三角矩阵，必然是满秩的，建模能力更强。

  37. SFT

  38. 强化学习和监督学习有什么区别？

    答：监督学习中每一个决策（预测标签）是独立的，它对决策的优化取决于标签，强化学习每一个决策是相互影响的，它对决策的优化取决于延时标签（奖励）。

  39. PPO

    答：

    \[L^{\text{PPO}}(\theta) = \mathbb{E}_t \left[ \min \left( r_t(\theta) \hat{A}_t,\ \text{clip}(r_t(\theta),\ 1 - \epsilon,\ 1 + \epsilon) \hat{A}_t \right) \right]\]

    其中 \(r_t(\theta) = \frac{\pi_\theta(a_t \mid s_t)}{\pi_{\theta_{\text{old}}}(a_t \mid s_t)}\)，\(\hat{A}_t\)是优势函数的估计，\(\epsilon\) 是控制策略变动幅度的裁剪阈值（如 0.2）。

    PPO 流程如下：

    1. 查询 q 是任务输入，例如一个上下文或状态；

    2. 输入到策略模型（Policy Model），生成对应的输出 o（动作或结果），即用可更新的 LLM 生成 q 的 o；

    3. 输出 o 被输入到冻结的参考模型（Reference Model），计算输出 o 与参考策略之间的 KL 散度，用于限制策略更新；

    4. 输出 o 被输入到冻结的奖励模型（Reward Model），生成奖励 r（通常是 sample-level 的一个标量），用于衡量 o 的质量；

    5. 用 value head 输出每个 token 的 V(s_t)，从 reward 回溯分配每个 token 的 TD 残差 \(\delta_t\)，用 GAE 计算每个 token 的优势 A_t；​

    6. 用以下 loss 进行优化，剪切函数限制策略更新幅度，确保数值稳定性。

    def ppo_loss(log_probs, old_log_probs, advantages, clip_range=0.2):
    ratio = torch.exp(log_probs - old_log_probs)  # [B]
    unclipped = ratio * advantages
    clipped = torch.clamp(ratio, 1 - clip_range, 1 + clip_range) * advantages
    loss = -torch.min(unclipped, clipped).mean()
    return loss

  40. PPO 怎么计算 advantages？

    答：

    1. 直接使用 reward。不是 token level
    2. response 的平均：advantages = reward - values_response.sum(dim=1) / response_mask.sum(dim=1)。容易产生很大的方差，导致训练不稳定。
    3. GAE gamma 是时间折扣因子，控制未来奖励的重要性，越大代表未来奖励越重要。lambda 是 GAE 平衡因子，控制 bias-variance 权衡，λ 越大 → 方差大，偏差小；λ 越小 → 方差小，偏差大。
    def compute_gae(rewards, values, gamma=1.0, lam=0.95):
    advantages = torch.zeros_like(rewards)
    last_adv = 0
    for t in reversed(range(rewards.size(1))):
        delta = rewards[:, t] + gamma * values[:, t + 1] - values[:, t]
        advantages[:, t] = last_adv = delta + gamma * lam * last_adv
    return advantages

  41. PPO 有了 reward model 为什么还要 critic/value model？

    答：critic/value model 是内部奖励，仅需当前上下文，会在 RL 过程中更新，reward model 是外部奖励，需要完整回答，是训练好的

  42. DPO

    答：

    \[L^{\text{DPO}}(\theta) = -\log \left( \frac{\exp\left( \beta \cdot \log \pi_\theta(y^+ \mid x) \right)}{\exp\left( \beta \cdot \log \pi_\theta(y^+ \mid x) \right) + \exp\left( \beta \cdot \log \pi_\theta(y^- \mid x) \right)} \right)\]

    其中，\(y^+\) 是人类偏好的回答，\(y^-\) 是较差的回答，\(\beta\) 是温度系数，控制偏好强度

    def dpo_loss(logp_chosen, logp_rejected, beta=0.1):
    diff = logp_chosen - logp_rejected  # [B]
    loss = -torch.nn.functional.logsigmoid(beta * diff).mean()
    return loss

  43. GRPO

    答：

    \[L^{\text{GRPO}}(\theta) = - \log \left( \frac{\exp\left(R_\theta(x, y^+)\right)}{\exp\left(R_\theta(x, y^+)\right) + \exp\left(R_\theta(x, y^-)\right)} \right)\]

    其中，$R_\theta$ 表示奖励形式的打分函数：

    \[R_\theta(x, y) = \beta \cdot \left( \log \pi_\theta(y \mid x) - \log \pi_{\text{ref}}(y \mid x) \right)\]

    \(\pi_{\text{ref}}\) 是参考策略（例如预训练模型），用于提供稳定的对比基准。

    GRPO 流程如下：

    1. 查询 q 是任务输入，例如一个上下文或状态；

    2. 输入到策略模型（Policy Model），生成对应的多个输出 o_1, o_2, …, o_G（动作或结果），即用可更新的 LLM 生成 q 的 o_1, o_2, …, o_G；

    3. 输出 o_i 被输入到冻结的参考模型（Reference Model），计算输出 o_i 与参考策略之间的 KL 散度，用于限制策略更新；

    4. 输出 o_i 被输入到冻结的奖励模型（Reward Model），生成奖励 r_i（通常是 sample-level 的一个标量），用于衡量 o_i 的质量；

    5. 根据 r_1, r_2, …, r_G，计算奖励均值和奖励标准差，得到 o_i 的相对奖励；​

    6. 用以下 loss 进行优化。

    def grpo_loss(group_log_probs, group_old_log_probs, group_advantages, clip_range=0.2):
    # 计算每个组的 ratio
    ratio = torch.exp(group_log_probs - group_old_log_probs)  # [G, B]
	    
    # 计算组内相对优势（相对于组内其他策略优势的平均）
    mean_advantages = group_advantages.mean(dim=0, keepdim=True)  # [1, B]
    relative_advantages = group_advantages - mean_advantages     # [G, B]
	    
    # 计算组内相对 ratio（相对于组内其他策略 ratio 的平均）
    mean_ratio = ratio.mean(dim=0, keepdim=True)  # [1, B]
    relative_ratio = ratio / (mean_ratio + 1e-8)  # [G, B]
	    
    # Unclipped and clipped losses 基于相对比率和相对优势
    unclipped = relative_ratio * relative_advantages
    clipped = torch.clamp(relative_ratio, 1 - clip_range, 1 + clip_range) * relative_advantages
	    
    # 对所有组和批次求平均，取最小
    loss = -torch.min(unclipped, clipped).mean()
    return loss

  44. PPO vs DPO vs GRPO

    答：PPO 是 token-level，DPO/GRPO 是 sample-level，但 GRPO 可以回传到 token-level

  45. GRPO 怎么去掉 critic/value model 的？

    答：采样多次，用 reward model 评价的平均值来充当 critic/value model

  46. LoRA

    答：LoRA 的公式为 \(W‘ = W + \alpha * BA\)，\(A \in R^{r \times d}\)，\(B \in R^{d \times r}\)，A 用的是小的高斯随机初始化，B 用的是全 0 初始化，所以初始时 W = W’，\(\alpha\) 是缩放因子，用于控制 LoRA 注入的权重大小。target_modules 一般为q_proj、v_proj，有时也会注入到 k_proj 或 o_proj。modules_to_save 表示指定哪些原模型模块需要一起训练 & 保存，如果扩展了词表可能要加 embed_tokens、lm_head。

  47. 手撕 LoRA

    答：

    import torch
import torch.nn as nn
import torch.nn.functional as F

class LoRALinear(nn.Module):
    def __init__(self, in_features, out_features, r=4, alpha=1):
        super().__init__()
        self.r = r
        self.scale = alpha / r
        self.weight = nn.Parameter(torch.randn(out_features, in_features))
        self.weight.requires_grad = False
        self.A = nn.Parameter(torch.randn(r, in_features) * 0.01)
        self.B = nn.Parameter(torch.randn(out_features, r) * 0.01)
        self.bias = nn.Parameter(torch.zeros(out_features))

    def forward(self, x):
        base = F.linear(x, self.weight, self.bias)
        lora = F.linear(x, self.B @ self.A) * self.scale
        return base + lora

  48. Adapter

    答：插入小型网络模块

  49. Prefix Tuning

    答：优化输入前缀

  50. Base model eval

    答：MMLU（通用语言理解类），GSM8K（编程与数学能力）

  51. Chat model eval

    答：MT-Bench，AlpacaEval，Arena，Red-Teaming

  52. Safety / Halluciation

    答：RAG

  53. Long Context

    答：位置编码改进；模型结构优化；记忆缓存机制；检索增强（RAG）；分块/窗口机制；扩展训练数据。

  54. LLM设计中的 System 1 和 System 2

    答：默认模式是 System 1：标准的自回归生成，快速但单步预测。

    通过 Prompt Engineering 或架构设计激活 System 2：

    • Chain-of-Thought（思路链）提示，引导模型一步步“推理”。

    • 多阶段推理框架，如ReAct、Self-Ask、Tool Augmentation。

    • 结合检索（RAG）、记忆模块或外部计算器等工具。

  55. RAG; KG + LLM

    答：RAG 可以解决 LLM 知识过时，幻觉问题以及无法调用私有数据等问题 Naive RAG: Indexing + Retrieval + Generation Advanced RAG: Indexing + Pre-Retrieval + Retrieval + Post-Retrieval (Re-ranking, Prompt Compression) + Generation

  56. 文本分块

    答：文本分块需考虑平衡信息完整性和检索效率。最常见的方式是根据标点符号和长度切。

  57. Reasoning

  58. MCP 和 function calling 有什么区别？

    答：MCP 可以在一次回复中调用多个函数，function calling 每轮最多调用一个函数。

  59. LangChain

    答：LangChain 让你像搭乐高一样搭建一个 LLM 应用，串起来 Prompt、模型、知识库、工具、记忆等组件，快速构建复杂应用。

  60. bf16，fp16，fp32区别

    答：bf16 保留了 fp32 的指数位，只截断尾数，精度略低于 fp16，但数值范围与 fp32 一致。

  61. LLM 常用的优化器有？

    答：AdamW，Lion

  62. 混合精度计算

    答：fp16/bf16 做前向 & 反向传播，fp32 保存主权重。

  63. 7B 模型在训练和推理时的显存占用如何估算，显存与参数量，批次大小，序列长度的关系是什么？

    答：模型大小（参数量） × 精度 = 参数显存占用，fp16/bf16 精度为 2 字节，fp32 精度为 4 字节。 训练显存 ≈ 模型参数 × 3/4（包括权重 + 梯度 + Optimizer 状态 * 1/2） + 激活（反向传播时，需要用它来计算梯度），主要瓶颈是激活值和优化器状态，batch_size 越大，激活越大。 推理显存 ≈ 参数显存 + batch_size × seq_len × num_layers × hidden_size × 2 × bytes，主要瓶颈是 KV Cache。

  64. 多卡多机训练

    答：Data Parallel，Tensor Parallel，Pipeline Parallel，Expert Parallel

  65. DataParallel（DP）和 DistributedDataParallel（DDP）区别

    答：DP 单进程，多 GPU（主卡调度），主卡负责 forward/backward；DDP 多进程，每个 GPU 一个进程，每卡独立计算 + 自动同步梯度。

  66. 为什么 MoE 训练使用 Expert Parallelism 而不是 Tensor Parallelism

    答：MoE 用 gating 网络在多个专家中选择最合适的几个来处理输入，因此 Expert Parallelism 不会损失 Data Parallelism 的数量，因为不同 Expert 处理不同的 Data

  67. deepspeed 的 Zero-1， Zero 2， Zero 3

    答：Zero-1 优化器状态拆分（例如 Adam 的动量），Zero-2 再加梯度拆分，Zero-3 参数也切分，每卡只保存部分权重。三个模式支持自动 Offload 到 CPU / NVMe，进一步节省显存

  68. 量化

    答：PTQ（训练后量化）和 QAT（训练时量化）

    GPTQ (GPT Quantization) 的主要创新是它采用逐层、逐通道的方式优化量化参数，使用二次误差最小化方法来确定最佳量化值，并通过重建误差传播来补偿量化误差。这种方法在保持模型性能的同时实现了高压缩率。

    AWQ(Activation-aware Weight Quantization) 改进 GPTQ，减少激活主导的精度偏差。核心思想是根据激活值的重要性选择性地量化权重。

  69. vllm

    答：把 KV 缓存当作虚拟内存；每条序列的缓存按页（page）管理，动态分配到显存中；PagedAttention = 分页机制 + 注意力机制；动态批处理

  70. GPT 的原理？

    答：基于语言模型的动态词向量。采用单向的、多层的、并行能力强的 Transformer 提取特征，利用到的是 Transformer 的 decoder 部分，见到的都是不完整的句子。

  71. bert 的原理？

    答：基于语言模型的动态词向量。采用双向的、多层的、并行能力强的 Transformer 提取特征，利用到的是 Transformer 的 encoder 部分，采用了完整句子。

  72. bert 的训练目标？

    答：bert 有 masked language modeling 和 next sentence prediction 两个目标

  73. roberta 相比 bert 做了哪些改进？

    答：更大的训练数据；移除 Next Sentence Prediction（NSP）任务，发现没有它模型更稳定、更强；更长时间的训练；更大的 batch size 和学习率调度优化；BERT 的 masking 是静态的（数据预处理阶段决定），RoBERTa 每个 epoch 随机重新 mask。

  74. bert 强于 rnn 的地方？

    答：并行，对大数据比较友好。

  75. Qwen

  76. Deepseek

    答：1. 采用 GRPO 算法，显著降低 RL 训练成本。

    1. R1 中的 MLA（Multi-Head Latent Attention）机制，通过引入一个中间稀疏表示（Latent）空间，在推理（inference）阶段有效节约了 KV-Cache 的内存使用和访问开销。
    2. R1 在 SFT（Supervised Fine-Tuning）阶段采用冷启动（cold start），不使用预训练模型的全部参数直接微调，其核心目的是避免训练初期的不稳定与性能退化，稳定训练过程、充分激活新结构（如 MLA）。
    3. fp8 精度计算
    4. Multi-Token Predition
    5. 细粒度专家划分，共享专家隔离
    6. 为解决 language mixing 的问题，在 RL 阶段增加奖励项，计算目标语言词汇占比

Search/Recommendation

  1. 搜索/推荐 Pipeline

    答：由于海量数据，所以不是端到端。 Recall，Rank，Rerank

  2. 浏览器的联想词运用了什么理论和原理？

    答：贝叶斯原理。

  3. CTR（点击率预估）

    答：样本偏差包括：

    1. 选择性偏差（Selection Bias）：用户只点击曝光的部分结果，非点击不代表不感兴趣。

    2. 位置偏差（Position Bias）：排名靠前位置点击率更高，影响真实兴趣判断。

  4. NDCG

    答：衡量推荐结果的排序质量，考虑点击或相关性得分及其在列表中的位置。结果越靠前且相关性越高，分数越大。

  5. 推荐系统召回策略

    答：1. 热门召回：浏览/点击量统计。通用性强、无冷启动问题

    1. 协同过滤召回：UserCF、ItemCF。利用用户-物品交互的相似性
    2. 向量召回：Item2Vec、DSSM、双塔模型。能捕捉语义和行为的相似性

  6. 推荐系统多路召回

    答：通过多个不同的召回策略或通道，并行生成多个初步候选 item 集合，再融合形成最终的召回候选集合，送入排序模型。

    1. 合并取 Top-N：从每路召回中取 top-K，合并去重；
    2. 加权融合：每一路打分加权（可用模型或策略决定）；
    3. 训练融合：用模型（如召回 ranker）对召回候选打分融合。

  7. 精排模型

    答：DIN

  8. 多目标排序

  9. 推荐系统冷启动

    答：用户冷启动和物品冷启动。元信息（如用户基本属性、物品描述、标签等），尽可能收集各种信息（问卷调查）。

  10. 推荐系统如何解决长尾问题？

    答：提升长尾内容曝光。

Basic

  1. Choose one paper

    答：multilingual，coding，RAG，reasoning

  2. Choose one LLM

    答：Qwen, LLaMA, GPT, deepseek

  3. Choose one project

    答：task description; solution; results; future work; challenges

Sentiment Analysis

  1. 情感分析相对于一般文本分类有什么不同？

    答：特征方面（情感词典，融合了情感的词向量）。

  2. 怎么构建情感词典？

    答：可以先人工制作一个小型的情感词典，然后利用语料，根据一些启发式规则（如“and”连接的词情感一样，“but”相反）来获得新的情感词，不断迭代扩展词典大小。

  3. 情感词典会有哪些问题？

    答：不同的领域的情感词可能不一样；表达情感的词不一定是情感词；讽刺语境。

  4. 如何检测不文明词汇？

    答：词典，分类问题。

Multilinguality

  1. 数据收集和采样策略

    答：1. 重点针对新语言

    1. 考虑可信赖的数据集而非从头开始收集
    2. 进行平衡采样，参考 XLM-R，用 temperature-based sampling，并对已覆盖语言采取最少采样

  2. 语言适配

    答：1. 词表扩展（新 embedding 学习/推理速度/OOV）

    1. continued pretraining（forgetting）
    2. high-resource languages help low-resource languages
    3. PPL，NLU and NLG（measures）

Others

  1. 性格测试: 链接 1

  2. 自我介绍

  3. 请用三个词形容自己

  4. 每天的生活怎么安排

  5. 生活和工作上遇到的问题

  6. 优势和劣势

  7. 团队合作

  8. 为什么加入我们公司

  9. 有其他 offer 时怎么选择

  10. 职业规划（工作方向）: 链接

  11. 个人工作内容 & 部门工作内容（业务，技术栈）

  12. 工作地点：城市，具体位置，远程办公

  13. 薪资（期望薪资，最低接收工资） & 定级 & 绩效考核 & 晋升机制 & 转正: 链接 1，链接 2

  14. 工作时间：日常工作时间，单双休，年假

Search

    Table of Contents