专栏首页ACM小冰成长之路今日头条2018校招大数据/算法方向(第一批)详解

今日头条2018校招大数据/算法方向(第一批)详解

版权声明:听说这里让写版权声明~~~ https://blog.csdn.net/f_zyj/article/details/79162401

问答题

1、给定一棵树的根节点, 在已知该树最大深度的情况下, 求节点数最多的那一层并返回具体的层数。
如果最后答案有多层, 输出最浅的那一层,树的深度不会超过100000。实现代码如下,请指出代码中的多处错误:
/*
 *  Node 结构体,包含一个元素为 Node * 的向量
 *  用来存储树结构的父子关系
 */
struct Node {
    vector<Node*> sons;
};

/*
 *  深度优先遍历,用来遍历树并且对每层结点数计数
 *  node 为父节点的指针,dep 为深度,counter 为存储每层结点数的数组
 */
void dfsFind(Node *node, int dep, int counter[]) {
    counter[dep]++;                             //  计数操作
    for(int i = 0; i < node.sons.size(); i++) { //  错误 1 指针操作错误
        dfsFind(node.sons[i], dep, counter);    //  错误 2 指针操作错误,深度控制不当
    }
}

/*
 *  find 函数,root 是树的根,maxDep 是树的最大深度
 */
int find(Node *root, int maxDep) {
    int depCounter[100000];               //  错误 3 存储树的每层结点数,可能存在越界问题
    dfsFind(root, 0, depCounter);         //  调用深度优先遍历函数,
                                          //  传入根和初始深度以及存储数每层结点数的数组
    int max, maxDep;                      //  错误 4 未初始化、命名冲突
    for (int i = 1; i <= maxDep; i++) {
        if (depCounter[i] > max) {
            max = depCounter[i];
            maxDep = i;                   //  错误 5 被赋值变量错误
        }
    }
    return maxDep;                        //  错误 6 返回错误变量
}
参考答案:
/*
 *  Node 结构体,包含一个元素为 Node * 的向量
 *  用来存储树结构的父子关系
 */
struct Node {
    vector<Node*> sons;
};

/*
 *  深度优先遍历,用来遍历树并且对每层结点数计数
 *  node 为父节点的指针,dep 为深度,counter 为存储每层结点数的数组
 */
void dfsFind(Node *node, int dep, int counter[]) {
    counter[dep]++;                                 //  计数操作
    for(int i = 0; i < node->sons.size(); i++) {    //  错误 1 指针操作错误
        dfsFind(node->sons[i], dep + 1, counter);   //  错误 2 指针操作错误,深度控制不当
    }
}

/*
 *  find 函数,root 是树的根,maxDep 是树的最大深度
 */
int find(Node *root, int maxDep) {
    int depCounter[100003];               //  错误 3 存储树的每层结点数.可能存在越界问题
    dfsFind(root, 0, depCounter);         //  调用深度优先遍历函数,
                                          //  传入根和初始深度以及存储数每层结点数的数组
    int max = 1, res = 0;                 //  错误 4 未初始化、命名冲突
    for (int i = 1; i <= maxDep; i++) {    
        if (depCounter[i] > max) {
            max = depCounter[i];
            res = i;                      //  错误 5 被赋值变量错误
        }
    }
    return res;                           //  错误 6 返回错误变量
}
2、早期短链接广泛应用于图片上传网站,通过缩短网址URL链接字数,达到减少代码字符串的目的。常见于网店图片分类的使用,因有字符个数限制,采用短链接可以达到外链图片的目的。自微博盛行以来,在微博字数有限的特色下,短链接也盛行于微博网站,以节省字数给博主发布更多文字的空间。
问题描述:设计一个短链生成和查询系统,需要提供以下两个功能:
1、提供长链转换短链的接口
2、点击短链能跳转到对应的长链
题目要求:
1、同一个长链生成同一个短链接,不要有多个短链指向同一个长链。
2、同一个短链只能指向某一个长链,短链生成后要固定不变,不能再指向其它长链。
3、给出系统架构,需要考虑高并发解决方案。
4、考虑存储和缓存方案
数据量预估:
1、预计长链接总量500亿
2、长链换短链请求量:10W qps
3、短链跳转请求量:100W qps
参考答案:

设计: 1、长链转短链 发号器,每过来一个长链换短链请求发一个号,发号器所发号码从 000 自增,所发号码为十进制,转化为 626262 进制后作为短链(626262 进制对应 262626 小写字母加上 262626大写字母还有 101010 数字)。 2、短链跳转长链 将短链所对应号码与长链一一映射存储于表中。

