## Google Interview Question for Software Engineer / Developers

Country: Israel
Interview Type: In-Person

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

Two parts:
1. 2D plate: 2D array of short, 0 for free, 1 for items to eat, 2 for blocks (including snake body);
2. Snake body: Queue of int pair indicating position like (x, y), every move enqueue new head position and dequeue tail position. Enqueue two nodes if a item eaten. Enqueue and dequeue operation includes set flag in its pixel.

For every move, only constant time (O(1)) needed.

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

I'm just wondering if instead of 2D array of shorts simply a HashMap would not be better. It would still ensure O(1) read/write and do not consume as much space as 2D array (unless your snake does not cover whole 2D plate).

HashMap<String,Integer>, where
key: contains position on 2D array (x,y) in a form: "x:y"
value: 0 for free; 1 for items to eat; 2 for blocks (including snake body)

Enqueue and dequeue operations add/remove/modify items in the HashMap.

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

is your queue here running in opposite direction?

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

How will you know whether the square your snake moves to is already taken up by the snake itself?

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

One very simple one comes my mind is a 2-D matrix (let's say initialized with 0s).

We keep track of head, tail and length of snake.

if head is in Right direction and so is Tail - you increment [i, n+1] col to 1 and [i, n-1] col to 0 -> to signify that snake has travelled in right direction.

if head is in Down direction and so is Tail - make [n+1, j] to 1 and [n-1, j] to 0

interesting things happen when Snake makes a turn. You can store the history of all turns made by snake. Let's say at any point in Matrix P(bendRow, bendCol) when snake was travelling left-to-right, it makes a down turn. You change direction of 'Head' to Down, but direction of 'Tail' remains the same i.e. Right. So now when snakes moves forward, you change [i, bendCol+1] as 1 and [bendRow-sankeLength-1, j]. When 'Tail' passes over P(bendRow, bendCol), you delete that point.

Sanke die events - If head hits any of the matrix boundaries or lands up on a cell with 1 (i.e. sanke body still exists there).

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

I'll go for a double linked list.

``````public class Snake{

moveR();
moveL();
moveUp();
moveDown();
{
// for each node from tail to head, update nodes.
Node tmp  = tail;
while(tmp != null){
node = node.next;
}
}
}

public class Node{
Node previus;
Node next;
int x;
int y;
}``````

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

``````moveUp()
{
}
move down()
{
}
moveR()
{
}
moveL()
{
}

validateForCrashes()
{
// check if head does not overlaps with the rest of the snake or any of the walls or any of the obstacules

while(tmp != null)
{
// check for walls
/ check for obstacules
}
}``````

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

If the snake's head moves down, it does not necessarily mean that it's tail is also moving down. Consider below case where H is head, going down and T is tail still travelling to right.
eg:

``````T=====
|
|
H``````

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

Aaand it messes up the formatting again!

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

hi Roxanne.
There is not problem at all.
The way the snake data structure (double linked list) is being updated is as follow:

The head moves: then the previus node will be equals to the old head. and the previus of the previus will be updated to the old value of the previus node and so on.
So por example:

``````N1 - N2 - N3 - N4
|
|

In the following example, the head is going left but the tail is going right and N4 should go down.
In this case, If the user press down key, then the following will happen:
1) Head will go down Y++
2) N5 will be update to the old head ( previus to be updated in step 1)
3) N4 = N5, N3= N4, N2 = N3, N1 = N2 and so on.

since each node represent a Point ( X, Y ) then It will simulate the movement of the snake.

Each move or each frame or each update will cost O(n) to repaint + The complexity to validate the integrity of the game ( crashiong, feeding, wining, lowing, pointing, etc etc etc)

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

I will use the following data structures for it:

Grid:
Array of nxn

Snake:
Queue to hold the head position and all other positions where the snake made a turn. The positions are en-queued when the head makes a turn and de-queued when the tail reaches it. This will also involve a special functionality to update the position of the head.

Items that the snake eats:

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

Using LinkedList data structure. At each movement, delete the first node and add a new node at the end.

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

1. We can have Array of int Board for the Board.
2. Hash Map data Structure - Snakes. Key value pairs Where Key will be Head of the Snake and corresponding Value will be Tail of the Snake
3. Hash Map data Structure - Ladders. Key will be Starting point of Ladder and value will be end point of Ladder

