Amazon Interview Question
SDE1sCountry: United States
Interview Type: In-Person
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);
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)
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:
before[module].add(d)
after[d].add(module)
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'])
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){
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;
results.add(g.nodes.get(index));
}
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);
this.connections.get(fromIndex).add(toIndex);
}
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>());
this.nodes.add(c);
}
return index;
}
}
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());
}
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