阿里云技术面试真题公开！云原生、大数据、IOT、数据库等领域的30道面试真题！（下篇）

本文内容截取自《阿里云技术面试红宝书》
阿里云技术面试官面试真题和题解，助你拿下Offer！

1. 对某种高位特征的搜索，以寻找相似特征的个体

问题：实际应用中经常需要我们对进行对某种高位特征的搜索，以寻找相似特征的个体。请问业界通常针对该问题的解决方法是啥，核心原理是啥。

参考答案：近似最邻近（ Approximate Nearest Neighbor）算法，基本分类：

基于树的方法

KD 树是其下的经典算法。一般而言，在空间维度比较低时，KD 树的查找性能还是比较高效的；但当空间维度较高时，该方法会退化为暴力枚举，性能较差，这时一般会采用下面的哈希方法或者矢量量化方法。

哈希方法

LSH(Locality-Sensitive Hashing) 是其下的代表算法。对于小数据集和中规模的数据集 ( 几个 million- 几十个 million)，基于 LSH 的方法的效果和性能都还不错。这方面有 2 个开源工具 FALCONN 和 NMSLIB。

矢量量化方法

矢量量化方法，即 vector quantization。在矢量量化编码中，关键是码本的建立和码字搜索算法。比如常见的聚类算法，就是一种矢量量化方法。而在相似搜索中，向量量化方法又以 PQ 方法最为典型。对于大规模数据集 ( 几百个 million 以上 )，基于矢量量化的方法是一个明智的选择，可以用用 Faiss 开源工具。

基于图的方法：

基于 k- 近邻图构造（k-neighbor-graph construction）。阿里跟浙大合作的算法NSG，即为基于图的算法。

2. 在目标跟踪算法中，需要判定路径的统计学合理性。请列举几种可能的统计学模型来解决该问题。

参考答案：一些经典模型如马尔可夫随机场（MRF），条件随机场（CRF），标签传播（label propagation）。
如果给出的答案没有提及明确的算法，但是接近于优化最大联合概率分布，也 ok。

3. 服务限流有哪些算法？

参考答案：服务限流常见算法有并发计数器算法，漏桶算法，令牌桶算法。前两种算法不支持突发流量的限流，令牌桶算法支持突发流量的限流。 一般用谷歌 guava 落地令牌桶算法，用 sentinel 作为服务限流的中间件。

4. free -m 命令输出，buffer 和 cached 各是什么含义，有什么区别？ -/+ buffers/cache 目的是看什么，分别是什么意思？

参考答案：buffer 是块设备的读写缓冲区，cache 作为 pagecache 的内存，文件系统的 cache。
查看内存真正被占用的容量（Used-buffers-cached），查看内存还可使用的容量（Free+buffers+cached）。

5. 模拟构造一个哈希表。

问题：模拟构造一个哈希表（哈希函数可以用 rand(seed) 代替），统计出哈希表在指定加载因子（实际元素数量除以哈希表容量）下 slot 被占用的比率、冲突链平均长度（用链表解决冲突）、最大冲突链长度。假设在查询哈希表时，一半元素命中，一半不命中，计算这种情况下的平均访存次数。

答案: 下面的代码并没有真正实现哈希表，每个 slot 位置只用了一个计数器来统计。答题者如果实现一个哈希表来真正模拟出结果也是可以的。

