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

题目

一、编程题

1、为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为k。因为一些特殊的原因，不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。

输入描述:

输入： 第1行为n代表用户的个数 第2行为n个整数，第i个代表用户标号为i的用户对某类文章的喜好度 第3行为一个正整数q代表查询的组数  第4行到第（3+q）行，每行包含3个整数l,r,k代表一组查询，即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数。 数据范围n <= 300000,q<=300000 k是整型

输出描述:

输出：一共q行，每行一个整数代表喜好值为k的用户的个数

输入例子1:

5

1 2 3 3 5

3

1 2 1

2 4 5

3 5 3

输出例子1:

1

0

2

例子说明1:

样例解释:

有5个用户，喜好值为分别为1、2、3、3、5，

第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1

第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0

第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2

2、作为一个手串艺人，有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色，要么涂了若干种颜色。为了使手串的色彩看起来不那么单调，金主要求，手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次（注意这里手串是一个环形）。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上，每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。

输入描述:

第一行输入n，m，c三个数，用空格隔开。(1 <= n <= 10000, 1 <= m <= 1000, 1 <= c <= 50) 接下来n行每行的第一个数num_i(0 <= num_i <= c)表示第i颗珠子有多少种颜色。接下来依次读入num_i个数字，每个数字x表示第i颗柱子上包含第x种颜色(1 <= x <= c)

输出描述:

一个非负整数，表示该手链上有多少种颜色不符需求。

输入例子1:

5 2 3

3 1 2 3

0

2 2 3

1 2

1 3

输出例子1:

2

例子说明1:

第一种颜色出现在第1颗串珠，与规则无冲突。

第二种颜色分别出现在第 1，3，4颗串珠，第3颗与第4颗串珠相邻，所以不合要求。

第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。

总计有2种颜色的分布是有问题的。

这里第2颗串珠是透明的。

二、问答题

1、以下函数使用二分查找搜索一个增序的数组，当有多个元素值与目标元素相等时，返回最后一个元素的下标，目标元素不存在时返回-1。请指出程序代码中错误或不符最佳实践的地方（问题不止一处，请尽量找出所有你认为有问题的地方）

int BinarySearchMax(const std::vector<int>& data, int target)
{
  int left = 0;
  int right = data.size();
  while (left < right) {
      int mid = (left + right) / 2;
      if (data[mid] <= target)
          left = mid + 1;
      else
          right = mid - 1;
  }
  if (data[right] == target)
      return right;
  return -1;
}

2、如何测试一个消息系统，这个消息系统包含了：今日头条的评论消息、点赞消息、关注提醒、头条号提醒、问答邀请和系统消息（比如头条活动）
3、某城市部分移动用户反馈无法刷新今日头条的信息流， 并且总是提示网络错误。 可能是什么原因导致的？

参考答案

一、编程题

1、

#include <bits/stdc++.h>
using namespace std;
bool sort_cmp(const pair<int, int> &A, const pair<int, int> &B)
{
   return A.first == B.first ? A.second < B.second :
       A.first < B.first;
}
struct find_first_cmp {
   bool operator()(const pair<int, int> &P, int k) const
   {
       return P.first < k;
   }
   bool operator()(int k, const pair<int, int> &P) const
   {
       return k < P.first;
   }
};
struct find_second_cmp {
   bool operator()(const pair<int, int> &P, int k) const
   {
       return P.second < k;
   }
   bool operator()(int k, const pair<int, int> &P) const
   {
       return k < P.second;
   }
};
int main()
{
   int n, q;
   while (EOF != scanf("%d", &n)) {
       vector<pair<int, int> > arr;
       for (int i = 0, x; i < n; cin >> x, arr.emplace_back(x, ++i)) {}
       sort(arr.begin(), arr.end(), sort_cmp);
       for (scanf("%d", &q); q--;) {
           int L, R, k;
           scanf("%d%d%d", &L, &R, &k);
           pair<vector<pair<int, int> >::iterator, vector<pair<int, int> >::iterator> sd =
               equal_range(arr.begin(), arr.end(), k, find_first_cmp{});
           printf("%d\n", upper_bound(sd.first, sd.second, R, find_second_cmp{}) -
               lower_bound(sd.first, sd.second, L, find_second_cmp{}));
       }
   }
   return 0;
}

2、

#include <bits/stdc++.h>
using namespace std;
int main()
{
   int n, m, c;
   while (EOF != scanf("%d%d%d", &n, &m, &c)) {
       vector<vector<int> > arr(n + m);
       for (int i = 0, num, x; i < n; i++)
           for (scanf("%d", &num); num--;
               arr[i].push_back((scanf("%d", &x), x))) {}
       for (int i = 0; i < m; i++)
           arr[n + i] = arr[i];
       vector<bool> used(c, false);
       map<int, int> color;
       for (int i = 0; i < c; color[i++] = 0) {}
       for (int i = 0; i < n + m; i++) {
           for (int j = 0; !(i < m) && j < (int)arr[i - m].size(); j++)
               color[arr[i - m][j] - 1]--;
           for (int j = 0; j < (int)arr[i].size(); j++)
               color[arr[i][j] - 1]++;
           for (map<int, int>::iterator it = color.begin(); it != color.end(); ++it)
               used[it->first] = it->second > 1 ? true : used[it->first];
       }
       int ans = 0;
       for (int i = 0; i < c; ans += used[i++]) {}
       printf("%d\n", ans);
   }
   return 0;
}

3、

#include <bits/stdc++.h>
using namespace std;
int main()
{
   string s;
   int m;
   while (cin >> s >> m) {
       int ans = 1;
       for (char c = 'a'; c <= 'z'; c++) {
           vector<int> pos;
           for (int i = 0; i < (int)s.size(); i++)
               if (c == s[i])
                   pos.push_back(i);
           if (pos.size() < 2)
               continue;
           int ret = 1;
           vector<vector<int> > dp(pos.size(), vector<int>(pos.size(), 0));
           for (int len = 2; len <= (int)pos.size(); ++len) {
               for (int i = 0; i + len - 1 < (int)pos.size(); i++) {
                   dp[i][i + len - 1] = dp[i + 1][i + len - 2] + pos[i + len - 1] - pos[i] - len + 1;
                   if (dp[i][i + len - 1] <= m)
                       ret = len;
               }
           }
           ans = max(ans, ret);
       }
       cout << ans << endl;
   }
   return 0;
}

二、问答题

1、

先做功能测试，看相应的按钮能佛实现功能。

2、

无法连接可能是因为端口被屏蔽，如果出现端口被屏蔽，可以联系网络供应商帮忙处理（户所用网络常见的被封端口是81和3001，进去频道的话是8443-8460，1443-1460，443-460之间的随机TCP和UDP）