A9 Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
this looks like Prim MST algo to cover all the nodes in a graph in shortest path
now what we can do is each edge is travel time between successive exits (given). -
so say exit 1 - exit2 is 20 mins, and exit 2 two students drop off then edge coming into exit2 is of weight 20/2 - rate of 1 student dropped every min for that path, reverse edge would be exit2 - exit 1 (say exit 1 3 students dropped) then edge weight is 20/3 - so shorter edge weight
Prim mst can be solved using greedy algorithm with finding smallest edge weight from one specific node or exit. and covering all the exits.
is this right way ?
public class DropOff {
public static class Exit {
public int dropOff =0;
public HighwayStretch l,r;
public Exit(int dropOff) {
this.dropOff = dropOff;
}
@Override
public String toString() {
return "["+dropOff+"]";
}
}
public static class HighwayStretch {
public int length = 0;
Exit l,r;
public HighwayStretch(int length) {
this.length = length;
}
@Override
public String toString() {
return "-"+length+"-";
}
}
public static void main(String[] args) {
Random r = new Random(5);
int exits = 5;
int maxDrops = 10;
int maxStretchLen =10;
Exit[] allExits = new Exit[exits];
allExits[0] = new Exit(r.nextInt(maxDrops));
allExits[0].dropOff = r.nextInt(maxDrops);
Exit prevExit = allExits[0];
System.out.print("Highway = " + prevExit);
for (int i = 1; i < exits; i++) {
allExits[i] = new Exit(r.nextInt(maxDrops));
HighwayStretch hs = new HighwayStretch(r.nextInt(maxStretchLen));
prevExit.r = hs;
allExits[i].l = hs;
hs.l = prevExit;
hs.r = allExits[i];
System.out.print(hs.toString() + allExits[i].toString());
prevExit = allExits[i];
}
System.out.println();
int currExitIndx = r.nextInt(exits);
System.out.println("currExitIndx = " + currExitIndx + " " + allExits[currExitIndx]);
int passengers = 30;
System.out.println("passengers = " + passengers);
findRecursSol(allExits[currExitIndx],passengers,0,new LinkedList<Exit>());
System.out.println("Min cost = "+mincost + " " + Arrays.toString(bestSequence.toArray()));
}
static int mincost = Integer.MAX_VALUE;
static LinkedList<Exit> bestSequence = null;
private static void findRecursSol(Exit currentExit, int passengers, int cost, LinkedList<Exit> exits) {
if(passengers <= 0) {
if(cost < mincost){
System.out.println("cost= "+cost + " " + Arrays.toString(exits.toArray()));
mincost = cost;
bestSequence = (LinkedList<Exit>) exits.clone();
}
return;
} else {
//chose left
if(currentExit.l != null) {
exits.add(currentExit.l.l);
findRecursSol(currentExit.l.l,
passengers - currentExit.l.l.dropOff,
cost += passengers * currentExit.l.length,
exits);
exits.removeLast();
}
//chose right
if(currentExit.r != null) {
exits.add(currentExit.r.r);
findRecursSol(currentExit.r.r,
passengers - currentExit.r.r.dropOff,
cost += passengers * currentExit.r.length,
exits);
exits.removeLast();
}
}
}
}
My solution in Java using dynamic programming(with a test case):
public class ChildrenDropOffProblem {
public static void main(String[] args) {
System.out.println(computeMinWeightedSum(
new int[]{10, 7, 5, 9}, // number of children that can be dropped off at each stop
new int[]{20, 2, 2}, // distance between successive stops
26, // number if children to start out with
2 // 1-indexed stop to start at (in this case, A[1])
));
}
public static int computeMinWeightedSum(int[] A, int[] B, int numChildren, int start) {
int n = A.length;
assert start >= 1 && start <= n;
assert n >= 2 && B.length == n - 1;
int[][] C = new int[n][numChildren];
for(int i=0; i<n; i++) {
for(int w=0; w<numChildren; w++) {
if(w <= A[i]) {
C[i][w] = 0; // initialization
} else {
C[i][w] = Integer.MAX_VALUE;
}
}
}
for(int w=0; w<numChildren; w++) {
for(int k=0; k<n; k++) {
int prevBest = Integer.MAX_VALUE;
int wNew = 0;
if(w <= A[k]) {
continue; // as per initialization, C[k][w] = 0
} else {
wNew = w - A[k];
}
for(int m=0; m<n; m++) {
if(m != k) {
int innerBest = 0;
if(wNew >= A[m]) {
innerBest = C[m][wNew];
}
innerBest += (wNew+1)*distance(B, k, m);
if(innerBest < prevBest) prevBest = innerBest;
}
}
C[k][w] = prevBest;
}
}
return C[start-1][numChildren-1];
}
public static int distance(int[] B, int start, int end) {
assert start < B.length;
assert end < B.length;
int trueStart, trueEnd;
if(start < end) {
trueStart = start;
trueEnd = end;
} else {
trueStart = end;
trueEnd = start;
}
int dist = 0;
for(int j=trueStart; j<trueEnd; j++) dist += B[j];
return dist;
}
}
It might help if you show your recursive solution.
- Anonymous October 31, 2014