优化: 1、长链对应唯一短链 当长链转短链请求过来时率先在字典树(映射)中查找该长链是否已经分配短链,如果分配,则直接返回短链,若未分配则利用发号器继续分配。字典树在发号同时建立。 2、系统架构与高并发 采用 keyvaluekey−valuekey-value 分布式储存系统,创建更多发号器,减小发号请求高并发时的压力,比方说创建 100001000010000 个发号器,发号器编号从 0∼99990∼99990 \sim 9999,对应每个发号器分别只发送以 0∼99990∼99990 \sim 9999 为尾号的号码,每个发号器对应一片内存存储所发号码与长链对应的表,减小跳转访问高并发时的压力。 3、存储和缓存 利用分布式系统,采用 NoSqlNoSqlNoSql 数据库存储彼此一一映射,采用 LRULRULRU (最近最久未使用)算法管理内存与缓存。 4、其他 砸钱就好了!!!有钱真的可以为所欲为……

编程题

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

这个题最简单的方法是 O(n2)O(n2)O(n^2) 的暴力思维,但是很明显会超时,所以我们需要寻求更加高效的 O(nlogn)O(nlogn)O(nlogn) 的算法。

我们可以率先对点按照 xxx 轴进行排序,然后从右往左进行遍历,记录历史最大 yyy 值,同时更新最大点集。

这里我们很容易想到,最右侧的点一定是最大点,那么当我们往左进行遍历时,凡是大于历史最大 yyy 值得点均为最大点集中得点。

参考答案:
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 10;  //  设置点数上限

//  结点
struct point
{
    int x, y;

    //  重载运算符以备 sort 时使用
    bool operator < (const point &a) const
    {
        return x < a.x;
    }
};

int n, cnt;         //  n 点数,cnt 最大点集点数
point pts[MAXN];    //  存放初始点集
point res[MAXN];    //  存放最大点集

void solve()
{
    sort(pts, pts + n); //  按照 x 轴进行从小到大排序

    res[0] = pts[n - 1];//  最右点绝对在最大点集中
    int mx = res[0].y;  //  记录从右往左扫描过程中最大 y 值
    cnt = 1;
    //  从右往左扫描时,如果当前点 y 值大于历史最大 y 值,该点在最大点集中
    for (int i = n - 2; i >= 0; i--)
    {
        if (pts[i].y >= mx)
        {
            res[cnt++] = pts[i];    //  更新最大点集
            mx = pts[i].y;          //  更新历史最大 y 值
        }
    }
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &pts[i].x, &pts[i].y);
    }

    solve();

    for (int i = cnt - 1; i >= 0; i--)
    {
        printf("%d %d\n", res[i].x, res[i].y);
    }

    return 0;
}
4、给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个:
区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可,不需要输出具体的区间。如给定序列 [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]=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;

