Game Specific Coding Problems Questions

Coding and algorithmic interview problems framed in game development contexts. Typical tasks include implementing pathfinding algorithms such as A star and Dijkstra, collision detection techniques including axis aligned bounding box and circle collisions and swept collisions, finite state machines and hierarchical state machines for game logic, sorting strategies for rendering, wave spawning and scheduling systems, inventory management and event queue implementations, player ranking and matchmaking algorithms, and simple physics calculations or coordinate transformations. Candidates should be able to translate game requirements into appropriate data structures and algorithms, reason about time and space complexity, design for real time performance and memory constraints, handle numerical precision and determinism issues, discuss trade offs and alternative approaches, and propose test cases and edge case handling. This canonical topic covers both standard algorithmic problems presented in game terminology and game domain specific implementation scenarios.

HardTechnical

57 practiced

Design an animation blending system that supports multiple layered animations with weight blending and root motion extraction. Describe the runtime data layout, how to evaluate blended bone transforms efficiently per-frame, and trade-offs if blending is done on CPU vs GPU.

Sample Answer

**Clarify requirements**- Layered animations with per-layer weights, per-bone masks, additive/override clips, and root-motion extraction per-frame for character movement.

**Runtime data layout**- AnimationClip: keyframe arrays (time-sampled compressed), boneIndices, sampleRate, isAdditive flag.- Layer: pointer to active clip(s), weight, per-bone mask (bitset or 8-bit weights), blendMode.- Pose buffer: array of N bone transforms (quat + vec3) in local space.- RootMotion accumulator: vec3 translation + quat rotation per-frame.- Scratch buffers: per-layer evaluated poses (sparse if masked) or GPU SSBOs.

**Per-frame evaluation (efficient)**1. Cull inactive layers; skip zero-weight.2. For each active layer, sample clip into a compact per-bone delta buffer using cached key indices and slerp/lerp; use SIMD for vectors/quats.3. Apply per-bone mask: only write bones whose mask > 0 (store as 8-bit index list to minimize writes).4. Blend hierarchically: perform per-bone weighted quaternion blending (NLERP or cumulative SQUAD for quality) using accumulators: - accumulate rotation via normalized weighted sum of quaternions, translation via weighted sum.5. Extract root motion: accumulate root bone delta per-layer before blending using layer weight and additive flag; convert to world by applying previous frame root transform if needed.6. Post-process: normalize quaternions, compute world transforms via parent chain (DFS), skinning.

**CPU vs GPU trade-offs**- CPU pros: simpler integration with gameplay/root-motion, lower latency for small numbers of characters, easier per-bone masks and branching, deterministic.- CPU cons: limited core SIMD scale; expensive with many characters.- GPU pros: massive parallelism for many characters; sample+blend in SSBOs with compute shaders; offloads skinning.- GPU cons: root-motion extraction and gameplay coupling costly to read back (sync); harder handling of dynamic masks, branching, and deterministic timing; higher implementation complexity.

**Recommendations**- Hybrid: do sampling+blending on GPU for bulk characters; keep one authoritative CPU-driven character(s) for gameplay-critical root-motion and animation-driven logic. Use compression, per-layer sparse masks, and cached key indices to minimize memory and branch cost.

HardSystem Design

65 practiced

You must design a matchmaking microservice supporting 100k concurrent queued players. Define the service API, data structures, scaling strategy (sharding, region affinity), and the algorithm to match players by rank, latency, and party size. Address fairness, starvation, and latency SLAs.

Sample Answer

**Requirements & SLAs**- Support 100k concurrent queued players globally; match latency SLA: 200ms for matchmaking decision, full session start <3s. Prioritize low ping, rank proximity, and party constraints. Prevent starvation and ensure fairness.

**API**- POST /enqueue { player_id, rank, party_id?, party_size, region_pref, ping_samples[], attributes[] } → enqueue_token- POST /dequeue { enqueue_token }- GET /status { enqueue_token } → position, estimated_wait- POST /report_ready { match_id, node_affinity }

**Core data structures**- In-memory sorted buckets per shard: priority queues keyed by (rank_bin, join_time)- Player struct: { id, rank, latency, party_id, size, timestamp }- Party map: party_id → list(player_ids), atomic enqueue/dequeue

**Sharding & Region affinity**- Primary shard by region (continent) + secondary by rank_hash to balance hot regions.- Each shard = cluster of matchmakers (state in Redis cluster with RAFT-backed replication for leader).- Use consistent hashing to assign players to shards; overflow routing for hot shards.