Comment hidden because of low score. Click to expand.
0
of 0 vote
I'll use map and deque. Time complexity for adding is O(1) {{{ class Point{ int x; int y; Point(int x, int y){ this.x = x; this.y = y; } } enum MapTile { BLOCK, NOTHING, APPLE } class Snake{ MapTile[][] map; Dequeue<Point> body; Snake(Point p, int width, int height){ this.map = new MapTile[width + 2][height + 2 ]; for(int i = 0; i < width + 2; i++){ map[i] = MapTile.BLOCK; map[i][height + 1] = MapTile.BLOCK; } for(int i = 0; i < height + 2; i++){ map[i] = MapTile.BLOCK; map[width + 1][i] = MapTile.BLOCK; } this.body = new Dequeue<Point>(); if(p.x < 1 || width < p.x || p.y < 1 || height < p.y) throw new Exception("Invalid Point"); this.body.addFirst(p) } void setApple(int x, int y){ if(map[x][y] == MapTile.NOTHING) map[x][y] = MapTile.APPLE; } void moveRight(){ this.move(1, 0); } void moveLeft(){ this.move(-1, 0); } void moveUp(){ this.move(0, -1); } void moveDown(){ this.move(0, 1); } boolean move(int dx, int dy){ Point first = body.getFirst(); int x = first.x + dx; int y = first.y + dy; if(map[x][y] == MapTile.BLOCK) // Can't Move return false; body.addFirst(new Point(x, y)); if(map[x][y] == MapTile.NOTING){ Point last = body.pollLast(); map[last.x][last.y] = MapTile.NOTHING; } map[x][y] = MapTile.BLOCK; return true; } } }}
Comment hidden because of low score. Click to expand.
0
of 0 vote

My snake is a double linked list of points. I used double linked list in order to append a new element in O(1). I have used java.util.LinkedList which is double linked list implementation. Game is over whenever end point hits the borders.

``````class Point {

int x;

int y;

Point(int x, int y) {
if (x < Snake.HORIZANTAL_MAX && y < Snake.VERTICAL_MAX && x > 0
&& y > 0) {
this.x = x;
this.y = y;
} else {
throw new RuntimeException("Game Over!!!");
}

}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}

@Override
public String toString() {
return "(" + x + "," + y + ")";
}

}

class Snake {

static final int HORIZANTAL_MAX = 100; // border of x axis
static final int VERTICAL_MAX = 100; // border of y axis

this.points = points;
}

int length() {
return points.size();
}

void checkCollision(Point point) {
if (points.contains(point)) {
throw new RuntimeException("Game Over!!!");
}
}

void moveRight(boolean grow) {
Point endPoint = points.get(length() - 1);
Point newEndPoint = new Point(endPoint.x + 1, endPoint.y);
checkCollision(newEndPoint);
if (!grow) {
points.remove(0);
}

}

void moveUp(boolean grow) {
Point endPoint = points.get(length() - 1);
Point newEndPoint = new Point(endPoint.x, endPoint.y - 1);
checkCollision(newEndPoint);
if (!grow) {
points.remove(0);
}

}

void moveDown(boolean grow) {
Point endPoint = points.get(length() - 1);
Point newEndPoint = new Point(endPoint.x, endPoint.y + 1);
checkCollision(newEndPoint);
if (!grow) {
points.remove(0);
}
}

void moveLeft(boolean grow) {
Point endPoint = points.get(length() - 1);
Point newEndPoint = new Point(endPoint.x - 1, endPoint.y);
checkCollision(newEndPoint);
if (!grow) {
points.remove(0);
}
}

@Override
public String toString() {
StringBuilder buf = new StringBuilder();
for (Point p : points) {
buf.append(p + " ");
}
return buf.toString();
}
}``````

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

Solution documented here:
amitcodes.com/2014/01/26/design-the-nokia-snake-game/

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

``````package google;

import java.util.HashMap;
import java.util.ListIterator;

public interface SnakeGame
{
void move(direction dir) throws Exception;
int getScore();
}

enum direction
{
RIGHT,
LEFT,
UP,
DOWN
}

class Node
{
public direction dir;
public int xPos;
public int yPos;
}

