用了同学的白金内推码，所以直接进入了面试，全程都在写题！机器学习的问题非常少！
一面：
1、介绍项目
2、强化学习PG的推导
3、强化学习DQN，DDQN，AC，DDPG的区别
4、n个[0,n)的数，求每个数的出现次数（不能开辟额外空间）
这里关键是看清楚题意，n个数，然后是左闭右开的区间，也就是说每个数都不会大于等于n，那么思路就来了：如果我们给一个索引下的数不管加上多少个n，那么这个数对n取余的话，我们就能知道这个数原来是多少；另一方面，如果一个数出现一次，我们就在对应索引位置下的数加上n，那么每个数对应索引位置上的数对n取商的话，就是这个数出现的次数。这样就做到了没有开辟额外的空间。代码现场直接略过了。
5、K个有序数组，找一个长度最小的区间，在这个区间里至少包含每个数组各一个数。
分析：初始化带下为K的最小堆，K个数字是每个数组中的最小值，设置变量max记录k个数字中的最大值，删除堆顶元素，将原堆顶元素对应的数组中下一个元素加入到堆中，调整堆，并且记录当前区间范围为（max-min），重复执行直到某个数组所有值都被删除。
package ByteDance;
/*
给定K个有序数组，求一个最小长度的区间【s,t】，使得每个数组中最少有一个元素在这个区间内。如果有多个长度相等的区间满足条件，则选择起始点s最小的那一个。
*/
class HeapNode{
public int value;
public int arrNum;
public int index;
public HeapNode(int value,int arrNum,int index){
this.value = value;
this.arrNum = arrNum;
this.index = index;
}
}
public class minScope {
public void modifyHeap(HeapNode[] heap,int index,int heapSize){
HeapNode temp = heap[index];
int child = index * 2 + 1;
while(child < heapSize){
if(child + 1 < heapSize && heap[child + 1].value < heap[child].value)
child = child + 1;
if(temp.value > heap[child].value){
heap[index] = heap[child];
index = child;
}
else
break;
child = 2 * index + 1;
}
heap[index] = temp;
}
public void getMinScope(int[][] matrix){
int heapSize = matrix.length;
HeapNode[] heap = new HeapNode[heapSize];
int max = Integer.MIN_VALUE;
for(int i=0;i<heapSize;i++){
heap[i] = new HeapNode(matrix[i][0],i,0);
max = Math.max(heap[i].value,max);
}
for(int i=heapSize / 2 - 1;i>=0;i--){
modifyHeap(heap,i,heapSize);
}
int min = heap[0].value;
int res = max - min;
int tempMax = max;
int tempMin = min;
while(heap[0].index < matrix[heap[0].arrNum].length){
if(heap[0].index == matrix[heap[0].arrNum].length-1){
System.out.println("最小范围为：" + tempMin + ":" + tempMax);
break;
}
heap[0].value = matrix[heap[0].arrNum][++heap[0].index];
if(max<heap[0].value)
max = heap[0].value;
modifyHeap(heap,0,heapSize);
min = heap[0].value;
if(max - min < res){
res = max - min;
tempMax = max;
tempMin = min;
}
}
}
public static void main(String[] args) {
int[][] martix = new int[][]{{1,3,5},{4,8},{2,5}};
new minScope().getMinScope(martix);
}
}
二面
1、介绍DQN的项目
2、数组的全排列（空间复杂度O（1））
数组中有重复元素，所以我们需要一个Set保存已经出现过的排列。因此我先写了一个回溯的方法，可是空间复杂度比较高，面试官说能不能用O（1）的空间复杂度，全排列直接print出来就行。即我们不需要保存已经出现过什么排列。这需要对数组先进性排序：
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums==null || nums.length==0) return res;
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
backtracking(nums,used,new ArrayList<Integer>(),res);
return res;
}
public static void backtracking(int[] nums,boolean[] used,ArrayList<Integer> arr,List<List<Integer>> res){
if(arr.size() == nums.length)
res.add(new ArrayList<Integer>(arr));
else{
for(int i=0;i<nums.length;i++){
if(used[i]) continue;
if(i>0 && nums[i-1]==nums[i] && used[i-1]) continue;
used[i] = true;
arr.add(nums[i]);
backtracking(nums,used,arr,res);
arr.remove(arr.size()-1);
used[i] = false;
}
}
}
}
3、两堆钞票，尽可能均分（利用背包问题的思想）
想了半天，写出来一个深度优先搜索的算法。面试官提示我可以考虑从背包问题的角度出发，但最后也没想出来。
背包问题的思路，参考我们之前写过的文章：https://www.jianshu.com/p/25f4a183ede5
package ByteDance;
public class Package {
private final int MIN = Integer.MIN_VALUE;
public void test() {
int[] w = {3, 2, 2};
int[] v = {5, 10, 20};
knapsackOptimal(5, w, v);
}
/**
* 01背包-容量压缩
*
* @param c 包容量
* @param weight 各物品质量
* @param value 各物品价值
*/
public void knapsackOptimal(int c, int[] weight, int[] value) {
int n = weight.length; //物品数量
int[] w = new int[n + 1];
int[] v = new int[n + 1];
int[][] G = new int[n + 1][c + 1];
for (int i = 1; i < n + 1; i++) {
w[i] = weight[i - 1];
v[i] = value[i - 1];
}
//初始化values[0...c]=0————在不超过背包容量的情况下，最多能获得多少价值
//原因：如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了
int[] values = new int[c + 1];
//初始化values[0]=0，其它全为负无穷————解决在恰好装满背包的情况下，最多能获得多少价值的问题
//原因：只有容量为0的背包可以什么物品都不装就能装满，此时价值为0，其它容量背包均无合法的解，属于未定义的状态，应该被赋值为负无穷
/*for (int i = 1; i < values.length; i++) {
values[i] = MIN;
}*/
for (int i = 1; i < n + 1; i++) {
for (int t = c; t >= w[i]; t--) {
if (values[t] < values[t - w[i]] + v[i]) {
values[t] = values[t - w[i]] + v[i];
G[i][t] = 1;
}
}
}
System.out.println("最大价值为： " + values[c]);
System.out.print("装入背包的物品编号为： ");
/*
输出顺序:逆序输出物品编号
注意：这里另外开辟数组G[i][v],标记上一个状态的位置
G[i][v] = 1:表示物品i放入背包了，上一状态为G[i - 1][v - w[i]]
G[i][v] = 0:表示物品i没有放入背包，上一状态为G[i - 1][v]
*/
int i = n;
int j = c;
while (i > 0) {
if (G[i][j] == 1) {
System.out.print(i + " ");
j -= w[i];
}
i--;
}
}
}
三面：
1、无向无环图中，最短路径的最大值（O(n^3)的解法)
这里考察的其实就是Floyd算法。哎，只可惜自己当时没有复习图的相关算法，完全不会写呀。
算法思想原理：Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
public class Floyd {
int[][] Matrix;
char[] Nodes;
private final int INF = Integer.MAX_VALUE;
public Floyd(char[] Nodes, int[][] Matrix){
this.Nodes = Nodes;
this.Matrix = Matrix;
}
public void floyd(){
int[][] distance = new int[Nodes.length][Nodes.length];
// 初始化距离矩阵
for(int i=0; i<Nodes.length; i++){
for(int j=0; j<Nodes.length; j++){
distance[i][j] = Matrix[i][j];
}
}
//循环更新矩阵的值
for(int k=0; k<Nodes.length; k++){
for(int i=0; i<Nodes.length; i++){
for(int j=0; j<Nodes.length; j++){
int temp = (distance[i][k] == INF || distance[k][j] == INF) ? INF : distance[i][k] + distance[k][j];
if(distance[i][j] > temp){
distance[i][j] = temp;
}
}
}
}
// 打印floyd最短路径的结果
System.out.printf("floyd: \n");
for (int i = 0; i < Nodes.length; i++) {
for (int j = 0; j < Nodes.length; j++)
System.out.printf("%12d ", distance[i][j]);
System.out.printf("\n");
}
}
2、LSTM的公式
3、RNN为什么出现梯度消失
4、BPTT的推导。
