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.

- Anonymous October 31, 2014 | Flag Reply
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 ?

- Preet January 09, 2015 | Flag Reply
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[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();
            }


        }
    }

}

- Anonymous March 29, 2015 | Flag Reply
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[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;
    }
}

- Killedsteel April 26, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More