class SnakeGameImpl implements SnakeGame{

private HashMap<Integer, Integer> boundary;

public SnakeGameImpl(int xlength, int ylength, Node animal)
{
for(int i=0; i<xlength; i++)
{
for(int j=0; j<ylength; j++)
{
if(i==0 || i==xlength-1 || j==0 || j==ylength-1)
boundary.put(xlength, ylength);
}
}
}

@Override
public int getScore() {
// TODO Auto-generated method stub
return 0;
}

@Override
public void move(direction dir) throws Exception {

//moving to opposite direction is not permitted
if((head.dir == direction.UP && dir == dir.DOWN) ||(head.dir == direction.DOWN && dir == dir.UP)
|| (head.dir == direction.RIGHT && dir == dir.LEFT) || (head.dir == direction.LEFT && dir == dir.RIGHT))
{
throw new Exception("Invalid Move");
}
else
{

if(dir == direction.UP)
else if(dir == direction.DOWN)
else if(dir == direction.RIGHT)
else

throw new Exception("You've hit the wall, Game over!!!");

}
}

private void makeMove(Node head) throws Exception
{
Node prev, cur;
ListIterator<Node> itr = snake.listIterator();
while(itr.hasNext())
{
cur = itr.next();
throw new Exception("You've bite yourself, game over!!! ");
cur.xPos = prev.xPos;
cur.yPos = prev.yPos;
cur.dir = prev.dir;
prev = cur;
}
}

@Override
public void eat(Node head) throws Exception
{
Node animal = generateAnimalAtRandomPosition();

{
Node last = snake.peekLast();
throw new Exception("You've bite yourself, game over!!! ");
}
}

private Node generateAnimalAtRandomPosition() {
// generate animal node at random position
return new Node();
}

private boolean bitesItself(Node node, Node head)
{
}

private boolean hitsWall(Node node)
{
return boundary.get(node.xPos)==node.yPos;
}

}``````

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

Snake is the game of snakes and ladders over the board of squares numbered row wise. The game can have two or more players. All the players start at the position 1 and target is to reach 100 in the board of 10x10. Turn wise, each player throws a dice of 8 numbers and makes a move by number of positions according to dice number. The player who reaches the goal last loses.

SnakeGame -> Board
-> Player
-> Dice
: PlayerPositions,
: PlayerTurn

Board -> Positions

``````class SnakeGame
{
class Board;
List<Player> playerList;
class Dice;
public int getPlayerTurn();
public int movePlayerPosition(int playerId, int positions);
public int getLoser();
}

class Board
{
Position positions[][];
}
class Position
{
int row, col;
int type;
Position endPosition;
}

class Dice
{
int numSides;
public int throwDice();
}

class Player
{
String name;
int age;
}``````

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

queue for snake
bool array for the field (not the most memory effective, but anyway)

``````package andmed;

import java.util.ArrayDeque;
import java.util.Deque;

