网易NLP算法实习笔试复盘从KMP到Transformer一次搞清考察重点每年三四月份都是实习生招聘最密集的时候很多同学私信问我当年网易NLP算法实习生笔试到底考了什么。说实话这类笔试和竞赛、面试题不太一样它不追求让你证明多天才的结论而是用一套组合拳快速判断你的基本功、代码能力和对NLP核心知识的熟悉程度。我翻了当年整理的笔记结合后来在真实业务里做文本分类、序列标注、信息检索的经验把这场笔试里最有代表性的考点重新梳理了一遍。这篇内容不是回忆录而是给准备投NLP算法岗的同学一份可复用的复习地图你照着这个框架去查漏补缺比漫无目的地刷题效率高得多。先说下这篇内容适合谁。如果你正在准备大厂NLP算法实习生、校招提前批笔试或者刚接触自然语言处理、想系统补算法基础这篇文章都值得你花二三十分钟读完。文中不会只列知识点名字而是把每个考点背后的“为什么考”“怎么答”“容易错在哪”讲透你读完能直接拿去用。1. 笔试画像网易NLP算法实习岗到底在考什么1.1 岗位能力模型拆解拿到任何一份NLP算法实习生的笔试题第一步不是做题而是先看清楚出题人想要什么样的人。网易这类互联网公司招NLP实习生目标非常明确你进来之后要能快速参与真实项目而不是从头教起。所以能力模型基本可以拆成四块。第一块是编程基本功包括数据结构、常用算法、代码实现速度和边界处理能力这部分通常占卷面30%到40%。第二块是机器学习基础覆盖概率统计、常见分类聚类算法、过拟合正则化这些通用知识因为NLP模型本质上还是机器学习模型只会在文本数据上做文章。第三块是NLP专业知识比如词向量、语言模型、序列标注、文本分类这些这是区分你和一个普通后端候选人最核心的部分。第四块是数学功底主要是概率、信息论和矩阵求导深度学习模型要能推导这部分在笔试里通常以选择题或简答题形式出现。有意思的是笔试往往不会只考“算法实习生”这三个字直接对应的内容。出题人默认你具备的是“能独立写代码解决文本问题”的能力所以数据结构和算法题占的比例不低甚至有些题目和NLP毫无关系。很多同学栽跟头不是因为不会做NLP题而是挂在基础编程题上。1.2 笔试模块与考察范围根据当年笔试的题型分布整张卷子大概分三个模块。第一模块是客观题单选多选混合覆盖数据结构栈、队列、二叉树、图、算法复杂度、概率论贝叶斯公式、期望方差、机器学习基础损失函数、正则化、评价指标和NLP基础TF-IDF、N-gram、词向量。这些题的特点是“看着都会一选就错”非常考验概念理解的精度。第二模块是简答题通常有2到3道要求用文字说明某个算法的原理或推导某个公式。常见的有“简述KMP算法的核心思想”“写出朴素贝叶斯分类器的公式并解释各符号含义”“说说Word2Vec中CBOW和Skip-gram的区别”。第三模块是编程题一般给2道左右难度从LeetCode中等题到简单业务场景题不等。常见类型是字符串处理、文本统计、动态规划也有少量涉及图或其他数据结构的题目。编程题占的分值最高有时候一道题就顶得上十道客观题。你可能会问为什么NLP岗位笔试还要考KMP和排序这些东西和文本处理关系没那么直接。答案是真实业务里有大量字符串匹配、日志解析、关键词提取场景公司希望你具备扎实的代码基础去处理这些脏活累活。1.3 按考点分布定复习优先级我建议你复习的时候不要平均用力。客观题里的NLP基础、概率论简答题里的朴素贝叶斯、KMP、Word2Vec编程题里的字符串处理这五块内容必须拿到大部分分数。数据结构里的复杂树操作、图论高级算法笔试中出现的频率其实没那么高简单了解即可。我见过不少同学花大量时间钻研红黑树、后缀自动机这类高级内容结果基础题反而丢分非常可惜。另外提醒一点编程题往往允许使用Python少数题目限定C或Java。当年网易笔试支持多语言但我建议你至少掌握一种顺手的主流语言尤其是Python因为它在NLP算法岗中普及度最高代码量也少。如果题目恰好只能用C那你至少要能完成字符串操作和排序这类基础代码。2. 数据结构与算法基础KMP、排序、堆这些硬骨头2.1 KMP算法与next数组手算一遍就懂了KMP是NLP相关笔试里出现频率极高的一道题。它的核心价值在于解决字符串匹配的效率问题。朴素的字符串匹配算法在匹配失败时只能回退到模式串头部重新比较最坏复杂度是O(n*m)KMP利用已匹配部分的信息让模式串尽量往右滑把复杂度降到O(nm)。为什么NLP岗位要考这个因为分词、关键词匹配、敏感词过滤这些基础NLP任务本质上都是字符串匹配KMP是绕不开的底子。KMP的难点是next数组的计算。next[i]的定义是模式串P的前i个字符组成的子串中最长相等前后缀的长度。我拿一个典型例子演示一下。给定模式串p abacaba我们来手算它的next数组下标从0开始next[0] 0。next[0] 0单个字符没有真前后缀。next[1]前两个字符ab前缀集合{a}后缀集合{b}没有公共部分所以next[1] 0。next[2]前三个字符aba前缀有a、ab后缀有a、ba最长公共前后缀是a长度1所以next[2] 1。next[3]前四个字符abac前缀a、ab、aba后缀c、ac、bac没有公共部分所以next[3] 0。next[4]前五个字符abaca前缀a、ab、aba、abac后缀a、ca、aca、baca公共部分只有a长度1所以next[4] 1。next[5]前六个字符abacab前缀a、ab、aba、abac、abaca后缀b、ab、cab、acab、bacab最长公共前后缀是ab长度2所以next[5] 2。next[6]前七个字符abacaba前缀a、ab、aba、abac、abaca、abacab后缀a、ba、aba、caba、acaba、bacaba最长公共前后缀是aba长度3所以next[6] 3。完整的next数组就是 [0, 0, 1, 0, 1, 2, 3]。提示不同教材对next数组的下标起始和定义有细微差异有的用next[0] -1有的用next[0] 0。笔试中如果出现具体题目先看清题目对next[i]的定义再动手避免因为定义不一致丢分。实际匹配时当主串和模式串在某一位不匹配模式串滑动位数 已匹配字符数 - next[已匹配字符数 - 1]。这个公式不用死记理解成“利用已匹配部分的最长相同前后缀跳过不可能匹配的位置”就够了。2.2 排序算法复杂度对比与典型问法排序算法是笔试客观题最爱的出题点核心考查点有两个复杂度、稳定性。时间复杂度对比上冒泡排序、插入排序、选择排序都是O(n^2)快速排序平均O(nlogn)、最坏O(n^2)堆排序、归并排序稳定在O(nlogn)。稳定性方面插入、冒泡、归并是稳定排序选择、快排、堆排是不稳定排序。有一道很常见的问法“已知数据基本有序用哪种排序最快”答案是插入排序因为基本有序的情况下它的最优复杂度是O(n)。还有一种问法是“求大量数据中的TopK用哪种排序”重点不是排序本身而是用堆维护一个大小为K的最小堆每次和堆顶比较复杂度O(nlogK)。另外快速幂也经常出现。它的原理是把指数拆成二进制比如计算a^1313的二进制是1101也就是a^13 a^8 * a^4 * a^1只需要做三次乘法和几次平方运算复杂度从O(n)降到O(logn)。笔试中它可能以“计算某大数的幂取模”编程题出现也可能以复杂度问答题出现。2.3 快速幂、贪心、堆编程题的常客编程题里出现的算法其实并不难套路化很强常见的有贪心、堆、双指针、动态规划、快速幂。贪心算法的核心是“每一步都取当前看起来最优的解”关键要能证明局部最优能推到全局最优。常见的贪心例子包括活动安排问题、区间覆盖问题、哈夫曼编码。笔试中贪心题通常不会太绕比如“给定一组区间的开始结束时间求最多能安排多少个不重叠的活动”这类题按结束时间排序然后贪心地选最早结束的区间就能得到最优解。堆排序则是解决TopK问题的标准答案。比如“从10亿个整数中找出最大的1000个数”如果先全部排序内存和时间上都扛不住用大小为1000的最小堆遍历一遍数据发现比堆顶大的就替换堆顶并调整堆最终堆里留下的就是最大的1000个。这个思路在文本场景里也很常用比如从海量日志中统计出现频率最高的关键词。NLP场景还有一个常客是Trie树前缀树。比如“给定一大批词典词判断某段文本中是否包含字典里的词”。用Trie树可以把多个模式串组织起来一次扫描文本完成多模式匹配比对着每个词分别调KMP快得多。笔试如果考到这类题用Trie树实现非常加分。3. 机器学习与数学基础从统计学习到检索排序3.1 概率统计与信息论高频考点NLP里面的很多模型都是概率模型所以概率统计是必考内容。我最常遇到的考点是贝叶斯公式给定P(A|B)、P(B)、P(A)求P(B|A)。考题经常换个马甲出现比如“已知某疾病的检出率是98%总人群发病率是0.1%求检测阳性的人真正患病的概率”看着是医学题本质是贝叶斯公式而且结果是反直觉的。这类题考查的不是计算而是你有没有用条件概率去更新先验信息的概念。另一个高频考点是信息熵包括熵的公式H(X) -Σp(x)logp(x)、交叉熵、KL散度。交叉熵在机器学习里就是分类任务的损失函数KL散度则用于衡量两个分布的差异。当年笔试有一道题问“KL散度是否对称能否作为距离度量”答案是KL散度不满足对称性和三角不等式所以不能直接当距离。严格地说D_KL(P||Q)和D_KL(Q||P)是不相等的。比如P是真实分布Q是模型分布D_KL(P||Q)更关注P中概率大的区域而反过来则更关注Q中概率大的区域。这个点理解透了后面理解变分推断里的ELBO就顺了。3.2 分类、聚类与检索KNN、KMeans、BM25机器学习基础题里KNN和KMeans出现频率很高但很多人会搞混。KNN是监督学习里的分类算法它不训练模型预测时直接计算待分类样本和所有训练样本的距离取最近的K个点投票决定类别。KMeans是无监督聚类算法它的目标是把样本分成K簇使得每个样本到所属簇中心的距离平方和最小。KNN里K是“邻居数”KMeans里K是“簇数”千万别弄混。KMeans的迭代过程本身也有考点初始化K个中心按最近中心分配样本重新计算每簇中心再分配直到中心收敛。笔试可能会问你“KMeans的初始中心怎么定”答案是随机选择K个样本作为初始中心或用KMeans策略让初始中心尽量分散减少陷入局部最优的概率。检索排序相关的考点则离不开BM25。BM25是信息检索里常用的文本相关性评分函数它在TF-IDF基础上做了改良考虑了文档长度归一化和词频饱和效应。公式的核心思路是一个词在文档中出现的次数越多相关性越高但这种增长不是线性的而是逐步衰减的同时词在文档中的占比要结合文档平均长度来归一化避免长文档天然占便宜。笔试一般不会要求你完整写出BM25公式但可能会问“BM25相比TF-IDF的改进点是什么”或“为什么词频要设置饱和上限”。从本质上答就是因为一篇文档里同一个词出现20次的贡献不是出现10次的两倍词频的边际收益在下降BM25通过对数函数和参数k1、b来刻画这种非线性关系。3.3 KL散度与ELBO变分推导的入门题如果你投的是偏研究型的NLP算法岗位简答题里出现KL散度和ELBO的推导是很正常的。ELBO是变分自动编码器VAE和变分推断里的核心概念全称是Evidence Lower BOund证据下界。推导逻辑说起来很简单。我们希望用变分分布q(z)去近似真实后验p(z|x)两者之间的KL散度是D_KL(q(z)||p(z|x))。但p(z|x)很难直接计算于是通过贝叶斯公式变形把log p(x)拆成ELBO和KL散度之和log p(x) ELBO(q) D_KL(q(z)||p(z|x))因为KL散度恒大于等于0所以ELBO是log p(x)的下界。最大化ELBO等价于最小化KL散度这就是变分推断“用优化代替采样”的核心思想。笔试如果考这道题不需要你把每一步推导都写出来但要能说清楚第一ELBO存在的意义是解决后验分布不可计算的问题第二ELBO和KL散度的关系第三为什么最大化ELBO等价于让q(z)逼近真实后验。如果能把公式写出来解释每个符号的含义得分会更高。4. NLP核心题从词向量到注意力机制4.1 词向量与语言模型基础NLP笔试最核心的模块就是NLP基础词向量几乎是必考内容。Word2Vec是2013年提出的经典词向量方法包含CBOW和Skip-gram两种结构。CBOW是给定上下文预测中心词Skip-gram是给定中心词预测上下文。训练时两个模型都用了优化技巧层次Softmax和负采样。负采样的思路是每次训练只随机选少量负样本而不是对整个词表做Softmax计算量大幅下降。当时笔试有一道高频简答题“Word2Vec和传统N-gram语言模型有什么区别”标准答法分三点第一Word2Vec的目标是学习词向量表示N-gram目标是计算句子的概率第二Word2Vec用神经网络把词映射到低维稠密向量N-gram是统计离散的共现次数第三Word2Vec的输入是稠密的分布式表示能捕捉词语的语义相似性N-gram则面临数据稀疏问题。后来ELMo、BERT这些预训练模型出现后词向量问题会升级成“请说明Word2Vec、ELMo、BERT三种词向量表示的区别”。核心区别在于Word2Vec得到的词向量是静态的一个词不管在什么上下文里都是同一个向量无法解决一词多义ELMo是动态的通过双向LSTM根据上下文生成词向量BERT更进一步通过Transformer的双向编码器和掩码语言模型来生成上下文相关的表示但代价是计算量更大。这个话题虽然是2018年前后逐渐热起来的但放在今天的笔试里依然是高频题建议你按这个框架准备。4.2 序列标注HMM与CRF序列标注是NLP里非常经典的任务包括分词、词性标注、命名实体识别。传统的序列标注模型以HMM和CRF为代表笔试简答题里经常让阐述两者区别。HMM是生成式模型它建模的是联合概率P(X,Y)也就是观测序列和状态序列同时出现的概率。它有两个核心假设一是当前状态只依赖上一个状态二是当前观测只依赖当前状态。参数包括初始概率向量、状态转移矩阵、发射概率矩阵。解码时用维特比算法求解最优状态序列。CRF是判别式模型建模的是条件概率P(Y|X)。它不需要HMM那些独立性假设而是通过特征函数来灵活描述上下文信息。相比HMMCRF能利用更丰富的特征并且在观测到整个序列后再做全局归一化避免了标注偏置问题。在实际的命名实体识别任务中CRF的效果通常优于HMM。笔试里如果考CRF的损失函数核心是条件概率的负对数似然。训练目标就是最大化正确标注序列的条件概率这个概率通过Softmax在状态转移矩阵和发射矩阵上计算。它能保证全局最优解因为不像逐位置分类那样只看局部。4.3 注意力机制与Transformer现在的必考项虽然2018年实习生笔试那会儿Transformer刚提出不久常考的NLP新知识还不像现在这么密集但放到今天备考Transformer和注意力机制已经是绕不开的必考内容了。先说Attention机制的核心思想对于当前要生成的每个词它不会只看前一个词RNN思路而是把输入序列中所有词的信息按权重汇总起来权重由Query和Key的相似度决定最终从Value中提取信息。自注意力Self-Attention则是Query、Key、Value都来自输入序列本身让每个词都能直接看到其他所有词解决了RNN长距离依赖难捕捉的问题。Transformer里最重要的创新点有三个自注意力、多头注意力、位置编码。多头注意力把Q、K、V分别映射到多个子空间并行计算注意力捕捉不同方面的语义关系。位置编码则是因为Transformer没有循环结构必须额外注入序列位置信息。笔试常见的问法是“为什么Transformer需要位置编码”或者“多头注意力的意义是什么”抓住这两个关键点就能答到点上。BERT则是在Transformer基础上进行预训练核心思路是用大规模无标注文本训练语言模型再在下游任务上微调。它用了掩码语言模型随机遮挡部分词让模型预测被遮挡的词和下一句预测两个预训练任务。笔试问“BERT和GPT的区别”是高频题答案核心是BERT是双向编码器适用于理解类任务GPT是单向解码器适用于生成类任务因为每个token只能看到它左边的token。5. 编程实操题完整推演一道文本处理题的全过程5.1 题目理解与思路设计编程题往往是整场笔试区分度最大的一部分我拿一道很有代表性的模拟题来讲。题目大意是给定一个很长的字符串S和一个字典集合D统计S中出现次数最多的字典词并输出该词和出现次数。这类题目看起来很简单但坑不少因为S可能长达百万级字符字典词可能有上万个。如果你对每个字典词都调一次KMP去匹配复杂度就是O(len(D) * len(S))大概率超时。这就需要你在解题时主动想到多模式匹配方法。我的思路分两步第一步用字典词构建Trie树第二步扫描S在每个位置尝试从Trie根节点开始匹配能匹配到某个单词结尾就把对应计数加一。整个过程只需要遍历一次S每步操作和字典词平均长度成正比总体复杂度近似O(len(S) * avg_word_len)可行性大大提升。5.2 代码实现与边界处理Python实现Trie树加计数的代码大致如下class TrieNode: def __init__(self): self.children {} self.is_end False self.word None def build_trie(words): root TrieNode() for w in words: node root for ch in w: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.is_end True node.word w return root def count_words(text, words): root build_trie(words) counts {w: 0 for w in words} n len(text) for i in range(n): node root j i while j n and text[j] in node.children: node node.children[text[j]] if node.is_end: counts[node.word] 1 j 1 return counts text the quick brown fox jumps over the lazy dog words [the, quick, fox, dog, over] print(count_words(text, words))这段代码有几个边界点要特别注意。第一单词匹配是重叠匹配还是非重叠匹配题目要求不同代码逻辑就不同。上面代码每次从每个位置开始尝试匹配得到的是重叠匹配的计数。如果题目要求非重叠匹配需要额外维护一个最近匹配位置当前匹配的起始位置在上一次匹配结束之前就跳过。第二同一个位置如果同时匹配到不同长度的词比如“cat”和“category”都以“cat”开头按上面的逻辑两个都会统计到这是符合常理的做法但如果题目只要求最长匹配你需要先遍历完所有可能的前缀再决定。5.3 复杂度分析很关键很多时候编程题不仅要求代码正确还要求你写清楚时间复杂度和空间复杂度甚至在代码注释里标注出来。这道题的时间复杂度是O(len(S) * max_word_len total_len(words))空间复杂度是字典词总字符数。这里额外提一点笔试判题系统通常比较严格内存限制通常不会太大Python的字典结构本身内存开销不小。如果你预计字典词总量达到几十万级别可以考虑用数组代替字典存储子节点或者用双数组Trie进一步压缩内存。不过对于笔试题来说用字典实现Trie树已经够了不必过度优化。6. 复习路上的常见问题与避坑记录6.1 时间分配与复习优先级这些年看到太多人复习NLP算法笔试时踩同一个坑钻牛角尖。比如花一周时间精读Transformer论文里的数学推导却连KMP的next数组都手算不对。这种投入产出比很低的复习方式在笔试面前非常吃亏。我的建议是如果只有不到一个月准备时间按“四三二一”的原则分配四成时间刷编程题重点覆盖字符串、数组、动态规划、栈队列三成时间过机器学习基础重点掌握贝叶斯、KNN、KMeans、损失函数和评价指标两成时间过NLP基础重点掌握Word2Vec、语言模型、HMM、CRF和注意力机制剩下一成时间看简答题总结常见考点和答题模板。6.2 只刷题不看原理的教训另外一个常见误区是只刷LeetCode不复习理论基础。LeetCode刷题练的是代码能力但笔试里的选择题和简答题靠的是系统性理解。我见过有同学能把动态规划写得很好却说不清楚维特比算法和动态规划的关系这就是“会写代码但不理解算法”的典型表现。反过来理论上也要注意“理解到位”。比如让你解释“为什么朴素贝叶斯假设特征独立”你要能说出这个假设让联合概率分解成各特征概率的乘积大幅减少了参数数量虽然现实中特征不独立但很多场景下依然能取得不错的效果。6.3 真题资源与手写代码训练方法最后说下推荐的学习资料和练习方法。笔试和面试准备资料里吴恩达的机器学习课程、《统计学习方法》前几章、周志华的《机器学习》前几章覆盖了大部分笔试客观题和简答题的知识点。LeetCode上的字符串、数组、动态规划、贪心题刷150道左右就够应付笔试编程题了。手写代码训练是很重要但容易被忽略的一环。我强烈建议你在准备期间不要一直用IDE而是在纯文本编辑器里写代码。笔试环境通常没有代码补全和自动纠错你在IDE里能跑通并不代表在白板环境下能写对。我备考时每天至少手写两道完整代码题写完自己在纸上人工跑一个简单用例验证这个方法极大提升了我在笔试环境里的代码准确率。另外把每次笔试中遇到的陌生知识点整理成错题本。比如我当时整理过“KL散度为什么不满足对称性”“为什么堆排序不稳定”这类易错点笔试前翻一遍错题本比重新看一遍书效率高得多。说回这场网易NLP算法实习笔试它考察的东西说多不多说少也不少。这些年我见过太多人去死磕偏题难题却忽略了最基础的KMP、朴素贝叶斯、Word2Vec这些必考点。根据我个人的体会这类笔试的通过率靠的不是天赋而是对基础知识的掌握精度和手写代码的熟练度。如果你正在准备NLP算法方向的实习或校招先把这篇里提到的每个考点过一遍再针对薄弱项集中突击笔试通过的概率会比盲目刷题高很多。最后再分享一个小建议笔试前找一套往年真题严格按考试时间模拟一遍熟悉节奏很多考场上的手忙脚乱其实都是因为缺乏模拟导致的。