Summarization of Interview Problems and Solutions

This blog is aimed at collecting interview problems and solutions through nowcoder,books and so on. So, I will update this article usually. Best luck for me and everyone to find a satisfactory intern!🤩

Machine Learning

ByteDance AI LAB

CRF讲一下？(原理与推导)

答：看自己写的关于CRF的那篇博文。从HMM->MEMM->CRF。

ROC曲线？AUC的计算？

答：

bagging vs boosting?

答：1. bagging叫做重采样，譬如说，给定一个含有m个样本的训练集，我们从中随机抽取一个样本，然后再放回，依次循环，直到得到T个含有m个元素的训练集，然后，我们就在这T个训练集中训练T个模型，最后在畸形模型融合。bagging降低的是方差。值得注意的是，在RF中，我们种子进行决策树分裂的时候，我们不是从所有属性中选取最优属性，而是从一个属性子集中选取最优属性，这也是为了降低各个弱分类器之间的相关性。重采样也是为了降低各个弱分类器之间的相关性。

2. boosting是提升方法。它的思路是每次上一次的残差作为下一次的输入。它关注的是降低偏差。因为，各个弱分类器之间具有强相关性。

HMM讲一下？原理与推导
GBDT VS XGBoost

GBDT的一种算法，而XGBOOst是对GBDT的一种很好的工程化的实现。
在以CART为基本分类器的时候，XGBoost中加入了正则化项，控制模型的复杂度，防止模型出现过拟合，而GBDT则没有。
XGboost中对cost function使用二阶的泰勒展开，能够同时使用一阶与二阶信息，而GBDT值使用一阶信息。
XGBoost中，增加了对缺失值的处理，GBDT中没有。
XGBoost中支持多种基分类器，譬如：gbtree、dart、linear，而GBDT只采用CART。

解答：https://blog.csdn.net/qq_28031525/article/details/70207918

Natural Language Processing

ByteDance AI LAB

单向双向 BERT 与BiLSTM 有什么不同？其实问的就是ELMo与BERT的区别。
如何解决梯度消失弥散？

答：在一般的NN中，我们主要是在随机初始化参数的时候，需要留意一下。

1	w=np.random.randn(shape)*np.sqrt(1/n)

这个叫做Xavier初始化。其中，n表示前一层的神经元的数目。当然还可以替换激活函数，譬如使用relu。还有BN，正则化等等。

在RNN中，使用LSTM或者GRU单元来代替普通的RNN单元，解决梯度消失问题。对于梯度爆炸问题，我们使用梯度裁剪来解决。具体来说，就是当梯度超过某个阈值的时候，我们对齐进行归一化操作，使其活在某个区间范围内。在tf中，使用tf.clip_by_norm().

梯度消失：1初始化(xavier). 2 rnn->lstm/gru 3.transformer->方差 4. 替换激活函数

过拟合：1.dropout 2.bn/ln/gn/in 3.减少参数，剪枝；4.增加数据。5.增加噪声(对抗训练、对数据本身进行操作)

(重要)wordembedding有哪些？（发展史以及word2vec的两种训练方法与两种加速方法）
transformer讲一下？（KQV position）
交叉熵loss公式？
pytorch的代码流程（我是这样回答的：预处理数据/词表-写好模型-定义损失和优化器-训练-测试）
Dropout的原理？
sgd与adam的区别？
L1L2正则化？

答：L0正则，表示是不是0的参数的个数，公式：$\sum_{j=1,w_j\not=0}^{m}w_j^0$；L1正则，表示所有参数的一范数的和，公式：$\sum_{j=1}^{m}|w_j|$；L2张正则，表示所有参数的二范数的平方，公式：$\sum_{j=1}^{m}|m_j|^2$。这些正则项实际上都是到原点的马式距离($L(x_i,x_j)=\sum_{k=1}^{m}{(\sqrt {(x_i^{(k)}-x_j^{(k)})^2})}^p$)。正则项

L1为什么比L2更容易获得稀疏解？（可以从梯度的角度来看）l1正则化

讲一下BERT？
SoftMax + CrossEntropy的反向梯度求导
sentence embedding vs docment embedding?
Tf-idf?
LR中为什么使用CE，而不是MSE？

答：如果使用MSE的话，很容易出现梯度消失问题。LR中的MSE与CE选择问题

Sigmoid，Tanh，Relu等激活函数的优缺点

答：sigmoid函数的优点：1.将数据压缩到（0，1）范围内；2.sigmoid函数是光滑的，也就是它处处可导；3. sigmoid函数的值域为（0，1）,那么可以被作为概率，很好的解释模型；sigmoid函数的缺点：1.容易发生梯度消失问题；2.不是关于原点中心对称，所以模型收敛速度会比较慢。中心对称；3. 计算量大。

tanh函数的优点：解决了sigmoid函数不是中心对称的问题；缺点：仍然存在梯度消失的问题。

relu函数的优点：导数稳定，计算量小；relu函数的缺点：容易发生dead relu的情况。也就是当输入小于0的时候，经过relu之后，输出为0，这样的倒数也会为0，梯度很难传递。

