1.在某个工厂的生成一件产品（A，B, C, …)。其中产品A依赖于半成品和原料（E,F, g…)。其中半成品B又依赖于 其它的半成品或原料（H, I, …)。现在发现原料x发生质量问题，所以由原料x制成的半成品或产品以及直接或间接依赖这些半成品的生成物都要销毁掉。请设计一个C++数据结构来描述这些原料，半成品和最终产品的依赖关系，能够满足以下两个常用请求的速度要求。

一：指定的产品A，列出它所需要的原料列表A-Set。

二：并且给出指定的原料x发生质量问题的所有需要销毁的半成品或产品的列表。

 

 

2.描述
Memcached是一款非常流行的开源缓存软件，请根据下面的网络协议说明，实现解析函数。补充题目中的代码片段和结构体定义。程序代码运行于X86 64bit Linux平台。

The format of a packet is a fixed size header followed by three optional variable size components (command-specific extras, the key and the value):

Byte/ 0 | 1 | 2 | 3 |
/ | | | |
|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|
+---------------+---------------+---------------+---------------+
0/ HEADER /
/ /
/ /
/ /
+---------------+---------------+---------------+---------------+
24/ Command-specific extras (as needed) /
+/ (note length in the extras length header field) /
+---------------+---------------+---------------+---------------+
m/ Key (as needed) /
+/ (note length in key length header field) /
+---------------+---------------+---------------+---------------+
n/ Value (as needed) /
+/ (note length is total body length header field, minus /
+/ sum of the extras and key length body fields) /
+---------------+---------------+---------------+---------------+

header:

Byte/ 0 | 1 | 2 | 3 |
/ | | | |
|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|
+---------------+---------------+---------------+---------------+
0| Magic | Opcode | Key length |
+---------------+---------------+---------------+---------------+
4| Extras length | Data type | Reserved |
+---------------+---------------+---------------+---------------+
8| Total body length |
+---------------+---------------+---------------+---------------+
12| Opaque |
+---------------+---------------+---------------+---------------+
16| CAS |
| |
+---------------+---------------+---------------+---------------+
Total 24 bytes

Magic is a magic byte which distinguishes requests from responses. It must be 0x80 for requests and 0x81 for responses.
Opcode specifies the type of command, e.g. GET is 0 and SET is 1. 
Key Length specifies the size in bytes of the Key-part of the packet.
Extras length specifies the size in bytes of the Command-specific extras-part of the packet.
Data type is currenly not used and should always be 0.
Bytes 7-8 is either Reserved in the request or Status in the response. - The status corresponds to an error code or 0 if successful.
Total body length is the total size of the body in bytes, i.e. Total body length = Key length + Key length + Value length. The value length is not given explicitly in the header, but can be calculated as Total bodylength - Key length - Extras length.
Opaque is 4 bytes which are passed along in a request and passed back unmodified in the response.
CAS is used for data version checking. When storing a value you can optionally set its CAS value. Future modifications will be rejected if a matching CAS value is not provided.
example:

Byte/ 0 | 1 | 2 | 3 |
/ | | | |
|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7|
+---------------+---------------+---------------+---------------+
0| 0x80 | 0x00 | 0x00 | 0x05 |
+---------------+---------------+---------------+---------------+
4| 0x00 | 0x00 | 0x00 | 0x00 |
+---------------+---------------+---------------+---------------+
8| 0x00 | 0x00 | 0x00 | 0x05 |
+---------------+---------------+---------------+---------------+
12| 0x00 | 0x00 | 0x00 | 0x00 |
+---------------+---------------+---------------+---------------+
16| 0x00 | 0x00 | 0x00 | 0x00 |
+---------------+---------------+---------------+---------------+
20| 0x00 | 0x00 | 0x00 | 0x00 |
+---------------+---------------+---------------+---------------+
24| 0x48 ('H') | 0x65 ('e') | 0x6c ('l') | 0x6c ('l') |
+---------------+---------------+---------------+---------------+
28| 0x6f ('o') |
+---------------+

Total 29 bytes (24 byte header, and 5 bytes key)

Field (offset) (value)
Magic (0) : 0x80
Opcode (1) : 0x00
Key length (2,3) : 0x0005
Extra length (4) : 0x00
Data type (5) : 0x00
Reserved (6,7) : 0x0000
Total body (8-11) : 0x00000005
Opaque (12-15): 0x00000000
CAS (16-23): 0x0000000000000000
Extras : None
Key (24-29): The textual string: "Hello"
Value : None

问题

struct Packet 
{

};

Packet* DeocdeBuffer(char *buffer, int32_t len) 
{

}

 

 