#include<stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define HASH_TBL_SZ 100000
int hsh_ary[HASH_TBL_SZ];
int hash_stati( int ratio )
{
 int i, slots_occu = 0;
 int max_collision = 0;
 int ele_nr = ratio * HASH_TBL_SZ / 100;
 double avg_col_len;
 if( ratio <=0 || ratio > 100 ){
 printf( “Error parameter: ratio must be between 1-100.\n” );
 return -1;
 }
 for( i = 0; i < HASH_TBL_SZ; ++i ){ // 也可用 memset() 等函数清零
 hsh_ary[i] = 0;
 }
 for( i = 0; i < ele_nr; ++i ){
 uint32_t idx = rand() % HASH_TBL_SZ;
 if( hsh_ary[idx] == 0 ){
 slots_occu ++;
 }
 hsh_ary[idx] ++;
 if( hsh_ary[idx] > max_collision ){
 max_collision = hsh_ary[idx];
 }
 }

 avg_col_len = (double)ele_nr/slots_occu;
 double slot_ratio = (double)slots_occu/HASH_TBL_SZ;
 printf( “slot occupied ratio =%f, avglen = %f, max_collision = %d\n”, 
slot_ratio, avg_col_len, max_collision );
 double access_nr;
 access_nr = 0.5 * avg_col_len + 0.5 * avg_col_len * slot_ratio;
 printf(“average access number(50%% hit) = %f\n”, access_nr);
}
int main(int argc, char**argv)
{
 hash_stati(10);
 hash_stati(20);
 hash_stati(50);
 hash_stati(80);
 hash_stati(100);
}

例子中 5 次调用的输出：

slot occupied ratio =0.095280, avglen = 1.049538, max_collision = 4
average access number(50% hit) = 0.574769
slot occupied ratio =0.181190, avglen = 1.103814, max_collision = 5
average access number(50% hit) = 0.651907
slot occupied ratio =0.392900, avglen = 1.272588, max_collision = 5
average access number(50% hit) = 0.886294
slot occupied ratio =0.551120, avglen = 1.451589, max_collision = 8
average access number(50% hit) = 1.125795
slot occupied ratio =0.632040, avglen = 1.582178, max_collision = 8
average access number(50% hit) = 1.291089

6. 如何用 GPU 来并行计算矩阵乘？

问题：输入为：dimention 为 NxN 的数组 A，B，输出为矩阵 C；考察点就是如何用GPU 来并行计算矩阵乘。每个线程算 C 里面的一个 element

答案：

#include <math.h>
#include <iostream>
#include “cuda_runtime.h”
#include “kernel.h”
#include <stdlib.h>
using namespace std;
__global__ void matrixMultiplicationKernel(float* A, float* B, float* C, int N) {
 int ROW = blockIdx.y*blockDim.y+threadIdx.y;
 int COL = blockIdx.x*blockDim.x+threadIdx.x;
 float tmpSum = 0;
 if (ROW < N && COL < N) {
 // each thread computes one element of the block sub-matrix
 for (int i = 0; i < N; i++) {
 tmpSum += A[ROW * N + i] * B[i * N + COL];
 }
 }
 C[ROW * N + COL] = tmpSum;
}
void matrixMultiplication(float *A, float *B, float *C, int N){
 // declare the number of blocks per grid and the number of threads per block
 // use 1 to 512 threads per block
 dim3 threadsPerBlock(N, N);
 dim3 blocksPerGrid(1, 1);
 if (N*N > 512){
 threadsPerBlock.x = 512;
 threadsPerBlock.y = 512;
 blocksPerGrid.x = ceil(double(N)/double(threadsPerBlock.x));
 blocksPerGrid.y = ceil(double(N)/double(threadsPerBlock.y));
 }
 matrixMultiplicationKernel<<<blocksPerGrid,threadsPerBlock>>>(A, B, C, N);
}

7. 如何使用优秀的时空复杂度快速找到这个数字？

问题：长度为 n 的数组，其中只有 2 个数字出现了奇数次，其他均出现偶数次，问如何使用优秀的时空复杂度快速找到这个数字？

思路：主要是利用异或定理，若 a^b=x，则 a=b^x，b=xa。

解法：

1. 假设这两个数分别为 a、b，假设将数组中所有元素全部异或后结果为 x，因为a!=b，所以 x=a^b，且 x!=0
2. 判断 x 中某位 bit 为 1 的位置，例如 x=0x00101100，那么 k=2/k=3/k=5 皆可，只需一个 ;
3. 因为 x 中第 k 位为 1 表示 a 或 b 中有一个数的第 k 位也为 1，另一个数第 k 位为0；假设 a 的第 k 位为 1；
4. 将 x 与数组中第 k 位为 1 的所有数字进行异或，最终结果得到 b；
5. 将 x 与 b 异或，得到的结果即为 a

