Amazon Interview Question Senior Software Development Engineers
Country: UK
Interview Type: In-Person
Create two lists, one with pending libraries, and one empty for results. Go through the pending list and move all the libraries with no dependencies to the results list.
For each library left in the pending list, move those which have all dependencies already in the results list to the results list. Repeat until you are left with an empty pending list or you make it though the pending list without moving anything. If it's the later, you've detected one or more cyclic dependencies and all the remaining libraries in the pending list are involved.
-- Use union find algorithm to find if there are cycles in graph , if not then
1.) Create a directed graph from A->B if B is dependent on A.
2.) Keep set of vertices which have no dependencies, basically no incoming vertices
Then run Topological sort
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
It is a DAG, Directional A-cyclic Graph. If it is not (it has cycles) you have no way to load the libraries.
To get the order of the nodes:
1) Convert input to graph
2) DFS
4) Load the libs according to the finish time of each node e.g. the first node to finish is the first lib that should be loaded, second node to finish is the second lib and so on.
Quick Algorithm
For each statement, Library X depends Library Y, Create an entry if not created already in a Dictionary for X. else add Y to it.
While(Dictionary is not empty)
Take first element which is having null list or empty list if exists, delete it from the dictionary, and delete all its presence in any other nodes last as well.
If not, then there is a cycle here, and you can report it and exit.
Complexity : O(number of relations) Time.
#include <iostream>
#include <stack>
using namespace std;
#define SIZE 6
bool topoSort(char vtx[], bool visited[], char edges[][SIZE], char start_vtx, stack<char> *s){
if (isExist(*s, start_vtx)){
printf(" There is a Cycle between %c and %c \n", start_vtx, s->top());
return false;
}
if (visited[start_vtx - 'A'] == false)
{
s->push(start_vtx);
visited[start_vtx - 'A'] = true;
if (edges[start_vtx - 'A'][0] != 0)
topoSort(vtx, visited, edges, edges[start_vtx - 'A'][0], s);
}
return true;
}
bool isExist(stack<char> s, char ch){
while (!s.empty()){
if (s.top() == ch)
return true;
s.pop();
}
return false;
}
/* Edges between*/
char vertices[SIZE] = { 'A', 'B', 'C', 'D', 'E', 'F' };
bool visited[SIZE] = { false, false, false, false, false };
/*Edges matrix for non-cyclic dependency*/
char edgeList[][SIZE] = {
/* A -> */{ 'B', 'C', 0, 0, 0, 0 },
/* B -> */{ 'C', 'D', 'E', 0, 0, 0 },
/* C -> */{ 'D', 'E', 0, 0, 0, 0 },
/* D -> */{ 'F', 0, 0, 0, 0, 0 },
/* E -> */{ 0, 0, 0, 0, 0, 0 },
/* F -> */{ 0, 0, 0, 0, 0, 0 }
};
/*Edges matrix for cyclic dependency*/
//char edgeList[][SIZE] = {
// /* A -> */{ 'B', 'C', 0, 0, 0, 0 },
// /* B -> */{ 'C', 'D', 'E', 0, 0, 0 },
// /* C -> */{ 'D', 'E', 0, 0, 0, 0 },
// /* D -> */{ 'F', 0, 0, 0, 0, 0 },
// /* E -> */{ 0, 0, 0, 0, 0, 0 },
// /* F -> */{ 'B', 0, 0, 0, 0, 0 }
//};
int main(){
stack<char> s;
for (int i = 0; i < SIZE; i++)
if (!visited[i] && topoSort(vertices, visited, edgeList, vertices[i], &s));
while (!s.empty()){
printf("%c ", s.top());
s.pop();
}
return 0;
}
#include <iostream>
#include <stack>
using namespace std;
#define SIZE 6
bool topoSort(char vtx[], bool visited[], char edges[][SIZE], char start_vtx, stack<char> *s){
if (isExist(*s, start_vtx)){
printf(" There is a Cycle between %c and %c \n", start_vtx, s->top());
return false;
}
if (visited[start_vtx - 'A'] == false)
{
s->push(start_vtx);
visited[start_vtx - 'A'] = true;
if (edges[start_vtx - 'A'][0] != 0)
topoSort(vtx, visited, edges, edges[start_vtx - 'A'][0], s);
}
return true;
}
bool isExist(stack<char> s, char ch){
while (!s.empty()){
if (s.top() == ch)
return true;
s.pop();
}
return false;
}
/* Edges between*/
char vertices[SIZE] = { 'A', 'B', 'C', 'D', 'E', 'F' };
bool visited[SIZE] = { false, false, false, false, false };
/*Edges matrix for non-cyclic dependency*/
char edgeList[][SIZE] = {
/* A -> */{ 'B', 'C', 0, 0, 0, 0 },
/* B -> */{ 'C', 'D', 'E', 0, 0, 0 },
/* C -> */{ 'D', 'E', 0, 0, 0, 0 },
/* D -> */{ 'F', 0, 0, 0, 0, 0 },
/* E -> */{ 0, 0, 0, 0, 0, 0 },
/* F -> */{ 0, 0, 0, 0, 0, 0 }
};
/*Edges matrix for cyclic dependency*/
//char edgeList[][SIZE] = {
// /* A -> */{ 'B', 'C', 0, 0, 0, 0 },
// /* B -> */{ 'C', 'D', 'E', 0, 0, 0 },
// /* C -> */{ 'D', 'E', 0, 0, 0, 0 },
// /* D -> */{ 'F', 0, 0, 0, 0, 0 },
// /* E -> */{ 0, 0, 0, 0, 0, 0 },
// /* F -> */{ 'B', 0, 0, 0, 0, 0 }
//};
int main(){
stack<char> s;
for (int i = 0; i < SIZE; i++)
if (!visited[i] && topoSort(vertices, visited, edgeList, vertices[i], &s));
while (!s.empty()){
printf("%c ", s.top());
s.pop();
}
return 0;
}
I forget the specific name of this approach (EDIT: It is a graph topology), but a DFS search on all contents if converted to a graph would work. O(n) runtime and O(n) memory for the searching of the graph.
Assumes that the incoming parameter are a List<List<String>> where the first item on each list is the name of the library and each following item is a dependency (something that should be loaded first)
private static class Vertex{
String name;
ArrayList<Vertex> dependencies;
private Vertex(String name){
this.name = name;
this.dependencies = new ArrayList<Vertex>();
}
}
private static class Graph{
ArrayList<Vertex> vertices;
HashMap<String, Vertex> vertexLookup;
private Graph(){
this.vertices = new ArrayList<Vertex>();
this.vertexLookup = new HashMap<String, Vertex>();
}
private Vertex getVertex(String libName){
Vertex v = this.vertexLookup.get(libName);
if(v == null){
v = new Vertex();
v.name = libName;
this.vertexLookup.put(libName, v);
this.vertices.add(v);
}
return v;
}
}
//(EDIT: Didn't describe this, but the original code returns null if there is a cycle)
public static List<String> getDependencyLoadOrder(List<List<String>> libraries){
//build the graph
Graph g = new Graph();
for(List<String> dependency : libraries){
Iterator<String> iter = dependency.iterator();
String libName = iter.next();
Vertex v = g.getVertex(libName);
while(iter.hasNext){
libName = iter.next;
Vertex child = g.getVertex(libName);
v.dependencies.add(child);
}
}
//construct the list for return
ArrayList<String> results = new ArrayList<String>(g.vertices.size());
HashMap<String, State> loadState = new HashMap<String, State>();
try{
for(int i = 0; i < g.vertices.size(); i++){
tryLoad(g.vertices.get(i), results, loadState );
}
}
catch(IllegalArgumentException e){
return null;
}
return results;
}
enum State{
LOADED, LOADING, NOT_LOADED
}
private static void tryLoad(Vertex v, ArrayList<String> results, HashMap<String, State> loadState ){
State state = loadState.get(v.name);
if(state == LOADING){
throw new IllegalArgumentException();
}
if(state == LOADED){
return;
}
loadState.put(v.name, LOADING);
for(Vertex child : v.dependencies){
tryLoad(child, results, loadState);
}
results.add(v.name);
loadState.put(v.name, LOADED);
}
its called topological sort of graph with DFS
- um01 July 13, 2015