Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
it can be solved using weighted graph in O(n) -- where n is number of edges
but i have stuck at this case:
AB = 5
BC = 10
CD = 5
AC = 5
BD = 5
AD = 10 ohm
how will you solve it theoretically ??
for the case given by ninja, i am giving an overview:
create an adjacency matrix.
here where BC is repeated
means you have to update graph['B']['C'] using ohm's law(1/r = 1/r1 + 1/r2)
now graph[B][C] = 3.15
now add graph[B][C] and graph[C][D] , and store in graph[B][D] which is 8.15
now add graph[A][B] and graph[B][D] and store in graph [A][D] which is 13.15..
How about storing the information ? if we store the resultant resistance , we lose the information about the parallel resistances ?
@nachi: they havent asked about retrieving the data.. no need to store the input till the end of the process..
here they have asked ,"to find the total resistance how will you store(in which data structure) and calculate"...
Matrix is not a good idea because if I give you 100 nodes and 99 resistance in series, you get a 100x100 matrix with a lot of zeros.
I don't know how to explain in few words without writing code but one way is "topological sort". At each node, have a variable named oneByResistance
oneByResistance = 1/(1/(oneByResistanceOfParent) + edgeResistance) (For root oneByResistanceOfParent should not be added).
Process the whole graph and final resistance is 1/(OneByResistance) of last node processed. Hope this helps
@cobra In that case, you will have to check if AB*CD = AC*BD. If it is then no current would flow between BC (bridge circuit) and you can neglect that edge in graph.
But that's a specific case. Can't think of anything in general.
The general approach to solving a circuit problem is to use Kirchoff's laws. But this is way too sophisticated for an interview.
@eugene: Not so sure.
The purpose of an interview is not always to get a solution out of the candidate...
It is also possible that the candidate has an elec eng background, the position calls for it (software position in hardware team?) etc...
Of course, it is also possible that people are trying to get their homework done, and amazon happens to be the first company in the drop-down.
why not use a hash table.
key is your route "a-b' or "cd"
value is list of parallel resitances
public class Resistance{
public static void main(String[] args){
HashMap <String, Double> resistances = new HashMap<String, Double>();
Double val = addResistance("AB", 0.1, resistances);
Double val2 = addResistance("AB", 0.1, resistances);
Double totalResistance = computeTotal(resistances);
System.out.println("Total resistance is " + totalResistance);
}
public static Double addResistance(String endPoints, Double value, HashMap <String, Double> resistances){
if(resistances != null){
if(resistances.get(endPoints) == null){
resistances.put(endPoints, value);
}else{
Double temp = resistances.get(endPoints);
resistances.put(endPoints, 1/value + 1/temp);
}
}else{
resistances.put(endPoints, value);
}
return resistances.get(endPoints);
}
public static Double computeTotal(HashMap <String, Double> resistances){
Collection <Double> values = resistances.values();
Double sum = 0.0;
for(Iterator <Double> it = values.iterator();it.hasNext();){
sum = sum + it.next();
}
return sum;
}
}
Resistance between which two points? I would think that's rather relevant.
- eugene.yarovoi July 21, 2012