2022携程暑期实习后端开发二面面经

2022年3月25日13点30-14点10

没有自我介绍

上来直接问你对后端开发的研究有哪些？

我结合自己做的项目，从JavaWeb讲到了SpringBoot

接下来就做面试官出的算法题

public class Main {


    public static void main(String[] args) {

        Flight f1 = new Flight("F001", "SHA", "HKG");
        Flight f2= new Flight("F002", "SHA", "TYO");
        Flight f3 = new Flight("F003", "HKG", "NYC");
        Flight f4 = new Flight("F004", "TYO", "NYC");
        Flight f5 = new Flight("F005", "HKG", "TYO");
        Flight f6 = new Flight("F006", "TYO", "HKG");
        Flight f7 = new Flight("F007", "TYO", "OSA");
        Flight f8 = new Flight("F008", "OSA", "NYC");
        Flight f9 = new Flight("F009", "SHA", "OSA");

    }



    static class Flight{
        String flightId;
        String depart;
        String arrival;

        Flight (String id, String start, String end) {
            this.flightId = id;
            this.depart = start;
            this.arrival = end;
        }
    }
    
}

以上代码是面试官聊天框里发过来的题目：要求飞机从上海飞到纽约的所有路径

我的想法是：这是一道图论算法题，采用dfs就行了

由于这是一道应用题，不像力扣牛客那样直接秒就行了，还需要处理一下数据

我一开始光讲，面试官建议我画一下，我就用画图演示了一下，表示需要将数据转换成邻接表的形式

因为Java处理字符串比较麻烦，所以我想用数字代替字符串，其实是一样的，面试官同意了

以下是我的解题代码

public class Main {

    static List<List<Integer>> res=new LinkedList<>();
    static LinkedList<Integer> path=new LinkedList<>();

    public static void main(String[] args) {

        Flight f1 = new Flight("F001", 0, 1);
        Flight f2= new Flight("F002", 0, 2);
        Flight f3 = new Flight("F003", 1, 4);
        Flight f4 = new Flight("F004", 2, 4);
        Flight f5 = new Flight("F005", 1, 2);
        Flight f6 = new Flight("F006", 2, 1);
        Flight f7 = new Flight("F007", 2, 3);
        Flight f8 = new Flight("F008", 3, 4);
        Flight f9 = new Flight("F009", 0, 3);
        int[][] graph=new int[][]{{1,2,3},{2,4},{1,3,4},{3,4},{}};
        boolean[] vis=new boolean[5];
        dfs(graph,0,4,vis);
        for(List<Integer> a:res){
            for (int b:a){
                System.out.print(b);
            }
            System.out.println();
        }
    }

    static class Flight{
        String flightId;
        Integer depart;
        Integer arrival;

        Flight (String id, Integer start, Integer end) {
            this.flightId = id;
            this.depart = start;
            this.arrival = end;
        }
    }

    public static void dfs(int[][] graph,int cur,int end,boolean[] vis){
        if (vis[cur]==true)return;
        path.add(cur);
        vis[cur]=true;
        if (cur==end){
            res.add(new LinkedList<>(path));
            vis[cur]=false;
            path.removeLast();
            return;
        }
        for (int a:graph[cur]){
            dfs(graph,a,end,vis);
        }
        vis[cur]=false;
        path.removeLast();
    }

}

最后反问

结束

#携程##实习##后端开发##面经#