Docker Build Order

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.

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"}}
Ouput: 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, -1 unsuccessful.

shared_prt, 这题也练了shared pointer，用法是：

vector<string> result = {"a", "b"};
shared_ptr<vector<string>> sh_ptr = make_shared<vector<string>>(result);
for(auto& e: *sh_ptr){
    cout<<e<<' ';
}

Code:

#include <iostream>
#include <vector>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <climits>
#include <utility>
#include "../array_utils.h"
using namespace std;
int DFS(unordered_map<string, string>& dict, unordered_map<string, int>& status, string word, vector<string>& result);

shared_ptr<vector<string>> serialize_build_order(
    const vector<pair<string, string>>& relations) {

    vector<string> result;
    int n=relations.size();

    unordered_map<string, string> dict;
    unordered_map<string, int> status;
    for(auto e: relations){
        dict[e.first]=e.second; // Set the dictionary
        status[e.first]=0;  // initialize the status table
    }


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

    for(int i=0; i<n; i++){
        if(status[relations[i].first]==0){
            DFS(dict, status, relations[i].first, result);
            // cout<<relations[i].first<<' ';
        }
    }

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

    shared_ptr<vector<string>> sh_ptr = make_shared<vector<string>>(result);

    return sh_ptr;
}

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<<endl;
    if(status[word]!=0) return status[word];

    if(dict.find(word)==dict.end()){
        status[word]=1; // 到头了，没有dependency，可以build，并且返回
        return 1;
    }

    status[word]=-1;

    string next = dict[word];
    int flag = DFS(dict, status, next, result);
    if(flag==1){
        status[word]=1; // 可以build，change status，并且return 可以
        result.push_back(word);
    }

    return flag;
}


int main(){

    // vector<pair<string, string>> input={{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}};
    // vector<pair<string, string>> input={{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}};
    vector<pair<string, string>> input={{"a", "b"}, {"b", "c"}, {"c", "d"}, {"d", "e"}, {"e","c"}, {"f", "g"}};
    vector<string> result;

    shared_ptr<vector<string>> result;

    result = serialize_build_order(input);

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

}