## Google Interview Question for Technical Support Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

Use Topological sort

Comment hidden because of low score. Click to expand.
0
of 0 vote

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; }
3)
for each task in auxillary array:
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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
- 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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Its simple,do a topological sorting of the vertices

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <map>
using namespace std;

}

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, '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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

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)

print(g.nonRecDFSInv(3))``````

Output:
[2, 3, 1, 0]

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.