8. 在两个有序自增数组中寻找第 k 大的数，并分析时间复杂度。

思路：有多种解法，要求查找效率最高

解法 1：由于数组本身有顺序没必要全部再排序，可以定义两个游标分别指向两个有序数组，按序移动，并用 count 计数，当 count 等于 k 时，返回两个游标指向的数中较小的那一个，时间复杂度 O(m+n)，不是最优解

解法 2：充分利用两个数组都是有序的条件：
1）当 array1[k/2-1] == array2[k/2-1] 则返回 array1[k/2-1] 或者 array2[k/2-1]
2）当 array1[k/2-1] > array2[k/2-1]  则 array2 在 [0,k/2-1] 范围内的元素一定比array1、array2 合并后第 k 个元素小，可以不用考虑array2 在 [0,k/2-1] 范围内的元素
3）当 array1[k/2-1] < array2[k/2-1]  则 array1 在 [0,k/2-1] 范围内的元素一定比array1、array2 合并后第 k 个元素小，可以不用考虑 array1 在 [0,k/2-1] 范围内的元素因此算法可以写成一个递归的形式，递归结束的条件为：
1）array1[k/2-1] == array2[k/2-1] return array1[k/2-1]
2）array1 或者 array2 为空时，return array1[k-1] 或者 array2[k-1]
3）k==1 时，返回 min(array1[0],array2[0])
时间复杂度 O(log(m+n))

解法 3：归并排序，时间复杂度 O(nlogn)，此解法效率低，没有考虑实际情况，不得分

9. 给定一个单向链表如何判断是否存在环，并给出环的起始节点。

不存在环返回 NULL，存在返回环的起始点。

参考答案：

struct List
{
 int val;
 struct List *next;
 
}
List* FindStart(struct List *head)
{
 if (head == NULL || head->next == NULL) 
 {
 return NULL;
 }
 
 struct List *slow = head;
 struct List *fast = head;
 struct List *meet = NULL;
 
 while (fast != NULL && fast->next != NULL)
 {
 slow = slow->next;
 fast = fast->next->next;
 
 if (slow == fast)
 {
 meet = fast;
 break;
 }
 }
 
 if (meet == NULL) 
 {
 return NULL;
 }
 
 slow = head;
 fast = meet;

while (slow != fast)
 {
 slow = slow->next;
 fast = fast->next;
 }
 
 return slow;
}

10. 连续子数组最大和

给定一个整数数组，有正有负有 0，比如 [7, 8, 10, -24, 15, 11]
1. 找出和最大的连续子数组的和
2. 找出和最大的连续子数组的起止 index
3. 找出最长的和最大的连续子数组的起止 index

考察能力：

1. 基础算法灵活运用能力
2. 初始值，数据类型，边界条件的严谨度
3. 随着题目变化不断深入的能力

参考答案：

1. O（n）算法，从前往后叠加并记录当前和，当前和小于或者小于等于 0 时，从下一个数字开始重新叠加。注意：
   a) 全负的数组如何处理
   b) 记录和的变量的类型
   c) 小于还是小于等于，差别在哪里？
2. 在发现更大的和的时候，更新临时起止 index
3. 核心是 1 中的小于或者小于等于 0，以及每次遇到一样的最大和时，判断长度

vector<int> getSum(vector<int>& nums) {
 int n = nums.size();
 int ans = nums[0], l = 0, r = 0;
 int cur = nums[0]，tl;
 
 for (int i=1; i<n; ++i) {
 cur += nums[i];
 if (cur > ans) {
 ans = cur;
 l = tl;
 r = i;
 }
 if （cur < 0） {
 cur = 0;
 tl = i;
 }
 }
 
 return {ans, l, r};
}

更多相关文章 :

阿里云技术面试真题公开！（上篇）
阿里云技术面试真题公开！（中篇）