Data structures

Arrays store indexed elements with good locality. Linked lists store nodes with links; they trade index access and extra allocation for convenient splicing when a node and its predecessor are already known.

Example: Use an array for a scoreboard read by rank; a list can help splice a known work item.

Common mistake: Saying linked-list deletion is always constant time ignores finding the node.

Follow-up: How would the choice change when most operations are iteration?

Most appends write into unused capacity. Occasionally a larger buffer must be allocated and existing elements copied; spread across geometrically growing capacity, total copying over n appends is linear.

Example: Appending one million items does not copy a million items on every append.

Common mistake: Amortized is not the same as average over randomly distributed inputs.

Follow-up: When would reserving capacity help?

A stack removes the most recently added item first. It represents unfinished nested work, such as matching brackets or undo operations; in Java, ArrayDeque is a common single-threaded choice.

Example: Push each opening bracket and match each closing bracket against the top.

Common mistake: Popping without checking for an empty stack can hide invalid input.

Follow-up: How would you implement a minimum stack?

A queue removes the earliest enqueued item first. It supports breadth-first work and buffering, while a stack explores the newest work first.

Example: Process tree nodes level by level with a queue.

Common mistake: Using ArrayList.remove(0) shifts elements on every removal.

Follow-up: How would a bounded blocking queue handle a slow consumer?

A hash chooses a bucket and equality identifies the matching key within it. Good hash distribution keeps buckets short; resizing maintains load but occasionally moves many entries.

Example: Store customer ID to customer record for exact lookups.

Common mistake: A hash collision does not mean two keys are equal.

Follow-up: Why must a key's hash-relevant state stay stable?

A set represents membership and uniqueness. A map associates each key with a value; choose it when you need counts, metadata or a lookup result rather than only presence.

Example: Use a set for visited IDs and a map for visit counts.

Common mistake: A set removes duplicates but does not inherently preserve order.

Follow-up: How would you preserve encounter order?

ArrayDeque is a resizable circular array that supports push, pop, offer and poll at both ends in amortized constant time. Stack extends Vector and synchronizes every call, and LinkedList allocates a node per element with poor locality, so ArrayDeque is the default for both stacks and queues in single-threaded code.

Example: Use Deque<Integer> stack = new ArrayDeque<>() for iterative DFS and the same type with offer/poll for BFS.

Common mistake: ArrayDeque rejects null elements; code that used null as a sentinel will throw NullPointerException.

Follow-up: Which implementation would you use if producers and consumers run on different threads?

Java strings are immutable, so s += part creates a new string and copies every existing character each iteration. Across n appends with total length L, the copies sum to O(L²) in the worst case. StringBuilder keeps a growable buffer and doubles capacity, so appends are amortized O(length of the appended part).

Example: Building a CSV row from 10,000 fields with += copies the growing prefix 10,000 times; StringBuilder copies each character about twice.

Common mistake: Assuming the compiler always rewrites loops into one StringBuilder; it optimizes single expressions, not repeated loop concatenation.

Follow-up: When would String.join or a Collector.joining be clearer than an explicit builder?

Every left subtree contains smaller keys and every right subtree larger keys according to a consistent comparator. Search follows one branch; balancing keeps height logarithmic.

Example: Use a balanced ordered map for predecessor and range queries.

Common mistake: An ordinary BST built from sorted input can become a chain.

Follow-up: How do duplicates affect your invariant?

A min-heap guarantees each parent is no greater than its children, so the root is the minimum. It does not keep siblings or the full backing array sorted.

Example: Maintain the largest k stream values using a min-heap of size k.

Common mistake: Iteration over PriorityQueue does not produce sorted order.

Follow-up: Why is heap construction faster than repeated insertion?

Lists store only present edges and suit sparse graphs. A matrix stores every possible pair and makes edge existence cheap, but scans a full row to enumerate neighbors.

Example: Road networks are usually sparse; a tiny dense compatibility graph may suit a matrix.

Common mistake: Calling every graph operation O(V + E) ignores representation.

Follow-up: How would you represent weighted directed edges?

Each step follows one character, sharing prefix nodes across words. Reaching a prefix node locates its subtree; enumerating suggestions still costs the size of the output.

Example: Autocomplete for words beginning with inter.

Common mistake: Prefix lookup is not the same cost as returning every matching word.

Follow-up: How would compressed edges reduce memory?

Combine a key-to-node hash map with a doubly linked recency list. On access move the node to the front; on insertion beyond capacity unlink the tail and remove its key.

Example: Capacity two: access A, B, A, then insert C; evict B.

Common mistake: A concurrent map alone cannot make map/list updates atomic.

Follow-up: How would TTL expiration interact with recency?

It tracks connected components while edges are added. Union by rank or size plus path compression avoids repeatedly walking long parent chains.

Example: Detect whether a new undirected edge joins two already connected vertices.

Common mistake: It does not efficiently undo arbitrary deletions or return a path between vertices.

Follow-up: What changes for offline dynamic connectivity?

Keep candidate indices in decreasing value order. Remove expired indices from the front and smaller candidates from the back; each index enters and leaves at most once.

Example: For window size three, track the largest of each consecutive triple.

Common mistake: Storing only values makes duplicate expiration harder to handle correctly.

Follow-up: How does this differ from a monotonic stack?

HashMap suits exact lookups. TreeMap maintains comparator order and supports floor, ceiling and sorted ranges, paying a logarithmic update cost.

Example: Find the most recent price at or before a timestamp with floorEntry.

Common mistake: A comparator returning zero treats keys as equivalent even when equals differs.

Follow-up: What happens if comparator order disagrees with equals?

Use an array of capacity N, a head index for the oldest element and a size counter. Writes go to (head + size) % N; when full, overwrite the oldest slot and advance head. Reads index from head. All operations are constant time and memory never grows, which suits rolling metrics, logs and rate windows.

Example: Keeping the last 1,000 request latencies to compute a moving p99 on demand without unbounded memory.

Common mistake: Using only head and tail without a size counter makes full and empty indistinguishable when head == tail.

Follow-up: How would you make it safe for a single producer and a single consumer thread without locks?

Readers can share a stable snapshot without defensive locking around mutations. Persistent structures can share unchanged nodes, but immutability alone does not specify operation costs.

Example: Publish a new configuration snapshot while existing requests retain the old one.

Common mistake: An unmodifiable wrapper is not a deep immutable copy of its elements.

Follow-up: How would you safely publish a snapshot between threads?

Both support point updates and range queries in O(log n). A Fenwick tree is shorter and uses n + 1 slots, but its prefix-difference trick needs an invertible operation such as sum or xor. A segment tree supports any associative combine, including min, max and gcd, and with lazy propagation it also supports range updates, at more memory and code.

Example: Live leaderboard counts per score bucket: Fenwick. Range minimum of sensor readings with updates: segment tree.

Common mistake: Using Fenwick prefix differences for range minimum; min(0..r) − min(0..l) is meaningless.

Follow-up: How would you support adding a value to every element in a range?

A Bloom filter is a bit array with k hash functions. Adding sets k bits; a query returns maybe-present only if all k bits are set. It never gives false negatives for inserted items but allows tunable false positives, and standard filters do not support deletion. It saves memory when a cheap negative answer avoids an expensive lookup.

Example: A storage engine checks a per-file Bloom filter before reading a disk block, skipping files that definitely lack the key.

Common mistake: Using it as a set of record of truth; a positive answer must still be verified, and removing items requires a counting variant.

Follow-up: How do you size m bits and k hashes for one million keys and a one percent false-positive rate?