昨天下午去hulu面试，在望京，好远……
一共两个小哥哥面试，第一面写了两道算法题，要求调试通过，不到半小时搞定，时间很充足，所以最后又给了一道bonus题，只要求给出思路，不用写代码。
第二面先聊了聊简历，然后问了一道算法题和一道概率题，算法题给出伪代码就行。

下面就是大家最关心的环节，面试题详述：

第一面第1题

要求实现一个栈，除了包含pop(), push(), empty()等基本操作外，还要实现min()函数，返回栈中元素的最小值。

算法

(单调队列/栈) $O(1)$

这道题目是AcWing原题：AcWing 41。

我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。
下面介绍如何维护单调栈：

• 当我们向栈中压入一个数时，如果该数 $\le$ 单调栈的栈顶元素，则将该数同时压入单调栈中；否则，不压入，这是由于栈具有先进后出性质，所以在该数被弹出之前，栈中一直存在一个数比该数小，所以该数一定不会被当做最小数输出。
• 当我们从栈中弹出一个数时，如果该数等于单调栈的栈顶元素，则同时将单调栈的栈顶元素弹出。
• 单调栈的栈顶元素，就是当前栈中的最小数。

时间复杂度分析：四种操作均不涉及循环，所以时间复杂度都是 $O(1)$.

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

class MinStack
{
public:
    int pop()
    {
        int t = data.top();
        data.pop();
        if (t == q.top()) q.pop();
        return t;
    }

    void push(int value)
    {
        data.push(value);
        if (q.empty() || q.top() >= value) q.push(value);
    }

    int min()
    {
        return q.top();
    }

    bool empty()
    {
        return data.empty();
    }

private:
    stack<int> data, q;
};

int main()
{
    int data[] = { 5, 3, 1, 2, 1, 3 };
    int n = (sizeof data) / 4;
    MinStack minStack;
    for (int i = 0; i < n; i++)
    {
        minStack.push(data[i]);
        cout << minStack.min() << endl;
    }
    cout << "--------------------" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << minStack.min() << endl;
        minStack.pop();
    }
    return 0;
}

第一面第2题

AcWing 797

给出 $n$ 个整数和 $m$ 个操作，每个操作输入三个数 $l, r, v$，表示将区间 $[l, r]$ 中的每个数加上 $v$. 问最终数列中每个数是多少。

算法

(部分和) $O(n + m)$

我们开一个新的长度为 $n$ 的数组 $b[N]$，初始化为0。
对于每个操作 $l, r, v$, 令 $b[l]$ 加上 $v$, $b[r+1]$ 减去 $v$。
则原数组 $a[N]$ 中的每个数 $a[k]$ 加上 $\sum_{i=1}^kb_k$ 即为最终结果(假设数组下标从1开始)。

简单解释一下原理：考虑每个操作$l, r, v$，我们令$b[l]$ 加上 $v$, $b[r+1]$ 减去 $v$，对原数组的最终结果会有何影响呢？
最终原数组中的每个数是 $a[k] + \sum_{i=1}^kb_k$，我们会发现：

1. 对于 $k \lt l$，即区间左边的数，$a[k]$ 没有加上 $v$；
2. 对于 $l \le k \le r$，即区间内的数，$a[k]$ 加上了 $v$；
3. 对于 $k \gt r$，即区间右边的数，$a[k]$ 先加上了 $v$，又减去了 $v$，没有影响；

时间复杂度分析：每个操作的时间复杂度是 $O(1)$，所以最终总时间复杂度是线性的，$O(n + m)$。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n, m;
int a[N], b[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (m--)
    {
        int l, r, v;
        cin >> l >> r >> v;
        b[l] += v, b[r + 1] -= v;
    }
    for (int i = 1; i <= n; i++)
    {
        b[i] += b[i - 1];
        cout << a[i] + b[i] << ' ';
    }
    cout << endl;
    return 0;
}

第一面bonus题

给定 $m$ 个骰子，每个骰子6个面，每个面上一个随机的小写字母。
给定一个长度为 $n$ 的字符串，由小写字母组成。
问是否存在一种方案，使得将所有骰子顺次排好，骰子的朝上的面恰好组成给定的字符串。如果存在，请给出任意一种可行方案。

算法

(最大流) $(m ^ 3)$

最大流的基本题。建图方式如下：

1. 从源点向每个骰子连条边，边的容量是1；
2. 统计字符串中每个字母出现的次数，从每个小写字母向汇点连条边，容量是字母出现次数；
3. 从每个骰子向6个面的字母分别连条边，容量是1；

则存在合法方案，当且仅当连向汇点的边都满流。我们可以根据骰子每条边的最终流量，构造出一个合法方案。

时间复杂度分析：最大流的Dinic算法的时间复杂度是 $O(n^2*m)$，$n$表示点数，$m$ 表示边数。此题中总点数 $(2 + m + 26)$，总边数 $m + 6m + 26$，所以总时间复杂度是 $O(m^3)$.

此题是bonus题，相当于附加题，不要求现场写代码，所以这里就不给出代码实现了。

第二面第1题

AcWing 1454

给出 $n$ 个互不相同的正整数，$(n \le 5000)$，每个数在5000以内。问存在多少个子集，使得子集中所有数的异或和是质数。

算法

（背包问题）$(n^2)$

0/1背包问题，$f[i][j]$ 表示考虑前 $i$ 个数，异或和是 $j$ 的方案数。
状态转移：$f[i][j] = f[i - 1][j] + f[i - 1][j \wedge a[i]]$。

复杂度分析：状态数 $O(n^2)$，状态转移复杂度 $O(1)$，所以总时间复杂度是 $(n^2)$；可以用滚动数组，将空间复杂度优化成 $O(n)$。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 5010, M = 10010, mod = 1e9 + 7;

int n;
int a[N], f[2][M];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        memset(f[i & 1], 0, sizeof f[i & 1]);
        for (int j = 0; j < M; j ++ )
        {
            f[i & 1][j] = f[i - 1 & 1][j];
            if ((j ^ a[i]) < M) f[i & 1][j] = (f[i & 1][j] + f[i - 1 & 1][j ^ a[i]]) % mod;
        }
    }

    vector<int> primes;
    for (int i = 2; i < M; i++)
    {
        int j = 2;
        while (j * j <= i)
        {
            if (i % j == 0) break;
            j++;
        }
        if (j * j > i) primes.push_back(i);
    }

    int res = 0;
    for (auto x : primes) res = (res + f[n & 1][x]) % mod;
    cout << res << endl;
    return 0;
}

第二面第2题

这是一道数学题，不要求写代码。
现在有 $n$ 个人抢红包，一共 $M$ 元。
要求给出一种随机算法，使得每个人期望得到的钱数相同，且每个人得到的钱数是个随机变量。但不要求每个人得到的钱数的取值范围是 $[0, M]$。

算法

1. 第一个人在 $[0, 2M/n]$ 范围内按均匀分布随机取个数，期望是 $M/n$；
2. 假设第一个人取的钱数是 $m_0$，则剩下的钱数是 $M - m_0$，它的期望是$E[M - m_0] = (n-1)M/n$，此时我们让第二个人在 $[0, 2(M - m_0) / (n - 1)]$ 范围内，按均匀分布随机取个数，则它的期望是：$(M - m_0) / (n - 1) = $$(n-1)M/n / (n - 1) = M / n$;
3. 依次类推，对于第 $k$ 个人，我们让他在 $[0, 2(M - \sum_{i=0}^{k-2}m_k)]$ 内按均匀分布随机取数，则他取到的数的期望是 $M/n$；