题目
一、编程题
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]的范围内;
输入描述:
第一行输入数组序列长度n，第二行输入数组序列。
对于 50%的数据, 1 <= n <= 10000;
对于 100%的数据, 1 <= n <= 500000;
输出描述:
输出数组经过计算后的最大值。
输入例子1:
3
6 2 1
输出例子1:
36
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实现的时间点。
输入描述:
输入第一行三个数N、M、P，分别表示有N个PM，M个程序员，P个idea。随后有P行，每行有4个数字，分别是PM序号、提出时间、优先等级和所需时间。全部数据范围 [1, 3000]。
输出描述:
输出P行，分别表示每个idea实现的时间点。
输入例子1:
2 2 5
1 1 1 2
1 2 1 1
1 3 2 2
2 1 1 2
2 3 5 5
输出例子1:
3
4
5
3
9
二、问答题
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、早期短链接广泛应用于图片上传网站，通过缩短网址URL链接字数，达到减少代码字符串的目的。常见于网店图片分类的使用，因有字符个数限制，采用短链接可以达到外链图片的目的。自微博盛行以来，在微博字数有限的特色下，短链接也盛行于微博网站，以节省字数给博主发布更多文字的空间。
问题描述：设计一个短链生成和查询系统，需要提供以下两个功能：
（1）、提供长链转换短链的接口
（2）、点击短链能跳转到对应的长链
题目要求：
（1）、同一个长链生成同一个短链接，不要有多个短链指向同一个长链。
（2）、同一个短链只能指向某一个长链，短链生成后要固定不变，不能再指向其它长链。
（3）、给出系统架构，需要考虑高并发解决方案。
（4）、考虑存储和缓存方案
数据量预估：
（1）、预计长链接总量500亿
（2）、长链换短链请求量：10W qps
（3）、短链跳转请求量：100W qps
参考答案
一、编程题
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;
}
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、
（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、
定义
短链服务：将一个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获取短链。
个人资料
推荐圈子
猜你感兴趣的圈子：
标签： 短链、ideatask、raisetime、pm、timecost、面试题
