Katkat
Back

Implement 2048 Game Logic

GleanSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates array and matrix manipulation, stateful simulation of game mechanics, and handling edge cases such as merge constraints, single-merge-per-move rules, and empty-cell management.

Implement the core movement logic for the 2048 game.

You are given an n x n integer board where 0 represents an empty cell and every nonzero value represents a tile. Implement a method such as move(direction) that updates the board in place after a single move in one of four directions: up, down, left, or right.

The rules for one move are:

  • All tiles slide as far as possible in the chosen direction (no gaps remain between a tile and the wall or the tiles ahead of it).
  • Two adjacent tiles with the same value merge into one tile of double the value.
  • A tile may participate in at most one merge per move.
  • After sliding and merging, the remaining cells are filled with 0.
  • You do not need to implement the UI or scoring. If random new-tile spawning is needed, keep it separate from the deterministic movement logic so the move can be unit-tested.

Worked examples for a left move on a single row (the leading edge is the left wall):

  • [2, 0, 2, 0] -> [4, 0, 0, 0]
  • [2, 2, 2, 0] -> [4, 2, 0, 0]
  • [2, 2, 2, 2] -> [4, 4, 0, 0]
  • [4, 4, 2, 2] -> [8, 4, 0, 0]
  • [2, 0, 0, 2] -> [4, 0, 0, 0]

Constraints & Assumptions

  • The board is square, n x n, with n typically small (e.g. 4), but your solution should work for any n >= 1.
  • Tile values are positive powers of two; 0 denotes empty.
  • The board can have up to n*n tiles; aim for O(n^2) time and O(n) or O(1) extra space per move.
  • move mutates the board in place (or you may return the new board — state your choice). Spawning a new random tile after a move is out of scope for the deterministic logic.

Clarifying Questions to Ask

  • Should move mutate the board in place, or return a new board and leave the input untouched?
  • Does the interviewer want move to report whether the board actually changed (useful for deciding whether to spawn a new tile)?
  • Are tile values guaranteed to be powers of two, or can the board contain arbitrary integers (which would only affect merge equality, not the algorithm)?
  • Is n always 4, or must the solution generalize to arbitrary n?
  • For the merge order on left, do tiles merge starting from the leading (wall) edge? (Standard 2048 merges from the direction you push toward, so [2,2,2] → [4,2], not [2,4].)

Hints

Hint 1

Decompose the problem: Notice that a move in any direction is the **same one-dimensional operation applied to each row or column**. Solve "collapse one line toward index 0" once, then reuse it for all four directions by transforming the board so the chosen direction becomes "left".

Hint 2

The 1-D collapse: For a single line, do it in two passes to avoid double-merging: (1) drop all zeros so nonzero values are packed to the front, then (2) scan left to right and merge `line[i] == line[i+1]` into `2*line[i]`, advancing past both. A "skip the next index after a merge" flag is what enforces *at most one merge per tile per move*.

Hint 3

Reusing one line function for four directions: `left` is the line function directly. `right` is the line function applied to each **reversed** row (then reverse back). `up`/`down` apply it to **columns** — transpose the board, run the row logic, transpose back (reverse rows too for `down`). This keeps merge correctness in exactly one place.

Follow-up questions

  • Implement `isGameOver()`: return `true` when no legal move remains. The board is over when there are **no empty cells** and **no two horizontally- or vertically-adjacent equal tiles**. What is its time complexity, and can you do it without simulating all four moves?
  • Add a `canMove(direction)` / `hasMoved` signal so the caller knows when to spawn a new tile. How would you implement it cheaply inside `move`?
  • How would you unit-test the movement logic exhaustively for `n = 4`? What property-based invariants hold (e.g. tile-value sum is conserved except where merges occur, number of nonzero tiles never increases)?
  • Generalize: suppose tiles could merge in chains of three equal values, or the board were non-square. Which parts of your design stay fixed and which change?