Citadel·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Citadel SWE interview threw a 2048 simulation problem at me, which I did not expect at all. Two parts: implement the actual game move logic, then encode the whole board into a 64-bit integer. Felt like a systems-y puzzle dressed up as a game, and I had mixed feelings about how I handled the encoding half.

Questions Asked (2)

Implement a move function for the 2048 game on a 4x4 grid. Given a board and a direction (left, right, up, down), return the new board state after applying standard 2048 slide-and-merge rules.

Algorithms & Data Structures

Author's notes

The sliding part was fine, I just treated each row or column as a 1D array and wrote a helper to compact it left.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the rules: tiles slide as far as possible in the chosen direction, and when two tiles of the same value collide, they merge into one tile with double the value, with each tile merging at most once per move. Then, implement a helper function to process a single row (or column) by removing zeros, merging adjacent equal values from the direction of movement, and padding with zeros. Finally, apply this helper to all rows or columns based on the direction, using transposition and reversal to reuse the same logic.

Pro tip: Write a helper that processes a single line (row or column) in the left direction, then for other directions, transform the board (reverse rows for right, transpose for up/down) so you can reuse the same helper. This reduces code duplication and potential bugs.

1. Clarify rules and edge cases

Confirm the exact merging rules: each tile can merge only once per move, and merges happen in the direction of movement. Discuss edge cases like empty board, no possible moves, and multiple merges in a line.

2. Design a line-processing helper

Create a function that takes a list of 4 integers and returns the list after sliding and merging to the left. This involves removing zeros, merging adjacent equal values, and padding with zeros.

3. Generalize to all directions

For left, apply the helper to each row. For right, reverse each row, apply the helper, then reverse back. For up/down, transpose the board, apply the row helper, then transpose back.

4. Implement and test

Write the code, ensuring in-place or new board creation as required. Test with various cases: simple slides, merges, multiple merges, and no-op moves.

5. Analyze complexity and optimize

Discuss time and space complexity: O(16) operations per move, which is constant. Mention potential optimizations like early termination if board unchanged.

Key Points to Mention

Each tile can merge at most once per move (e.g., [2,2,2,2] left becomes [4,4,0,0], not [8,0,0,0]).
Merges happen in the direction of movement, so order matters when processing a line.
Use a helper function for a single line to avoid code duplication.
Transform the board for different directions: reverse rows for right, transpose for up/down.
Time complexity is O(1) since the board size is fixed (4x4), but generally O(n^2) for an n x n board.
Consider edge cases: empty board, no merges possible, and moves that don't change the board.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Implement encode and decode functions that pack a 4x4 2048 board into a single 64-bit integer and recover it losslessly. Each cell should be stored as a 4-bit exponent.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This part I actually liked more than the move simulation.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Treat the 4x4 board as a 16-cell array where each cell's exponent (0-15) is packed into 4 bits of a 64-bit integer. Use bitwise shifts and masks to encode each cell at position i*4, and decode by extracting 4-bit chunks. Discuss edge cases like maximum exponent (15) and ensure lossless round-trip.

Pro tip: Mention that this compact representation enables efficient board hashing and memoization in game AI, and that using unsigned 64-bit integers avoids sign-extension issues during bitwise operations.

1. Clarify requirements and constraints

Confirm that each cell stores an exponent from 0 to 15 (since 2^15 = 32768, typical for 2048), and that the 64-bit integer must be lossless. Ask if the board is always 4x4 and if any cell can exceed 15.

2. Design the encoding scheme

Map each cell (row-major order) to a 4-bit field at bit position i*4. Use bitwise OR with shifted values to pack all cells into a single uint64_t.

3. Implement encode function

Iterate over the 16 cells, compute the exponent (e.g., log2(value) or stored directly), and set the corresponding 4 bits using bitwise operations: encoded |= (exponent << (i*4)).

4. Implement decode function

Extract each 4-bit chunk by shifting right and masking with 0xF: exponent = (encoded >> (i*4)) & 0xF. Reconstruct the board by converting exponent back to value (1 << exponent).

5. Test and discuss trade-offs

Verify round-trip correctness with edge cases (all zeros, max exponents). Discuss trade-offs: compactness vs. readability, and potential use in game state hashing or network transmission.

Key Points to Mention

Bitwise operations: shifts, masks, and OR to pack/unpack 4-bit fields.
Use of unsigned 64-bit integer to avoid sign-extension and ensure portability.
Row-major ordering for consistent cell-to-bit mapping.
Handling of exponent 0 (empty cell) and maximum exponent 15 (value 32768).
Lossless round-trip verification and edge case testing.
Practical applications: efficient board hashing, memoization in AI, and compact storage.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.