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 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<<' ';
}

}
``````