Docker Build Order II

Interview

Description:

In Docker, building an image has dependencies. An image can only be built once its dependency is built (If the dependency is from outside, then the image can be built immediately).

Sometimes, engineers make mistakes by forming a cycle dependency of local images. In this case, ignore the cycle and all the images depending on this cycle.

这个地方我看错了，我理解成cycle不能build，但是depend于cycle的image可以build。

Input is vector of pair of images (image, its dependency).

Output the order of images to be built in order.

Example:

Example 1:
{{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}}
Output: master, numpy, tensorflow

Example 2:
{{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}}
Output: tensorflow

Example 3:
{{"b", "c"}, {"c", "d"}, {"a", "b"}, {"d", "e"}, {"e","c"}, {"f", "g"}}
"c->d->e->c" is a cycle
Ouput: b a f

Idea:

用DFS加上DP，DP用hashtable记录。dependency用hashtable来记录成dictionary。

这个其实不算太难，但我理解错了，以为cycle不能build，但是dependend于cycle的image可以build，这个见Docker Build Order II.

DFS return int代表状态，同时改变status table。

status table: 0代表unvisited， -1代表正在visit， 1代表成功 （3代表是cycle，这个II里用到)。

DFS return value: 1 successful, 3 cycle

如果上一步return 3， check status table， if 3, return 1, if -1, return 3 and change the table status to 3.

if last step return 1, return 1, change status table to 1.

Code:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>
using namespace std;



int DFS(unordered_map<string, string>& dict, unordered_map<string, int>& status, string word, vector<string>& result){
    // for(auto e: status){
    //     cout<<e.first<<"->"<<e.second<<' ';
    // }
    // cout<<'\n';

    if(status[word]==1) return 1;
    if(status[word]==3) return 1;
    if(status[word]==-1){
        status[word]=3;
        return 3;
    }
    if(dict.find(word)==dict.end()){
        status[word]=1;
        return 1;
    }

    status[word]=-1;
    int flag = DFS(dict, status, dict[word], result);
    if(flag==1){
        status[word]=1;
        result.push_back(word);
// cout<<"**** ";
// for(auto e: status){
//     cout<<e.first<<"->"<<e.second<<' ';
// }
// cout<<'\n';
        return 1;
    }
    else if(flag==3){
        if(status[word]==3){
// cout<<"**** ";
// for(auto e: status){
//     cout<<e.first<<"->"<<e.second<<' ';
// }
// cout<<'\n';
            return 1;
        }
        else if(status[word]==-1){
            status[word]=3;
// cout<<"**** ";
// for(auto e: status){
//     cout<<e.first<<"->"<<e.second<<' ';
// }
// cout<<'\n';
            return 3;
        }

    }
    else cout<<"ERROR!"<<endl; // Won't research this step!

    // cout<<"**** ";
    // for(auto e: status){
    //     cout<<e.first<<"->"<<e.second<<' ';
    // }
    // cout<<'\n';
}

vector<string> printOrder(vector<pair<string, string>> & input){
    unordered_map<string, string> dict;
    unordered_map<string, int> status;
    for(auto e: input){
        dict[e.first]=e.second;
        status[e.first]=0;
    }
    vector<string> result;

    for(auto e: input){
        if(status[e.first]==0){
            DFS(dict, status, e.first, result);
        }
    }
    return result;
}

int main(){
    vector<pair<string, string>> input={{"c","d"}, {"b","c"}, {"d","e"}, {"e","b"}, {"a","b"}, {"f","g"}, {"g","h"}};

    vector<string> result;
    result = printOrder(input);

    for(auto e: result){
        cout<<e<<' ';
    }

}