24届参加社招：幂律科技一面

全程三道算法（不问任何八股、实习和项目），用自己的环境上机写，共享屏幕面试官看着写

面试官鼓励我截图他们的题目，让我面试结束后再自己研究一下，不属于恶意泄露。

1.就是判断两个数组的重复出现问题，我是用Hash判断去重的思路。

代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        int [] arr = {5,3,1,5,4};
        int [] brr = {5,3};

        System.out.println(getIndex(arr,brr));
    }

    private static List<Integer> getIndex(int[] arr, int[] brr) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i =0;i<brr.length;i++){
            map.put(brr[i],i);
        }
        List<Integer> res = new ArrayList<>();
        for(int i=0;i<arr.length;i++){
            if(map.containsKey(arr[i])){
                res.add(i);
            }
        }
        return res;
    }
}

2.就是个规定的Node类，两个元素分别是ID和父ID，创建几个Node对象，利用两个元素确定了他们的链接关系，是个树结构，根节点的父ID是“-1”。得出所有的路径，比如A是根节点，子节点是A-1，A-1的子节点是A-1-1，以/A/A-1/A-1-1/的格式返回。

代码：

import java.util.ArrayList;
import java.util.List;

public class ShowMeBug {
    public static void main(String[] args) {
        List<Node> nodes = new ArrayList<>();
        nodes.add(new Node("A","-1"));
        nodes.add(new Node("A-1","A"));
        nodes.add(new Node("A-2","A"));
        nodes.add(new Node("A-3","A"));
        nodes.add(new Node("A-2-1","A-2"));
        nodes.add(new Node("A-2-2","A-2"));
        nodes.add(new Node("A-2-3","A-2"));
        nodes.add(new Node("A-2-4","A-2"));
        System.out.println(nodes);

        // 打印所有路径
        printAllPaths(nodes);
    }

    private static void printAllPaths(List<Node> nodes) {
        for (Node node : nodes) {
            String path = buildPath(nodes,node,"");
            if(!path.isEmpty()){
                System.out.println(path);
            }
        }
    }

    private static String buildPath(List<Node> nodes,Node node, String currentPath) {
        String newPath = node.ID +(currentPath.isEmpty()?"" : "/") +currentPath;
        if(node.PID.equals("-1")){
            newPath = "/" + newPath + "/";
        }
        if(node.PID == "-1") {
            return newPath;
        }else{
            for (Node n : nodes) {
                if(n.ID.equals(node.PID)) {
                    return buildPath(nodes,n,newPath);
                }
            }
        }
        return "";
    }


static class Node {
    Node(String ID, String PID) {
        this.ID = ID;
        this.PID = PID;
    }

    public String ID;
    public String PID;

    @Override
    public String toString() {
        return "Node{" +
                "ID='" + ID + '\'' +
                ", PID='" + PID + '\'' +
                '}';
    }
}
}

3.路径对小的问题。我是采用的dp方法，设置dp【i】【j】为当前行，列的最优解，然后再在最后一列选一个最小的就是解。

代码：

import java.util.List;

public class DPMain {
    public static void main(String[] args) {
        int [][] matrix = new int[][] {
                {5,8,1,2},
                {4,1,7,4},
                {3,6,2,9}
        };

        System.out.println(dp(matrix));
    }

    private static int dp(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return  0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;

        int [][] dp = new int[rows][cols];

        // 初始化第一行
        for(int j =0;j < cols;j++){
            dp[0][j] = matrix[0][j];
        }

        // 填充剩下的行
        for(int i = 1;i<rows;i++){
            for(int j = 0;j<cols;j++){
                int min = Integer.MAX_VALUE;
                if(j > 0){
                    min = Math.min(min,dp[i-1][j-1]);
                }
                if(j<cols-1){
                    min = Math.min(min,dp[i-1][j+1]);
                }
                min = Math.min(min,dp[i-1][j]);
                dp[i][j] = matrix[i][j] + min;
            }
        }
        int min  = Integer.MAX_VALUE;
        for(int j = 0;j<cols;j++){
            min = Math.min(min,dp[rows-1][j]);
        }
        return min;
    }
}