摘要：給出了這個(gè)例子還給出了實(shí)際情況中，這種多線程可能出現(xiàn)的場(chǎng)景。文章的發(fā)布時(shí)間應(yīng)該是有記錄的，那么至少現(xiàn)在這個(gè)時(shí)候我還基本處于完全不懂操作系統(tǒng)的狀態(tài)，多線程也只是的看了幾個(gè)視頻。

首先，這是一篇馬后炮。這題在面試過程中，面試官首先提到了操作系統(tǒng)，多線程操作什么的。然后現(xiàn)在給定線程只有一個(gè)，任務(wù)有f1，f2.。。可能多個(gè)，打出各個(gè)任務(wù)執(zhí)行的時(shí)間。
給出了這個(gè)例子：

input:
funcName, isStart, timestamp(long)
f1 start 1
f2 start 3
f1 start 7
f1 end 8
f2 end 13
f1 end 22

output:
f1 : [[1, 3],[7,8], [13,22]]
f2 : [[3, 7], [8,13]]

還給出了實(shí)際情況中，這種多線程可能出現(xiàn)的場(chǎng)景。比如這樣：

void f1() {
    // record the func start time
    if (some_condition) {
        f2();
    }
    // record the func end time
}

void f2() {
    // record the func start time
    if (some_condition) {
        f1();
    }
    // record the func end time
}

main() {
    f1();
}

然后要求是寫個(gè)function，給定了輸入，把輸出弄出來。

這題其實(shí)背后應(yīng)該有操作系統(tǒng)的基礎(chǔ)知識(shí)支撐。文章的發(fā)布時(shí)間應(yīng)該是有記錄的，那么至少現(xiàn)在這個(gè)時(shí)候我還基本處于完全不懂操作系統(tǒng)的狀態(tài)，多線程也只是Java的看了幾個(gè)視頻。既然是馬后炮，直接給出我的解決想法，就是用stack來做，每次任務(wù)來的時(shí)候，判斷當(dāng)前要執(zhí)行的任務(wù)，打斷了之前的哪些任務(wù)。同時(shí)做的時(shí)候發(fā)現(xiàn)需要一個(gè)變量來記錄上一次有任務(wù)變更的時(shí)間。背后的原理總感覺只隔了一層紙，但是現(xiàn)在只能按照刷題的思路去解決它。