leaky relu：解决了dead relu问题。但是参数是人为指定的。

pRELU：让参数也跟着网络一块训练，得到的参数更加合理。

激活函数的比较

讲讲subword算法？

答：BPE、wordpiece。

label smoothing？

答：LSR通常用于softmax中。在普通的softmax中，只会关注正确标签位置的损失，而不去考虑其他位置的损失，这就就会导致模型过于关注增大正确标签位置的概率，而不去关于减小预测错误标签的概率，这样的结果，就是模型在训练集上拟合的很好，而在测试集上表现的不好，也就是会导致过拟合。

而在LSR中，我们引入一个平滑因子 $\epsilon$，那么 $\hat y=(1-\epsilon)*y+\epsilon*u$ ，其中 $u$ 表示一个均匀分布。实际上LSR就是引入噪声。从而，让模型不仅考虑在标签正确位置的损失，也考虑在标签错误位置的损失，让导致模型的损失增大，从而导致模型的学习能力提高。也就是说，要降低损失，就必须学习的更好，也就是迫使模型向增大正确分类的概率以及减小错误分类的概率的方向前进。LSR在transformer中有使用。LSR的介绍

Xavier初始化和He初始化

答：Xavier初始化和He初始化

L1优化方法？（坐标下降法、LARS角回归）

答：坐标轴下降法

SVM算法核函数的选择

答：1.当没有任何先验知识的时候，选择RBF核函数；2.当特征数远远大于样本数的时候，选择线性核，因为此时，如果选择高斯核的话，我们会将特征映射到更加复杂的空间中，会导致模型容易过拟合；3.当样本数远远大于特征数的时候，选择线性核；当样本数一般大小，特征数较小的时候，选择高斯核。

如何·处理不平衡问题？

答：1。上采样与下采样。上采样：对少样本的类别进行采样，将采样后的样本加入数据集。重复多次，从而得到数据分布更加平衡的数据集。下采样：对多样本的类别进行采样，将采样后的样本移出数据集，重复多次，从而得到数据分布更加均匀的数据集。

2.修改权重 3。bagging；4. 多任务联合学习。5.对于二分类问题来说，激情问题转化为异常检测。答案

Skip-gram的loss？

Mathematics

ByteDance AI LAB

x, y是独立的随机变量，方差期望已知，那么如何求 xy 的方差？

$D(XY)=E[(XY)^2]-[E(XY)]^2=E(X^2)E(Y^2)-[E(X)E(Y)]^2$

常见的公式：

$D(X)=E(X^2)-[E(X)]^2$
$如果X与Y独立，那么 D(X+Y)=D(X)+D(Y)$
$如果X与Y独立，那么 E(XY)=E(X)E(Y)$
$方差的定义：D(X)=E[[X-E(X)]^2]$
$设X与Y是两个随机变量，那么D(X+Y)=D(X)+D(Y)+2cov(X,Y)$
$协方差：Cov(X,Y)=E\{[X-E(X)][Y-E(Y)]\}=E(XY)-E(X)E(Y)$

期望，方差，协方差

Algorithm

ByteDance AI LAB

topk问题

topk问题一律使用最小堆解决。

解答：https://blog.csdn.net/zyq522376829/article/details/47686867?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

一道编程题：
给一个数组A，如何变成数组B，B要满足这个形式 B0 >= B1<= B2 >= B3 <= B4….【leetcode324】
（不需要对数组排序，只需要将数组A按照中位数分成两集合，大集合内的数放奇数位，小集合内的数放偶数位。分成两集合的方法：先得到数组长度len，然后使用快排剪枝或者使用堆来选出两个大小为len/2的集合，可看作topk问题）
最快速度最小空间求一个数组的第k小
如何找到一个无序数组的中位数

解答：1.使用排序算法，这是最直接的想法；2.建立最小堆。这里要分情况讨论：当数组元素数目n为奇数的时候，我们取(n+1)/2个元素来建立最小堆；之后，遍历剩余的元素，比堆顶元素大，就替换堆顶元素，最后，堆顶元素就是中位数。

已知数组a和正整数m，从数组a中找到一个连续子序列，使得连续子序列的和>=m，求满足条件的最短的连续子序列的长度。
海量数据处理题目

解答：https://blog.csdn.net/v_july_v/article/details/6279498/

最长公共子序列.

解答：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        if(text1.size()==0 || text2.size()==0) return 0;

       vector<vector<int> > dp(text1.size()+1,vector<int>(text2.size()+1,0))
      
       for(int i=1;i<=text1.size();i++){
           for(int j=1;j<=text2.size();j++){
               if(text1[i-1]==text2[j-1]){
                   dp[i][j]=dp[i-1][j-1]+1;
               }
               else{
                   dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
               }
           }
        }

        return dp[text1.size()][text2.size()];
    }
};

10亿int，4GB内存，找出所有不重复数字？

答案

统计词频

bash命令：

1	cat words.txt \| tr -s ' ' '\n' \| sort \| uniq -c \| sort -r \| awk '{print $2" "$1}'

