今日头条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]的范围内;

3、产品经理(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实现的时间点。

二、问答题

如果最后答案有多层, 输出最浅的那一层，树的深度不会超过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、早期短链接广泛应用于图片上传网站，通过缩短网址URL链接字数，达到减少代码字符串的目的。常见于网店图片分类的使用，因有字符个数限制，采用短链接可以达到外链图片的目的。自微博盛行以来，在微博字数有限的特色下，短链接也盛行于微博网站，以节省字数给博主发布更多文字的空间。

问题描述：设计一个短链生成和查询系统，需要提供以下两个功能：

   1、提供长链转换短链的接口

   2、点击短链能跳转到对应的长链

题目要求：

   1、同一个长链生成同一个短链接，不要有多个短链指向同一个长链。

   2、同一个短链只能指向某一个长链，短链生成后要固定不变，不能再指向其它长链。

   3、给出系统架构，需要考虑高并发解决方案。

   4、考虑存储和缓存方案

数据量预估：

   1、预计长链接总量500亿

   2、长链换短链请求量：10W qps

   3、短链跳转请求量：100W qps

参考答案

一、编程题

#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;
}

#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;
}

3、

import java.util.*;   
public class Main{  
   private static Scanner sc = new Scanner(System.in);  
    static class IdeaTask {  
       int pmSeq;  
       int raiseTime;  
       int prio;  
       int timeCost;  
       int endTime;   
       public IdeaTask(int pmSeq, int raiseTime, int prio, int timeCost) {  
           this.pmSeq = pmSeq;  
           this.raiseTime = raiseTime;  
           this.prio = prio;  
           this.timeCost = timeCost;  
       }  
   }  
   static class PM {  
       PriorityQueue<IdeaTask> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x.raiseTime));  
       //给定程序员开始工作的时间，找到这个PM最想完成的任务  
       IdeaTask mostDesiredTask(int startTime) {  
           PriorityQueue<IdeaTask> pq2 = new PriorityQueue<>((x, y) -> {  
               if (x.prio != y.prio) return y.prio - x.prio;  
               else {  
                   if (x.timeCost != y.timeCost) return x.timeCost - y.timeCost;  
                   else return x.raiseTime - y.raiseTime;  
               }  
           });  
           while (pq.peek() != null && pq.peek().raiseTime <= startTime) {  
               pq2.offer(pq.poll());  
           }  
           IdeaTask mostDesiredTask = (pq2.isEmpty()) ? pq.poll() : pq2.poll();  
           while (!pq2.isEmpty()) {  
               pq.offer(pq2.poll());  
           }  
           return mostDesiredTask;  
       }  
   }   
   static class Programmer {  
       int nextWorkTime;//下次可以工作的时间  
       public Programmer(int nextWorkTime) {  
           this.nextWorkTime = nextWorkTime;  
       }  
   }   
   //从多个PM 最想要完成的Idea中，选其中的一个PM想要完成的idea  
   private static IdeaTask selectTask(PM[] pms, int workTime) {  
       PriorityQueue<IdeaTask> pq = new PriorityQueue<>((x, y) -> {  
           if (x.raiseTime == y.raiseTime || (x.raiseTime <= workTime && y.raiseTime <= workTime)) {  
               if (x.timeCost != y.timeCost) return x.timeCost - y.timeCost;  
               else return x.pmSeq - y.pmSeq;  
           }  
           if (x.raiseTime > workTime && y.raiseTime > workTime) return x.raiseTime - y.raiseTime;  
           if (x.raiseTime > workTime) return 1;  
           if (y.raiseTime > workTime) return -1;  
           return 0;  
       });  
       for (int i = 1; i < pms.length; i++) {  
           PM pm = pms[i];  
           IdeaTask desiredTask = pm.mostDesiredTask(workTime);  
           if (desiredTask != null)  
               pq.offer(desiredTask);  
       }  
       IdeaTask task = pq.poll();  
       while (!pq.isEmpty()) {  
           IdeaTask tmp = pq.poll();  
           pms[tmp.pmSeq].pq.offer(tmp);  
       }  
       return task;  
   }   
   private static List<IdeaTask> getTasks(int taskNum) {  
       List<IdeaTask> tasks = new LinkedList<>();  
       while (taskNum-- > 0) {  
           tasks.add(new IdeaTask(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt()));  
       }  
       return tasks;  
   }   
   private static PM[] initPM(int n, List<IdeaTask> tasks) {  
       PM[] pms = new PM[n + 1];  
       for (int i = 1; i <= n; i++) pms[i] = new PM();  
       for (IdeaTask task : tasks) {  
           pms[task.pmSeq].pq.offer(task);  
       }  
       return pms;  
   }   
   public static void main(String[] args) {  
       int n = sc.nextInt(), m = sc.nextInt(), p = sc.nextInt();   
       List<IdeaTask> tasks = getTasks(p);  
       PM[] pms = initPM(n, tasks);  
       PriorityQueue<Programmer> losersPq = new PriorityQueue<>(Comparator.comparingInt(x -> x.nextWorkTime));  
       for (int i = 0; i < m; i++) losersPq.offer(new Programmer(0));  
       while (true) {  
           Programmer loser = losersPq.poll();  
           IdeaTask task = selectTask(pms, loser.nextWorkTime);  
           if (task == null) break;  
           task.endTime = Integer.max(task.raiseTime, loser.nextWorkTime) + task.timeCost;  
           loser.nextWorkTime = task.endTime;  
           losersPq.offer(loser);  
       }  
       for (IdeaTask task : tasks) {  
           System.out.println(task.endTime);  
       }  
   }  
}  

二、问答题

（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++)

定义

短链服务：将一个long link URL转化为更短的link， 通过short link 可以重定向到原始的link URL。

如何设计

生成算法需要保证long url生成的short url是唯一的,如何保证生成唯一？例如，可以使用mysql来存储短链对应的种子生成器,假设使用mysql来存储短链种子的生成器id,生成算法如下：

从mysql中拿到唯一id，可以取一批id放到内存中，从内存中取id，等到内存中的id用完之后，再从mysql中取；

对取到的id进行编码，编码成short link，需要设计能够编码和解码的算法，使id生成的编码尽可能的短，参考：http://www.geeksforgeeks.org/how-to-design-a-tiny-url-or-url-shortener/

如何保证可靠性和生成性能

使用redis、hbase

Redis：缓存最近生成的短链以及最近访问的短链（比如最近一个月）

Hbase：在redis可用时，充当异步的持久化短链的职责；redis不可用时，从hbase查询

Mysql：提供唯一种子生成，并对生成的短链进行备份

生成流程

从mysql中获取短链种子id，生成短链；

将[短链，长链]和[长链，短链]的映射关系放入到redis中；

异步将短链存入hbase；

查询时，从redis获取短链，不存在从hbase获取短链。