今日头条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]; // 存储树的每层结点数
dfsFind(root, 0, depCounter); // 调用深度优先遍历函数，
// 传入根和初始深度以及存储数每层结点数的数组
int max, maxDep; // 错误 3 未初始化、命名冲突
for (int i = 1; i <= maxDep; i++) {
if (depCounter[i] > max) {
max = depCounter[i];
maxDep = i; // 错误 4 被赋值变量错误
}
}
return maxDep; // 错误 5 返回错误变量
}
######参考答案：
/*
* 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[100000]; // 存储树的每层结点数
dfsFind(root, 0, depCounter); // 调用深度优先遍历函数，
// 传入根和初始深度以及存储数每层结点数的数组
int max = 1, res = 0; // 错误 3 未初始化、命名冲突
for (int i = 1; i <= maxDep; i++) {
if (depCounter[i] > max) {
max = depCounter[i];
res = i; // 错误 4 被赋值变量错误
}
}
return res; // 错误 5 返回错误变量
}
#####2、某一个RPC服务A，对外提供接口MatchAds(AdTargetRequest req)，发送请求，返回可展示的广告。如何测试这个服务接口的性能。
######题解：
R P C RPC RPC 是远程过程调用，通俗讲就是用来向远程计算机请求服务的一种协议。至于这个接口，我也不知道是啥玩意儿，但是题目说的很清楚，发送请求返回可展示广告的接口，不是重点。
接口测试属于功能测试，我们需要根据接口文档来编写测试用例，测试用例可以从三方面着手，第一，正确请求返回数据情况；第二，错误请求返回数据情况；第三，多次请求返回数据情况以及反应速度。
######参考答案：
1、测试发送请求之后是否返回的是可展示的广告内容；
2、测试发送错误请求之后接口返回的数据内容；
3、测试同时发送多个请求接口的反应速度和返回的数据内容
#####3、如果一个头条的客户端程序，冷启动时间为4秒，怎么判断开启速度是合理的还是不合理的？如果不合理，该如何找到问题，提供思路。
######题解：
首先我们需要知道什么是冷启动，百度百科可以找到电脑冷启动是切断电脑电源，重新启动，一旦冷启动，内存的数据全部丢失，重新检测硬件。
举一反三，客户端的冷启动指的是内存中没有任何该客户端数据的情况下启动客户端。
头条客户端冷启动耗时 4 s 4s 4s，是否合理需要先考虑客户端所在设备的系统配置和性能，其次考虑网络环境，还可以与其他软件冷启动进行对比，分别与同类软件和不同类软件进行对比。
根据上述几种判断手段可以分别获悉其存在的问题。
######参考答案：
1、考虑客户端所在的系统配置和性能是否满足要求，如果系统配置和性能正常，则转向第二步，否则开启速度不合理，说明客户端所需系统配置和性能偏高，不适合在本系统配置下运行；
2、判断网络环境是否通畅，是否满足要求，如果网络环境满足要求，则转向的第三步，否则开启速度不合理，说明可能存在网络问题导致客户端冷启动过慢；
3、对比系统打开同类软件的冷启动时间，如果打开同类软件的冷启动时间平均高于 4 s 4s 4s，则转向第四步，否则开启速度不合理，属于软件自身问题。
4、对比系统打开不同类软件的冷启动时间平均高于 4 s 4s 4s，则开启速度合理，否则开启速度不合理，属于软件自身问题。
##编程题
#####4、P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9] 内）
######如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。
######题解：
这个题最简单的方法是 O ( n 2 ) O(n^2) O(n2) 的暴力思维，但是很明显会超时，所以我们需要寻求更加高效的 O ( n l o g n ) O(nlogn) O(nlogn) 的算法。
我们可以率先对点按照 x x x 轴进行排序，然后从右往左进行遍历，记录历史最大 y y y 值，同时更新最大点集。
这里我们很容易想到，最右侧的点一定是最大点，那么当我们往左进行遍历时，凡是大于历史最大 y 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;
}
#####5、给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：
######区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列 [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:
[ 6 ] = 6 ∗ 6 = 36 ; [ 2 ] = 2 ∗ 2 = 4 ; [ 1 ] = 1 ∗ 1 = 1 ; [ 6 , 2 ] = 2 ∗ 8 = 16 ; [ 2 , 1 ] = 1 ∗ 3 = 3 ; [ 6 , 2 , 1 ] = 1 ∗ 9 = 9 ; \begin{aligned} & [6] = 6 * 6 = 36;\\ & [2] = 2 * 2 = 4;\\ & [1] = 1 * 1 = 1;\\ & [6,2] = 2 * 8 = 16;\\ & [2,1] = 1 * 3 = 3;\\ & [6, 2, 1] = 1 * 9 = 9; \end{aligned} [6]=6∗6=36;[2]=2∗2=4;[1]=1∗1=1;[6,2]=2∗8=16;[2,1]=1∗3=3;[6,2,1]=1∗9=9;
######从上述计算可见选定区间 [6] ，计算值为 36， 则程序输出为 36。
######区间内的所有数字都在[0, 100]的范围内;
######题解：
这个题很明显是一个区间问题，我们需要求每个元素作为最小值的最大区间，只有这样我们才能保证局部最优，所以这是一个单调栈问题。
然而，这个题给定了一个十分强的条件，即区间内所有数字都在 [ 0 , 100 ] [0, 100] [0,100] 之间，那么我们完全没有必要使用单调栈，单调栈更适合于区间内数字范围极大的情况。在数字范围很小时，单调栈不一定比暴力更优。
所以，这个题我们可以暴力枚举 [ 1 , 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;
}
爱奇艺公司氛围 42人发布