3.描述

阿里云RDS目标为用户提供高质量的数据库云服务，用户的数据库放到云端后，不仅能够省去自己运维的烦恼，还可以获得很多附加的服务，SQL执行时间分析就是其中的一项。

在这个问题里面，会给出一系列的SQL语句及其执行时间，SQL语句需要以空格为分割符划分为关键词，用户会通过关键词来查询所有含有这个关键词的SQL语句的平均执行时间，如果查询结果不存在，则平均执行时间设为0。

约束：CPU主频2.30GHz，内存限制≤512MB，只允许单线程运行，如果算法的时间复杂度允许程序在5s内执行完毕则可拿到全部分数，问题1需要给出源代码，问题2、3可只使用伪代码说明算法实现思路。

问题1

有个SQL语句及对应的执行时间，每个SQL语句包含英文字母字符、数字和空格，所有SQL语句的总长度。

用户会执行次查询，每次查询给出一个关键词，所有查询关键词总长度。

请根据给出的函数原型实现程序，给出清晰的源代码（SQL语句分割请不要使用语言自带的字符串Split函数），并给出时间复杂度。 

样例说明

SQL语句及执行时间，左侧为执行时间（单位是ms），右侧为对应的SQL语句 2.5   insert into tableA values (1, "columnA", "columnB") 12.5  insert into tableB values (2, "columnA", "columnB", "columnC") 30.0  select columnA, columnC from tableB   查询关键词 tableB insert select tableA   输出结果 21.25 7.50 30.00 2.50   说明：例如第一个查询tableB关键词，第二个和第三个SQL语句存在这个关键词，计算这两个语句的平均时间为(12.5+ 30.0) / 2 = 21.25。

 

C++函数原型（也可用其它主流语言实现，自定义类似C++版本的函数原型）

// sqls是SQL语句列表，times是对应的执行时间，keywords是每次查询的关键词。 //返回每个关键词对应查询结果SQL集合中SQL执行时间的平均值。 vector<double> BatchQueryExecutionTime(const vector<string>&sqls, const vector<double>×, const vector<string>&keywords) {          // your code }

 

问题2

随着用户的业务变得越来越复杂，SQL语句的种类也多起来，我们需要给用户提供分类搜索的功能。

用户可以定义一些分类，这些分类按照树形进行组织，除了叶子分类外每个分类有自己的子分类，整个分类树有唯一根分类，每个SQL会属于其中任意一个分类（不仅仅是叶子分类）。

用户每次查询给出一个分类加一个关键词，我们需要计算此分类及其所有后代分类中存在这一关键词的所有SQL的平均执行时间。

有M(M≤100)个分类，分类由0~M-1个数字表示，并给出分类之间的树形关系，有唯一的根分类。

SQL语句和查询的规模和问题1相同，但每个SQL和查询都额外给出一个对应的分类，请说明算法实现思路，并给出时间复杂度。 

样例说明

分类树，每一行A B，表示B为A的子类，共6个分类 0 1 0 2 0 3 1 4 1 5   从左到右依次为执行时间（单位是ms），此SQL语句的分类，SQL语句 2.5   0 insert into tableA values (1, "columnA", "columnB") 12.5  1 insert into tableB values (2, "columnA", "columnB", "columnC") 30.0  2 select columnA, columnC from tableB 40.0  3 select columnA from tableA 12.0  4 select * from tableC 16.0  4 insert into tableC values (1, 2)   查询的分类和关键词 1 insert 4 select 0 insert   查询结果 14.25 12.00 10.33   说明：第一个查询1 insert，分类1的后代分类有4、5，第二个SQL语句和最后一个SQL语句属于这些分类并且存在查询关键词，因此计算对应的平均值为(12.5+ 16.0)/2 = 14.25。

 

C++函数原型（此函数原型供参考，本问题可只用伪代码说明思路）

struct SQL {     string text; //SQL语句     int kind;//所属分类     double time;//执行时间 };   struct Query {     string keyword;// 查询关键词     int kind;// 查询分类     int id;// 查询标示，为传入查询列表的下标 };   // kindSize为分类数M, kindsTree是分类的树形关系，对于每个分类kind，kindsTree[kind]存储其所有子分类，sqls和queries对应着SQL语句列表和查询列表。 vector<double> BatchQueryExecutionTime(int kindSize, const vector<vector<int>>&kindsTree, const vector<SQL>&sqls, const vector<Query>&queries);

 

问题3

如果将问题2的分类个数M的范围进行扩展，使得，说明算法实现思路，并给出时间复杂度。

C++函数原型同问题2