**Matching algorithm**1. Place player/party in rank_bin (e.g., ±50 Elo) and latency_bin.2. Periodic tick (20–50ms): attempt local matches within same rank_bin & latency_bin.3. If exceed wait thresholds (t1=1s, t2=5s), progressively relax rank and latency windows (exponential backoff).4. Party handling: treat party as atomic with matching slot = party_size.5. Use greedy + backtracking: try best-fit combination minimizing rank spread and latency variance; if none, widen constraints.

**Fairness & starvation**- Age-based weighting: effective_rank = rank + f(wait_time) where f increases linearly after t1 to guarantee eventual match.- Enforce max wait cap (e.g., 15s) after which region/skill constraints relaxed for guaranteed match.

**Scaling & resiliency**- Autoscale matchmaker pods per shard; Redis for fast lookups; Kafka for audit/logs and cross-shard merges.- Leader election for cross-shard merges; fallback cross-region pooling if local capacity insufficient.- Monitor metrics: queue size, match latency, failure rate; circuit-breakers for overloaded shards.

**Trade-offs**- Strong region affinity reduces ping but may increase wait for rare ranks; progressive relaxation balances UX.

MediumTechnical

55 practiced

Design a lightweight deterministic RNG for use in replayable single-player games. Requirements: repeatable sequence given seed, low memory, ability to fast-forward N steps efficiently, and good statistical properties for gameplay. Suggest an implementation and its complexity for fast-forward.

Sample Answer

**Approach (brief)** Use a small, well-known linear generator that is deterministic, compact, fast, and supports O(log N) jump-ahead: a 64-bit LCG or better, a 64-bit PCG/LCG hybrid. I'll show a 64-bit LCG with jump-ahead math (works for any modulus m = 2^64 using uint64 overflow). It’s repeatable, tiny state (one 64-bit), and you can fast-forward N steps with modular exponentiation and geometric-series summation in O(log N) time.

**Implementation (C++ - 64-bit LCG with jump-ahead)**

cpp

#include <cstdint>

// parameters: multiplier a, increment c
static const uint64_t A = 6364136223846793005ULL;
static const uint64_t C = 1442695040888963407ULL;

uint64_t lcg_next(uint64_t &state) {
  state = state * A + C;
  return state;
}

// compute (a^n mod 2^64) and (sum_{i=0..n-1} a^i * c) mod 2^64
void lcg_jump(uint64_t &state, uint64_t n) {
  uint64_t a_pow = 1;
  uint64_t c_mul = 0;
  uint64_t a = A;
  uint64_t c = C;
  while (n) {
    if (n & 1) {
      // combine current block: new_a = a_pow * a; new_c = c_mul * a + c
      uint64_t new_c = c_mul * a + c;
      uint64_t new_a = a_pow * a;
      a_pow = new_a;
      c_mul = new_c;
    }
    // square block: a = a * a; c = c * (1 + a)
    uint64_t next_c = c * (1 + a);
    a = a * a;
    c = next_c;
    n >>= 1;
  }
  state = a_pow * state + c_mul;
}

**Why it works / reasoning** LCG recurrence: X_{k+1} = a X_k + c (mod m). Closed form: X_{k+n} = a^n X_k + c * (a^n - 1) / (a - 1). Using exponentiation by squaring you compute a^n and the geometric sum in O(log n) multiplies — no loops over N, constant memory.

**Complexity** - Next-step generation: O(1) time, O(1) memory. - Fast-forward by N: O(log N) multiplications (64-bit), O(1) memory.

**Statistical notes & trade-offs** - LCG is tiny and speedy but has known low-dimensional correlation issues. For most gameplay uses (deterministic events, procedural seeds, replays) it's often acceptable. - If you need stronger statistical quality, use PCG or xorshift* (128-bit state) and implement jump-ahead via linear-algebra over GF(2) (also O(log N) but with bit-matrix exponentiation). That increases state slightly but improves randomness for gameplay fairness.

**Recommendation** For minimal memory and easiest implementation use the LCG above. For better gameplay statistical properties while keeping jump-ahead, use PCG with published jump constants or xorshift128+ with precomputed jump polynomials.

MediumTechnical

62 practiced

Design a data structure to support an inventory with O(1) add/remove by item-instance id, O(1) lookup by item type, and efficient iteration for UI. Include support for stack limits and fast removal of the oldest stacks. Describe implementation and complexity.

