## A9 Interview Question for Software Engineer Interns

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

It might help if you show your recursive solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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 = new Exit(r.nextInt(maxDrops));
allExits.dropOff = r.nextInt(maxDrops);

Exit prevExit = allExits;
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);

System.out.println("Min cost = "+mincost + " " + Arrays.toString(bestSequence.toArray()));
}

static int mincost = Integer.MAX_VALUE;

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;
}
return;
} else {
//chose left
if(currentExit.l != null) {
passengers - currentExit.l.l.dropOff,
cost += passengers * currentExit.l.length,
exits);
exits.removeLast();
}
//chose right
if(currentExit.r != null) {
passengers - currentExit.r.r.dropOff,
cost += passengers * currentExit.r.length,
exits);
exits.removeLast();
}

}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
));
}

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;
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.