IQ Tests

现在有三枚硬币，一个是一正一反，一个是两面都是正，一个是两面都是反，现在随机抛出一枚硬币是正面，那么这枚硬币的反面也是正面的概率；（2/3）

解答：$\frac {1/3}{1/3*1/2+1/3}=2/3$

Python/C++

python的多线程？(假的多线程)
python的浅拷贝与深拷贝。
yield？yield的使用

#yield的使用
def print_number(n):
    for i in range(n):
        print(f"{i}")
        yield

#注意a=[i for i in range(n)]，当改成：a=(i for i in range(n)),就变成一个generator了！
def foo():
    print(f"starting.......")
    while True:
        res=yield 4
        print(f"res: {res}.")

if __name__=="__main__":
    a=print_number(10)
    for i in a: continue
    
    print('*'*20)
    g=foo()
    print(next(g))
    
    print('*'*20)
    print(next(g))

python中的genertor？generator总结
rand7生成rand10？

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int rand7(){
	//https://www.cnblogs.com/xiaokang01/p/9786751.html
	//srand保证每次产生的随机数是不一样的
	srand((int)time(0));
  return rand()%7+1;
}

int rand10(){
	int i=0;
  //1 2 3 4 5 6 7
	//0 1 2 3 4 5 6
	//0 7 14 21 28 35 42
	// 1 49
	// 40 41 42 43 44 45 46 47 48 49
	do{
    	i=(rand7()-1)*7+rand7();
  	}while(i>40);

	  return i%10+1;
}

int main(){   
  int x=rand10();
  printf("%d\n",x);
  return 0;
}

AUC计算

https://www.bioinfo-scrounger.com/archives/767/

word trie 实现

import os

class trie(object):
    def __init__(self):
        self.root=dict()

    def insert(self,word):
        cur_dict=self.root
        for char in word:
            cur_dict=cur_dict.setdefault(char,{})
        cur_dict["is_word"]=True

    def search(self,word):
        cur_dict=self.root
        for char in word:
            if char in cur_dict.keys():
                cur_dict=cur_dict[char]
            else:
                return False
        else:
            if "is_word" in cur_dict.keys():
                return True
            else:
                return False

    def recursive(self,word_list):
        match_list=[]

        for i in range(word_list.__len__()):
            for j in range(0,i):
                if self.search(word_list[j:i]):
                    match_list.append(word_list[j:i])

        return match_list


if __name__=="__main__":
    keywords=["abc","dec","s","ew"]
    query="dabcdewsa"

    word_trie=trie()
    for word in keywords:
        word_trie.insert(word)

    matched_keywords=word_trie.recursive(query)
    print(" ".join(matched_keywords))

kmeans

import numpy as np
from matplotlib import pyplot as plt


def cal_dis(vec_a, vec_b):
    '''
    欧式距离
    :param vec_a: a vector, 1d
    :param vec_b: a vector, 1d
    :return: scaler
    '''
    return np.sqrt(np.sum(np.power(vec_a - vec_b, 2)))


def initialize_centroids(data, k):
    '''
    初始化质心
    :param data: [n_samples,n_features]
    :param k: k, a scalar
    :return: [k,n_features]
    '''
    n_features = np.shape(data)[1]

    centroids = np.mat(np.zeros((k, n_features)))

    for i in range(n_features):
        min_i = np.min(data[:, i])
        max_i = np.max(data[:, i])

        range_i = np.float(max_i - min_i)

        centroids[:, i] = min_i + range_i * np.random.rand(k, 1)

    return centroids


def kmeans(data, k):
    '''
    主函数
    :param data:[n_samples,n_features]
    :param k: k ,a scalar
    :return: centroids:[k,n_features], cluster_matrix:[n_samples,2]
    '''

    n_samples = np.shape(data)[0]

    # [k,n_features]
    cetroids = initialize_centroids(data, k)
    cluster_matrix = np.mat(np.zeros((n_samples, 2)))

    convergence = False
    while not convergence:
        convergence = True
        for i in range(n_samples):
            min_dist = np.inf
            min_idx = -1

            for j in range(k):
                dist_j_i = cal_dis(cetroids[j, :], data[i, :])
                if dist_j_i < min_dist:
                    min_dist = dist_j_i
                    min_idx = j

            if cluster_matrix[i, 0] != min_idx:
                convergence = False

            cluster_matrix[i, 0] = min_idx
            cluster_matrix[i, 1] = min_dist ** 2

        # 更新新的质心
        for center in range(k):
            center_data = data[np.nonzero(cluster_matrix[:, 0].A == center)[0]]
            cetroids[center, :] = np.mean(center_data, axis=0)

    return cetroids, cluster_matrix


if __name__ == "__main__":
    data = np.random.randn(20, 2)
    cetroids, cluster_matrix = kmeans(data, 3)
    plt.scatter(data[:, 0], data[:, 1], c=np.array(cluster_matrix)[:, 0].tolist())
    plt.scatter(cetroids[:,0].tolist(),cetroids[:,1].tolist(),c="r")
    plt.show()