Below are interview questions asked in first two rounds of my interview at Atlassian for SDE-2 role.
First Round Question:
Remember the old phone game of Snake?
The snake can move up, down, left or right in a 2-dimensional board of arbitrary size.
Let’s try to implement the base logic of this game.
Rules:
Every time moveSnake() is called, the snake moves up, down, left or right
The snake’s initial size is 3 and grows by 1 every 5 moves
The game ends when the snake hits itself
interface SnakeGame {
moveSnake(snakeDirection);
isGameOver();
}// Assume:
- moveSnake is valid.
- Board size is limited.
- Board is square.
- Snake moves only when moveSnake is called.
- Game ends when snake hits itself.
// Entity:
Snake - Deque of coordinates
GameBoard - 2D array of coordinates
// Algorithm:
For collision check - Set of coordinates
LinkedHashSet -
- Insertion: O(1), add(E e) -> Adds at the end
- Removal: O(1)
- Contains: O(1)
My Approach:
import java.util.*;
enum Direction {
UP, DOWN, LEFT, RIGHT;
}
class Position {
int x, y;
Position(int x, int y) {
this.x = x;
this.y = y;
}
Position move(Direction dir, int boardSize) {
Position newPos = null;
switch (dir) {
case UP -> {
int newX = x - 1;
if (newX < 0) newX = boardSize - 1;
newPos = new Position(newX, y);
}
case DOWN -> {
int newX = x + 1;
if (newX == boardSize) newX = 0;
newPos = new Position(newX, y);
}
case LEFT -> {
int newY = y - 1;
if (newY < 0) newY = boardSize - 1;
newPos = new Position(x, newY);
}
case RIGHT -> {
int newY = y + 1;
if (newY == boardSize) newY = 0;
newPos = new Position(x, newY);
}
};
return newPos;
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Position newPos)) return false;
return (this.x == newPos.x && this.y == newPos.y);
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
interface SnakeGame {
void moveSnake(Direction dir);
boolean isGameOver();
}
class SnakeGameImpl implements SnakeGame {
public final int snakeInitialSize;
public final int size;
public final Deque<Position> body;
public final Set<Position> bodySet;
public boolean gameOver = false;
public int move;
public SnakeGameImpl(int boardSize) {
this.size = boardSize;
this.body = new LinkedList<>(); // Note: Last position denotes head
this.bodySet = new HashSet<>();
this.move = 0;
this.snakeInitialSize = 3;
// Initialize snake of size `snakeInitialSize`
initializeSnake(this.snakeInitialSize);
}
private void initializeSnake(int snakeSize) {
for (int i=0; i<snakeSize; ++i) {
// TODO: Make it random
Position pos = new Position(0, i);
this.body.addLast(pos);
this.bodySet.add(pos);
}
}
/*
Time Comp: O(1)
Space Comp: O(N*N), where N is size of Board.
*/
@Override
public void moveSnake(Direction dir) {
if (gameOver) return;
Position currHead = body.peekLast();
Position newHead = currHead.move(dir, this.size);
// check for collision
if (bodySet.contains(newHead)) {
gameOver = true;
return;
}
Position tail = body.peekFirst();
boolean isGrow = (++move %5 == 0);
if (!isGrow) {
body.pollFirst();
bodySet.remove(tail);
}
body.addLast(newHead);
bodySet.add(newHead);
}
@Override
public boolean isGameOver() {
return gameOver;
}
public void printSnake() {
for (Position pos : body) {
System.out.printf(pos.x + " " + pos.y + ", ");
}
System.out.println();
// System.out.println("Snake: " + body);
}
}
public class Main {
public static void main(String[] args) {
int boardSize = 6;
SnakeGameImpl game = new SnakeGameImpl(boardSize);
game.printSnake();
Direction[] moves = {
Direction.RIGHT,
Direction.RIGHT,
Direction.RIGHT,
Direction.RIGHT,
Direction.DOWN,
Direction.LEFT,
Direction.UP,
};
for (Direction dir : moves) {
game.moveSnake(dir);
game.printSnake();
if (game.isGameOver()) {
System.out.println("Game Over");
break;
}
}
}
}Second Round Question:
interface MostPopular {
void increasePopularity(Integer contentId);
Integer mostPopular();
void decreasePopularity(Integer contentId);
}Sample execution:
[
popularityTracker.increasePopularity(7);
popularityTracker.increasePopularity(7);
popularityTracker.increasePopularity(8);
popularityTracker.mostPopular(); // returns 7
popularityTracker.increasePopularity(8);
popularityTracker.increasePopularity(8);
popularityTracker.mostPopular(); // returns 8
popularityTracker.decreasePopularity(8);
popularityTracker.decreasePopularity(8);
popularityTracker.mostPopular(); // returns 7
popularityTracker.decreasePopularity(7);
popularityTracker.decreasePopularity(7);
popularityTracker.decreasePopularity(8);
popularityTracker.mostPopular(); // returns -1 since there is no content with popularity greater than 0
]// Most popular means, contentId with heighest popularity value.
Assumptions:
- In case of a tie: -> Return any contentId
- Popularity of contentId can never go below zero.
Follow-up
- Return the most recent mostPopular contentId changed
My Approach:
import java.util.*;
interface MostPopular {
void increasePopularity(Integer contentId);
Integer mostPopular();
void decreasePopularity(Integer contentId);
}
class PopularityTracker implements MostPopular {
private final HashMap<Integer, Integer> popularityMap;
private final TreeMap<Integer, HashSet<Integer>> popularityToContentMap;
// This map is only required for follow-up question.
private final HashMap<Integer, Integer> mostRecentMap;
PopularityTracker() {
popularityMap = new HashMap<>();
mostRecentMap = new HashMap<>();
popularityToContentMap = new TreeMap<>();
}
@Override
public void increasePopularity(Integer contentId) {
int oldPopularity = popularityMap.getOrDefault(contentId, 0);
int newPopularity = oldPopularity + 1;
if (oldPopularity > 0) {
HashSet<Integer> oldSetContents = popularityToContentMap.get(oldPopularity);
oldSetContents.remove(contentId);
if (oldSetContents.isEmpty()) {
popularityToContentMap.remove(oldPopularity);
}
}
popularityToContentMap.computeIfAbsent(newPopularity, k -> new HashSet<>()).add(contentId);
popularityMap.put(contentId, newPopularity);
mostRecentMap.put(newPopularity, contentId);
}
@Override
public Integer mostPopular() {
System.out.println(popularityToContentMap);
System.out.println("most recent map");
System.out.println(mostRecentMap);
if (popularityToContentMap.isEmpty())
return -1;
// Code for first implementation
// return popularityToContentMap.lastEntry().getValue().iterator().next();
// Code change after follow-up
return mostRecentMap.get(popularityToContentMap.lastEntry().getKey());
}
@Override
public void decreasePopularity(Integer contentId) {
int oldPopularity = popularityMap.get(contentId);
int newPopularity = oldPopularity - 1;
HashSet<Integer> oldSetContents = popularityToContentMap.get(oldPopularity);
oldSetContents.remove(contentId);
if (oldSetContents.isEmpty()) {
popularityToContentMap.remove(oldPopularity);
}
if (newPopularity > 0) {
popularityToContentMap.computeIfAbsent(newPopularity, k -> new HashSet<>()).add(contentId);
popularityMap.put(contentId, newPopularity);
mostRecentMap.put(newPopularity, contentId);
} else {
popularityMap.remove(contentId);
}
}
}
public class Main {
public static void main(String[] args) {
PopularityTracker popularityTracker = new PopularityTracker();
popularityTracker.increasePopularity(7);
popularityTracker.increasePopularity(8);
System.out.println(popularityTracker.mostPopular()); // returns 8
popularityTracker.increasePopularity(8);
popularityTracker.increasePopularity(7);
System.out.println(popularityTracker.mostPopular()); // returns 7
popularityTracker.decreasePopularity(8);
popularityTracker.decreasePopularity(7);
System.out.println(popularityTracker.mostPopular()); // returns 7, since 7
}
}Comments (6)