Drive.AI SDE OA两题

说一下他家的OA，两题， 两小时time limit。
第一题简单, merge two sorted array, in place.
第二题有些难，类似topological sort,但又不一样。

# 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

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

uot;c", "d"}, {"a", "b"}, {"d", "e"}, {"e","c"}, {"f", "g"}}
Ouput: f
```

请问楼主可不可以用Java

1. class Solution482 {
   
2. public:
   
3.     vector<string> detectCycle(vector<vector<string>>& image) {
   
4.         if (image.empty()) {
   
5.             return {};
   
6.         }
   
7.         unordered_map<string, bool> available;
   
8.         vector<string> output;
   
9.         unordered_map<string, vector<string>> graph;
   
10.         buildGraph(image, graph);
    
11.         int leng=graph.size();
    
12.         unordered_map<string, bool> visited;
    
13.         unordered_map<string, bool> recStack;
    
14.         for (auto it = graph.begin(); it != graph.end(); ++it) {
    
15.             //case 1:not visited
    
16.             visited[it->first]=false;
    
17.             recStack[it->first]=false;
    
18.         }
    
19.         for (auto it = graph.begin(); it != graph.end(); ++it) {
    
20.             if (recStack[it->first]==true) {
    
21.                 continue;
    
22.             }
    
23.             if (!isCyclicHelper(it->first, graph, visited, recStack)) {
    
24.                 available[it->first]=true;
    
25.             }
    
26.         }
    
27.         topoSort(graph, available, output);
    
28.         return output;
    
29.     }
    
30.     void test() {
    
31.         vector<vector<string>> graph;
    
32.         vector<string> result;
    
33.         graph={{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}};
    
34.         result=detectCycle(graph);
    
35.         //Output: ubuntu, master, numpy, tensorflow
    
36.         for (auto i : result) {
    
37.             cout<<i<<" ";
    
38.         }
    
39.         cout<<endl;
    
40.         graph={{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}};
    
41.         result=detectCycle(graph);
    
42.         //Output: ubuntu, tensorflow
    
43.         for (auto i : result) {
    
44.             cout<<i<<" ";
    
45.         }
    
46.         cout<<endl;
    
47.         graph={{"b", "c"}, {"c", "d"}, {"a", "b"}, {"d", "e"}, {"e","c"}, {"f", "g"}};
    
48.         result=detectCycle(graph);
    
49.         //Ouput: g, f
    
50.         for (auto i : result) {
    
51.             cout<<i<<" ";
    
52.         }
    
53.         cout<<endl;
    
54.     }
    
55. private:
    
56.     void topoSort(unordered_map<string, vector<string>> graph, unordered_map<string, bool>& available, vector<string>& result) {
    
57.         unordered_map<string, int> state;
    
58.         for (auto it = graph.begin(); it != graph.end(); ++it) {
    
59.             state[it->first]=0;
    
60.         }
    
61.         for (auto it = graph.begin(); it != graph.end(); ++it) {
    
62.             if (available[it->first]==true) {
    
63.                 visit(graph, it->first, result, state);
    
64.             }
    
65.         }
    
66.         return;
    
67.     }
    
68.    
    
69.     void visit(unordered_map<string, vector<string>>& image,
    
70.                string it,
    
71.                vector<string>& list,
    
72.                unordered_map<string, int>& state) {
    
73.         if (state[it]==3) {
    
74.             return;
    
75.         }
    
76.         if (state[it]==2) {
    
77.             return;
    
78.         }
    
79.         state[it]=2;
    
80.         for (auto neib:image[it]) {
    
81.             visit(image, neib, list, state);
    
82.         }
    
83.         state[it]=3;
    
84.         list.push_back(it);
    
85.     }
    
86.                
    
87.     void buildGraph(vector<vector<string>>& image, unordered_map<string, vector<string>>& graph) {
    
88.         for (int i=0; i<image.size(); i++) {
    
89.             graph[image[i][0]].push_back(image[i][1]);
    
90.         }
    
91.     }
    
92.    
    
93.     bool isCyclicHelper(string v, unordered_map<string, vector<string>>& graph, unordered_map<string, bool>& visited, unordered_map<string, bool>& recStack) {
    
94.         if (visited[v]==false) {
    
95.             visited[v]=true;
    
96.             recStack[v]=true;
    
97.             for (auto it=graph[v].begin(); it!=graph[v].end(); ++it) {
    
98.                 if (!visited[*it] && isCyclicHelper(*it, graph, visited, recStack)) {
    
99.                     return true;
    
100.                 }
     
101.                 else if (recStack[*it]==true) {
     
102.                     return true;
     
103.                 }
     
104.             }
     
105.         }
     
106.         recStack[v]=false;
     
107.         return false;
     
108.     }
     
109. };
     
110. 这里的E1 为什么不输出ubuntu, E2 也是， E3 为什么不输出g呢
     

复制代码

所以就是说，一个图里面的第一个元素都不用放在结果里对吗？

chaohubian 发表于 2017-8-26 03:35

层主可以解释一下那三个状态吗？