Google Interview Question for Software Developers


Country: United States
Interview Type: In-Person




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

/**
 * Task is to detect if robot walks in a square. For that we need to find a cycle in path (360 turn) 
 * and if robot returns to origin after a while.
1. Start Robot looking North, Angle 0.
2. For each rotation move check if full cycle has been achieved >= 360 angle
3. Use a large treshold and test sample from i ... treshold times repeatedly.
4. If full turn not achieved return false
	Time: O(T * N) where T is the testing treshold and N array of moves size.
 */
public class DetectRobotCycle {
		
	public static void main(String[] args) {
		int m[] = {10, 180, 10};
		System.out.println(isWallPossible(m));

		int m1[] = {10, 45, 10, -45, 10, 45};
		System.out.println(isWallPossible(m1));
		
		int m2[] = {10, 45, 10, -45, 10, 45, 10, -45};
		System.out.println(isWallPossible(m2));		
	}
	
	public static boolean isWallPossible(int[] moves) {		
		int treshold = 10000;
		int i = 0;
		Position p = new Position(0, MoveDirection.N); // start north
		boolean rotate = false;

		while (i < treshold) {
			rotate = false;
			for (int j = 0; j < moves.length; j++) {
				if (rotate) {
					p.addAngle(moves[j]);
				} else {
					p.addSteps(moves[j]);					
				}
				rotate = !rotate;
			}
			if (p.cycled && p.x == 0 && p.y == 0) {
			   return true;	
			}		
			i++;
		}		
		return false;
	}

}

class Position {
	int x;
	int y;
	
	int angle;
	MoveDirection d;
	boolean cycled;
	
	public Position(int angle, MoveDirection d) {
		super();
		x = y = 0;
		this.angle = angle;
		this.d = d;
		this.cycled = false; 
	}

	public void addSteps(int s) {
		if (d.equals(MoveDirection.N)) {
			y += s;
		} else if (d.equals(MoveDirection.E)) {
			x += s;
		} else if (d.equals(MoveDirection.S)) {
			y -= s;
		} else if (d.equals(MoveDirection.W)) {
			x -= s;
		}
	}

	public void addAngle(int a) {
		angle += a;
		if (angle >= 360) {
			angle = angle % 360;
			cycled = true;
		}
		if(angle >= 0 && angle < 90) {
			d = MoveDirection.N;
		}
		else if(angle >= 90 && angle < 180) {
			d = MoveDirection.E;
		}
		else if(angle >= 180 && angle < 270) {
			d = MoveDirection.S;
		}
		else if(angle >= 270 && angle < 360) {
			d = MoveDirection.W;
		} 
	}
}

enum MoveDirection {
	N,E,S,W;
}

/**
output:
true
false
false
*/

- guilhebl June 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This solution calculates the bot path for as many iterations as needed for its orientation to go back to zero degrees. Once there, return whether the bot is at the origin or not.
An error margin (arbitrarily chosen) is considered to account for rounding.

import math                                                                                         
                                                                                                    
def check_path(commands):                                                                      
    orientation = 0                                                                                 
    x, y = 0, 0                                                                                     
    epsilon = 0.01                                                                                  
                                                                                                    
    while True:                                                                                     
        for command in commands:                                                                    
            if command[0] == 'rotate':                                                              
                orientation = (orientation + command[1]) % 360                                      
            elif command[0] == 'move':                                                              
                x += command[1]*math.cos(math.radians(orientation))                                 
                y += command[1]*math.sin(math.radians(orientation))                                 
            else:                                                                                   
                print "Invalid Command"                                                             
                                                                                                    
        if orientation == 0:                                                                        
            # Verify that both is back to origin                                                    
            return ((x < epsilon and x > -1 * epsilon) and                                          
                        (y < epsilon and y > -1 * epsilon))

print check_path([('move', 10), ('rotate', 45), ('move', 10), ('rotate', -45),                      
                            ('move', 10), ('rotate', -45), ('move', 10), ('rotate', 45),                      
                            ('move', 10), ('rotate', 180)])

- HoldTheCode June 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

First, transform the list of commands into a single command. (E.g. go forward 1, turn around, go back one turns into "turn around")

If this command has 0 movement, then we can build a wall. If the command has nonzero movement and the bearing changes, then we can also build a wall. (Draw some pictures to see why this is. For example, if the bearing changes 90 degrees, the robot will draw a box. If it changes 60 degrees, it draws a triangle. It creates more complicated shapes for bearing changes that do not divide 360, but it will still create a contained shape. It may never even reach its original point).

If the command has nonzero movement and no bearing change, it will draw a straight line to infinity and thus no box can contain it.

- aascrivener July 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

On a theoretical level the problem is quite simple.

Take the list of commands. When repeated over and over the list can be simplified to a single translation t followed by a single rotation r.

