滴滴：2019校招 安全研发工程师 一二面

一面

就一个算法编程题，没有其他问题。

题面：

There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

---

Input: 2, [[1,0]]

Output: [0,1]

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .

---

Input: 4, [[1,0],[2,0],[3,1],[3,2]]

Output: [0,1,2,3] or [0,2,1,3]

Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

中文大意：

给定整数，以及个二元组，表示的前置条件是，即要先完成才能完成。

要求输出任意一个合法的顺序。没有前置条件的，出现在任意位置都是合法的。

面试官补充：当出现环的时候，输出空（啥也不输出）。

思路：

拓扑排序，可考虑使用DFS或者BFS进行实现。

因为只有题面，面试的平台并不具备OJ功能，所以简单化一下输入，会在n后面输入m表示二元组的数量。

代码：

import java.util.*;

public class Main {
    static Scanner in = new Scanner(System.in);
    static int MAXN = 1000;
    static int n, m;
    static ArrayList<Integer>[] G = new ArrayList[MAXN];
    static int[] order = new int[MAXN];
    static Integer[] nums = new Integer[MAXN];
    static boolean loop = false;
    static boolean[] vis = new boolean[MAXN];
    static boolean[] path_vis = new boolean[MAXN];
    public static void init() {
        for (int i = 0; i < MAXN; i++) {
            G[i] = new ArrayList<Integer>();
            nums[i] = i;
        }
        Arrays.fill(order, 0);
        Arrays.fill(vis, false);
        Arrays.fill(path_vis, false);
    }

    public static void addEdge(int u, int v) {
        G[u].add(v);
    }

    static void dfs(int u, int or) {
        if (path_vis[u]) {
            loop = true;
            return;
        }
        order[u] = Math.max(order[u], or + 1);
        vis[u] = true;
        path_vis[u] = true;
        for (int v : G[u]) {
            if (loop) return;
            dfs(v, order[u] + 1);
        }
        path_vis[u] = false;
    }

    public static void main(String[] args) {
        init();
        n = in.nextInt();
        m = in.nextInt();   // 直接假设有m个二元关系组
        for (int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            addEdge(b, a);
        }
        for (int i = 0; i < n && !loop; i++) {
            if (!vis[i]) {
                dfs(i, 0);
            }
        }
        if (loop)
            System.out.println();
        else {
            Arrays.sort(nums, 0, n, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return order[o1] - order[o2];
                }
            });
            for (int i = 0; i < n; i++) {
                System.out.println(nums[i]);
            }
        }

    }
}

二面

• 项目相关问题

  ---

• 数据结构中“树结构”常用来干嘛

  主要是用作索引，但也可用来存储数据。

• 说一说你知道的树结构

  红黑树、B+树、线段树、平衡二叉树。

• 简单介绍一下红黑树

  红黑树中节点有红黑两种颜色，并需要满足一些约束：

  1. 不能有两个连续的红色节点。
  2. 根是黑色 。
  3. 从每个叶子到根的所有路径上不能有两个连续的红色节点 。
  4. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点 。

• 红黑树和二叉树的关系异同

  红黑树是二叉树的一种，属于包含关系。相比于简单的二叉树，红黑树具有自平衡的特性，在对节点进行增删改操作时，会自动调整树结构以满足约束，整体结构和操作较为复杂，但各种操作有较好的时间复杂度。

• 文件系统中用到的树结构具体是怎么样的

  B+树。

• 介绍一下B+树

  B+树是一种典型的用于索引的二叉树，如用作MySQL的索引。其主要特点为：

  1. 每个节点中存有多条数据（多叉树）。
  2. 非叶子节点只保存其子节点的指针，叶子节点保存数据。
  3. 叶子节点之间会如同链表相互连接。

• 介绍一下死锁

  死锁描述的是一种：多个进程之间互相占有其他进程所必需的资源，且一直处于等待其他进程释放，最终导致所有线程无线等待下去的现象。

• 怎么避免死锁

  破坏死锁的四个条件中一个或多个：

  1. 循环等待：存在资源的循环等待链。

     破坏：顺序资源分配。

  2. 不可剥夺：一个进程资源未使用完之前，不能被其他进程程夺走。

     破坏：强行释放一些进程的资源（但反复申请和释放资源可能导致性能问题）。

  3. 请求和保持：即想要其他资源，有保持已获得资源不释放。

     破坏：进程所需的资源一次性申请完，而不是边用边申请。

  4. 互斥：一个资源只能同时被一个进程使用

     破坏：允许资源共享使用（大部分情况下不太可行）。

感受、总结

感受

面试的部门是国际化的部门，有一部分的外国同事，所以面试中与面试官交谈、提问时，都会涉及到一些英文，而不是完全中文的面试，但用到英文词汇都比较简单，属于基本的口语和基本的专业词汇，并无大碍。

一面整体流程很简单，就一个英文题面的算法题，给出dfs的解法后，面试官也顺口提了一句还有bfs的解法，就结束了。

二面时面试官对项目问的比较深入，占了一定的篇幅，除了问项目的技术框架外，还问了一些诸如“项目过程中印象最深最有趣的事”、“对于摄影的了解在项目中发挥什么作用”（有一个摄影相关的项目）这样的问题，感觉考察的是自身更为内在的想法与对于项目整体的把控、投入与思考。与项目无关的问题则是一些比较基础的数据结构和操作系统题，属于必须掌握的内容。

整体两轮面试的时间都不长，考察的专业知识面较广（项目、算法、数据结构、操作系统），但整体难度不算很难，中英结合，对于个人的考察非常综合。两轮面试，面试官均对个人的简历、学习方向给出了一些建议，非常友好的面试体验。

总结

• 深入学习。

  自己的很多知识面深度有待提高，需要更加深入的去进行一个学习（面试官的建议）。

• 简历优化。

  简历上的薪资会取决于个人能力、公司、工作地区、岗位等诸多因素，并无定值，如果拿捏不准，可以不写（面试官建议+2）。

• 对于英语口语、专业词汇的积累也有待提高。

  虽然这一次面试中没有在这上面栽跟头，自己的英语水平如何自己心里也清楚😂，今后也肯定会有相应的应用场景，是有这个必要的。