Google Interview Question
Technical Support EngineersCountry: United States
Interview Type: Phone Interview
Here's a DFS approach with time O(N^2) and space O(N^2)
1) define a class Task { public: string name; bool finished; }
2) create auxillary vector<Task> for each task
3)
for each task in auxillary array:
push task on stack<Task&>
if has dependency, push them on stack
- Note: have to check for circular dependency and can have up to N-1 dependency
so space can grow to O(N^2) in worst case
4)
while stack not empty:
pop top
if Task.finished == false:
Task.finished = true
execute(Task)
Consider this as a directed graph and traverse the graph using Breadth First/Depth First. I prefer Breadth first.
- While traversing, create a dictionary to store the count of adjacent vertices to each vertex
adj(a) = 2
adj(b) = 2
adj(c) = 0
adj(d) = 1
- Set prevNode = null
- Get the nodes with minimum value in dictionary and set that as start node -- node c
- Choose the one that includes prevNode or pick one if prevNode == null
- Store it in a list
- Keep on looping and you will get the order
- Print the list
#include <iostream>
#include <map>
using namespace std;
void insertTask(map<char,int>& m, char lowTask, char highTask){
m[highTask] += m[lowTask]+1;
}
map<int,char> toRankedMap(map<char,int> m){
map<int,char> rankedMap;
for(auto it : m){
rankedMap[it.second] = it.first;
}
return rankedMap;
}
int main()
{
map<char,int> tempMap;
insertTask(tempMap,'A','B'); //A <- B
insertTask(tempMap,'A','C'); //A <- C
insertTask(tempMap,'B','C'); //B <- C
insertTask(tempMap,'B','D'); //B <- D
insertTask(tempMap, 'D', 'C'); //D <- C
auto rankedMap = toRankedMap(tempMap);
for(map<int,char>::reverse_iterator rit = rankedMap.rbegin(); rit != rankedMap.rend(); ++rit){
cout << rit->second << " < ";
}
return 0;
}
Output:
C < D < B < A <
Process returned 0 (0x0) execution time : 0.015 s
Press any key to continue.
The way I came up with, you invert the vertices of the graph, and then do a depth first search. I used integers instead of letters, but the point is the same. This is just a dfs with tracking the path, so it should compute in O(log(V +E))
class Graph:
def __init__(self, V):
self.V = V
self.graph = defaultdict(list)
self.invgraph = defaultdict(list)
def addEdgeDirected(self, start, end):
self.graph[start].append(end)
self.invgraph[end].append(start)
def nonRecDFSInv(self, start):
visited = [False for _ in range(self.V)]
stack = []
stack.append(start)
path = []
while stack:
current = stack.pop()
if not visited[current]:
visited[current] = True
path.append(current)
for neighbor in self.invgraph[current]:
if not visited[neighbor]:
stack.append(neighbor)
return path
g = Graph(4)
g.addEdgeDirected(0,1)
g.addEdgeDirected(0,2)
g.addEdgeDirected(1,2)
g.addEdgeDirected(1,3)
g.addEdgeDirected(3,2)
print(g.nonRecDFSInv(3))
Output:
[2, 3, 1, 0]
Use Topological sort
- guilhebl May 02, 2018