Sample Answer

**Approach (brief)**

Use two-level indexing: a global id->Node map for O(1) add/remove by instance id, and a type->TypeBucket map to support O(1) lookup by item type and efficient iteration. Each TypeBucket maintains a doubly-linked list of stacks (oldest at head) and a total-count. Nodes represent stack entries (count, capacity, timestamp/sequence).

**Data structures**

- unordered_map<ItemId, Node*> idMap — direct lookup and removal.- unordered_map<ItemType, TypeBucket> typeMap — lookup by type.- TypeBucket: - Doubly-linked list (head=oldest stack, tail=newest) of StackNodes. - totalCount (for UI/display)- StackNode: - itemType, stackCount, stackLimit, unique stackId, prev/next. - Optional sequence number for eviction ordering.

**Operations**

- Add(item instance or quantity): - If merging allowed: check tail (newest) or first non-full stack in TypeBucket; fill up to stackLimit; create new StackNode if needed. - Insert new StackNode -> append to tail; register each instance id mapping to Node* if per-instance id needed. - Complexity: O(1) amortized (append + map inserts). For merging, you may check only tail to keep O(1); scanning for partially filled stacks would be avoided.

- Remove by instance id: - idMap lookup -> Node* -> decrement stackCount or delete stack. - If stack becomes empty: unlink from TypeBucket list and remove mappings. - Complexity: O(1).

- Lookup by item type: - typeMap[type] returns TypeBucket; can return totalCount, list head/tail for UI. - Complexity: O(1).

- Remove oldest stacks (eviction): - While need eviction: pop head of TypeBucket (oldest), unlink, update idMap. - Complexity: O(1) per stack removed.

- UI iteration: - Iterate TypeBucket linked list from tail (newest) or head; constant-time per stack and predictable order for UI virtualization.

**Complexity summary**

- Add/remove by instance id: O(1) average- Lookup by type: O(1)- Iterate stacks for UI: O(1) per stack visited- Evict oldest stack: O(1) per stack

**Notes & trade-offs**

- If individual item instances must map to ids, storing many id->Node entries increases memory; alternatively store ranges or only store per-stack metadata.- To support finding any partially filled stack in O(1), keep an extra pointer from TypeBucket to one non-full stack; otherwise merging may be limited to tail only.- Use object pools for StackNode to avoid GC/alloc churn in game loops.

EasyTechnical

65 practiced

Write a function in C# that tests collision between two axis-aligned bounding boxes (AABB) in 2D. Each box is defined by a center (x,y) and half-extents (hx,hy). Return a boolean indicating overlap and, if overlapping, the minimum translation vector (MTV) to separate them.

Sample Answer

**Approach**- Use Separating Axis Theorem for AABBs: overlap on both X and Y axes means collision. Compute overlap amount on each axis and return the minimum translation vector (MTV) along the smallest penetration.

**C# Implementation**

csharp

using UnityEngine; // optional for Vector2

public static class Collision2D
{
    // Returns (isOverlap, mtv). mtv is zero when no overlap.
    public static (bool, Vector2) AABBOverlap(Vector2 cA, Vector2 hA, Vector2 cB, Vector2 hB)
    {
        // Compute distance between centers
        Vector2 d = cB - cA;
        // Sum of half extents
        Vector2 ext = hA + hB;
        // Overlap on each axis
        float overlapX = ext.x - Mathf.Abs(d.x);
        if (overlapX <= 0f) return (false, Vector2.zero);
        float overlapY = ext.y - Mathf.Abs(d.y);
        if (overlapY <= 0f) return (false, Vector2.zero);

        // Choose smallest penetration axis for MTV
        if (overlapX < overlapY)
        {
            float sign = (d.x < 0f) ? -1f : 1f;
            return (true, new Vector2(overlapX * sign, 0f));
        }
        else
        {
            float sign = (d.y < 0f) ? -1f : 1f;
            return (true, new Vector2(0f, overlapY * sign));
        }
    }
}

**Explanation & Notes**- MTV pushes A out of B along shortest axis; sign orients it from A toward outside.- Time O(1), Space O(1).- Edge cases: touching edges yield no overlap (<= 0 treated non-colliding). For floating error tolerance, compare with small epsilon if needed.- Useful in games for simple rigid-body separation, physics correction, or trigger checks.

Unlock Full Question Bank

Get access to hundreds of Game Specific Coding Problems interview questions and detailed answers.

Join thousands of developers preparing for their dream job.