Data Structures
Recruitment and knowledge question base. Filter, search and test your knowledge.
easyarraylinked-listcomparison+1
Answer
An array (or ArrayList/dynamic array) stores elements next to each other in memory, so random access is O(1). Inserts/deletes in the middle are O(n) because elements must shift (and resizing may copy). A LinkedList stores nodes linked by pointers: inserts/deletes at a known node are O(1), but random access is O(n) and it uses extra memory.
easyjsonformatexample
Answer
Valid JSON is a text format for objects and arrays using {} and [], where keys and string values are in double quotes, and values can be only: string, number, boolean, null, array, or object. Example: { "name": "John", "age": 30, "roles": ["dev"], "active": true }.
{
"name": "John Doe",
"age": 30,
"isEmployed": true,
"roles": ["developer", "admin"],
"address": {
"city": "New York",
"zip": "10001"
}
}easystackqueuedata-structure+1
Answer
A stack is a LIFO structure where you push/pop at the top, used for call stacks, undo, and depth‑first search. A queue is FIFO where you enqueue at the tail and dequeue at the head, used for scheduling, buffering, and breadth‑first search.
mediumhashmaphashingcollision+1
Answer
A HashMap stores key–value pairs in buckets. It uses key.hashCode() to pick a bucket, and equals() to find the right key inside that bucket. Collisions are kept in a list/tree; when the load factor threshold is exceeded it resizes and rehashes to keep average lookups near O(1).
hardtreebinary-search-treebalancing+1
Answer
Balanced trees such as AVL or Red‑Black are self‑balancing binary search trees that keep height proportional to log n by performing rotations after inserts and deletes. This guarantees search/insert/delete in O(log n) even in the worst case.
easysetdeduplicationmembership
Answer
A Set stores unique values (no duplicates). Use it for fast membership checks and deduplication (e.g., keep unique user IDs).
const ids = new Set<number>();
ids.add(42);
console.log(ids.has(42)); // trueeasypriority-queueheapbig-o
Answer
A priority queue removes the element with the highest (or lowest) priority first, not the oldest. It’s commonly implemented with a heap, so insert/remove is O(log n).
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
System.out.println(pq.poll()); // 1easydequequeuering-buffer
Answer
A deque lets you add and remove elements from both the front and the back. With a ring buffer or linked list, these operations are O(1).
mediumgraphadjacency-listadjacency-matrix+1
Answer
A matrix uses O(V^2) memory and gives O(1) edge checks, so it’s good for dense graphs. A list uses O(V+E) memory and is better for sparse graphs and iterating neighbors.
mediumtrieprefixautocomplete
Answer
A trie stores strings by prefixes: each node represents a character. It enables fast prefix search/autocomplete; lookup is O(L), where L is the word length.
mediumhash-tablecollisionchaining+1
Answer
With chaining, each bucket stores a list/tree of entries that share the same hash. With open addressing, collisions are resolved by probing other slots (linear/quadratic/double hashing). Chaining is simpler under higher load; open addressing is cache-friendly but needs a lower load factor.
harddynamic-arrayamortizedresizing+1
Answer
Most appends write into free capacity in O(1). Occasionally the array resizes and copies O(n) elements; spread over many appends, the average cost per append stays O(1) (amortized).
let capacity = 4;
let size = 0;
function append(x: number) {
if (size === capacity) {
capacity *= 2; // resize + copy O(n)
}
size++;
}hardavlred-blackbalancing+1
Answer
AVL trees keep stricter balance, so lookups are often faster, but inserts/deletes may require more rebalancing. Red-Black trees relax the balance rules, making updates cheaper while still keeping height O(log n).
hardbloom-filterprobabilistichashing+1
Answer
A Bloom filter is a probabilistic set for membership tests. It can return false positives (might say “present” when it’s not), but it never returns false negatives. It’s very memory efficient and fast, but you can’t retrieve the original items.
hardunion-finddsukruskal+1
Answer
Union-Find maintains disjoint sets with find(x) (representative) and union(a,b) (merge). It’s used for connectivity and Kruskal’s MST; with path compression + union by rank, operations are almost O(1) amortized.
class DSU {
private parent: number[];
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
}
find(x: number): number {
if (this.parent[x] === x) return x;
this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(a: number, b: number) {
const ra = this.find(a);
const rb = this.find(b);
if (ra !== rb) this.parent[rb] = ra;
}
}easymapdictionaryhashmap+1
Answer
A Map stores values by key (key → value). Use it when you need fast lookup by an identifier (e.g., email → user) instead of by numeric index; a hash map is usually O(1) average for get/put.
mediumlrucachehashmap+2
Answer
LRU (Least Recently Used) evicts the item that hasn’t been used for the longest time. A common O(1) design is: HashMap for key→node lookup + doubly linked list to move items to the front on access and evict from the tail.
type Node = { key: string; prev?: Node; next?: Node }
// idea:
// map: key -> node
// list: head <-> ... <-> tail
// get(key): move node to head (O(1))
// put(key): insert/move to head; if over capacity, evict tail (O(1))mediumring-bufferqueueproducer-consumer
Answer
A ring buffer is a fixed-size array used as a queue with head/tail pointers that wrap around (mod capacity). It’s useful for streams and producer/consumer queues because it avoids allocations and gives O(1) enqueue/dequeue.
hardfenwickbitprefix-sum+1
Answer
A Fenwick tree supports prefix sums and point updates in O(log n) with O(n) memory. Use it when you need many updates and queries like “sum of [0..i]” quickly (e.g., frequency/counting problems).
class Fenwick {
private bit: number[];
constructor(n: number) {
this.bit = Array(n + 1).fill(0);
}
add(i: number, delta: number) {
for (let x = i + 1; x < this.bit.length; x += x & -x) this.bit[x] += delta;
}
sum(i: number) {
let res = 0;
for (let x = i + 1; x > 0; x -= x & -x) res += this.bit[x];
return res;
}
}hardskip-listlinked-listprobabilistic+1
Answer
A skip list is a layered linked-list structure where some nodes are promoted to higher levels randomly. It gives expected O(log n) search/insert/delete (like balanced trees), is simpler to implement, but its performance is probabilistic.
easyheapbinary-heappriority-queue+1
Answer
In a min-heap, every node is ≤ its children (the smallest element is at the root). In a max-heap, every node is ≥ its children. This makes peek O(1) and insert/remove O(log n).
mediumsegment-treerange-querybig-o
Answer
A segment tree stores aggregates over ranges (sum/min/max) and supports range queries and point updates in O(log n). It’s useful when you need many queries like “sum on [l..r]” with updates.
mediumhash-tableload-factorrehash+1
Answer
Load factor is roughly `items / buckets`. When it gets too high, collisions increase and operations slow down. Resizing increases bucket count and rehashes entries to keep average performance near O(1).
hardb-treebstdisk-io+1
Answer
B-trees have high branching factor, so they stay shallow and reduce disk IO (fewer page reads). BSTs are pointer-heavy and deep; they are good in memory but inefficient on disk compared to page-friendly B-trees.
hardstringssuffix-arraysuffix-tree+1
Answer
They are string data structures used for fast substring and pattern queries (e.g., “does pattern P appear in text T?”). They enable efficient searches and are used in text indexing, search, and bioinformatics.
easybitsetbitmapmemory+1
Answer
A bitset (bitmap) stores true/false flags as bits, so it is very memory efficient. Use it for fast membership on a small, dense range of integers (e.g., IDs 0..N) and for quick bit operations (AND/OR).
mediumropestringdata-structure+1
Answer
A rope represents a long string as a tree of smaller chunks. It can make concatenation and insert/delete in the middle cheaper than copying whole strings, at the cost of more complexity and usually slower random indexing.
mediumimmutablepersistentstructural-sharing+1
Answer
A persistent (immutable) data structure returns a new version on “update” instead of changing in place. Structural sharing means the new version reuses most of the old nodes, so copying is cheap (useful for undo/history and safer concurrency).
hardsparse-tablermqpreprocessing+1
Answer
A sparse table precomputes answers for ranges of length 2^k, so you can answer some static range queries fast. For idempotent operations like min/max/gcd, queries are O(1) after O(n log n) preprocessing, but it does not support updates efficiently.
hardhashingcuckoo-hashinghash-table+1
Answer
Cuckoo hashing uses two (or more) hash functions, so each key can live in one of a few positions. Lookups are O(1) and simple, but inserts can trigger a chain of evictions; in rare cases you must rehash/resize to break a cycle.
easylinked-listsinglydoubly+1
Answer
A singly linked list stores only `next`, so it uses less memory and is simpler. A doubly linked list stores `prev` and `next`, which makes removing a known node and iterating backwards easier, but costs more memory and pointer updates. Choose singly when you only need forward traversal; choose doubly when you frequently remove nodes in the middle or need reverse traversal.
mediumhash-tablerehashlatency+1
Answer
Resizing often means allocating a bigger table and rehashing/copying all entries, which is O(n) work done at once. That can create a pause and a latency spike. Mitigations: pick a good load factor, pre-size when you know the size, use incremental rehashing (move entries gradually), or use a concurrent map implementation that spreads the work.
mediumheapheapifycomplexity+1
Answer
If you build a heap bottom-up (heapify), most nodes are near the leaves and move only a small distance. The total work across all nodes forms a decreasing series, which sums to O(n). Doing n inserts one-by-one is O(n log n), but bottom-up heapify is O(n).
hardb-treeb-plus-treeindexes+1
Answer
In a B+ tree, all records (or pointers to records) are stored in the leaves, and internal nodes store only keys for routing. Leaves are usually linked, so range scans are very fast. This fits disk access well: high fan-out keeps the tree shallow, and linked leaves make ordered reads efficient.
hardradix-treepatriciatrie+1
Answer
A radix tree is a compressed trie: chains of single-child nodes are merged into one edge labeled with a string segment. It saves memory and reduces pointer chasing compared to a normal trie, while keeping fast prefix lookups. It’s used for things like routing tables and prefix-based search.
easydequequeuestack+1
Answer
A deque (double-ended queue) lets you add and remove elements from both the front and the back. It’s useful when you need both stack- and queue-like operations, or for algorithms like sliding window/monotonic queues.
mediumhash-tablecollisionschaining+1
Answer
Separate chaining stores colliding keys in a bucket list (or tree). Open addressing keeps all entries in the table and probes alternative slots (e.g., linear/quadratic probing, double hashing). Chaining is simpler for deletes; open addressing can be more cache-friendly but is sensitive to load factor.
mediumtrieprefixautocomplete+1
Answer
A trie stores strings as paths of characters; each edge represents a character. Prefix queries are efficient because all words with the same prefix share the same path, so lookup is O(L) where L is the key length. The trade‑off is higher memory usage compared to hashing.
easypriority-queueheapordering+1
Answer
A priority queue supports insert, peek (min/max), and extract (min/max). It’s typically implemented with a binary heap, giving O(log n) insert/extract and O(1) peek.
mediumgraphadjacency-listadjacency-matrix+1
Answer
Use an adjacency list for sparse graphs because it uses O(V + E) memory and iterates neighbors efficiently. Use an adjacency matrix for dense graphs or when you need O(1) edge‑existence checks; it costs O(V^2) memory.
hardsegment-treerange-queryupdates+1
Answer
A segment tree is a binary tree over array segments. It supports range queries (sum/min/max) and point updates in O(log n) after an O(n) build. With lazy propagation it can handle range updates too.
class SegTree {
private tree: number[];
private n: number;
constructor(n: number) {
this.n = n;
this.tree = Array(4 * n).fill(0);
}
update(node: number, l: number, r: number, idx: number, val: number) {
if (l === r) {
this.tree[node] = val;
return;
}
const mid = Math.floor((l + r) / 2);
if (idx <= mid) this.update(node * 2, l, mid, idx, val);
else this.update(node * 2 + 1, mid + 1, r, idx, val);
this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
}
}mediumheapbstpriority-queue+1
Answer
A binary heap is great for min/max: peek is O(1) and insert/extract is O(log n). A (balanced) BST supports ordered traversal and search by key in O(log n). Heaps are not good for fast search or range queries.
easymaptreemaphashmap+1
Answer
Choose an ordered map when you need keys in sorted order or range queries (e.g., all keys between A and B). TreeMap provides O(log n) operations and ordering; HashMap gives O(1) average operations but no ordering.
mediumsparse-matrixcsrcoo+1
Answer
Use sparse formats (CSR/COO) when most entries are zero. They store only non‑zero values and their positions, which saves memory and can speed up operations like matrix‑vector multiply. The trade‑off is slower random access and more complex updates.