The only way we can't build a wall that contains the robot is if it will travel in a single direction infinitely, e.g. r == 0 && t > 0.

So run through the list of commands updating the robots position and as long as it faces in a different direction than it started OR ends its travel in the start position the wall is possible.

If this problem is about how to do accurate 2d plane traversal using integer coordinates and angles that is a much harder problem to solve and I would be interested to see solutions.

- Johnie June 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Also I'm pretty sure that your second example is wrong, it would be possible to build a wall around that path.

- Johnie June 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I saw this question at Hackerrank. It's called "Encircular". So this begs the questions: does Google copy questions from Hackerank ? or is this not a real interview question ?
To me this seems to be a horrible interview question. It requires some Aha moment which beats the purpose of the interview. But I might be wrong.

- Lively June 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the missing part in the question is the fact that the series of commands can be repeated infinite times. (That is what the python code shows you).

The solution is probably simple.

Point p1 = getStartingPoint(); 
        Point p2 = getPointAfterIteration(commands,1); 
	Point p3 = getPointAfterIteration(commands,2); 
        Point p4 = getPointAfterIteration(commands,3); 

       Circle c = new Circle(p1,p2,p3); 
       if(p1==p2==p3 || c.contains(p4)){
           return true; 
       }
    
      return false;

- The missing part June 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assumption - Imaging X & Y axis dimensions. Robot will start at degree & (X,Y)=(0,0).
So at start robot is pointing towards positive X axis.

if output is (0,0) i..e final co-ordinates of robot then there is a wall.

import java.lang.Math;
import java.text.DecimalFormat;

public class RoboticWall {

static double X = 0.00d;
static double Y = 0.00d;
static double currentAngle = 0.0d;
static DecimalFormat numberFormat = new DecimalFormat("#.##");

public static void main(String[] s){
//System.out.println(Math.cos(180/57.2958));
isWall();
}

public static void isWall(){

move(10);
rotate(90);
move(10);
rotate(90);
move(10);
rotate(90);
move(10);

System.out.println("X="+numberFormat.format(X)+"Y="+numberFormat.format(Y));
}

private static void rotate(double i) {
currentAngle = currentAngle + i;
}

private static void move(double i) {

X = X + i*Math.cos(currentAngle/57.29);
Y = Y + i*Math.sin(currentAngle/57.29);
}


}

output: X=0 Y=0

- thakur.871 June 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assumption - Imaging X & Y axis dimensions. Robot will start at degree 0 & (X,Y)=(0,0).
So at start robot is pointing towards positive X axis.

if output is (0,0) i..e final co-ordinates of robot then there is a wall.

import java.lang.Math;
import java.text.DecimalFormat;

public class RoboticWall {
	
	static double X = 0.00d;
	static double Y = 0.00d;
	static double currentAngle = 0.0d;
	static DecimalFormat numberFormat = new DecimalFormat("#.##");
	
	public static void main(String[] s){
		//System.out.println(Math.cos(180/57.2958));
		isWall();
	}
	
	public static  void isWall(){
		
		move(10);
		rotate(90);
		move(10);
		rotate(90);
		move(10);
		rotate(90);
		move(10);
		
		System.out.println("X="+numberFormat.format(X)+"Y="+numberFormat.format(Y));
	}

	private static void rotate(double i) {
		currentAngle = currentAngle + i;
	}

	private static void move(double i) {
		
		X = X + i*Math.cos(currentAngle/57.29);
		Y = Y + i*Math.sin(currentAngle/57.29);
	}
	

}

- thakur.871 June 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Observe that the path p1 {(r0) m10, r-90, m10} has a mirror symmetry along a bisecting vector of 45 degrees (NE)

_.
  |

Observe also that p1^2 has the same mirror symmetry:

.__.
|    |

Extending this to P1^4 the path executes such that it forms a circuit around a center point.

A given path Px can be contained if for some number of executions of commands {C1, C2...} it circles some center point. Specifically if the start point s of execution1, the endpoint e of execution2, and common point c shared between execution1 and execution2 are all on the circumference of some circle of a given radius then this path carves out some
subsection of the curve of that circle.

Algorithm:

- Given P, execute Pn1 and Pn2, calculating the Start point, endpoint and the common point.
- Use 3 points formula to attempt to solve for a circle whose circumference contains the three. If no such solution exists return false else return true.

For the trivial case of P(r0, m10, r180, m10), all three points {s, e, c} are the same point and any arbitrary circle can contain any 1 point along it's circumference.

- Anonymous June 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since it can only move a maximum of X units size times, wouldn't it be always possible to build a wall? Maybe there's a constraint on the size of the wall?

- diogo.neves June 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Test

- aascrivener July 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*

