How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citadel during technical interviews.

Simulate 2048 and pack board into uint64

Quick Overview

This question evaluates proficiency in implementing deterministic game-state logic and compact binary representations, specifically array manipulation and merge semantics for 2048 slide operations plus bit-level packing/unpacking of 4-bit exponent fields.

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem: 2048 move simulation + board compression You are implementing part of the **2048** game on a fixed **4×4** grid. ### Part A — Simulate a move Given a 4×4 board of non-negative integers (each is either 0 or a power of two), implement a function: - `move(board, dir) -> new_board` where `dir ∈ {LEFT, RIGHT, UP, DOWN}`. **Rules** (standard 2048): 1. All tiles slide as far as possible in the chosen direction. 2. If two adjacent tiles in the direction of movement have the same value, they merge into one tile of value `2x`. 3. Each tile can merge **at most once per move**. 4. Zeros represent empty cells. ### Part B — Encode/decode the board into a 64-bit integer Implement two functions: - `encode(board) -> uint64` - `decode(x) -> board` Constraints/assumptions for encoding: - The board is 4×4 = 16 cells. - Store each cell in **4 bits** as the exponent `e` where value = `2^e`. - Empty cell (0) is stored as `e = 0`. - Example: value 2 → e=1, 4 → e=2, … - Assume no cell exceeds `2^15` (so exponent fits in 4 bits). - You may choose any fixed cell order (e.g., row-major), but `decode(encode(board))` must reproduce the original board. ### Deliverables Describe/implement `move`, `encode`, and `decode` with correct handling of merges and bit packing.

Quick Answer: This question evaluates proficiency in implementing deterministic game-state logic and compact binary representations, specifically array manipulation and merge semantics for 2048 slide operations plus bit-level packing/unpacking of 4-bit exponent fields.

Part 1: Simulate a 2048 Move

You are given a 4x4 2048 board and a move direction. Return the board after applying exactly one move in that direction. Use the standard 2048 rules: 1. Tiles slide as far as possible in the chosen direction. 2. Equal adjacent tiles merge into one tile with double the value. 3. A tile can merge at most once during the move. 4. Zeros represent empty cells. 5. Do not add a new random tile after the move. Implement a function solution(board, direction) that returns the new 4x4 board.

Constraints

board is always 4x4
Each cell is 0 or a power of two
direction is one of 'LEFT', 'RIGHT', 'UP', 'DOWN'
You must follow the rule that each tile merges at most once per move

Examples

Input: ([[2, 0, 2, 4], [0, 4, 4, 8], [2, 2, 2, 2], [0, 0, 0, 2]], 'LEFT')

Expected Output: [[4, 4, 0, 0], [8, 8, 0, 0], [4, 4, 0, 0], [2, 0, 0, 0]]

Explanation: Each row is compressed to the left, with equal adjacent tiles merging once.

Input: ([[2, 2, 2, 0], [4, 0, 4, 4], [2, 2, 4, 4], [0, 0, 0, 0]], 'RIGHT')

Expected Output: [[0, 0, 2, 4], [0, 0, 4, 8], [0, 0, 4, 8], [0, 0, 0, 0]]

Explanation: Merges happen from the side of movement, and no tile merges twice.

Input: ([[2, 0, 2, 2], [2, 4, 0, 2], [4, 4, 2, 0], [4, 0, 2, 2]], 'UP')

Expected Output: [[4, 8, 4, 4], [8, 0, 2, 2], [0, 0, 0, 0], [0, 0, 0, 0]]

Explanation: Process each column as if it were a row moving left, then rebuild the board.

