Interview Question
Country: India
public class MakeTheRobotsMeet {
private int count = -1;
private boolean moveOpposite = false;
public void makeRobotsMeet(Robot robot) {
count++;
//make sure that both the robots move at least once
if (count == 0 || count == 1) {
//arbitrarily chosen to move each robot towards left
robot.moveLeft();
}
if (robot.onTopOfParachute()) {
robot.noOperation();
moveOpposite = true;
} else if (moveOpposite) {
robot.moveRight();
} else {
robot.moveLeft();
}
}
//test client
public static void main(String[] args) {
Robot robot1 = new Robot(10, 56);
Robot robot2 = new Robot(56, 10);
MakeTheRobotsMeet makeTheRobotsMeet = new MakeTheRobotsMeet();
while (!robot1.didWeMeet(robot2)) {
makeTheRobotsMeet.makeRobotsMeet(robot1);
makeTheRobotsMeet.makeRobotsMeet(robot2);
}
}
}
//Sample Robot implementation
public class Robot {
private int parachuteLocationOfThisRobot, parachuteLocationOfTheOtherRobot;
private int currentLocation;
public Robot(int parachuteLocationOfThisRobot, int parachuteLocationOfTheOtherRobot) {
currentLocation = parachuteLocationOfThisRobot;
this.parachuteLocationOfThisRobot = parachuteLocationOfThisRobot;
this.parachuteLocationOfTheOtherRobot = parachuteLocationOfTheOtherRobot;
}
public void moveLeft() {
currentLocation--;
}
public void moveRight() {
currentLocation++;
}
public void noOperation() {
return;
}
public boolean onTopOfParachute() {
return currentLocation == parachuteLocationOfThisRobot || currentLocation == parachuteLocationOfTheOtherRobot;
}
public boolean didWeMeet(Robot otherRobot) {
return currentLocation == otherRobot.currentLocation;
}
public int getCurrentLocation() {
return currentLocation;
}
}
I think this is the smallest function I could write. Robots move to the left until they reach a set number or the other parachute, then they move back if and only if they didn't find the second parachute.
Then they do it again, going left a further amount, repeating until they meet.
They will always end up meeting on a parachute.
{
function meet() {
onOtherParachute = false
totalMovesThisTime (= 10
while (!didWeMeet()) {
movesSoFar = 0
while (movesSoFar < totalMovesThisTime) and (!onOtherParachute)
and (!didWeMeet()) {
moveLeft();
if (onTopOfParachute)
onOtherParachute = false
}
movesSoFar = 0
while (movesSoFar < totalMovesThisTime) and (!didWeMeet())
moveRight()
}
totalMovesThisTime += 10
}
}
}
Whoops, didn't work that time:
function meet() {
onOtherParachute = false
totalMovesThisTime (= 10
while (!didWeMeet()) {
movesSoFar = 0
while (movesSoFar < totalMovesThisTime) and (!onOtherParachute)
and (!didWeMeet()) {
moveLeft();
if (onTopOfParachute)
onOtherParachute = false
}
movesSoFar = 0
while (movesSoFar < totalMovesThisTime) and (!didWeMeet())
moveRight()
}
totalMovesThisTime += 10
}
}
Keep a flag whether the robot has reached the other's parachute or not.
* If it has reached, call moveLeft() two times, otherwise call moveLeft() and noOperation().
* This way one robot will double it's speed as soon as it reaches to the other's parachute and eventually they will meet.
*
* CATCH:
* Don't move a robot with twice as speed as other from landing point onwards.
* As we donot have any info which robot is behind and which one is in front.
* So if front robot is moved with double speed then lagging behind robot then it will never be able to catch it hence, never meet.
*/
void roboMeet()
{
bool reachedParachute = false
Hows this?
void fun()
{
count=1; //No. of steps to move in dir
dir=1; //Direction 0: left, 1: right
found=0; //Whether found other's parachute
canfind=1; //Is next parachute we find other's
if(didWeMeet()) return;
while(!found) //Search for other's parachute
{
for(int i=0;i<count;i++)
{
dir?moveRight():moveLeft();
if(didWeMeet()) return;
if(onTopOfParachute())
if(!canfind)
canfind=1;
else
{
found=1;
break;
}
}
count*=2;
dir = dir?0:1;
canfind=0;
}
while(!didWeMeet())
noOperation();
return();
}
I might me missing something given how complicated all these answers seem to be, but I think it works to have them both move in the same direction until one hits the other's parachute, and then have that one move twice as fast. Of course I can't actually make one go "twice as fast" but rather have them both start at something more like "half speed" then have the first one to hit go at normal speed. Maybe one of them can skip over the other in this way but I don't believe so.
do {
moveRight();
noOperation();
} while(!onTopOfParachute() && !didWeMeet());
while (!didWeMeet()) {
moveRight();
}
fun(){
static x =0;
static width=1;
if(x==0){ //i'm 1st one.
x=1;
while(onTopOfParachte()|| x<2); //wait
while(!didWeMeet())
{
for(left=0 to width) //go width left
{
moveLeft();
if(didWeMeet()) return;
}
for(right=0 to 2*width) //go width right
{
moveRight();
if(didWeMeet()) return;
}
for(left=0 to width) // bring back to original pos
{
moveLeft();
}
width = width*2; // only one person
}
}
if(x==1){ //i'm second one
x=2;
while(onTopOfParachte()|| x<2); //wait
while(!didWeMeet())
{
for(right=0 to width) //go width right
{
moveRight();
if(didWeMeet()) return;
}
for(left=0 to 2*width) //go width left
{
moveLeft();
if(didWeMeet()) return;
}
for(right=0 to width) // bring back to original pos
{
moveRight();
}
}
}
- Quintin June 23, 2014