Google Interview Question
Software Engineer / DevelopersCountry: Israel
Interview Type: In-Person
@wenhanl your solution is good.
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.
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).
I'll go for a double linked list.
public class Snake{
Node head;
moveR();
moveL();
moveUp();
moveDown();
updateSnake()
{
// 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;
}
moveUp()
{
head.y++;
}
move down()
{
head.y--;
}
moveR()
{
head.x++;
}
moveL()
{
head.x--;
}
validateForCrashes()
{
// check if head does not overlaps with the rest of the snake or any of the walls or any of the obstacules
Node tmp = head.previus;
while(tmp != null)
{
if(head.x ==tmp.x && head.y==tmp.y) return FALSE; // CRASHED
// check for walls
/ check for obstacules
}
}
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
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
|
|
<=Head- N5
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)
What about that?
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:
A linked list
1. We can have Array of int Board[99] 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
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
LinkedList<Point> points;
Snake(LinkedList<Point> points) {
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);
}
points.add(newEndPoint);
}
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);
}
points.add(newEndPoint);
}
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);
}
points.add(newEndPoint);
}
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);
}
points.add(newEndPoint);
}
@Override
public String toString() {
StringBuilder buf = new StringBuilder();
for (Point p : points) {
buf.append(p + " ");
}
return buf.toString();
}
}
package google;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.ListIterator;
public interface SnakeGame
{
void move(direction dir) throws Exception;
void eat(Node head) 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 LinkedList<Node> snake;
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 {
Node head = snake.peekFirst();
//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
{
head.dir = dir;
if(dir == direction.UP)
head.yPos--;
else if(dir == direction.DOWN)
head.yPos++;
else if(dir == direction.RIGHT)
head.yPos++;
else
head.yPos--;
if(hitsWall(head))
throw new Exception("You've hit the wall, Game over!!!");
eat(head);
makeMove(head);
}
}
private void makeMove(Node head) throws Exception
{
Node prev, cur;
prev = head;
ListIterator<Node> itr = snake.listIterator();
while(itr.hasNext())
{
cur = itr.next();
if(bitesItself(cur, head))
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();
if(animal.xPos==head.xPos && animal.yPos==head.yPos)
{
Node last = snake.peekLast();
Node addn = new Node();
addn.xPos = last.xPos;
addn.yPos = last.yPos;
addn.dir = last.dir;
snake.add(addn);
if(bitesItself(addn, head))
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)
{
return node.xPos == head.xPos && node.yPos == head.yPos;
}
private boolean hitsWall(Node node)
{
return boundary.get(node.xPos)==node.yPos;
}
}
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
Position : Type(Snake/Ladder), EndPosition
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;
}
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);
snake.addFirst(lastPos);
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 {
Thread.sleep(PAUSE);
} 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;
}
snake.addFirst(next);
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();
}
}
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);
snake.addFirst(lastPos);
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 {
Thread.sleep(PAUSE);
} 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;
}
snake.addFirst(next);
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();
}
}
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);
snake.addFirst(lastPos);
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 {
Thread.sleep(PAUSE);
} 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;
}
snake.addFirst(next);
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();
}
Two parts:
- wenhanl January 03, 20141. 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.