Input: ([[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], 'DOWN')

Expected Output: [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Explanation: Edge case: an empty board stays unchanged.

Solution

def solution(board, direction):
    def merge_line(line):
        nums = [x for x in line if x != 0]
        merged = []
        i = 0
        while i < len(nums):
            if i + 1 < len(nums) and nums[i] == nums[i + 1]:
                merged.append(nums[i] * 2)
                i += 2
            else:
                merged.append(nums[i])
                i += 1
        merged.extend([0] * (4 - len(merged)))
        return merged

    if direction == 'LEFT':
        return [merge_line(row) for row in board]

    if direction == 'RIGHT':
        return [list(reversed(merge_line(list(reversed(row))))) for row in board]

    if direction == 'UP':
        cols = list(zip(*board))
        merged_cols = [merge_line(list(col)) for col in cols]
        return [list(row) for row in zip(*merged_cols)]

    if direction == 'DOWN':
        cols = list(zip(*board))
        merged_cols = [list(reversed(merge_line(list(reversed(col))))) for col in cols]
        return [list(row) for row in zip(*merged_cols)]

    raise ValueError('Invalid direction')

Time complexity: O(1). Space complexity: O(1).

Hints

Write a helper that processes a single line moving left: remove zeros, merge equal neighbors once, then pad with zeros.
You can reuse the same helper for RIGHT, UP, and DOWN by reversing rows or working column-by-column.

Part 2: Encode and Decode a 4x4 2048 Board into 64 Bits

A 4x4 2048 board has 16 cells, so it can fit into 64 bits if each cell uses 4 bits. For each cell, store the exponent e instead of the tile value: - 0 is stored as e = 0 - 2 is stored as e = 1 - 4 is stored as e = 2 - in general, value = 2^e Use row-major order, and store cell index k = 4 * row + col in bits [4k, 4k+3] of the integer. Implement solution(board) that: 1. encodes the board into an integer 2. decodes that integer back into a board 3. returns a tuple (encoded, decoded_board) The decoded board must exactly match the original board.

Constraints

board is always 4x4
Each cell is 0 or a power of two
No cell exceeds 32768, so its exponent fits in 4 bits
Use row-major order with cell index k = 4 * row + col

Examples

Input: ([[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]])

Expected Output: (0x0, [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]])

Explanation: Edge case: all empty cells produce the integer 0.

Input: ([[2, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]])

Expected Output: (0x1, [[2, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]])

Explanation: The top-left cell has exponent 1, stored in the least-significant 4 bits.

Input: ([[2, 4, 8, 16], [0, 0, 0, 0], [32, 64, 128, 256], [512, 1024, 2048, 4096]])

Expected Output: (0xCBA9876500004321, [[2, 4, 8, 16], [0, 0, 0, 0], [32, 64, 128, 256], [512, 1024, 2048, 4096]])

Explanation: The exponents in row-major order are 1,2,3,4,0,0,0,0,5,6,7,8,9,10,11,12.

Input: ([[32768, 32768, 32768, 32768], [32768, 32768, 32768, 32768], [32768, 32768, 32768, 32768], [32768, 32768, 32768, 32768]])

Expected Output: (0xFFFFFFFFFFFFFFFF, [[32768, 32768, 32768, 32768], [32768, 32768, 32768, 32768], [32768, 32768, 32768, 32768], [32768, 32768, 32768, 32768]])

Explanation: Boundary case: exponent 15 in every cell fills all 16 nibbles with F.

Solution

def solution(board):
    encoded = 0

    for r in range(4):
        for c in range(4):
            value = board[r][c]
            exponent = 0 if value == 0 else value.bit_length() - 1
            index = 4 * r + c
            encoded |= exponent << (4 * index)

    decoded = [[0] * 4 for _ in range(4)]
    for index in range(16):
        exponent = (encoded >> (4 * index)) & 0xF
        decoded[index // 4][index % 4] = 0 if exponent == 0 else 1 << exponent

    return encoded, decoded

Time complexity: O(1). Space complexity: O(1).

Hints

For a non-zero power of two, the exponent can be found with bit_length() - 1.
To pack cell k, shift its 4-bit exponent left by 4 * k. To unpack, mask with 0xF after shifting right.

Quick Overview