Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
public class Solution {
int n = 6;
int shirt = 0;
int belt = 1;
int trouser = 2;
int shocks = 3;
int shoes = 4;
int tie = 5;
int[][] graph = new int[n][n];
Solution(){
graph[shirt][tie] = 1;
graph[shirt][belt] = 1;
graph[trouser][belt] = 1;
graph[trouser][shocks] = 1;
graph[shocks][shoes] = 1;
}
private void dfs(String order, int cur, List<Integer> list, int[] mark, int[] inDegree, int count){
// System.out.println(list);
// System.out.println("#### "+order);
if(count == n){
System.out.println(order);
return;
}
int num = 0;
for(int j = 0 ; j < n ; ++j){
if(graph[cur][j] == 1){
inDegree[j] --;
if(inDegree[j] == 0){
num++;
list.add(j);
}
}
}
int size = list.size();
for(int i = 0 ; i < size ; ++i){
if(mark[list.get(i)] == 0){
mark[list.get(i)] = 1;
dfs(order+" "+list.get(i), list.get(i), list, mark, inDegree, count+1);
mark[list.get(i)] = 0;
}
}
while(num != 0){
num--;
int a = list.get(list.size() - 1);
list.remove(list.size() - 1);
inDegree[a]++;
}
}
public void solve(int[][] graph){
int[] inDegree = new int[n];
for(int i = 0 ; i < n ; ++i){
for(int j = 0 ; j < n; ++j){
if(graph[i][j] == 1){
inDegree[j] ++;
}
}
}
int[] mark = new int[n];
List<Integer> list = new ArrayList<>();
for(int i = 0 ; i < n ; ++i){
if(inDegree[i] == 0) {
list.add(i);
}
}
int size = list.size();
for(int i = 0 ; i < size ; ++i){
if(mark[list.get(i)] == 0){
mark[list.get(i)] = 1;
dfs(list.get(i)+"", list.get(i), list, mark, inDegree, 1);
mark[list.get(i)] = 0;
}
}
}
public static void main(String[] args){
Solution solution = new Solution();
solution.solve(solution.graph);
}
}
I didn't really find a solution to get ALL possible combinations, maybe someone has an idea. how ever, the solution below will produce SOME combinations (as was asked for).
time complexity is O(#edges) until the results are produced which is linear in the number of results.
# Assumptions:
# 1) the example describes a DAG with one connected component. I assume the
# graph can be characterized in general like this: directed, a-cyclic, only
# one connected component, minimal two nodes
# 2) print some (and not all) possible topological orders
# 3) for simplicity the graph is given by edges [["Shirt", "Tie"], ["Belt", "Trousers"]]
#
# Solution:
# for any graph using DFS with arrival / departure time of a node can be used
# to analyze the graph and perform a topological sort. The problem is, this
# traversal creates only one possible topological sort. If I want an other,
# I have to change the start and the order in which I visit the adjacents.
# keeping track of this without doing way too much work is not trivial.
#
# Since it is a DAG there is an easier way to get some topological orders:
# 0. prepare the graph as adjacency list representation
# 1. find the nodes with in-degree = 0 (roots), give them order 0
# and start a BFS with those nodes as frontier
# 2. expand the frontier, do not check if a node was already visited
# just label the node with the distance from the root (no cycles)
# 3. create any order where the nodes distance from the root increase
from itertools import permutations
from collections import defaultdict
def allTopologicalOrders(edges):
# 0. create a adjacency list representation of the graph given by edges
nodes = defaultdict(set)
for e in edges:
nodes[e[0]].add(e[1])
# 1. find roots
roots = set(nodes.keys())
for u, adjs in nodes.items():
roots.difference_update(adjs)
# 2. expand until expansion is no further possible
# (loop will not terminate with cycles)
maxD = 0
nodeOrder = defaultdict(lambda: 0)
stack = list(roots)
while len(stack) > 0:
u = stack.pop() #node to expand from
du = nodeOrder[u] #distance of that node from "start""
for v in nodes[u]: #for all adjacent nodes v
dv = nodeOrder[v] #current distance of v from "start"
if dv <= du: # if v is currently on shorter distance from "start"
maxD = max(maxD, du + 1)
nodeOrder[v] = du + 1
stack.append(v)
# 3. create an array that has a list of nodes on each
# index representing the distance from "start"
# and create all possible permutations for each distance group...
d2Node = [[] for i in range(maxD + 1)]
for u, du in nodeOrder.items():
d2Node[du].append(u)
result = [[]]
for ng in d2Node:
nr = []
ngp = list(permutations(ng))
for r in result:
for p in ngp:
nr.append(r + list(p))
result = nr
return result
print(allTopologicalOrders([["Shirt", "Tie"], ["Shirt", "Belt"], ["Trouser", "Belt"], ["Trouser", "Socks"], ["Socks", "Shoes"]]))
#[['Trouser', 'Shirt', 'Tie', 'Belt', 'Socks', 'Shoes'],
# ['Trouser', 'Shirt', 'Tie', 'Socks', 'Belt', 'Shoes'],
# ['Trouser', 'Shirt', 'Belt', 'Tie', 'Socks', 'Shoes'],
# ['Trouser', 'Shirt', 'Belt', 'Socks', 'Tie', 'Shoes'],
# ['Trouser', 'Shirt', 'Socks', 'Tie', 'Belt', 'Shoes'],
# ['Trouser', 'Shirt', 'Socks', 'Belt', 'Tie', 'Shoes'],
# ['Shirt', 'Trouser', 'Tie', 'Belt', 'Socks', 'Shoes'],
# ['Shirt', 'Trouser', 'Tie', 'Socks', 'Belt', 'Shoes'],
# ['Shirt', 'Trouser', 'Belt', 'Tie', 'Socks', 'Shoes'],
# ['Shirt', 'Trouser', 'Belt', 'Socks', 'Tie', 'Shoes'],
# ['Shirt', 'Trouser', 'Socks', 'Tie', 'Belt', 'Shoes'],
# ['Shirt', 'Trouser', 'Socks', 'Belt', 'Tie', 'Shoes']]
print(allTopologicalOrders([["Shirt", "Tie"], ["Shirt", "Belt"], ["Trouser", "Belt"], ["Trouser", "Socks"], ["Socks", "Shoes"], ["Shoes", "Shirt"]]))
#[['Trouser', 'Socks', 'Shoes', 'Shirt', 'Tie', 'Belt'], ['Trouser', 'Socks', 'Shoes', 'Shirt', 'Belt', 'Tie']]
I added each item iteratively checking if it can be added to position. Below is the code:
public static void main(String[] args) throws Exception {
printAllowedLists(Lists.newArrayList(), Lists.newArrayList(Cloth.values()));
}
private static void printAllowedLists(List<Cloth> existingList, List<Cloth> remaining) {
if (CollectionUtils.isEmpty(remaining)) {
System.out.println(existingList);
return;
}
for (int i = 0; i < remaining.size(); i++) {
Cloth clothUnderConsideration = remaining.get(i);
List<Cloth> existingListNew = Lists.newArrayList(existingList);
List<Cloth> remainingNew = Lists.newArrayList(remaining);
if (prereqExists(clothUnderConsideration, existingList)) {
existingListNew.add(clothUnderConsideration);
remainingNew.remove(clothUnderConsideration);
printAllowedLists(existingListNew, remainingNew);
}
}
}
private static Boolean prereqExists(Cloth cloth, List<Cloth> cloths) {
if (CollectionUtils.isEmpty(cloth.preconditions)) {
return true;
}
List<Cloth> prereq = cloth.preconditions;
return cloths.containsAll(prereq);
}
static enum Cloth {
SHIRT(),
TIE(SHIRT),
TROUSER(),
SOCKS(TROUSER),
SHOES(SOCKS),
BELT(SHIRT, TROUSER);
List<Cloth> preconditions;
Cloth(Cloth... cloths) {
this.preconditions = Lists.newArrayList(cloths);
}
}
C++
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
void processDeps(int item, map<int, set<int>>& depList, stack<int>& depOrder, set<int>& visitedItems) {
if (visitedItems.end() != visitedItems.find(item))
return;
visitedItems.insert(item);
if (depList[item].empty()) {
depOrder.push(item);
return;
}
for (auto dependencyChild : depList[item]) {
if (visitedItems.end() != visitedItems.find(dependencyChild))
continue;
processDeps(dependencyChild, depList, depOrder, visitedItems);
}
depOrder.push(item);
}
bool isValidOrder(int* order, int nElems, map<int, set<int>>& invertDepList) {
vector<int> v(order, order + nElems);
bool isValid = true;
for (int i = 1; (i < nElems) && isValid; ++i) {
for (int vElem : invertDepList[v[i]])
{
vector<int> v2(order, order + i);
if (v2.end() != find(v2.begin(), v2.end(), vElem)) {
isValid = false;
break;
}
}
}
return isValid;
}
int main()
{
typedef enum {
SHIRT, TIE, TROUSER, BELT, SOCKS, SHOES
} Item;
map<int, string> items = { { SHIRT, "Shirt" },{ TIE, "Tie" },{ TROUSER, "Trouser" },{ BELT, "Belt" },
{ SOCKS, "Socks" },{ SHOES, "Shoes" } };
map<int, set<int>> depList = {
{ SHIRT,{} },
{ TIE,{ SHIRT } },
{ TROUSER,{} },
{ BELT,{ SHIRT, TROUSER } },
{ SOCKS,{ TROUSER } },
{ SHOES,{ SOCKS } }
};
map<int, set<int>> invertDepList = {
{ SHIRT,{ TIE, BELT, TROUSER } },
{ TIE,{} },
{ TROUSER,{ BELT, SOCKS } },
{ BELT,{} },
{ SOCKS,{ SHOES } },
{ SHOES,{} }
};
stack<int> depOrder;
set<int> visitedItems;
for (auto item : items) {
processDeps(item.first, invertDepList, depOrder, visitedItems);
}
int order[6], i = 0;
int currentOrder[6] = { 0, 1, 2, 3, 4, 5 };
while (!depOrder.empty()) {
order[i] = depOrder.top();
depOrder.pop();
++i;
}
set<int> indepNodes;
for_each(depList.begin(), depList.end(), [&indepNodes](pair<int, set<int>> itm) { if (itm.second.empty()) indepNodes.insert(itm.first); });
// Calculate combinations those start from independent nodes
vector<vector<int>> possibleCombinations;
do {
vector<int> v(currentOrder, currentOrder + 6);
if (isValidOrder(currentOrder, 6, invertDepList)) {
possibleCombinations.push_back(v);
}
} while (next_permutation(currentOrder, currentOrder + 6));
// Display possible combinations
for_each(possibleCombinations.begin(), possibleCombinations.end(), [&items](vector<int>& itms) {
for (auto i : itms)
cout << items[i].c_str() << ", ";
cout << "\b\b \n";
});
return 0;
}
public static void clothes(ArrayList<String> clothesSet){
ArrayList<String> result = new ArrayList<String>();
HashMap<String,Boolean> map = new HashMap<String,Boolean>();
for(String item:clothesSet){
map.put(item, true);
}
clothes(map,result);
System.out.println("Total ways="+ clothesways);
}
static int clothesways=0;
public static void clothes(HashMap<String,Boolean> map, ArrayList<String> result){
if(result.size()==map.size()){
System.out.println(result);
clothesways++;
}else{
for(String item:map.keySet()){
if (!(map.get(item)) )
continue;
if(item.equals("tie") && !result.contains("shirt"))
continue;
if(item.equals("belt") &&
!(result.contains("shirt") && result.contains("trouser"))
)
continue;
if(item.equals("socks") && !result.contains("trouser"))
continue;
if(item.equals("shoes") && !result.contains("socks"))
continue;
result.add(item);
map.put(item, false);
clothes(map,result);
map.put(item, true);
result.remove(item);
}
}
}
Topological sort ?
- Guru June 06, 2017