## Amazon Interview Question for SDE1s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
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.

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

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
{
public:

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);
}
cn[i.first]->outgoing.insert(cn[j]);
cn[j]->incoming.insert(cn[i.first]);
}
}
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();
q.pop_front();
out.push_back(n->value);
for (auto i : n->outgoing)
{
i->incoming.erase(n);
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;
dep['A'].insert('B');
dep['A'].insert('C');
dep['B'].insert('D');
dep['B'].insert('E');
dep['B'].insert('F');
dep['D'].insert('F');
dep['F'].insert('E');
get_order(dep, order);``````

Comment hidden because of low score. Click to expand.
0
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] == []:
installedModules.append(key)
for module in installedModules:
d.pop(module)

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:
installedModules.append(key)
modulesNoLongerNeeded.append(key)
for module in modulesNoLongerNeeded:
d.pop(module)

return installedModules

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

Comment hidden because of low score. Click to expand.
0
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]:
before[d].remove(module)
del before[module]
break

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

Comment hidden because of low score. Click to expand.
0
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++){
}
}

}

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){
continue;
}
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>>();

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);
}
return index;
}
}``````

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

Topological sort is what you are talking about
en.wikipedia.org/wiki/Topological_sorting

Comment hidden because of low score. Click to expand.
0
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()) {
visited.insert(key);
for (const auto &dep_key : dm[key])
Visit(dep_key, dm, visited, acc);
acc.push_back(key);
}
}

// 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());
}``````

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.

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

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