public class Snake {
public static final int FIELD_DIMENSION = 10;
public static final int MOVES_TO_GROW_SNAKE = 3;
public static final long PAUSE = 500L;
public static final int NUM_OF_BLOCKS = 1;

int numOfBlocks = NUM_OF_BLOCKS;
boolean[][] field;

Deque<Pos> snake = new ArrayDeque<>();
Pos lastPos;

public void go()  {
field = setupField();
updateField();
Pos lastPos = new Pos(FIELD_DIMENSION /2, FIELD_DIMENSION /2);
try {
for (int i = 0; ; i++) { //moves
if (i % MOVES_TO_GROW_SNAKE != 0) { //every n-th move make snake bigger
snake.removeLast();
}
if (tryNextMove()) break;
updateField();
try {
} catch (Exception e) {
}
}
System.out.println("You win!");
} catch (Exception e) {
System.out.println(e);
}
System.out.println("Game Over");
}

private static boolean[][] setupField() {
boolean field[][] = new boolean[FIELD_DIMENSION][FIELD_DIMENSION];
for (int i = 0; i < NUM_OF_BLOCKS; i++) {
int x = (int)(Math.random() * FIELD_DIMENSION);
int y = (int)(Math.random() * FIELD_DIMENSION);
field[x][y] = true;
System.out.println("Block added at: " + x + " " + y);
}
return field;
}

private boolean tryNextMove() throws Exception {
Pos current = snake.getFirst();
Pos nextGuess;
do {
int move = (int) (Math.random() * 4);
switch (move) {
case 0: //east
nextGuess = new Pos(current.x + 1, current.y);
break;
case 1://south
nextGuess = new Pos(current.x, current.y - 1);
break;
case 2: //west
nextGuess = new Pos(current.x - 1, current.y);
break;
default://north
nextGuess = new Pos(current.x, current.y + 1);
}
} while (nextGuess.equals(lastPos));
final Pos next = nextGuess;
if (snake.stream().anyMatch(pos -> pos.equals(next))) throw new GameOver("overlap at " + next.x + " " + next.y);
if (next.x > FIELD_DIMENSION - 1 || next.x < 0 || next.y > FIELD_DIMENSION - 1 || next.y < 0)
throw new GameOver("out of border" + next.x + " " + next.y);
if (field[next.x][next.y]) {
numOfBlocks--;
field[next.x][next.y] = false;
System.out.println("Nyam-nyam.");
// make weird sound;
}
updateField();
lastPos = current;
return numOfBlocks == 0 ? true : false;
}

private void updateField() {
snake.descendingIterator().forEachRemaining(pos -> System.out.print(pos.x + " " + pos.y + "; "));
System.out.println();
}

private static class GameOver extends Exception {
public GameOver(String msg) {
super(msg);
}
}

private static class Pos {
int x;
int y;

public Pos(int x, int y) {
this.x = x;
this.y = y;
}

public boolean equals(Object o) {
if (o == null || o.getClass() != getClass()) return false;
Pos otherPos = (Pos) o;
return (this.x == otherPos.x && this.y == otherPos.y);
}
}

public static void main(String[] args) throws Exception {
Snake snake = new Snake();
snake.go();
}
}``````

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

queue for snake
bool array for the field (not the most memory effective, but anyway)

``````package andmed;

import java.util.ArrayDeque;
import java.util.Deque;

public class Snake {
public static final int FIELD_DIMENSION = 10;
public static final int MOVES_TO_GROW_SNAKE = 3;
public static final long PAUSE = 500L;
public static final int NUM_OF_BLOCKS = 1;

int numOfBlocks = NUM_OF_BLOCKS;
boolean[][] field;

Deque<Pos> snake = new ArrayDeque<>();
Pos lastPos;

public void go()  {
field = setupField();
updateField();
Pos lastPos = new Pos(FIELD_DIMENSION /2, FIELD_DIMENSION /2);
try {
for (int i = 0; ; i++) { //moves
if (i % MOVES_TO_GROW_SNAKE != 0) { //every n-th move make snake bigger
snake.removeLast();
}
if (tryNextMove()) break;
updateField();
try {
} catch (Exception e) {
}
}
System.out.println("You win!");
} catch (Exception e) {
System.out.println(e);
}
System.out.println("Game Over");
}

private static boolean[][] setupField() {
boolean field[][] = new boolean[FIELD_DIMENSION][FIELD_DIMENSION];
for (int i = 0; i < NUM_OF_BLOCKS; i++) {
int x = (int)(Math.random() * FIELD_DIMENSION);
int y = (int)(Math.random() * FIELD_DIMENSION);
field[x][y] = true;
System.out.println("Block added at: " + x + " " + y);
}
return field;
}

private boolean tryNextMove() throws Exception {
Pos current = snake.getFirst();
Pos nextGuess;
do {
int move = (int) (Math.random() * 4);
switch (move) {
case 0: //east
nextGuess = new Pos(current.x + 1, current.y);
break;
case 1://south
nextGuess = new Pos(current.x, current.y - 1);
break;
case 2: //west
nextGuess = new Pos(current.x - 1, current.y);
break;
default://north
nextGuess = new Pos(current.x, current.y + 1);
}
} while (nextGuess.equals(lastPos));
final Pos next = nextGuess;
if (snake.stream().anyMatch(pos -> pos.equals(next))) throw new GameOver("overlap at " + next.x + " " + next.y);
if (next.x > FIELD_DIMENSION - 1 || next.x < 0 || next.y > FIELD_DIMENSION - 1 || next.y < 0)
throw new GameOver("out of border" + next.x + " " + next.y);
if (field[next.x][next.y]) {
numOfBlocks--;
field[next.x][next.y] = false;
System.out.println("Nyam-nyam.");
// make weird sound;
}
updateField();
lastPos = current;
return numOfBlocks == 0 ? true : false;
}

private void updateField() {
snake.descendingIterator().forEachRemaining(pos -> System.out.print(pos.x + " " + pos.y + "; "));
System.out.println();
}

private static class GameOver extends Exception {
public GameOver(String msg) {
super(msg);
}
}

private static class Pos {
int x;
int y;

public Pos(int x, int y) {
this.x = x;
this.y = y;
}

public boolean equals(Object o) {
if (o == null || o.getClass() != getClass()) return false;
Pos otherPos = (Pos) o;
return (this.x == otherPos.x && this.y == otherPos.y);
}
}

public static void main(String[] args) throws Exception {
Snake snake = new Snake();
snake.go();
}
}``````

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

