滴滴：2019校招安全研發(fā)工程師一二面

一面

就一個算法編程題，沒有其他問題。

題面：

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].

中文大意：

給定整數(shù) $n$ ，以及 $n$ 個二元組 $[x,y]$ ，表示 $x$ 的前置條件是 $y$ ，即要先完成 $y$ 才能完成 $x$ 。

要求輸出任意一個合法的順序。沒有前置條件的，出現(xiàn)在任意位置都是合法的。

面試官補充：當(dāng)出現(xiàn)環(huán)的時候，輸出空（啥也不輸出）。

思路：

拓?fù)渑判?，可考慮使用DFS或者BFS進行實現(xiàn)。

因為只有題面，面試的平臺并不具備OJ功能，所以簡單化一下輸入，會在n后面輸入m表示二元組的數(shù)量。

代碼：

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();   // 直接假設(shè)有m個二元關(guān)系組
        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]);
            }
        }

    }
}

二面

項目相關(guān)問題
數(shù)據(jù)結(jié)構(gòu)中“樹結(jié)構(gòu)”常用來干嘛

主要是用作索引，但也可用來存儲數(shù)據(jù)。
說一說你知道的樹結(jié)構(gòu)

紅黑樹、B+樹、線段樹、平衡二叉樹。
簡單介紹一下紅黑樹

紅黑樹中節(jié)點有紅黑兩種顏色，并需要滿足一些約束：
1. 不能有兩個連續(xù)的紅色節(jié)點。
2. 根是黑色。
3. 從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。
4. 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。
紅黑樹和二叉樹的關(guān)系異同

紅黑樹是二叉樹的一種，屬于包含關(guān)系。相比于簡單的二叉樹，紅黑樹具有自平衡的特性，在對節(jié)點進行增刪改操作時，會自動調(diào)整樹結(jié)構(gòu)以滿足約束，整體結(jié)構(gòu)和操作較為復(fù)雜，但各種操作有較好的時間復(fù)雜度。
文件系統(tǒng)中用到的樹結(jié)構(gòu)具體是怎么樣的

B+樹。
介紹一下B+樹

B+樹是一種典型的用于索引的二叉樹，如用作MySQL的索引。其主要特點為：
1. 每個節(jié)點中存有多條數(shù)據(jù)（多叉樹）。
2. 非葉子節(jié)點只保存其子節(jié)點的指針，葉子節(jié)點保存數(shù)據(jù)。
3. 葉子節(jié)點之間會如同鏈表相互連接。
介紹一下死鎖

死鎖描述的是一種：多個進程之間互相占有其他進程所必需的資源，且一直處于等待其他進程釋放，最終導(dǎo)致所有線程無線等待下去的現(xiàn)象。
怎么避免死鎖

破壞死鎖的四個條件中一個或多個：
1. 循環(huán)等待：存在資源的循環(huán)等待鏈。
  
  破壞：順序資源分配。
2. 不可剝奪：一個進程資源未使用完之前，不能被其他進程程奪走。
  
  破壞：強行釋放一些進程的資源（但反復(fù)申請和釋放資源可能導(dǎo)致性能問題）。
3. 請求和保持：即想要其他資源，有保持已獲得資源不釋放。
  
  破壞：進程所需的資源一次性申請完，而不是邊用邊申請。
4. 互斥：一個資源只能同時被一個進程使用
  
  破壞：允許資源共享使用（大部分情況下不太可行）。

感受、總結(jié)

感受

面試的部門是國際化的部門，有一部分的外國同事，所以面試中與面試官交談、提問時，都會涉及到一些英文，而不是完全中文的面試，但用到英文詞匯都比較簡單，屬于基本的口語和基本的專業(yè)詞匯，并無大礙。

一面整體流程很簡單，就一個英文題面的算法題，給出dfs的解法后，面試官也順口提了一句還有bfs的解法，就結(jié)束了。

二面時面試官對項目問的比較深入，占了一定的篇幅，除了問項目的技術(shù)框架外，還問了一些諸如“項目過程中印象最深最有趣的事”、“對于攝影的了解在項目中發(fā)揮什么作用”（有一個攝影相關(guān)的項目）這樣的問題，感覺考察的是自身更為內(nèi)在的想法與對于項目整體的把控、投入與思考。與項目無關(guān)的問題則是一些比較基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)題，屬于必須掌握的內(nèi)容。

整體兩輪面試的時間都不長，考察的專業(yè)知識面較廣（項目、算法、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)），但整體難度不算很難，中英結(jié)合，對于個人的考察非常綜合。兩輪面試，面試官均對個人的簡歷、學(xué)習(xí)方向給出了一些建議，非常友好的面試體驗。

總結(jié)

深入學(xué)習(xí)。

自己的很多知識面深度有待提高，需要更加深入的去進行一個學(xué)習(xí)（面試官的建議）。
簡歷優(yōu)化。

簡歷上的薪資會取決于個人能力、公司、工作地區(qū)、崗位等諸多因素，并無定值，如果拿捏不準(zhǔn)，可以不寫（面試官建議+2）。
對于英語口語、專業(yè)詞匯的積累也有待提高。

雖然這一次面試中沒有在這上面栽跟頭，自己的英語水平如何自己心里也清楚??，今后也肯定會有相應(yīng)的應(yīng)用場景，是有這個必要的。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

滴滴：2019校招安全研發(fā)工程師一二面