首页分享秋招笔记：2018阿里中间件部门C/C++岗在线测评

秋招笔记：2018阿里中间件部门C/C++岗在线测评

来源：花匠小妙招时间：2024-12-06 13:45

题目：

今天我们看到的阿里巴巴提供的任何一项服务后边都有着无数子系统和组件的支撑，子系统之间也互相依赖关联，
其中任意一个环节出现问题都可能对上游链路产生影响。小明做为新人接收到的第一个任务就是去梳理所有的依赖关系，
小明和每个系统的负责人确认了依赖关系，记录下调用对应系统的耗时，用这些数据分析端到端链路的数目和链路上最长的耗时。

输入：小明搜集到的系统耗时和依赖列表
5 4 // 表示有5个系统和 4个依赖关系
3 // 调用1号系统耗时 3 ms
2 // 调用2号系统耗时 2 ms
10 // 调用3号系统耗时 10 ms
5 // 调用4号系统耗时 5 ms
7 // 调用5号系统耗时 7 ms
1 2 // 2号系统依赖1号系统
1 3 // 3号系统依赖1号系统
2 5 // 2号系统依赖5号系统
4 5 // 4号系统依赖5号系统

输出: 调用链路的数目和最大的耗时，这里有三条链路1->2->5，1->3， 4->5，最大的耗时是1到3的链路 3+10 = 13，无需考虑环形依赖的存在。
3 13

思路：
1、有向图的遍历。图的存储用的是邻接表表示法，找出入度为0的点（根节点），然后dfs，将路径保存在一个二维的vector中，vector的size即为链路的数目，然后找出耗时最大的那一条。
2、评论有个老哥说可以用multimap来解决，才学疏浅以前确实没有用过0.0，学习了。
3、如果有环怎么办？有环也不用怕，dfs的时候判断一下下一个结点是否是根节点，是就结束，不是就继续。
代码：

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <vector> using namespace std; vector<vector<int> > paths(0); vector<int> path; /* 链表的基本结构，data保存的是是哪一个结点 */ typedef struct node { int data; struct node *next; }list; //邻接表用来保存图 list *lists[1001]; /* visit：该点是否被遍历过，0没有，1有 value：该点的权值 in：该点的入度，为0代表根节点 */ int visit[1001]; int value[1001]; int in[1001]; /* 创建链表的头结点 */ list *create_list(int data) { list *head = (list *)malloc(sizeof(list)); if (head == NULL) { cout << "head malloc error!" << endl; exit(1); } head->data = data; head->next = NULL; return head; } /* 尾插法，插入数据 head: 链表的头结点 data: 要插入的数据 */ void insert_list(list *head, int data) { list *phead = head; while(phead->next != NULL) { phead = phead->next; } list *tmp = (list *)malloc(sizeof(list)); if (tmp == NULL) { cout << "tmp malloc errorn" << endl; exit(1); } tmp->data = data; tmp->next = NULL; phead->next = tmp; } //dfs void dfs(int i) { path.push_back(i); if(lists[i]->next == NULL) { paths.push_back(path); } else { list *phead = lists[i]->next; while (phead != NULL) { if(visit[phead->data] == 0) { visit[phead->data] = 1; dfs(phead->data); visit[phead->data] = 0; } phead = phead->next; } } path.pop_back(); return ; } void print_list(list *head) { list *phead = head; while(phead) { cout << phead->data << " "; phead = phead->next; } cout << endl; } int main() { int m, n; scanf("%d %d", &m, &n); memset(value, 0, sizeof(value)); memset(visit, 0, sizeof(visit)); memset(in, 0, sizeof(in)); list *head; for(int i = 1; i <= m; i++) { scanf("%d", &value[i]); head = create_list(i); lists[i] = head; } int p, q; for(int i = 0; i < n; i++) { scanf("%d %d", &p, &q); in[q]++; insert_list(lists[p], q); } /* for (int i = 1; i <= m; i++) { print_list(lists[i]); } */ for (int i = 1; i <= m; i++) { if (in[i] == 0) { dfs(i); } } int max = -1, sum = 0; //cout << "paths size is:" << paths.size() << endl; for (int i = 0; i < paths.size(); i++) { sum = 0; for(int j = 0; j < paths[i].size(); j++) { //cout << paths[i][j] << " "; sum += value[paths[i][j]]; if (sum > max) { max = sum; } } //cout << endl; } cout << paths.size() << " " << max << endl; return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148

心得体会：
6号的时候投的简历，结果一直都没有给回消息，本以为凉了呢，16号的时候突然接到了邮件，还是挺意外的，虽然深知自己只是炮灰，但还是想去见识一下大厂的面试，希望可以过笔试吧。
努力努力再努力。