Comprehensive coverage of fundamental data structures, their operations, implementation trade offs, and algorithmic uses. Candidates should know arrays and strings including dynamic array amortized behavior and memory layout differences, linked lists, stacks, queues, hash tables and collision handling, sets, trees including binary search trees and balanced trees, tries, heaps as priority queues, and graph representations such as adjacency lists and adjacency matrices. Understand typical operations and costs for access, insertion, deletion, lookup, and traversal and be able to analyze asymptotic time and auxiliary space complexity using Big O notation including constant, logarithmic, linear, linearithmic, quadratic, and exponential classes as well as average case, worst case, and amortized behaviors. Be able to read code or pseudocode and derive time and space complexity, identify performance bottlenecks, and propose alternative data structures or algorithmic approaches to improve performance. Know common algorithmic patterns that interact with these structures such as traversal strategies, searching and sorting, two pointer and sliding window techniques, divide and conquer, recursion, dynamic programming, greedy methods, and priority processing, and when to combine structures for efficiency for example using a heap with a hash map for index tracking. Implementation focused skills include writing or partially implementing core operations, discussing language specific considerations such as contiguous versus non contiguous memory and pointer or manual memory management when applicable, and explaining space time trade offs and cache or memory behavior. Interview expectations vary by level from selecting and implementing appropriate structures for routine problems at junior levels to optimizing naive solutions, designing custom structures for constraints, and reasoning about amortized, average case, and concurrency implications at senior levels.
EasyTechnical
95 practiced
You must choose a container for active game entities that are frequently spawned and destroyed mid-frame. Compare using a linked list versus a contiguous array (vector) in terms of insertion/deletion cost, iteration performance, memory overhead, allocation patterns, and cache locality. For a real-time console game where iteration happens every frame, which would you choose and why?
Sample Answer
**Answer (concise comparison + choice)****Insertion / Deletion**- Linked list: O(1) insert/remove given node pointer; no element moves.- Contiguous array (vector): removal often O(n) if preserving order; O(1) if using swap-with-last or tombstones/free-list.**Iteration performance & cache locality**- Linked list: poor cache locality — pointer chasing causes many cache misses, expensive per-frame.- Vector: excellent locality; sequential memory access is fast and predictable — huge win when iterating every frame.**Memory overhead & allocation**- Linked list: per-node pointer overhead and many small allocations (fragmentation, allocator pressure).- Vector: compact memory, fewer allocations (grow strategy), lower overhead.**Allocation patterns**- Linked list: frequent small allocations/deallocations hurt frame time and memory.- Vector: bulk allocations; combine with object pool or preallocated capacity to avoid per-frame allocs.**Recommendation (real-time console game)**Choose a contiguous array (vector) with one of these strategies:- Preallocate capacity and use swap-remove on delete to keep O(1) removal.- Maintain a freelist/tombstone pool for reused slots to avoid shifting.- Or use a dense handle indirection (index -> dense array) for stable handles.Why: iteration performance and cache locality dominate per-frame costs on console hardware. Mitigate deletion costs with simple techniques rather than accepting the runtime and memory penalties of linked lists.
EasyTechnical
84 practiced
Explain why appending elements to a dynamic array (for example std::vector in C++ or List<T> in C#) has amortized O(1) time complexity. Describe a typical growth strategy (e.g., doubling), perform an aggregate/amortized cost analysis for n appends, and relate how this behavior affects a mobile game that performs many small appends during frame-critical asset streaming. Comment on memory overhead and reallocation costs.
Sample Answer
**Brief answer / intuition**Appending to a dynamic array is amortized O(1) because although some appends trigger expensive reallocations/copies, most do not. With a doubling strategy the average cost per append over n operations stays constant.**Typical growth strategy**- Start capacity C (often 0 or 1).- On full capacity, allocate new array of size 2 * C, copy C elements, free old buffer.- Append the new element.**Aggregate (amortized) analysis**- Suppose capacities grow: 1, 2, 4, 8, … up to >= n.- Total copies across all reallocations ≤ 1 + 2 + 4 + … + n/2 < 2n.- Work = n cheap appends + O(n) copies = O(n). So average cost per append = O(n)/n = O(1).(Plain intuition: every element gets copied O(1) times overall.)**Impact on mobile game frame-critical streaming**- Reallocation causes a spike: allocation + memcpy + free can stall the main thread and cause frame hitches.- Memory pressure on mobile amplifies cost (GC in managed runtimes or OS-level fragmentation).- Mitigations for games: - Reserve capacity upfront when streaming known sizes (vector::reserve, List.Capacity). - Use object pools or chunked buffers to avoid large copies. - Perform any necessary expansion on background threads and swap buffers on frame boundaries. - Use move semantics / emplace to reduce copy cost in C++.**Memory overhead & reallocation costs**- Doubling leads to up to ~50% unused capacity on average (wasted RAM).- Reallocation cost = allocation + element copy/move + deallocation; expensive on low-memory mobile devices.- Trade-off: faster amortized appends vs increased peak memory. For mobile, prefer explicit reservation or pooling to avoid runtime stalls.
MediumTechnical
89 practiced
Implement a trie (prefix tree) interface for autocomplete of in-game chat commands or player names. Provide methods or pseudocode for Insert(word), StartsWith(prefix), and Suggest(prefix, k) that returns up to k suggestions ordered by stored frequency. Use C++ or clear pseudocode and discuss memory usage and compression techniques to reduce footprint on consoles/mobile.
Sample Answer
**Approach (brief)** Use a trie where each node stores children map (compact array or vector for limited alphabet), end-of-word flag, frequency, and optionally top-k heap for fast suggestions. For consoles/mobile, use compressed children (bitset + child array) and string-packing (edge-compression).**C++-like pseudocode**
cpp
struct Node {
bool isWord = false;
int freq = 0; // frequency if isWord
uint32_t childMask = 0; // 26-bit mask for a-z (or larger)
vector<Node*> children; // dense list matching bits in childMask
};
Node* root = new Node();
Node* getChild(Node* n, int c) {
if (!(n->childMask & (1u<<c))) return nullptr;
// compute index = popcount(mask & ((1<<c)-1))
int idx = popcount(n->childMask & ((1u<<c)-1));
return n->children[idx];
}
void Insert(string s, int addFreq=1) {
Node* cur = root;
for (char ch : s) {
int c = ch - 'a';
Node* nxt = getChild(cur,c);
if (!nxt) {
// insert new child, maintain mask and children vector
}
cur = nxt;
}
cur->isWord = true;
cur->freq += addFreq;
}
vector<string> Suggest(string prefix, int k) {
Node* cur = walkToNode(prefix);
if (!cur) return {};
// DFS collecting words, keep a min-heap of size k by freq
// return sorted suggestions by freq desc
}
**Key concepts & complexity** - Insert & StartsWith: O(L) where L = length of word/prefix. - Suggest: O(L + m log k) where m = number of matched nodes visited; use heap to keep top-k.**Memory & compression techniques (game/dev focus)** - Use bitmask+compact child array to avoid 26 pointers per node. - Edge-compression (store common suffixes in one edge) reduces nodes for command lists. - Pool allocator / arena to reduce fragmentation. - Store strings in a single packed buffer and use offsets. - Quantize frequency to small integer (e.g., uint16) and encode node metadata in bitfields. **Edge cases** - Case-insensitivity, Unicode/names: map to normalized tokens or use UTF-8-aware trie with larger alphabets and more compression. - Frequent updates: maintain auxiliary top-k caches per node or rebuild lazily to keep Suggest fast.
EasyTechnical
92 practiced
Implement an undo/redo system for a simple level editor used by your game. In C++ or C#, provide a class (or pseudocode) supporting: ApplyAction(Action), Undo(), Redo(). Assume Action has Execute() and Unexecute() methods. Explain data structures used, time and space complexity of operations, and strategies to limit memory growth (e.g., checkpoints, delta compression, truncation of history).
Sample Answer
**Approach (brief)** Use the Command pattern: keep a list of Actions and an index pointing to the next action slot. ApplyAction appends or overwrites forward history, Execute() runs, Undo calls Unexecute() on previous, Redo calls Execute() on current. This gives O(1) per operation.
csharp
// C# implementation
public class UndoRedoManager {
private List<Action> history = new List<Action>();
private int index = 0; // next-action position; valid actions are [0 .. index-1]
public void ApplyAction(Action act) {
// truncate forward history if we are mid-history
if (index < history.Count) history.RemoveRange(index, history.Count - index);
history.Add(act);
act.Execute();
index++;
}
public bool CanUndo => index > 0;
public bool CanRedo => index < history.Count;
public void Undo() {
if (!CanUndo) return;
index--;
history[index].Unexecute();
}
public void Redo() {
if (!CanRedo) return;
history[index].Execute();
index++;
}
}
**Data structures** - List<Action> for contiguous history; index int for current position. Equivalent to two stacks but simpler for truncation/redo.**Complexity** - Time: ApplyAction, Undo, Redo — O(1) amortized (RemoveRange may be O(k) when truncating forward, but overall amortized constant if truncation infrequent). - Space: O(n) for n stored Actions.**Memory-growth strategies** - Fixed-cap history: drop oldest actions when history exceeds N. - Checkpoints/snapshots: store full snapshot every K actions; keep intermediate actions as deltas to speed restore. - Delta compression: store compact diffs (e.g., transform/ID changes, resource references) instead of full copies. - Serialize to disk or temp file for long sessions and lazy-load. Examples in games: store small property-deltas for transform edits, full snapshot when switching levels or before big operations.
HardSystem Design
70 practiced
Design an efficient event timer scheduler for a real-time game server that must handle millions of timers. Compare using a min-heap (priority queue) versus hierarchical timing wheels (or calendar queues) and analyze insertion, cancellation, tick/advance costs, memory overhead, and worst-case behaviors. Recommend a design for a low-latency authoritative server.
Sample Answer
**Clarify requirements**- Millisecond/ sub-ms latency, millions of simultaneous timers, frequent cancellation, deterministic worst-case for authoritative tick loop, memory constrained per-entity.**High-level comparison**- Min-heap (binary or pairing heap) - Insertion: O(log n) - Cancellation: O(log n) if you store handles; lazy deletion possible but increases memory - Tick/advance: pop while min <= now → O(k log n) for k expirations - Memory: O(n) nodes + handles - Worst-case: bursts cause many log n ops → GC pressure and variable latency - Good when n moderate and expirations random- Hierarchical timing wheel / calendar queue - Insertion: O(1) amortized (place in bucket) - Cancellation: O(1) if doubly-linked bucket list + handle - Tick/advance: O(1) per tick to advance wheel; amortized O(m) to process bucket of m timers - Memory: O(n + wheel size); fixed arrays reduce allocator churn - Worst-case: bucket storms where many timers land in same slot → O(m) processing but predictable and spreadable by wheel levels - Good for massive n, many short/medium TTLs, low per-tick CPU jitter**Practical considerations for authoritative game server**- Use hierarchical timing wheel with multiple levels: millisecond slots for immediate timers, coarser levels for long TTLs. This gives O(1) common-case and predictable tick cost.- Implement: - Preallocated node pool to avoid allocations - Handles with generation counters for safe cancellation - Backoff buckets: when bucket size > threshold, process across multiple frames or use worker threads - Metrics and adaptive wheel resizing (or an extra overflow heap for pathological long timers)- Hybrid option: timing wheel for most timers + small min-heap for long-tail or extremely precise timers.**Recommendation**- Hierarchical timing wheel + preallocated pools as primary scheduler for low-latency authoritative server; add a small heap overflow for pathological cases. This minimizes jitter, memory churn, and gives deterministic per-tick work suitable for game loops.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