import java.util.*;
//首先建一個(gè)File類，表示任務(wù)，id表示它的名字。
class File {
    String id;
    Boolean isStart;
    Long timestamp;
    public File(String name, Boolean isStart, Long timestamp){
        id = name;
        this.isStart = isStart;
        this.timestamp = timestamp;
    }
}
// Slot類表示時(shí)間區(qū)間。
class Slot {
    Long start;
    Long end;
    public Slot(Long start, Long end){
        this.start = start;
        this.end = end;
    }
}
// stack里面，要么是f2進(jìn)來，里面f1在跑，要么是f2進(jìn)來，里面f2在跑。這個(gè)分配必須要思考清楚。
// 補(bǔ)充一個(gè)，f2進(jìn)來，f2在跑的情況，中間是會(huì)被打斷的，比如f2-f1-f1-f2，所以要記錄一個(gè)prevTime，因?yàn)樽铋_始f2帶的timestamp沒用了。
class ParseLog{
    public void parseLog(List files){
        // 注意了，我開始注意命名規(guī)則了，這個(gè)map是為了最后輸出用。
        Map> fileMap = new HashMap<>();
        // 我當(dāng)時(shí)還是現(xiàn)查的Long類型需要加個(gè)L。
        Long prevTime = 0L;
        Stack fileStack = new Stack<>();
        // 從這里開搞，每次拿一個(gè)file進(jìn)去。
        for (int i = 0; i < files.size(); i++) {
            File curF = files.get(i);
            // 空stack那就往里壓。
            if (fileStack.isEmpty()) {
                fileStack.push(curF);
            }
            else {
                // 先把stack頂?shù)膄ile命名一下，后面方便辦事。
                File topF = fileStack.peek();
                // 這種就是f2進(jìn)來，發(fā)現(xiàn)上面也是個(gè)f2
                if (curF.id.equals(topF.id)) {
                    // 這時(shí)候f2必須是帶著結(jié)束屬性來的。
                    if (!curF.isStart) {
                        Long endTs = curF.timestamp;
                        List temp = new ArrayList<>();
                        if (fileMap.containsKey(curF.id)) {
                            temp = fileMap.get(curF.id);
                        }
                        // 這時(shí)候，prevTime的作用就顯示出來了。
                        temp.add(new Slot(prevTime, endTs));
                        fileMap.put(curF.id, temp);
                        // 上面是標(biāo)準(zhǔn)的添加到map的過程，然后把f2起始的那個(gè)file從stack里面刪掉。
                        fileStack.pop();
                    }
                    else {
                        // 這種就是非法情況，那就報(bào)錯(cuò)吧。
                        System.out.println("this task has already started");
                    }
                }
                else {
                    // 這里面是f2進(jìn)來，上一步執(zhí)行的是f1這種情況。
                    if (curF.isStart) {
                        Long endTs = curF.timestamp;
                        // 這時(shí)候需要停掉的是f1，也就是stack頂部的file，因?yàn)橹挥袉尉€程。
                        List temp = new ArrayList<>();
                        if (fileMap.containsKey(topF.id)) {
                            temp = fileMap.get(topF.id);
                        }
                        temp.add(new Slot(prevTime, endTs));
                        fileMap.put(topF.id, temp);
                        // 帶著開始屬性的file必須壓入。
                        fileStack.push(curF);
                    }
                    else {
                        System.out.println("this task hasn"t started yet");
                    }
                }
            }
            // 這里非常關(guān)鍵，就是每次讀完一個(gè)file之后，都要更新這個(gè)時(shí)間。
            prevTime = curF.timestamp;
        }
        // 這里就是擺弄好輸出就行。
        for(String str : fileMap.keySet()){
            System.out.print(str + " : ");
            List list = fileMap.get(str);
            for (Slot s : list) {
                System.out.print("[ " + s.start + " " + s.end + " ] ");
            }
            System.out.println();
        }
    }
    public static void main(String args[]){
        ParseLog test = new ParseLog();
        File f1 = new File("f1", true, 1L);
        File f2 = new File("f2", true, 3L);
        File f3 = new File("f1", true, 7L);
        File f4 = new File("f1", false, 8L);
        File f5 = new File("f2", false, 13L);
        File f6 = new File("f1", false, 22L);

        File[] infoArr = {f1, f2, f3, f4,f5, f6};
        List infos = Arrays.asList(infoArr);
        test.parseLog(infos);
    }
}

這個(gè)其實(shí)沒啥要分析復(fù)雜度的，就是跑一遍。把輸出算上，也就是O(n)。

這道題是面經(jīng)，準(zhǔn)備了23道題，做了22道，唯一一道沒做的題目，結(jié)果就被命中了。準(zhǔn)備不足是這次電面掛掉的主要原因。實(shí)力其實(shí)是足夠的，在沒有操作系統(tǒng)的基礎(chǔ)知識(shí)，加上只給了20分鐘不到的情況下，思路幾乎完全正確，除了忘了加prevTime這個(gè)，這么看好像這題跑不出別的思路了。總之是非常遺憾。
另外也總結(jié)出一個(gè)教訓(xùn)，就是千萬別給面試官直接噴你的機(jī)會(huì)，面試官真的啥人都有，哪怕是和你同齡的中國(guó)人，也是腦子有些問題，直接說背景不行，導(dǎo)致自己心態(tài)不穩(wěn)，發(fā)揮嚴(yán)重失常。下回還是保持平常心，然后別想太多吧。這一篇文字比較正經(jīng)，也是想借這個(gè)機(jī)會(huì)來面對(duì)一下自己失敗的經(jīng)歷吧。