阿里实习模拟笔试

1）某送货公司需要将一车货物送出，由于时效性要求，送货需要沿着特别定制的路线，从仓库出发在城市里绕一圈，然后再回到仓库。目前有送货电车若干辆，每辆车装配一个电池组，仅能行走1/2的送货路线，花费4小时。路线中无法充电，但车辆之间的电池组重新分配电量均需要1小时。如果使用最少的车辆进行送货，送完一次货物需要多少小时。
A. 9
B. 11
C. 12
D. 14
E. 15
F. 16

题目没有看懂，不明白送完一次货物是不是指一辆货车从起点开一圈再回到终点这个过程。如果是的话，下面是一种方案，不一定最优。

第一题示意图

假设从A点出发，途经B、C、D后回到A。设Cn为第n辆车。假设货物都在C1上，其他车辆用于充电。

1. t=0, C1从A开到B，花费2h，电量剩余1/2；
2. t=0, C2从A开到B，花费2h，电量剩余1/2；
3. t=2, C2把电都给C1，花费1h，C1电量慢，C2电用光；
4. t=3, C1从B开到D，花费4h, C1电用光；
5. t=5, C3从A开到D，花费2h，电量剩余1/2；
6. t=7, C3把电都给C1，C1电量剩余1/2，C3电用光；
7. t=8, C1从D开到A，花费2h.

C1送完一次货物，用了3辆车，花费了10h，剩下C2和C3在B点和D点，如果想让这两辆车回到A，需要用更多的车辆把电传给他们。
用2辆车可以使C2和C3从B和D回到A。其中一辆C4从A到B或D，另一辆C5到B和A或D和A的中点。这样C4分出1/4的电给C2或C3,然后C2和C3就能有1/4的电量，C2和C4就能一起从B或D开回B和A或D和A的中点。然后，C5再把1/2的电分给这C2和C4，这C2, C4, C5就能一起回到A。这个过程需要花费6h。

具体过程是：

1. t=1, C4从A开到B，花费2h，电量剩余1/2；
2. t=3, C4将1/4电量给C2，花费1h，C2和C4电量各剩1/4；
3. t=4, C5从A开到A和B的中点，花费1h, C5电量剩余3/4；
4. t=4, C2和C4一起从B开到A和B的中点，花费1h, 电量都用完了；
5. t=5, C5把1/2电量平分给C2和C4，花费1h，C2、C4、C5电量各剩1/4；
6. t=6，C2、C4、C5从B和A的中点开到A，花费1h；
7. t=7, C4和C5在A处充满电，花费1h；
8. t=8, C4从A开到D，花费2h, 电量剩余1/2；
9. t=10, C4将1/4电量给C3，花费1h，C3和C4电量各剩1/4；
10. t=11, C5从A开到A和D的中点，花费1h, C5电量剩余3/4；
11. t=11, C3和C4一起从D开到A和D的中点，花费1h, 电量都用完了；
12. t=12, C5把1/2电量平分给C3和C4，花费1h，C3、C4、C5电量各剩1/4；
13. t=13，C3、C4、C5从D和A的中点开到A，花费1h.

最后一共用了14个小时，5辆车。

上面的过程可以重复利用车辆，但是比较慢。可以提前让C2开到D，然后提前让前两辆车送电给C2，这样C2可以在C1到达D之前达到满电的状态，就不会占用更多的时间，但是这样会需要更多的车，而题目要求的是使用最少的车辆，所以不如重复利用接C2的车。

2）求矩阵的逆

第2题.png
选B
image.png

逆矩阵的定义是
一个n阶方阵A称为可逆的，或非奇异的，如果存在一个n阶方阵B，使得AB=BA=E，则称B是A的一个逆矩阵。A的逆矩阵记作A^(−1) 。
所以让每个选项和题目中的矩阵相乘，找到等于E的那个矩阵。

3）输入图片大小为200x200，一次经过一层卷积（kernel size 5x5, padding 1, stride 2）,pooling(kernel size 3x3, padding 0, stride 1), 又一层卷积（kernel size 3x3, padding 1, stride 1）之后，输出特征图大小为多少？
A. 96
B. 97
C. 98
D. 99
E. 100
F. 101

选B

第三题示意图

4）一个hash表长度为7，散列函数是h(key)=key mod 7,采用现行探测的开放式寻址法解决冲突，现在以如下操作序列写入数据
Insert 1
Insert 3
Insert 10
Insert 11
insert 2
insert 18
Insert 6
delete 3
操作之后剩下6个元素，这6个元素的平均查词寻址次数是多少？
A. 1
B. 1.3
C. 1.5
D. 1.67
E. 1.83
F. 2

11/6=1.83

位置	0	1	2	3	4	5	6
插入元素	6	1	2	3	10	11	18
查找次数	2	1	1	删除	2	2	3

5）在基于自然语言的人机交互系统中，通常会定义一些语义模板来训练NLU（自然语言理解）模型，比如下面的模板可以支持用户通过语音控制机器播放音乐：
1.放几首@{singer}的歌
2.播放一首@{singer}的歌
3.来一曲@{singer}的歌曲
4.来首@{singer}的音乐
5.来个@{singer}的流行音乐
其中"@{singer}"是一个参数，代表歌手，比如第一个模板可以匹配这样的用户query：“放几首刘德华的歌“。可以看到，同样是放歌，有很多种不同但相似的说法，但把他们一条一条单独列出来，编辑的成本会比较高，而且会漏掉一些说法，不严谨。实际上，上面的5个模板，可以用下面的语义模板表达式来表示：
<[播]放|来>[一|几]<首|曲|个>@{singer}的<歌[曲]|[流行]音乐>
其中包含中括号（“[]”）、尖括号（“<>”）和竖线（“|”）三种元素：
1.中括号代表其中的内容是可选的，比如“歌[曲]”，能匹配“歌”和“歌曲”；
2.尖括号代表其中的内容是必选的，比如“<播>放”，能匹配“播放”；
3.括号是可以嵌套的；
4.竖线代表“或”的关系，即竖线分隔的内容是可替换的，比如“<播放|来首>歌曲”,能匹配“播放歌曲”和“来首歌曲”,再如“[播放|来首]歌曲”,能匹配”播放歌曲“，”来首歌曲“和”歌曲“（因为中括号里面是可选的，所以可以匹配”歌曲“）；
5.竖线在其所属的括号内，优先级大于括号中的其他括号，比如” <[播]放|来>首歌曲”，能匹配“播放首歌曲“，“放首歌曲“和”来首歌曲“；
6.竖线可以脱离括号独立存在，比如”在哪里|哪里有”，可以匹配“在哪里”和“哪里有”;
那么，给一个上述的语义模板表达式和用户的query，你能判断用户的query是否能匹配这个表达式吗？

编译器版本: gcc 4.8.4
请使用标准输入输出(stdin，stdout) ；请把所有程序写在一个文件里，勿使用已禁用图形、文件、网络、系统相关的头文件和操作，如sys/stat.h , unistd.h , curl/curl.h , process.h
时间限制: 3S (C/C++以外的语言为: 5 S)   内存限制: 128M (C/C++以外的语言为: 640 M)
输入:
  输入数据包含两行， 第一行，上述格式的语义模板表达式 第二行，用户的自然语言指令（即：用户query）
输出:
  当前query是否匹配当前语义模板表达式。匹配，则输出1，否则输出0.
输入范例:
  <[播]放|来>[一|几]<首|曲|个>@{singer}的<歌[曲]|[流行]音乐> 来几首@{singer}的流行歌曲
输出范例:
  0