（1）代码题（leetcode类型），主要考察数据结构和基础算法，以及代码基本功

虽然这部分跟机器学习，深度学习关系不大，但也是面试的重中之重。基本每家公司的面试都问了大量的算法题和代码题，即使是商汤、face++这样的深度学习公司，考察这部分的时间也占到了我很多轮面试的60%甚至70%以上。我去face++面试的时候，面试官是residual net，shuffle net的作者；但他们的面试中，写代码题依旧是主要的部分。

大部分题目都不难，基本是leetcode medium的难度。但是要求在现场白板编程，思路要流畅，能做到一次性Bug-free. 并且，一般都是要给出时间复杂度和空间复杂度最优的做法。对于少数难度很大的题，也不要慌张。一般也不会一点思路也没有，尽力给面试官展现自己的思考过程。面试官也会引导你，给一点小提示，沿着提示把题目慢慢做出来也是可以通过面试的。

以下是我所遇到的一些需要当场写出完整代码的题目：

<1> 二分查找。分别实现C++中的lower_bound和upper_bound.

<2> 排序。手写快速排序，归并排序，堆排序都被问到过。

<3> 给你一个数组，求这个数组的最大子段积

时间复杂度可以到O(n)

<4> 给你一个数组，在这个数组中找出不重合的两段，让这两段的字段和的差的绝对值最大。

时间复杂度可以到O(n)

<5> 给你一个数组，求一个k值，使得前k个数的方差 + 后面n-k个数的方差最小

时间复杂度可以到O(n)

<6> 给你一个只由0和1组成的字符串，找一个最长的子串，要求这个子串里面0和1的数目相等。

时间复杂度可以到O(n)

<7> 给你一个数组以及一个数K，从这个数组里面选择三个数，使得三个数的和小于等于K，问有多少种选择的方法？

时间复杂度可以到O(n^2)

<8> 给你一个只由0和1组成的矩阵，找出一个最大的子矩阵，要求这个子矩阵是方阵，并且这个子矩阵的所有元素为1

时间复杂度可以到O(n^2)

<9> 求一个字符串的最长回文子串

时间复杂度可以到O(n) (Manacher算法)

<10> 在一个数轴上移动，初始在0点，现在要到给定的某一个x点，每一步有三种选择，坐标加1，坐标减1，坐标乘以2，请问最少需要多少步从0点到x点。

<11> 给你一个集合，输出这个集合的所有子集。

<12> 给你一个长度为n的数组，以及一个k值（k < n) 求出这个数组中每k个相邻元素里面的最大值。其实也就是一个一维的max pooling

时间复杂度可以到O(n)

<13> 写一个程序，在单位球面上随机取点，也就是说保证随机取到的点是均匀的。

<14> 给你一个长度为n的字符串s，以及m个短串（每个短串的长度小于10），每个字符串都是基因序列，也就是说只含有A,T,C,G这四个字母。在字符串中找出所有可以和任何一个短串模糊匹配的子串。模糊匹配的定义，两个字符串长度相等，并且至多有两个字符不一样，那么我们就可以说这两个字符串是模糊匹配的。

1、A为N*k矩阵，B为M*k的矩阵，求AB的欧式距离，要求用矩阵化的方法（不用for循环…）。

其中就是求一个distance矩阵。对A、B中的每一个元素直接求解他们的欧式距离。

一、for循环

分别对A和B中的数据进行循环遍历，计算每两个点之间的欧式距离，然后赋值给dist矩阵。

import numpy as npdef compute_squared_EDM_method(A,B):
  # determin dimensions of data matrix
  num1 = A.shape[0]
  num2 = B.shape[0]
  # initialize squared EDM D
  dists = np.zeros((num1, num2))
  # iterate over upper triangle of D
  for i in range(num1):
    for j in range(num2):
        dists[i][j] = np.sqrt(np.sum(np.square(A[i] - B[j])))  return dists

二、使用矩阵运算的方法替代之前的循环操作。

dist=sqrt（A^2+B^2-2A.Bt）

dists = np.sqrt(-2 * np.dot(A, B.T) + np.sum(np.square(B), axis=1) + np.transpose(
      [np.sum(np.square(A), axis=1)]))

2、给了个label和pred示例，计算AP写代码。

几个概念

