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>

struct Task {
    typedef std::vector<Task*> Vec_t;
    size_t id = 0;
    size_t duration = 0;
    Vec_t depends;
    std::string ToString() const
    {
        std::stringstream ss;
        ss << id;
        return ss.str();
    }
};

Task::Vec_t G;

#define NODE_MARKER_TEMP 1
#define NODE_MARKER_DONE 2

void Visit(Task* t, std::unordered_map<size_t, size_t>& M, Task::Vec_t& runOrder)
{
    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;
    // add the task to the start
    runOrder.push_back(t);
}

void GetStartingPoints(Task::Vec_t& S)
{
    std::unordered_map<size_t, size_t> M; // Node markers
    Task::Vec_t runOrder;

    size_t maxExecutionTime = 0;
    for(Task* t : G) {
        if(M.count(t->id)) { continue; }
        runOrder.clear();
        Visit(t, M, runOrder);
        // print the runOrder
        size_t tempMaxExecutionTime = 0;
        for(Task* dep : runOrder) {
            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
    Task t1{ 1, 5 };
    Task t2{ 2, 7 };
    Task t3{ 3, 8 };
    Task t4{ 4, 20 };
    Task t5{ 5, 1 };
    Task t6{ 6, 1 };

    // 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
    Task::Vec_t S;
    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)

- PenChief April 24, 2019 | Flag Reply
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.

- Himanshu Verma September 04, 2019 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More