今日头条2018校招大数据/算法方向（第一批）详解
问答题
1、给定一棵树的根节点, 在已知该树最大深度的情况下, 求节点数最多的那一层并返回具体的层数。
如果最后答案有多层, 输出最浅的那一层，树的深度不会超过100000。实现代码如下，请指出代码中的多处错误：
/* * Node 结构体，包含一个元素为 Node * 的向量 * 用来存储树结构的父子关系 */
struct Node {
vector<Node*> sons;
};
/* * 深度优先遍历，用来遍历树并且对每层结点数计数 * node 为父节点的指针，dep 为深度，counter 为存储每层结点数的数组 */
void dfsFind(Node *node, int dep, int counter[]) {
counter[dep]++; // 计数操作
for(int i = 0; i < node.sons.size(); i++) { // 错误 1 指针操作错误
dfsFind(node.sons[i], dep, counter); // 错误 2 指针操作错误，深度控制不当
}
}
/* * find 函数，root 是树的根，maxDep 是树的最大深度 */
int find(Node *root, int maxDep) {
int depCounter[100000]; // 错误 3 存储树的每层结点数，可能存在越界问题
dfsFind(root, 0, depCounter); // 调用深度优先遍历函数，
// 传入根和初始深度以及存储数每层结点数的数组
int max, maxDep; // 错误 4 未初始化、命名冲突
for (int i = 1; i <= maxDep; i++) {
if (depCounter[i] > max) {
max = depCounter[i];
maxDep = i; // 错误 5 被赋值变量错误
}
}
return maxDep; // 错误 6 返回错误变量
}参考答案：
/* * Node 结构体，包含一个元素为 Node * 的向量 * 用来存储树结构的父子关系 */
struct Node {
vector<Node*> sons;
};
/* * 深度优先遍历，用来遍历树并且对每层结点数计数 * node 为父节点的指针，dep 为深度，counter 为存储每层结点数的数组 */
void dfsFind(Node *node, int dep, int counter[]) {
counter[dep]++; // 计数操作
for(int i = 0; i < node->sons.size(); i++) { // 错误 1 指针操作错误
dfsFind(node->sons[i], dep + 1, counter); // 错误 2 指针操作错误，深度控制不当
}
}
/* * find 函数，root 是树的根，maxDep 是树的最大深度 */
int find(Node *root, int maxDep) {
int depCounter[100003]; // 错误 3 存储树的每层结点数.可能存在越界问题
dfsFind(root, 0, depCounter); // 调用深度优先遍历函数，
// 传入根和初始深度以及存储数每层结点数的数组
int max = 1, res = 0; // 错误 4 未初始化、命名冲突
for (int i = 1; i <= maxDep; i++) {
if (depCounter[i] > max) {
max = depCounter[i];
res = i; // 错误 5 被赋值变量错误
}
}
return res; // 错误 6 返回错误变量
}2、早期短链接广泛应用于图片上传网站，通过缩短网址URL链接字数，达到减少代码字符串的目的。常见于网店图片分类的使用，因有字符个数限制，采用短链接可以达到外链图片的目的。自微博盛行以来，在微博字数有限的特色下，短链接也盛行于微博网站，以节省字数给博主发布更多文字的空间。
问题描述：设计一个短链生成和查询系统，需要提供以下两个功能：
1、提供长链转换短链的接口
2、点击短链能跳转到对应的长链
题目要求：
1、同一个长链生成同一个短链接，不要有多个短链指向同一个长链。
2、同一个短链只能指向某一个长链，短链生成后要固定不变，不能再指向其它长链。
3、给出系统架构，需要考虑高并发解决方案。
4、考虑存储和缓存方案
数据量预估：
1、预计长链接总量500亿
2、长链换短链请求量：10W qps
3、短链跳转请求量：100W qps
参考答案：
设计：
1、长链转短链
发号器，每过来一个长链换短链请求发一个号，发号器所发号码从 0 0 自增，所发号码为十进制，转化为 进制后作为短链（ 62 62 进制对应 26 26 小写字母加上 26 26 大写字母还有 10 10 数字）。
2、短链跳转长链
将短链所对应号码与长链一一映射存储于表中。
优化：
1、长链对应唯一短链
当长链转短链请求过来时率先在字典树（映射）中查找该长链是否已经分配短链，如果分配，则直接返回短链，若未分配则利用发号器继续分配。字典树在发号同时建立。
2、系统架构与高并发
采用 key−value k e y − v a l u e 分布式储存系统，创建更多发号器，减小发号请求高并发时的压力，比方说创建 10000 10000 个发号器，发号器编号从 0∼9999 0 ∼ 9999 ，对应每个发号器分别只发送以 0∼9999 0 ∼ 9999 为尾号的号码，每个发号器对应一片内存存储所发号码与长链对应的表，减小跳转访问高并发时的压力。
3、存储和缓存
利用分布式系统，采用 NoSql N o S q l 数据库存储彼此一一映射，采用 LRU L R U （最近最久未使用）算法管理内存与缓存。
4、其他
砸钱就好了！！！有钱真的可以为所欲为……
编程题
3、P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9] 内）
如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。
题解：
这个题最简单的方法是 O(n2) O ( n 2 ) 的暴力思维，但是很明显会超时，所以我们需要寻求更加高效的 O(nlogn) O ( n l o g n ) 的算法。
我们可以率先对点按照 x x 轴进行排序，然后从右往左进行遍历，记录历史最大 值，同时更新最大点集。
这里我们很容易想到，最右侧的点一定是最大点，那么当我们往左进行遍历时，凡是大于历史最大 y y 值得点均为最大点集中得点。
参考答案：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10; // 设置点数上限
// 结点
struct point
{
int x, y;
// 重载运算符以备 sort 时使用
bool operator < (const point &a) const
{
return x < a.x;
}
};
int n, cnt; // n 点数，cnt 最大点集点数
point pts[MAXN]; // 存放初始点集
point res[MAXN]; // 存放最大点集
void solve()
{
sort(pts, pts + n); // 按照 x 轴进行从小到大排序
res[0] = pts[n - 1];// 最右点绝对在最大点集中
int mx = res[0].y; // 记录从右往左扫描过程中最大 y 值
cnt = 1;
// 从右往左扫描时，如果当前点 y 值大于历史最大 y 值，该点在最大点集中
for (int i = n - 2; i >= 0; i--)
{
if (pts[i].y >= mx)
{
res[cnt++] = pts[i]; // 更新最大点集
mx = pts[i].y; // 更新历史最大 y 值
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
scanf("%d%d", &pts[i].x, &pts[i].y);
}
solve();
for (int i = cnt - 1; i >= 0; i--)
{
printf("%d %d\n", res[i].x, res[i].y);
}
return 0;
}4、给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：
区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列 [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:
从上述计算可见选定区间 [6] ，计算值为 36， 则程序输出为 36。
区间内的所有数字都在[0, 100]的范围内;
题解：
这个题很明显是一个区间问题，我们需要求每个元素作为最小值的最大区间，只有这样我们才能保证局部最优，所以这是一个单调栈问题。
然而，这个题给定了一个十分强的条件，即区间内所有数字都在 [0,100] [ 0 , 100 ] 之间，那么我们完全没有必要使用单调栈，单调栈更适合于区间内数字范围极大的情况。在数字范围很小时，单调栈不一定比暴力更优。
所以，这个题我们可以暴力枚举 [1,100] [ 1 , 100 ] ，然后从左往右以及从右往左分别遍历数组，获取到每个元素作为最小值的最大区间。
接着我们可以直接遍历每个元素，然后乘以该区间的和，这个和可以率先求取前缀和，这样，最后取最优结果即可。
参考答案：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10; // 设置数组最大长度
const int MAX_NUM = 100; // 设置元素最大值
int n;
int a[MAXN]; // 题目给定数组序列
int l[MAXN]; // l[i] 表示第 i 个元素作为最小值最大区间的左界
int r[MAXN]; // r[i] 表示第 i 个元素作为最小值最大区间的右界
int s[MAXN]; // s[i] 表示前 i 个元素的和
// 初始化函数，预处理前缀和
void init()
{
s[1] = a[1];
for (int i = 2; i <= n; i++)
{
s[i] = s[i - 1] + a[i];
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", a + i);
}
init();
// 从左往右遍历，获取 l
int L, R;
for (int i = 1; i <= MAX_NUM; ++i)
{
L = 1;
for (int j = 1; j <= n; ++j)
{
if (a[j] < i)
{
L = j + 1;
}
if (a[j] == i)
{
l[j] = L;
}
}
}
// 从右往左遍历，获取 r
for (int i = 1; i <= MAX_NUM; ++i)
{
R = n;
for (int j = n; j >= 1; --j)
{
if (a[j] < i)
{
R = j - 1;
}
if (a[j] == i)
{
r[j] = R;
}
}
}
// 枚举取最优解
int ans = 0;
for (int i = 1; i <= n; ++i)
{
ans = max(ans, (s[r[i]] - s[l[i] - 1]) * a[i]);
}
cout << ans << endl;
return 0;
}5、产品经理(PM)有很多好的idea，而这些idea需要程序员实现。现在有N个PM，在某个时间会想出一个 idea，每个 idea 有提出时间、所需时间和优先等级。对于一个PM来说，最想实现的idea首先考虑优先等级高的，相同的情况下优先所需时间最小的，还相同的情况下选择最早想出的，没有 PM 会在同一时刻提出两个 idea。
同时有M个程序员，每个程序员空闲的时候就会查看每个PM尚未执行并且最想完成的一个idea,然后从中挑选出所需时间最小的一个idea独立实现，如果所需时间相同则选择PM序号最小的。直到完成了idea才会重复上述操作。如果有多个同时处于空闲状态的程序员，那么他们会依次进行查看idea的操作。
求每个idea实现的时间。
输入第一行三个数N、M、P，分别表示有N个PM，M个程序员，P个idea。随后有P行，每行有4个数字，分别是PM序号、提出时间、优先等级和所需时间。输出P行，分别表示每个idea实现的时间点。
题解：
这个题难点在语法的考核， STL S T L 使用的是否足够熟练。要有足够的耐心和细心才行。
首先，我们来从题目中提炼几个要点：
1、每个 idea i d e a 都有提出时间，每个程序猿只能找当时时刻已经提出的 idea i d e a 。
2、对于每个 PM P M 会有若干个 idea i d e a ，也可能没有，每个 PM P M 最想完成的 idea i d e a 是优先级最高的，如果优先级一样，则取花费时间最小的，依然一样，则选取提出时间最早的。
3、程序猿在寻求自己想要完成的 idea i d e a 时，首先考虑每个 PM P M 最想完成的一个 idea i d e a ，然后从中选择所需时间最小的 idea i d e a ，如果时间一样选取 PM P M 序号最小的。
4、程序猿只有在空闲时刻可以选择完成 idea i d e a ，选择后的一段时间繁忙知道该 idea i d e a 完成，如果某一时刻有多个程序猿空闲，则依次按照上述第三条进行选取任务，除非没有任务可选。
根据以上分析几点，我们几乎上已经可以得出算法了，其实就是一个略微暴力的思路，数据范围十分小，我们可以枚举时间，然后根据时间给 PM P M 添加 idea i d e a ，接着取每个 PM P M 最想完成的 idea i d e a 进行排序，然后让程序猿选择，选择后的 idea i d e a 需要及时删除。多个程序猿空闲时，需要注意一点是不能在前一个操作删除 idea i d e a 后直接选取，因为删除那个 idea i d e a 后该 idea i d e a 的 PM P M 也许还有其他 idea i d e a 需要加入进行排序供下一个空闲程序猿选择。就这样，每次完成一个 idea i d e a 记录一下该 idea i d e a 的完成时间即可，离线操作。
说到这儿，思路已经十分清晰了，我们只需要对若干个 vector v e c t o r 或者数组进行多次排序操作选取最优即可，一个暴力贪心模拟的思路， 我使用的是 vector v e c t o r ，因为数组在删除操作时多少显得有些不方便。
参考答案：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3003;
struct idea
{
int PM_id; // PM 序号
int post_time; // 提出时间
int priority; // 优先权
int cost_time; // 所需时间
int order; // idea 序号
} ideas[MAXN];
int N, M, P; // N PM, M Program, P idea
int finish_time[MAXN]; // 完成每个 idea 时间
int program_time[MAXN]; // 程序猿空闲时刻
vector<idea> PM_idea[MAXN]; // 每个 PM 在某时刻所拥有的未完成 idea
// 按照提出时间从小到达排序
bool cmp_post(const idea &a, const idea &b)
{
return a.post_time < b.post_time;
}
// 按照第一关键词优先级从大到小，第二关键词花费时间从小到大，第三关键词提出时间从小到大排序
bool cmp_priority(const idea &a, const idea &b)
{
if (a.priority != b.priority)
{
return a.priority > b.priority;
}
else
{
if (a.cost_time != b.cost_time)
{
return a.cost_time < b.cost_time;
}
return a.post_time < b.post_time;
}
}
// 按照第一关键词花费时间从小到大，第二关键词 PM 序号从小到大排序
bool cmp_cost(const idea &a, const idea &b)
{
if (a.cost_time != b.cost_time)
{
return a.cost_time < b.cost_time;
}
return a.PM_id < b.PM_id;
}
int main()
{
scanf("%d%d%d", &N, &M, &P);
int a, b, c, d;
for (int i = 0; i < P; i++)
{
scanf("%d%d%d%d", &a, &b, &c, &d);
ideas[i] = {a - 1, b, c, d, i};
}
sort(ideas, ideas + P, cmp_post); // 按照 cmp_post 排序，为后续给 PM 添加 idea
int now_time = 1, cnt = 0, last = 0; // now_time 现在时刻，cnt 已经完成任务，last 下一次添加任务起点
while (cnt < P)
{
for (int i = last; i < P; i++)
{
if (ideas[i].post_time == now_time)
{
// 给 PM 添加 idea 并且按照 cmp_priority 排序，为后续生成每个 PM 最想完成 idea
PM_idea[ideas[i].PM_id].push_back(ideas[i]);
sort(PM_idea[ideas[i].PM_id].begin(), PM_idea[ideas[i].PM_id].end(), cmp_priority);
if (i == P - 1)
{
last = P;
}
}
else
{
last = i;
break;
}
}
// 选取每个 PM 最想完成的 idea
vector<idea> PM_priority;
for (int i = 0; i < N; i++)
{
if (!PM_idea[i].empty())
{
PM_priority.push_back(PM_idea[i][0]);
}
}
for (int i = 0; i < M; i++)
{
// 程序猿空闲并且此刻有 idea 可供选择
if (program_time[i] <= now_time && !PM_priority.empty())
{
// 按照 cmp_cost 排序，为后续给程序猿选取 idea
sort(PM_priority.begin(), PM_priority.end(), cmp_cost);
// 选取 idea 并且更新程序猿空闲时间和存储该 idea 完成时间
program_time[i] = now_time + PM_priority[0].cost_time;
finish_time[PM_priority[0].order] = program_time[i];
// 从 PM 此刻 idea 中删除已经选取的 idea
PM_idea[PM_priority[0].PM_id].erase(PM_idea[PM_priority[0].PM_id].begin());
// 如果该 PM 依然有 idea，则将下一个 idea 添加到 PM 最想完成 idea 集合中
if (!PM_idea[PM_priority[0].PM_id].empty())
{
PM_priority.push_back(PM_idea[PM_priority[0].PM_id][0]);
}
// 从 PM 最想完成 idea 集合中删除已经选取过的 idea
PM_priority.erase(PM_priority.begin());
cnt++; // 完成 idea 数自增
}
}
now_time++; // 现在时间自增
}
for (int i = 0; i < P; i++)
{
printf("%d\n", finish_time[i]);
}
return 0;
}
查看6道真题和解析
