## Directi Interview Question for Applications Developers

• 1
of 1 vote

Country: India

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

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)]``

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

@Michael: your solution is wrong.

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

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.

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

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)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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.