字节跳动-算法

字节跳动2018校招算法方向（第一批）

字节的只有18年以前的题了 看笔试来说还是很亲民的~ 而且分了大数据小数据给大家 可以先骗点分

不过系统设计会考到的 这个是很值得复习的一部分

01 - [编程题]编程题1

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

输入描述:

第一行输入点集的个数 N， 接下来 N 行，每行两个数字代表点的 X 轴和 Y 轴。 对于 50%的数据, 1 <= N <= 10000; 对于 100%的数据, 1 <= N <= 500000;

输出描述:

输出“最大的” 点集合， 按照 X 轴从小到大的方式输出，每行两个数字分别代表点的 X 轴和 Y轴。

输入例子1:

5
1 2
5 3
4 6
7 5
9 0

输出例子1:

4 6
7 5
9 0

---

题里实际上给了暗示 输出要按x从小到大输出

首先就是按x排列 这样当遍历到当前节点时候，其右边的所有点都满足x更大，那么我们可以通过记录右边所有点最大的y是否比当前点的大 来判断 这里记录右边所有点最大的y就预处理 从右向左遍历一次就好了

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
using PII = pair<int, int>;
const int N = 500010;
int n;
PII p[N];
int maxy[N];
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        p[i] = {x, y};
    }
    // 按照x排序
    sort(p, p + n);
    maxy[n] = -1;
    for(int i = n - 1; i >= 0; i--)
        maxy[i] = max(maxy[i + 1], p[i].second);
    for(int i = 0; i < n; i++)
    {
        if(p[i].second > maxy[i + 1])
            printf("%d %d\n", p[i].first, p[i].second);
    }
    return 0;
}

02 - [编程题]编程题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

---

这题开始一看到区间问题就想到线段树了 后来发现不对

这里有一个隐藏的贪心性质，我们可以通过枚举每个点作为最小值的情况 这样就包含了所有可能性 而每个点作为最小值时最大的区间和 肯定是向左向右扩展，保证最长的区间，这样我们需要知道左边和右边第一个比他小的数的位置 这样最长的区间就可以确定 实际上就是leetcode接雨水/最大矩形面积的变形

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>

using namespace std;

const int N = 500010;
int n;
int nums[N];
int r[N];
int s[N];

int get(int l, int r)
{
    return s[r] - s[l - 1];
}
int main()
{
    scanf("%d", &n);
    stack<int> stk;
    for(int i = 1; i <= n; i++)
    {
       scanf("%d", nums + i);
       s[i] = s[i - 1] + nums[i];
    }
    for(int i = n; i > 0; i--)
    {
        while(stk.size() && nums[stk.top()] >= nums[i])
            stk.pop();
        // 此时栈顶是右边比他小的第一个元素
        if(stk.size()) r[i] = stk.top(); // 如果stk不为空
        else r[i] = n + 1;
        stk.push(i);
    }
    stk = stack<int>();
    int res = 0, l = 0;
    for(int i = 1; i <= n; i++)
    {
        while(stk.size() && nums[stk.top()] >= nums[i])
            stk.pop();
        if(stk.size())
            l = stk.top();
        else l = 0;
        res = max(res, nums[i] * get(l + 1, r[i] - 1));
        stk.push(i);
    }
    printf("%d\n", res);
    return 0;
}

03 - [编程题]编程题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

说真的 考模拟题的我还是第一次见... 这和算法没啥太大关系了

不过考试的时候能够搞明白这些乱七八糟的逻辑关系还是挺难的把（是我搞不出来的了）

#include <bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;

typedef struct node
{
    int id;
    int time;
    int rank;
    int cost;
    int global_id;
    int finish_time = 0;

    bool operator < (const struct node&b)const
    {
        if (rank != b.rank)
            return rank < b.rank;
        if (cost != b.cost)
            return cost > b.cost;
        if (time != b.time)
            return time > b.time;
        return false;
    }
} idea;

