今日头条2018校招测试开发方向（第一批） 企

题目

一、编程题

1、P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内）

如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。

2、给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：

区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列  [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;

从上述计算可见选定区间 [6] ，计算值为 36， 则程序输出为 36。

区间内的所有数字都在[0, 100]的范围内;

二、问答题

1、给定一棵树的根节点, 在已知该树最大深度的情况下, 求节点数最多的那一层并返回具体的层数。

如果最后答案有多层, 输出最浅的那一层，树的深度不会超过100000。实现代码如下，请指出代码中的多处错误：

struct Node {
   vector<Node*> sons;
};
void dfsFind(Node *node, int dep, int counter[]) {
   counter[dep]++;
   for(int i = 0; i < node.sons.size(); i++) {
       dfsFind(node.sons[i], dep, counter);
   }
}
int find(Node *root, int maxDep) {
   int depCounter[100000];
   dfsFind(root, 0, depCounter);
   int max, maxDep;
   for (int i = 1; i <= maxDep; i++) {
       if (depCounter[i] > max) {
           max = depCounter[i];
           maxDep = i;
       }
   }
   return maxDep;
}

2、某一个RPC服务A，对外提供接口MatchAds(AdTargetRequest req),发送请求，返回可展示的广告。如何测试这个服务接口的性能。

3、如果一个头条的客户端程序，冷启动时间为4秒，怎么判断开启速度是合理的还是不合理的？如果不合理，该如何找到问题，提供思路。

参考答案

一、编程题

1、

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pr make_pair
#define fi first
#define se second
const int MAX_N = 5e5 + 5;
typedef pair<int, int> pii;
vector<pii> p;
pii ans[MAX_N];
int main() {
   int n, x, y, num, limit;
   scanf("%d", &n);
   for (int i = 1; i <= n; i++) {
       scanf("%d%d", &x, &y);
       p.pb(pr(x, y));
   }
   sort(p.begin(), p.end());
   num = 0, limit = -1;
   for (int i = n - 1; i >= 0; i--) {
       if (p[i].se > limit) {
           ans[num] = p[i];
           num++;
           limit = p[i].se;
       }
   }
   for (int i = num - 1; i >= 0; i--) {
       printf("%d %d\n", ans[i].fi, ans[i].se);
   }
   return 0;
}

2、

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 5;
int a[MAX_N];
int main() {
   long long ans, sum;
   int n, minnum;
   scanf("%d", &n);
   for (int i = 0; i < n; i++) {
       scanf("%d", &a[i]);
   }
   a[n] = 0;
   ans = 0;
   for (int j = 100; j >= 1; j--) {
       sum = 0, minnum = 101;
       for (int i = 0; i <= n; i++) {
           if (a[i] < j) {
               ans = max(ans, sum * minnum);
               minnum = 101, sum = 0;
           }
           else {
               sum += a[i];
               minnum = min(minnum, a[i]);
           }
           //printf("i = %d, j = %d, ans = %lld\n", i, j, ans);
       }

   }
   printf("%lld\n", ans);
   return 0;
}

二、问答题

1、

（1）.dfsFind没有递归出口，应添加参数maxDep并加一句话 if (dep == maxDep) return;

（2）.node是指针，调用sons应使用node->sons  

（3）.dfsFind里的递归语句参数不对，应为 dfsFind(node->sons[i], dep + 1, counter)

（4）.find函数中的max和depCounter未清0

（5）.find里的循环应为 for (int i = 0; i < maxDep; i++)

2、

（1）.测试发送请求之后是否返回的是可展示的广告内容；

（2）.测试发送错误请求之后接口返回的数据内容；

（3）.测试同时发送多个请求接口的反应速度和返回的数据内容

3、

（1）.考虑客户端所在的系统配置和性能是否满足要求，如果系统配置和性能正常，则转向第二步；

（2）.判断网络环境是否通畅，是否满足要求，如果网络环境满足要求，则转向的第三步；

（3）.对比系统打开同类软件的冷启动时间，如果打开同类软件的冷启动时间平均低于4s，则开启速度不合理。

（4）.对比系统打开不同类软件的冷启动时间平均低于4s，则开启速度不合理。