Amazon Interview Question
Country: United States
Interview Type: Phone Interview
With topological sorting we can't get advantage of multithreading.
I think it's better use a Trie based on arguments
O(ln(k) * k)
k - Cardinality of the set of variables.
It does not make sense if it is not a DAG. Having a cycle in such a graph means that you cannot schedule it all (example, if a depends on b, b depends on c and c depends on a, you cannot execute any). So it has to be a DAG. And once you have topologically sorted it, determine which functions can be executed simultaneously and then accordingly create threads.
Simple List or array will do for holding the functions. Use set or hashset for the params since the order is not important but we will have to do contains.
///
Function[] functions = {
new Function("k", "f0", paramSet(new String[]{"a","c","e"})),
new Function("d", "f4", paramSet(new String[0])),
new Function("e", "f1", paramSet(new String[]{"a", "b", "c","d"})),
new Function("c", "f2", paramSet(new String[]{"a", "b", "d"})),
new Function(null, "f3", paramSet(new String[]{"a","c"})),
};
Arrays.sort(functions,
new Comparator<Function>() {
@Override
public int compare(Function o1, Function o2) {
if (o1.params.contains(o2.returnVar))
return 1;
if (o2.params.contains(o1.returnVar))
return -1;
if (o1.returnVar == null && o2.returnVar != null)
return 1;
return 0;
}
});
\\\
Could you please be more specific about what is actually been asked? I mean, by "Now read the file and we need to determine the order of execution of function depending on the input parameter list" what exactly do you mean? Are we here first choose those functions whose parameter list is a subset of the given parameters (I doubt this is what you mean), or what?
How about a makefile?
That the build of the left hand side object depends on the build of the right hand side object
a: b
c: d
b: e
e: f
and make must find the least dependent object to build it and also determine the build sequence
Thanks for both explanations. I see, now I understand the suggestion based on performing a topological sort. But could you please elaborate more on using "adjacency list"? Thanks in advance.
I was asked this question by the interviewer that which kind of data structure you are going to represent the objects and dependency relations in makefile....
You just need to find all variables and create the dependency graph for them. Then do topological sorting(if this is DAG; if not, find SCCs). Then calculate the values based on the order given the topological sorting.
- Daniel February 07, 2013