A robot on a plane has 2 types of commands:
1. move forward by X units (X is integer 0 <= X <= 10000 )
2. rotate by X degrees (X is integer in range [-180, 180] )
A robot looks like

def robot(commands):
    while True:
        for command in commands:
            execute(command)

Given a list of commands (of size <= 10000) tell if it's possible to build a wall around the robot such that he will never touch it.

Example:

[move(10), rotate(180), move(10)] -> answer is yes
[move(10), rotate(45), move(10), rotate(-45), move(10), r


*/

#include "stdafx.h"
#include <iostream>
#include <cmath>

using namespace std;

class Command
{
public:
        char commandType;
        double value;
        Command(char type, double v)
        {
            commandType = type;
            value = v;
        }
};

const double PI = atan(1) * 4;

#define NUMBER_OF_COMMANDS 3

int _tmain(int argc, _TCHAR* argv[])
{
	
    Command set[NUMBER_OF_COMMANDS]={Command('m',10), Command('r',180), Command('m',10)}; //input 1
   
    //Command set[NUMBER_OF_COMMANDS]={Command('m',10), Command('r',45), Command('m',10), Command('r',-45), Command('m',10), Command('r',45)}; //input 2

   // Command set[NUMBER_OF_COMMANDS]={Command('m',10), Command('r',120), Command('m',10)}; //test input 1
    
    double x_coordinate = 0;
    double y_coordinate = 0;
    int angle = 0;
    
    //Step1: Find the resultant angle after first iteration.If the angle is 0 the boundry is not possible
    
    int resultantAngle = 0;
    for (int i = 0 ; i < NUMBER_OF_COMMANDS; i++)
    {
        if (set[i].commandType == 'r')
        {
            resultantAngle += set[i].value;
        }
    }

    resultantAngle = resultantAngle % 360;

    if (resultantAngle == 0)
    {
        cout << " Wall is not possible."; 
        return 0;
    }   

    if ( resultantAngle < 0)
    {
        resultantAngle = 360 + resultantAngle;
    }

    if (resultantAngle > 180)
    {
        resultantAngle = 360 - resultantAngle;
    }

    int numberOfIterations = 360 / resultantAngle; 

    for (int i = 0; i < numberOfIterations; i++)
    {

        for (int j = 0 ; j < NUMBER_OF_COMMANDS; j++)
        {
            if (set[j].commandType == 'r')
            {
                angle += set[j].value;               
            }
            else if (set[j].commandType == 'm')
            {
                x_coordinate = x_coordinate + set[j].value * cos(angle *PI/180);
                y_coordinate = y_coordinate + set[j].value * sin(angle *PI/180);
            }

        }

    }

    if ((x_coordinate == 0) && (y_coordinate == 0))
    {
         cout << " Wall is possible.";          
    }
    else
    {
         cout << " Wall is not possible.";      
    }

    int l;

    cin >> l;

    return 0;
}

- Sumit Khedkar August 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a hacked out solution in Haskell.

import Data.List

data Pos = Pos Int Int deriving (Eq, Show)
data State = State Pos Int deriving (Eq, Show)

initialState :: State
initialState = State (Pos 0 0) 0

degToRad :: Int -> Float
degToRad deg = (fromIntegral deg) / 360 * (2 * pi)

degCos :: Int -> Float
degCos = cos . degToRad

degSin :: Int -> Float
degSin = sin . degToRad

rotate :: Int -> State -> State
rotate rotation (State pos angle) = State pos ((angle + rotation) `mod` 360)

move :: Int -> State -> State
move distance (State (Pos x y) angle) =
    let dx = round ((degCos angle) * (fromIntegral distance))
        dy = round ((degSin angle) * (fromIntegral distance)) in

    State (Pos (x + dx) (y + dy)) angle

runCommands :: [State -> State] -> State -> State
runCommands commands state = foldl (flip ($)) state commands

containable :: [State -> State] -> Bool
containable commands = find (== initialState) (take 10000 (iterate (runCommands commands) initialState)) /= Nothing

main :: IO ()
main = do
    let commands1 = [move 10, rotate 180, move 10]
    let commands2 = [move 10, rotate 45, move 10, rotate (-45), move 10, rotate 45]

    putStrLn (show (containable commands1))
    putStrLn (show (containable commands2))

- Matt Regehr August 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- piggyback September 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- Anonymous September 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- test September 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- tedddwddd September 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 5 vote

sum of all angles == 0 (cannot build a wall, it will be infinite)
sum of all angles !=0 can build a wall

- krbchd June 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the right one.

- HRG.wea June 17, 2016 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

if the wall is a square of side 10001 (max move is 10000 and max number of commands is 10000), it will always encompass the robot. Am I missing something? I don't see any constraints on the size of the wall.

- me June 07, 2016 | 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