搜狗2020校招【后端】笔试（第一场）
时长:120分钟 总分:100分
109浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 3 |
1.
核子聚变
请设计一个程序，在规定步数内，成功的使得一个原子核队列完全湮灭。
7种原子核(用A-G表示)，排成一条直线队列，在初始状态下它们是稳定的。
如果我们发射一个额外的原子核插入到队列，如果插入的位置没有形成大于等于3个相同的原子核的序列，那么队列继续保持稳定。
如果该位置上相邻的三个或以上的原子核种类相同， 就会诱发聚变湮灭成能量散失；然后队列上剩下的左右两半会受外部压力重新拼接在一起，拼接点两侧如果类型相同，且拼接后形成三个或以上连续相同序列，则连锁反映继续聚变湮灭。
为了方便描述插入位置，假定队列长度为n，我们把对列最左端外侧位置编号为0，右端外侧位置编号为n，共有n+1个位置。
例如：
AAABC，如果把一个A插入到位置4（或位置5）的时候，队列会变成AAABAC，继续稳定存在。
AABBCCA，如果把一个C插入到位置4（或位置5,6）的时候，会形成3个C，之后3个C会湮灭，队列变成AABBA，重新恢复稳定。
BAABBCCBACCB，一个C色球插入到位置5（或位置6,7）的时候，会触发连锁反应消去的过程如下（"+"表示拼接点）：
BAABB+C+CCBACCCB => BAABB+BACCCB => BAA+ACCCB => B+CCCB => BCCCB (稳定)
注意最后剩下3个连续的C，是因为最后一步拼接时，拼接点左右类型并不相同，不会触发连锁反应。
每在队列中新插入一个原子核，记为一步；每一步可插入任意类型的原子核。
本题给出1）初始的队列，2）要求在几步之内达成完全湮灭。
要求选手给出一个消去过程，将所有的原子核都聚变湮灭。该过程必须在给定的步数上限之内完成才算正确。
请选手注意，本题并不要求最优解，只需要给出一个不超过步数上限的解即可。
本题45%的case，初始字符串长度不大于30。
例如：
AAABBAAACCABDCAABC
10输入样例： AAABBAAACCABCAABC 10 输出描述： 若干行，每一行是一步，包含一个字母和一个数字，用空格分开；分别表示为这一步要插入的原子核类型，以及插入的位置。0表示最左端，n表示第n个字母的右侧。
例如对于上述的例子输入的的合法输出可以是：
C 8
C 3
C 3
D 5
D 5
B 0
B 0
C 0
C 0
这个输出文件共9行，小于输入文件的步数限制10，因此这个消去过程成立，该case通过。
注意：合法输出不唯一，也不要求最优解。
下面具体解释上述消去序列的每一步的输出和变化如下
C 8 ：AAABBAAACCCABDDAA => AAABBAAA+ABDCAABC => AAABB+BDCAABC => AAADDAA
C 3 ：AAACDCAABC
C 3 ：AAACCDCAABC
D 5 ：AAACCDDCAABC
D 5 ：AAACCDDDCAABC => AAACC+CAABC => AAA+AABC => BC
B 0 ：BBC
B 0 ：BBBC => C
C 0 ：CC
C 0 ：CCC => empty输出样例 C 8 C 3 C 3 B 0 B 0 C 0 C 0
2.
服务器数据分发
【题干描述】：
我们共有n台服务器，每台服务器可以和若干个子服务器传输数据，n台服务器组成一个树状结构。
现在要将一份数据从root节点开始分发给所有服务器。
一次数据传输需要一个小时时间，
一个节点可以同时对k个儿子节点进行并行传输，
不同节点可以并行分发。
问，全部分发完成，最短需要多少小时？
【示例】：
当共有5台服务器，其树状结构为
0
/ \
1 2
/ \
3 4
假设每一台服务器同时可以对1个儿子节点（k=1）并行传输，最优的数据传输过程示例如下：
第一个小时，0 -> 1；
第二个小时，1->3 & 0->2；
第三个小时，1 -> 4
所以当k=1时，全部分发完成最短需要3个小时。
假设每一台服务器同时可以对2个儿子节点（k=2）并行传输，最优的数据传输过程示例如下：
第一个小时，0 -> 1 & 0 -> 2
第二个小时，1 -> 3 & 1 -> 4
所以当k=2时，全部分发完成最短需要2个小时。
其他行用于服务器树状结构描述，每一行表示一个父节点以及父节点对应的所有子节点。每一行都通过空格符分割不同数字，第一位数字为父节点及其所有子节点个数，第二位数字为父节点编号，其他数字为对应的子节点编号。输入样例： 1 2 3 0 1 2 2 1 3 输出描述： 输出全部服务器分发完成，需要的最短时间。输出样例 2
3.
关联容器map设计
关联容器map保存<key, value>数据，能通过key快速存储或查找记录。请设计一个map，能够满足以下要求：
1. map的容量size是一个固定值N，即map最多保存N个<key, value>记录；
2. map insert一个<key, value>前，首先判断这个key是否已经在map中存在：
1) 如果存在：记这个已存在的记录为<key, old_value>，若old_value<value，则把old_value更新为value；否则，不做更新。
2) 如果不存在：
若size<N，则执行map的insert，保存这个<key, value>，且size+=1；
若size==N，先淘汰掉一个更新时间最早的记录，再执行map的insert，保存这个<key, value>，size保持为N不变。
说明：记录的更新时间默认为其被insert进map的时间，之后的某一时刻T，如果这个记录的value被更新，那么，该记录的更新时间就变为T。
