CareerCup

I guess it involves solving following recursive problem:

d(o1, o2, (p1, p2....pn)) = min[d(p1, o2, (p2, p3, ...pn)) + d(p1,o1) , d(o1, p2, (p2, p3, ...pn)) + d(p1,o2)]

@Michael: your solution is wrong.

Apply BFS, push the positions of both the players in the queue initially. Then do BFS..
this was asked to me in the Amazon interview.

F(Gk, p1) = min cost of covering gem Gk by player 1

Answer would be F(Gn, p1) or F(Gn, p2)

F(Gk, p1) = Min(Min(F(Gi, p1) + F(Gi+1, p2) + cost of covering all the nodes between i+1 to k-1 by single player ) for i< k-1 and > 0, F(Gi-1, p1) + cost of covering all the nodes i-1 to i)

o(n^2)

public int determineMinimumMoves(Point positionPlayer1, Point positionPlayer2,
            final Point... gems) {

        if (positionPlayer1 == null) {
            throw new IllegalArgumentException("Player 1 is null");
        } else if (positionPlayer2 == null) {
            throw new IllegalArgumentException("Player 2 is null");
        }

        int moves = 0;
        if (gems != null) {
            for (Point gemPosition : gems) {
                final int distancePlayer1ToGem = positionPlayer1.distanceTo(gemPosition);
                final int distancePlayer2ToGem = positionPlayer2.distanceTo(gemPosition);

                // player 2 is closer - move player 2
                if (distancePlayer1ToGem > distancePlayer2ToGem) {
                    positionPlayer2 = gemPosition;
                }
                // player 1 is closer or distance is equal - move player 1
                else {
                    positionPlayer1 = gemPosition;
                }
                moves += Math.min(distancePlayer1ToGem, distancePlayer2ToGem);
            }
        }
        return moves;
    }


public class Point {
    private final int _x;
    private final int _y;


    /**
     * Constructor
     *
     * @param x the x position of the current point
     * @param y the y position of the current point
     */
    public Point(final int x, final int y) {
        this._x = x;
        this._y = y;
    }


    /**
     * Determines the distance between the current and the given point. All 8 movement directions
     * are allowed.
     * <p/>
     * This algorithm determines the max distance of x1 -> x2 and y1 -> y2. Because all 8 movement
     * directions are allowed, this is the distance between both points
     *
     * @param otherPoint the other point
     * @return the distance between the current point and the other point
     */
    public int distanceTo(final Point otherPoint) {

        int disX = Math.abs(_x - otherPoint.getX());
        int disY = Math.abs(_y - otherPoint.getY());
        return Math.max(disX, disY);
    }


    /**
     * @return the x position of the current point
     */
    public int getX() {
        return _x;
    }


    /**
     * @return the y position of the current point
     */
    public int getY() {
        return _y;
    }
}