\begin{aligned} & [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; \end{aligned}

从上述计算可见选定区间 [6] ,计算值为 36, 则程序输出为 36。
区间内的所有数字都在[0, 100]的范围内;
题解:

这个题很明显是一个区间问题,我们需要求每个元素作为最小值的最大区间,只有这样我们才能保证局部最优,所以这是一个单调栈问题。

然而,这个题给定了一个十分强的条件,即区间内所有数字都在 [0,100][0,100][0, 100] 之间,那么我们完全没有必要使用单调栈,单调栈更适合于区间内数字范围极大的情况。在数字范围很小时,单调栈不一定比暴力更优。

所以,这个题我们可以暴力枚举 [1,100][1,100][1, 100],然后从左往右以及从右往左分别遍历数组,获取到每个元素作为最小值的最大区间。

接着我们可以直接遍历每个元素,然后乘以该区间的和,这个和可以率先求取前缀和,这样,最后取最优结果即可。

参考答案:
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 10;  //  设置数组最大长度
const int MAX_NUM = 100;    //  设置元素最大值

int n;
int a[MAXN];                //  题目给定数组序列
int l[MAXN];                //  l[i] 表示第 i 个元素作为最小值最大区间的左界
int r[MAXN];                //  r[i] 表示第 i 个元素作为最小值最大区间的右界
int s[MAXN];                //  s[i] 表示前 i 个元素的和

//  初始化函数,预处理前缀和
void init()
{
    s[1] = a[1];
    for (int i = 2; i <= n; i++)
    {
        s[i] = s[i - 1] + a[i];
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", a + i);
    }

    init();

    //  从左往右遍历,获取 l
    int L, R;
    for (int i = 1; i <= MAX_NUM; ++i)
    {
        L = 1;
        for (int j = 1; j <= n; ++j)
        {
            if (a[j] < i)
            {
                L = j + 1;
            }
            if (a[j] == i)
            {
                l[j] = L;
            }
        }
    }

    //  从右往左遍历,获取 r
    for (int i = 1; i <= MAX_NUM; ++i)
    {
        R = n;
        for (int j = n; j >= 1; --j)
        {
            if (a[j] < i)
            {
                R = j - 1;
            }
            if (a[j] == i)
            {
                r[j] = R;
            }
        }
    }

    //  枚举取最优解
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ans = max(ans, (s[r[i]] - s[l[i] - 1]) * a[i]);
    }

    cout << ans << endl;

    return 0;
}
5、产品经理(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实现的时间点。
题解:

这个题难点在语法的考核,STLSTLSTL 使用的是否足够熟练。要有足够的耐心和细心才行。

首先,我们来从题目中提炼几个要点: 1、每个 ideaideaidea 都有提出时间,每个程序猿只能找当时时刻已经提出的 ideaideaidea。 2、对于每个 PMPMPM 会有若干个 ideaideaidea,也可能没有,每个 PMPMPM 最想完成的 ideaideaidea 是优先级最高的,如果优先级一样,则取花费时间最小的,依然一样,则选取提出时间最早的。 3、程序猿在寻求自己想要完成的 ideaideaidea 时,首先考虑每个 PMPMPM 最想完成的一个 ideaideaidea,然后从中选择所需时间最小的 ideaideaidea,如果时间一样选取 PMPMPM 序号最小的。 4、程序猿只有在空闲时刻可以选择完成 ideaideaidea,选择后的一段时间繁忙知道该 ideaideaidea 完成,如果某一时刻有多个程序猿空闲,则依次按照上述第三条进行选取任务,除非没有任务可选。

根据以上分析几点,我们几乎上已经可以得出算法了,其实就是一个略微暴力的思路,数据范围十分小,我们可以枚举时间,然后根据时间给 PMPMPM 添加 ideaideaidea,接着取每个 PMPMPM 最想完成的 ideaideaidea 进行排序,然后让程序猿选择,选择后的 ideaideaidea 需要及时删除。多个程序猿空闲时,需要注意一点是不能在前一个操作删除 ideaideaidea 后直接选取,因为删除那个 ideaideaidea 后该 ideaideaidea 的 PMPMPM 也许还有其他 ideaideaidea 需要加入进行排序供下一个空闲程序猿选择。就这样,每次完成一个 ideaideaidea 记录一下该 ideaideaidea 的完成时间即可,离线操作。

说到这儿,思路已经十分清晰了,我们只需要对若干个 vectorvectorvector 或者数组进行多次排序操作选取最优即可,一个暴力贪心模拟的思路, 我使用的是 vectorvectorvector,因为数组在删除操作时多少显得有些不方便。

参考答案:
#include <bits/stdc++.h> 

using namespace std;

const int MAXN = 3003;

struct idea
{
    int PM_id;              //  PM 序号 
    int post_time;          //  提出时间 
    int priority;           //  优先权 
    int cost_time;          //  所需时间 
    int order;              //  idea 序号 
} ideas[MAXN];

int N, M, P;                //  N PM, M Program, P idea              
int finish_time[MAXN];      //  完成每个 idea 时间 
int program_time[MAXN];     //  程序猿空闲时刻 
vector<idea> PM_idea[MAXN]; //  每个 PM 在某时刻所拥有的未完成 idea 

//  按照提出时间从小到达排序 
bool cmp_post(const idea &a, const idea &b)
{
    return a.post_time < b.post_time;
}

//  按照第一关键词优先级从大到小,第二关键词花费时间从小到大,第三关键词提出时间从小到大排序 
bool cmp_priority(const idea &a, const idea &b)
{
    if (a.priority != b.priority)
    {
        return a.priority > b.priority;
    }
    else
    {
        if (a.cost_time != b.cost_time)
        {
            return a.cost_time < b.cost_time;
        }
        return a.post_time < b.post_time;
    }
}

//  按照第一关键词花费时间从小到大,第二关键词 PM 序号从小到大排序 
bool cmp_cost(const idea &a, const idea &b)
{
    if (a.cost_time != b.cost_time)
    {
        return a.cost_time < b.cost_time;
    }
    return a.PM_id < b.PM_id;
}

int main()
{
    scanf("%d%d%d", &N, &M, &P);

    int a, b, c, d; 
    for (int i = 0; i < P; i++)
    {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        ideas[i] = {a - 1, b, c, d, i};
    }
    sort(ideas, ideas + P, cmp_post);     //   按照 cmp_post 排序,为后续给 PM 添加 idea 

    int now_time = 1, cnt = 0, last = 0;  //   now_time 现在时刻,cnt 已经完成任务,last 下一次添加任务起点 
    while (cnt < P)
    {
        for (int i = last; i < P; i++)
        {
            if (ideas[i].post_time == now_time)
            {
                //  给 PM 添加 idea 并且按照 cmp_priority 排序,为后续生成每个 PM 最想完成 idea 
                PM_idea[ideas[i].PM_id].push_back(ideas[i]);          
                sort(PM_idea[ideas[i].PM_id].begin(), PM_idea[ideas[i].PM_id].end(), cmp_priority);

                if (i == P - 1)
                {
                    last = P;
                }
            }
            else 
            {
                last = i;
                break;
            }
        }

        //  选取每个 PM 最想完成的 idea 
        vector<idea> PM_priority;
        for (int i = 0; i < N; i++)
        {
            if (!PM_idea[i].empty())
            {
                PM_priority.push_back(PM_idea[i][0]);
            }
        } 

        for (int i = 0; i < M; i++)
        {
            //  程序猿空闲并且此刻有 idea 可供选择 
            if (program_time[i] <= now_time && !PM_priority.empty())
            {
                //  按照 cmp_cost 排序,为后续给程序猿选取 idea 
                sort(PM_priority.begin(), PM_priority.end(), cmp_cost);
                //  选取 idea 并且更新程序猿空闲时间和存储该 idea 完成时间 
                program_time[i] = now_time + PM_priority[0].cost_time;
                finish_time[PM_priority[0].order] = program_time[i];
                //  从 PM 此刻 idea 中删除已经选取的 idea 
                PM_idea[PM_priority[0].PM_id].erase(PM_idea[PM_priority[0].PM_id].begin());
                //  如果该 PM 依然有 idea,则将下一个 idea 添加到 PM 最想完成 idea 集合中 
                if (!PM_idea[PM_priority[0].PM_id].empty())
                {
                    PM_priority.push_back(PM_idea[PM_priority[0].PM_id][0]);
                }
                //  从 PM 最想完成 idea 集合中删除已经选取过的 idea 
                PM_priority.erase(PM_priority.begin());
                cnt++;                                 //  完成 idea 数自增 
            }
        }

        now_time++;                                    //  现在时间自增 
    }

    for (int i = 0; i < P; i++)
    {
        printf("%d\n", finish_time[i]);
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 95 后程序员一出校门就拿年薪 32 万?

    原文出处:https://blog.csdn.net/csdnnews/article/details/83114697 ​

    Java
  • 第四范式被指毁约大批秋招意向offer,CEO连夜回应:内部沟通出问题

    10月25日,不少网友匿名爆料,在2018秋招季,国内AI创业公司第四范式“毁了一大批人的意向offer”。

    新智元
  • AI 百万级人才缺口:应届生年薪 50 万,没出校门被抢光

    60多年来,人工智能产业发展经历三起三落,如今可谓到了一日千里的发展速度,现阶段的人工智能领域,最赚钱的可能是里的“人工”生意了,因为人工智能领域的人才,太短缺...

    钱塘数据
  • 理科生全面掌管AI?中戏告诉你,文科也要人工智能了!

    这句话在2019年时达到了羡慕值的巅峰。从多家头部企业曝出的校招薪资以及最终兑现的金额来看,AI人才的短缺使得包括算法工程师、安全工程师等在内的数十个岗位都诞生...

    镁客网
  • 26所高校联合建议:尽快设置人工智能本科专业

    量子位
  • 世界AI人才分布 , 应届生年薪50万,没出校门被抢光!

    刚刚过去的周末,人工智能连放大招——来自波士顿动力(Boston Dynamics)的机器人“阿特拉斯”展现了完美的后空翻动作;腾讯推出的新闻写作机器人Drea...

    IT派
  • 重磅 | 283所高校获批数据科学与大数据专业,985/211高校仅占13%

    月21日下午,历时近一年时间,教育部公布了2017年度普通高等学校本科专业备案和审批结果的最新通知,第三批大数据本科专业院校获批。 此次教育部最新公布的高校新增...

    小莹莹
  • 叮!你的校招提醒微信机器人已上线!

    招聘季即将到来,如何实时的得知招聘信息呢?自然是爬虫+微信了。 这几日在票圈和各微信群看到大家疯狂刷“京东”、“腾讯”等秋招类的“广告”,我对这些营销方式存怀...

    一点儿也不潇洒
  • 教育部最新:283所高校获批数据科学与大数据专业(附完整名单+公益计划)

    大数据文摘

扫码关注云+社区

领取腾讯云代金券