PR曲线：即以 precision 和 recall 作为纵、横轴坐标的二维曲线。

AP值：Average Precision，即平均精确度。

如何衡量一个模型的性能，单纯用 precision 和 recall 都不科学。于是人们想到，哎嘛为何不把 PR曲线下的面积当做衡量尺度呢？于是就有了 AP值这一概念。这里的 average，等于是对 precision进行取平均

mAP值：Mean Average Precision，即平均AP值。

是对多个验证集个体求平均AP值。

直接通过label和pred计算AP的方法。

通过p和C计算AP和mAp方法：

Recall = TPR = TP/(TP+FN)

Precision = TP/(TP+FP) (精确度/率)

Accuracy = (TP+TN)/(P+N) = (TP+TN) / (TP + FN + FP + TN) (准确率，姑且这么叫吧，其中P为所有的正样本，N为所有的负样本)
F-Meature = 2(Precision*Recall)/(Precision + Recall)

https://blog.csdn.net/Jesse_Mx/article/details/79169991SSD算法评估：AP， mAP和Precision-Recall曲线

for i in range(len(precisions) - 2, -1, -1):
        precisions[i] = np.maximum(precisions[i], precisions[i + 1])    # Compute mean AP over recall range
    indices = np.where(recalls[:-1] != recalls[1:])[0] + 1
    mAP = np.sum((recalls[indices] - recalls[indices - 1]) *
                 precisions[indices])

[so,si]=sort(-out);%out is the result from your classifier
tp=gt(si)>0;
fp=gt(si)<0;fp=cumsum(fp);%判为负样本的数
tp=cumsum(tp);%判为正样本的数
rec=tp/sum(gt>0);%召回率
prec=tp./(fp+tp);%精确度ap=VOCap(rec,prec);function ap = VOCap(rec,prec)
//matlab 计算AP的过程
mrec=[0 ; rec ; 1];
mpre=[0 ; prec ; 0];
for i=numel(mpre)-1:-1:1
    mpre(i)=max(mpre(i),mpre(i+1));
end
i=find(mrec(2:end)~=mrec(1:end-1))+1;%去掉mrec中重复的部分，+1是保持下标的一致
ap=sum((mrec(i)-mrec(i-1)).*mpre(i));%area=（x(2)-x(1)）*y

机器学习：Python实现聚类算法(二)之AP算法

3、一维maxpooling操作长度1*k，stride=1，窗口大小n，时间复杂度要求很小。

tf.layers.max_pooling1d(
    inputs,
    pool_size,
    strides,
    padding='valid',
    data_format='channels_last',
    name=None
)

inputs：池的张量，秩必须为3。
pool_size：单个整数的整数或元组/列表，表示池化窗口的大小。
strides：单个整数的整数或元组/列表，指定池操作的步幅。
padding：一个字符串，表示填充方法，可以是“valid”或“same”，不区分大小写。
data_format：一个字符串，一个channels_last（默认）或channels_first，表示输入中维度的顺序，channels_last对应于具有形状(batch, length, channels)的输入，而channels_first对应于具有形状(batch, channels, length)的输入。
name：字符串，图层的名称。

输出张量，秩为3。

类似题目：对一个一维数组做核为k的max_pooling, 步长为1，并写出时间复杂度

max pooling 的操作如下图所示：整个图片被不重叠的分割成若干个同样大小的小块（pooling size）。每个小块内只取最大的数字，再舍弃其他节点后，保持原有的平面结构得出 output。

一维数组做max_pooling就是分段比较。

pooling的原理与Python实现

# max pooling
    for r_idx in range(0,out_row):
        for c_idx in range(0,out_col):
            startX = c_idx * poolStride
            startY = r_idx * poolStride
            poolField = temp_map[startY:startY + poolSize, startX:startX + poolSize]
            poolOut = np.max(poolField)
            outputMap[r_idx,c_idx] = poolOut    # retrun outputMap
    return  outputMap

4、字符串反转 hello world —> dlrow olleh。

String str = "Hello World"; //首先定义一个Hello World字符串
StringBuilder sb = new StringBuilder(str); //创建一个StringBuilder变量，将定义的字符串传递进去
System.out.println(sb.reverse().toString()); //使用StringBuilder里面的函数，将字符串反转，然后已字符串的方式输出。