今日头条算法工程师秋招面试题，想进头条的童鞋赶紧来看看!

这是一份去年的今日头条算法工程师秋招面试题，用了同学的白金内推码，所以直接进入了面试，全程都在写题！机器学习的问题非常少！想进头条的童鞋赶紧来看看！

一面：

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的推导。

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