queue for snake
bool array for the field (not the most memory effective, but anyway)

``````package andmed;

import java.util.ArrayDeque;
import java.util.Deque;

public class Snake {
public static final int FIELD_DIMENSION = 10;
public static final int MOVES_TO_GROW_SNAKE = 3;
public static final long PAUSE = 500L;
public static final int NUM_OF_BLOCKS = 1;

int numOfBlocks = NUM_OF_BLOCKS;
boolean[][] field;

Deque<Pos> snake = new ArrayDeque<>();
Pos lastPos;

public void go()  {
field = setupField();
updateField();
Pos lastPos = new Pos(FIELD_DIMENSION /2, FIELD_DIMENSION /2);
try {
for (int i = 0; ; i++) { //moves
if (i % MOVES_TO_GROW_SNAKE != 0) { //every n-th move make snake bigger
snake.removeLast();
}
if (tryNextMove()) break;
updateField();
try {
} catch (Exception e) {
}
}
System.out.println("You win!");
} catch (Exception e) {
System.out.println(e);
}
System.out.println("Game Over");
}

private static boolean[][] setupField() {
boolean field[][] = new boolean[FIELD_DIMENSION][FIELD_DIMENSION];
for (int i = 0; i < NUM_OF_BLOCKS; i++) {
int x = (int)(Math.random() * FIELD_DIMENSION);
int y = (int)(Math.random() * FIELD_DIMENSION);
field[x][y] = true;
System.out.println("Block added at: " + x + " " + y);
}
return field;
}

private boolean tryNextMove() throws Exception {
Pos current = snake.getFirst();
Pos nextGuess;
do {
int move = (int) (Math.random() * 4);
switch (move) {
case 0: //east
nextGuess = new Pos(current.x + 1, current.y);
break;
case 1://south
nextGuess = new Pos(current.x, current.y - 1);
break;
case 2: //west
nextGuess = new Pos(current.x - 1, current.y);
break;
default://north
nextGuess = new Pos(current.x, current.y + 1);
}
} while (nextGuess.equals(lastPos));
final Pos next = nextGuess;
if (snake.stream().anyMatch(pos -> pos.equals(next))) throw new GameOver("overlap at " + next.x + " " + next.y);
if (next.x > FIELD_DIMENSION - 1 || next.x < 0 || next.y > FIELD_DIMENSION - 1 || next.y < 0)
throw new GameOver("out of border" + next.x + " " + next.y);
if (field[next.x][next.y]) {
numOfBlocks--;
field[next.x][next.y] = false;
System.out.println("Nyam-nyam.");
// make weird sound;
}
updateField();
lastPos = current;
return numOfBlocks == 0 ? true : false;
}

private void updateField() {
snake.descendingIterator().forEachRemaining(pos -> System.out.print(pos.x + " " + pos.y + "; "));
System.out.println();
}

private static class GameOver extends Exception {
public GameOver(String msg) {
super(msg);
}
}

private static class Pos {
int x;
int y;

public Pos(int x, int y) {
this.x = x;
this.y = y;
}

public boolean equals(Object o) {
if (o == null || o.getClass() != getClass()) return false;
Pos otherPos = (Pos) o;
return (this.x == otherPos.x && this.y == otherPos.y);
}
}

public static void main(String[] args) throws Exception {
Snake snake = new Snake();
snake.go();
}``````

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.