上次聊理想，这次谈现实。本篇将分享笔者顶着12小时时差，清晨笔试凌晨面试，迷迷瞪瞪地获取到的本季校招第一手资料，供大佬们来年开春或是秋招备用。所有题目均只作大致描述，代码及详解会于后续文章发布，所有内容均隐去雇主及题目细节，仅供个人学习使用。

总体情况

个人参加了大概十场笔试。考试形式上，“选择题与编程题搭配服用”和“只考编程题，可能要求做性格测试”的雇主各占一半。出自 LeetCode 的原题很少，但基本上是换汤不换药，都是“瞎编一个故事 XD，然后让你套到某个具体数据结构和算法上去解题”，范浩强大神“编程竞赛水浅”的经验之谈诚不欺我(果然最难还是数学->发现新算法+证明其正确性Orz)。考试时长在两小时左右(本中年猹动作迟缓，经常笔试结束后才做完…)。

具体来看：

• 类似 B 树 vs B+ 树之类的概念只会在选择题中出现。鉴于选择题内容五花八门，在此不做具体讨论。
• 编程题里一般有一道“轻松上分，交个朋友”题(对 Dalao 而言全是友情赠分题)。
• 各位雇主对于动态规划(DP)甚是钟爱，背个包都要搞点五花八门的限制。
• 偶尔会有雇主出一些只能在小数据量下跑通的机智题，对实际项目意义不大，可适度高冷，考试时将其暂时忽略。若是碰到需要用快速傅立叶变换(FFT)来加速多项式乘法的问题也建议暂时忽略 :)

题目类型

BFS/DFS/MST/2-SAT

基于图的问题比较多，以下是常见考法：

• 引导考生使用深度优先搜索(BFS)配合动态规划(DP)在给定限制条件下求解优化问题(如：已知xxx, 求 yyy 的最小值)。
• 引导考生基于广度优先搜索(DFS)配合优先级队列(PQ，通过堆(heap)来实现比较方便)寻找有向图的最短路径。
• 引导考生通过 Kruskal 等算法构建最小生成树(MST)来计算“造桥”等情景下的最小代价。

实现上不需要用剪枝， A* 等特殊处理，或做线性 find-k 算法以及 Yao’s MST 构造算法(based on boruvka’s algorithm)等小众优化。

几小时前刚刚见到一个笔试题，出题者用十分刻意且奇怪的故事引导考生去解 2-SAT 问题并在此基础上计算可满足最多子句(Clause)的组合数，怪味十足hhhh。

Greedy

贪心(Greedy)策略导向的题目也比较多(比如上面提到的找最短路和最小生成树构造)，具体例子还有给定一组区间，寻找最大不相交区间集的元素个数。该类问题最麻烦的是其常和动态规划仅一步之遥，开始误判了解题路线的话在有限时间里就很难拉回来了 :( 比如“计算最少插入数使括号匹配”的问题可以很方便地通过贪心解决，但涉及到括号的增/删/改甚至多种括号混用的情况就让人一头雾水，中途再去算编辑距离基本来不及了。

Math

考数学题的雇主很少，基本上只有微信娘家才会例行放一两道该类型题目，内容要么是求方程近似解，要么是计算某种具体情境下的概率, 不拼手速，没思路的话可以直接跳过(比如不知道 e 是 (1+1/n)^n 或以 n 的阶乘为底的级数的极限的话就机智弃题 :0 )

DP

动态规划类的题目不方便调库求解且形式多样，各家都很爱出此类题目，从最大子串和、最长上升子序列，到各种奇奇怪怪的背包。实在是门类繁多，结合树来考更可以玩出新花样。本质上讲，DP 实际还是递归的一种鸡贼实现方法，通过缓存子问题结果把原问题从 NP 拉到 P，本质上还是要先找到递归关系和递归基。（如果面试官出的题目全是判定 n 个元素的集合是否可以筛出部分元素求和为特定值的问题，大家都做个开心的 NPC 多好 :)

面试技巧

木有hhhh，只要考试不作弊，面试真心聊，适当换位思考，其他随缘就好，毕竟 offer 不能叠起来用，“以好充次”留给同辈更多机会岂不妙哉 XD 遇到心仪雇主，适当拽点”快排在细化的渐进复杂度意义下稍优于归并排序”的料也能使面试官眼前一亮，至于“料在何方”, 自然要祭出邓公的数据结构与算法 MOOC 大讲堂👍 数据结构(上), 数据结构(下), THUOJ, DSA.WORKSPACE，十二道编程题做了不吃亏，做了不上当(就是不能用 STL 各种结构全要手动实现 hhhh)

学术界与工业界的紧密联系仅是近年的事。尝试跳出校园，从追求 SOTA 到追求简单、高效、可扩展的实现(例: 实现并行版本的稀疏矩阵乘法)并培养业务思维才是一个决定“外出务工”的新毕业生更应专注的方向。

打完收工 :) 下期开始做详解和配代码，本期作测试用途先展示一个用 buff 加速 mergesort 并降低内存负载的小技巧，烦请大屏查看:

int merge_and_count(long long *arr, int lo, int mi, int hi, long long *buff)
{
    int res = 0;
    for (int i = lo; i < mi; i++) buff[i] = arr[i];
    
    int i = lo, j = mi, curr = lo;
    
    while (i < mi && j < hi) {
        if (buff[i] <= arr[j])
        {
            arr[curr] = buff[i];
            i++;
        } else {
            arr[curr] = arr[j];
            res += (mi - i);
            j++;
        }
        curr++;
    }
    
    while (i < mi) {
        arr[curr++] = buff[i++];
    }
    
    while (j < hi) {
        res += (mi - i);
        j++;
    }

    return res;
}


int count_by_mergesort(long long *arr, int lo, int hi, long long *buff)
{
    if (hi - lo < 2) return 0;
    int mi = (lo + hi) >> 1;
    int res1 = count_by_mergesort(arr, lo, mi, buff);
    int res2 = count_by_mergesort(arr, mi, hi, buff);
    int res3 = merge_and_count(arr, lo, mi, hi, buff);
    return res1+res2+res3;

}

ps, 麻烦 “share” 本篇给需要的同伴，后续内容会在此公众号继续刊发，笔芯♥️