Amazon Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

Create a dependency graph (directed graph) like A -> B if B is dependent on A. After that perform topological sorting on graph. it will provide proper build order.

- bhumij December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 votes

Here's an implementation

#include <list>
#include <boost/unordered_map.hpp>
#include <boost/unordered_set.hpp>

template <typename K, typename V>
using map = boost::unordered_map<K,V>;

template <typename T>
using set = boost::unordered_set < T > ;

class Node 

	Node(char _value) : value(_value) {};

	char value;
	set<Node*> outgoing;
	set<Node*> incoming;

// topological sort
void get_order(const map<char, set<char>>& dep, std::list<char>& out)
	map<char, Node*> cn;
	for (auto i : dep)
		if (cn.find(i.first) == std::end(cn))
			cn[i.first] = new Node(i.first);
		for (auto j : i.second)
			if (cn.find(j) == std::end(cn))
				cn[j] = new Node(j);
	std::list<Node*> q;
	for (auto i : cn)
		if (i.second->incoming.empty()) q.push_back(i.second);

	while (!q.empty())
		auto n = q.front();
		for (auto i : n->outgoing)
			if (i->incoming.empty()) q.push_back(i);

	for (auto i : cn)
		delete i.second;

// usage

	map<char, set<char>> dep;
	std::list<char> order;
	get_order(dep, order);

- Omri.Bashari May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
of 0 vote

def getInstallOrder(d):
    # get all modules.
    # assume d is a dictionary of all modules
    installedModules = []
    # install modules that don't have pre-reqs
    for key in d:
        if d[key] == []:
    for module in installedModules:

    while d:
        # search RHS / dict values to find all modules satisfied by installedList
        modulesNoLongerNeeded = []
        for key in d:
            modulesNeeded = d[key]
            dependenciesSatisfied = True
            for module in modulesNeeded:
                if module not in installedModules:
                    dependenciesSatisfied = False
            if dependenciesSatisfied:
        for module in modulesNoLongerNeeded:

    return installedModules

d = {1: [2], 2: [4], 3: [], 4: [3]}
print getInstallOrder(d)

- bdy December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

Maintain 2 hashmaps of "before" and "after" relationships. In this example, before['A'] = {'B','C'} while after['B'] = {'A'} etc. Keep finding the next module m where before[m] is empty. Then print this module, look up the modules that depend on it from after[m], and remove m from all the corresponding hashmap values.

def build_order(orders):
    before = {}
    after = {}
    for order in orders:
        for module in order:
            before[module] = set()
            after[module] = set()
    for order in orders:
        module = order[0]
        dependents = order[1:]
        for d in dependents:
    while len(before) > 0:
        for module in before.keys():
            if len(before[module]) == 0:
                print module
                for d in after[module]:
                del before[module]

print build_order(['ABC', 'BDEF', 'DF'])

- Sunny December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

Convert the dependencies into a Graph and use a Topological Sort. Should be O(m + n) where m is the number of dependencies and n is the number of different modules.

//input dependencies- each char[] is one set of dependencies.  
//[0] is the thing that has dependencies
//[1]..[n] are the things that are needed before the build can happen
public static ArrayList<Character> getBuildOrder(char[][] dependencies){
	if(dependencies == null){
		throw new NullPointerException();
	//construct the graph
	Graph g = new Graph();
	for(char[] dependency : dependencies){
		if(dependency == null || dependency.length < 2){
			throw new IllegalArgumentException();
		char from = dependency[0];
		for(int i = 1; i < dependency.length; i++){
			g.addConnection(from, dependency[i]);

	return topologicalSort(g);

static final int WORKING = 1;
static final int FINISHED = 2;

private static ArrayList<Character> topologicalSort(Graph g){
	int[] nodeStatus = new int[g.nodes.size()];
	ArrayList<Character> results = new ArrayList<Character>();

	for(Character c : nodes){
		Integer index = g.getIndex(c);
		topologicalSort(g, nodeStatus, results, index);
	return results;

private static void topologicalSort(Graph g, int[] nodeStatus, ArrayList<Character> results, Integer index){
	if(nodeStatus[index] == FINISHED){
	if(nodeStatus[index] == WORKING){
		throw new IllegalArgumentException("Dependency Cycle Detected");
	nodeStatus[index] = WORKING;
	for(Integer childIndex: g.connections.get(index)){
		topologicalSort(g, nodeStatus, results, childIndex);
	nodeStatus[index] = FINISHED;
static class Graph{
	HashMap<Character, Integer> nodeToIndexMap = new HashMap<Character, Integer>();
	ArrayList<Character> nodes = new ArrayList<Character>();
	ArrayList<HashSet<Integer>> connections = new ArrayList<HashSet<Character>>();

	void addConnection(Character from, Character to){
		Integer fromIndex = this.getIndex(from);
		Integer toIndex = this.getIndex(to);

	Integer getIndex(Character c){
		Integer index = this.nodeToIndexMap.get(c);
		if(index == null){
			index = this.nodes.size();
			this.nodeToIndexMap.put(c, index);
			this.connections.add(new HashSet<Character>());
		return index;

- zortlord December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

Topological sort is what you are talking about

- dom torreto December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

C++11 implementation using topological sort

#include <map>
#include <set>
#include <stdio.h>
#include <vector>
using namespace std;

typedef map<string, vector<string>> DepMap;

// collect reversed topological sorted order in acc
void Visit(const string &key, DepMap &dm, set<string> &visited, vector<string> &acc) {
  if (visited.find(key) == visited.end()) {
    for (const auto &dep_key : dm[key])
      Visit(dep_key, dm, visited, acc);

// DepMap -> build order
vector<string> ModuleBuildOrder(DepMap dm) {
  vector<string> order;
  set<string> visited;
  if (!dm.empty())
    Visit(dm.begin()->first, dm, visited, order);
  return order;

int main() {
  vector<string> order = ModuleBuildOrder({
      {"A", {"B", "C"}},
      {"B", {"D", "E", "F"}},
      {"D", {"F"}} });
  for (const auto &s : order)
    printf("%s\n", s.c_str());

- Tobi January 13, 2015 | Flag Reply

Add a Comment

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


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


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