## Amazon Interview Question for SDE-2s

Country: United States

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

We approach this problem as a topological sorting problem:
We traverse the graph checking for circular dependencies while marking all nodes visited
The traverse yields 2 results: the execution order + all the possible starting points ("sub graphs"):

``````#include <exception>
#include <iostream>
#include <set>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

size_t id = 0;
size_t duration = 0;
Vec_t depends;
std::string ToString() const
{
std::stringstream ss;
ss << id;
return ss.str();
}
};

#define NODE_MARKER_TEMP 1
#define NODE_MARKER_DONE 2

{
if(M.count(t->id) && M[t->id] == NODE_MARKER_TEMP) { throw std::logic_error("circular loop found"); }
if(M.count(t->id) && M[t->id] == NODE_MARKER_DONE) { return; }
// Visit the children
M[t->id] = NODE_MARKER_TEMP;
for(Task* dep : t->depends) { Visit(dep, M, runOrder); }
M[t->id] = NODE_MARKER_DONE;
runOrder.push_back(t);
}

{
std::unordered_map<size_t, size_t> M; // Node markers

size_t maxExecutionTime = 0;
if(M.count(t->id)) { continue; }
runOrder.clear();
Visit(t, M, runOrder);
// print the runOrder
size_t tempMaxExecutionTime = 0;
std::cout << dep->ToString();
tempMaxExecutionTime += dep->duration;
}
maxExecutionTime = std::max(tempMaxExecutionTime, maxExecutionTime);
std::cout << std::endl;
}

std::cout << "Total time needed to execute the tasks: " << maxExecutionTime << std::endl;
}

void CalcMinExecutionTime()
{
// Build some test graph

// Create dependencies
t1.depends.push_back(&t2);
t2.depends.push_back(&t3);
t4.depends.push_back(&t5);

G.push_back(&t1);
G.push_back(&t2);
G.push_back(&t3);
G.push_back(&t4);
G.push_back(&t5);
G.push_back(&t6);

// Build sub graphs
try {
GetStartingPoints(S);

} catch(std::logic_error& e) {
std::cerr << e.what() << std::endl;
}
}``````

The above code results with:

``````321
54
6
Total time needed to execute the tasks: 21``````

This means: we have 3 starting points (i.e. three separate processes), which needs 21 time units for execution (we simply sum and keep track of the longest sequence)

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

First find the minimum spanning tree of these tasks. Then we can apply the topological sort to find the order in which we should schedule the tasks.

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.