这是一份去年的今日头条算法工程师秋招面试题，用了同学的白金内推码，所以直接进入了面试，全程都在写题！机械学习的问题很是少！想进头条的童鞋赶快来看看！一面： 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/25f4a183ede5package 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的推导。

私信我或关注猿来如此呀民众号，回复：视频学习，免费领取30天学习资源包。

本文来源：爱游戏体育-www.capitanbollito.com