bool cmp2(idea a, idea b)
{
    return a.global_id < b.global_id;
}
bool cmp3(idea a, idea b)
{
    if(a.time!=b.time)
        return a.time < b.time;
    return false;
}
int main()
{
    int n, m, p;
    cin >> n >> m >> p;
    vector<idea> v;
    idea in;

    for (int i = 0; i < p; i++)
    {
        cin >> in.id>>in.time>>in.rank>>in.cost;
        in.global_id = i;
        v.push_back(in);
    }
    sort(v.begin(), v.end(), cmp3); // 先按提出时间排序
    vector<priority_queue<idea>> PM(n); // 每位pm用一个优先队列去枚举优先级最高的idea
    priority_queue<int, vector<int>, greater<int>> pq; // 程序员的空闲时间
    vector<idea> finished_idea; // 完成的idea
    for (int i = 0; i < m; i++)
        pq.push(1);
    int time = 1; // 当前时间
    int i = 0;
    while (finished_idea.size()!=p)
    {
        // 找到已经提出的idea 加入优先队列
        for (; i < v.size()&&v[i].time<=time; i++)
        {
            PM[v[i].id - 1].push(v[i]);
        }
        // 如果有程序员都空闲
        while (pq.top()<=time)
        {
            // 找到优先级最高的 这里暗示了一个优先级 找到cost最小的来完成
            int first = 0, minn = 9999;
            bool haveidea = false;
            for (int j = 0; j < n; j++)
            {
                if (PM[j].empty())
                    continue;
                if (minn > PM[j].top().cost)
                {
                    minn = PM[j].top().cost;
                    first = j;
                    haveidea = true;
                }
            }
            if (haveidea)
            {
                int coder = pq.top(); pq.pop();
                idea cur = PM[first].top(); PM[first].pop();
                cur.finish_time = time + cur.cost;
                coder = cur.finish_time;
                pq.push(coder);
                finished_idea.push_back(cur);
            }
            else
                break;
        }
        if (time >= pq.top())
            time++;
        else
            time = pq.top();
    }
    sort(finished_idea.begin(), finished_idea.end(), cmp2);
    for (int j = 0; j < p; j++)
    {
        cout << finished_idea[j].finish_time << endl;
    }
    return 0;
}

04 - [问答题]

给定一棵树的根节点, 在已知该树最大深度的情况下, 求节点数最多的那一层并返回具体的层数。 如果最后答案有多层, 输出最浅的那一层，树的深度不会超过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;
}

原代码 求一层中节点数最多的一层 其实应该用bfs来实现的 但这题用dfs也不是不行 找找他代码里面的问题吧

dfsFind函数

• node是指针，所以得是node->sons[i]

• 往下搜索 要dep + 1

• DFS 要有出口 如果是node为空，要直接返回

find函数

• 参数和内部定义的变量名字不能重复

• max 和 maxDep 都没赋初值

• root为空没有考虑

struct Node {
    vector<Node*> sons;
};
 
void dfsFind(Node *node, int dep, int counter[]) {
    if(node == nullptr) return;
    counter[dep]++;
 
    for(int i = 0; i < node.sons.size(); i++) {
        dfsFind(node->sons[i], dep + 1, counter); // dep + 1;
    }
}
 
int find(Node *root, int maxdepth) { //改革民治
    if(root == nullptr) return 0;
    int depCounter[100000]; 
    dfsFind(root, 0, depCounter);
 
    int max = 0, maxDep = 0; // 没赋初值
    for (int i = 1; i <= maxdepth; i++) {
        if (depCounter[i] > max) {
            max = depCounter[i];
            maxDep = i;
        }
    }
    return maxDep;
}

05 - [问答题]

题目描述

早期短链接广泛应用于图片上传网站，通过缩短网址URL链接字数，达到减少代码字符串的目的。常见于网店图片分类的使用，因有字符个数限制，采用短链接可以达到外链图片的目的。自微博盛行以来，在微博字数有限的特色下，短链接也盛行于微博网站，以节省字数给博主发布更多文字的空间。 **问题描述：**设计一个短链生成和查询系统，需要提供以下两个功能： 1、提供长链转换短链的接口 2、点击短链能跳转到对应的长链 题目要求： 1、同一个长链生成同一个短链接，不要有多个短链指向同一个长链。 2、同一个短链只能指向某一个长链，短链生成后要固定不变，不能再指向其它长链。 3、给出系统架构，需要考虑高并发解决方案。 4、考虑存储和缓存方案 数据量预估： 1、预计长链接总量500亿 2、长链换短链请求量：10W qps 3、短链跳转请求量：100W qps

系统设计等学到了再写吧~