Skip to content
Tech Interview Prep
Technical interview guide

Arrays & Hashing

Contiguous storage, O(1) average-case lookups via hash maps, and the frequency-counting patterns they enable.

Read
42 min
Practice MCQs
25
Interview Q&A
25
Edition
v6
Editorial status
Reviewed

Scope: Language-neutral, with operation costs cited from CPython 3.14, the C++ standard containers, and java.util as of Java 21.

Curated: · Written: · Reviewed:

25 questions

MCQ-1A service holds 1,000,000 records in a Python list. Each request performs one read at index 500,000 and one insert at index 0. Which statement about the cost of a single request is correct?
MCQ-2A service appends 1,000,000 items one at a time to a dynamic array that starts empty. The team replaces the array's doubling growth policy with a fixed increment of 1,000 elements per resize. Roughly how many element copies does the new policy perform in total?
MCQ-21A 3×4 grid is stored as a list of rows. A neighbour scan checks only the row index before reading a cell: ```python for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)): nr, nc = r + dr, c + dc if 0 <= nr < len(grid): visit(grid[nr][nc]) ``` The grid is ``` 7 0 0 0 0 0 0 5 3 0 0 9 ``` Starting from (2, 0), the scan runs all four moves. Which statement describes what it visits?
MCQ-13A service keeps a raw pointer to an element of a `std::vector<Entry>` and a reference to an entry of an open-addressing hash table, and reuses both after later insertions. Under which condition do those stored pointer and reference become dangling?
MCQ-23A batch job walks a graph of 5,000,000 nodes, each 32 bytes. Layout A keeps the nodes in one contiguous array with edges stored as indices; layout B heap-allocates each node and links them with pointers. Both visit every node exactly once. On a machine with 64-byte cache lines and a 32 MB L3, the measured traversal times are 18 ms for A and 240 ms for B. Which conclusion does the measurement support?
MCQ-15A service caches rendered pages in a dict keyed by `"-".join(path_segments)`. Two requests arrive, with segments `["docs", "a-b", "c"]` and `["docs", "a", "b-c"]`; they are different pages with different content. What happens on the second request?
MCQ-14A dedup service treats two log records as duplicates when they are anagrams of each other. It groups 12 million records by `sum(map(ord, record))`, and the output puts "ad" and "bc" in the same group. Which statement about this pipeline is correct?
MCQ-3A service caches records in a dict keyed by `UserKey` objects. `__hash__` returns `hash(self.uid)` and `__eq__` compares `self.uid`. A bug mutates a key after it has been inserted (Python 3.12): ```python class UserKey: def __init__(self, uid): self.uid = uid def __hash__(self): return hash(self.uid) def __eq__(self, other): return self.uid == other.uid k = UserKey(42) cache = {k: "old"} k.uid = 43 cache[UserKey(42)] = "new" print(len(cache), cache.get(UserKey(42))) ``` What does the final line print?
MCQ-7A batch job flags duplicate records by comparing every pair: at n = 20,000 that is about 2×10^8 comparisons and takes 20 seconds. The records are instances of a class whose __hash__ returns 0 for every instance. An engineer replaces the nested loop with one pass that inserts each record into a set and checks membership before inserting. What should the engineer expect?
MCQ-4A lookup-heavy service keys its cache on strings supplied by untrusted clients. A load test with fuzzer-generated keys pushes p99 lookup latency from 40 µs to 12 ms while the table's load factor stays at 0.7. Which claim should the design review accept?
MCQ-6A service keeps a live cache in an open-addressed table with linear probing and a power-of-two capacity of 1,048,576 slots. It holds 700,000 live keys plus 240,000 keys that were deleted and marked with tombstones. p99 lookup latency has risen from 180 ns to 1.6 µs. Which explanation fits?
MCQ-5A service builds an index in a chained hash table that starts with 16 buckets and doubles whenever an insert would push the load factor above 1.0. One run inserts 1,000 keys. Counting every time an already-stored entry is moved into a new bucket array, how many entry rehashes does the run perform in total?
MCQ-16A team needs a map that iterates in insertion order and supports get, put, and remove by key in O(1) average time. Their constraints: removal must reclaim the entry immediately, with no tombstones or background compaction, and the layout must not add a second heap object per entry. Which internal layout meets all of these?
MCQ-8You are comparing two ways to find element frequencies and duplicate counts in a stream of N items: a hash map, or in-place comparison sorting. Which statement correctly captures the time and space complexity trade-offs between the two approaches?
MCQ-24A log pipeline deduplicates 2,000,000 lines, each 200 bytes, by inserting every line into a Python set. A reviewer signs off with 'dedup is O(n), n = 2,000,000 lines: about 2 million operations.' Which assessment of that sign-off is correct?
MCQ-18A dedup stage receives 40 million 8-byte event IDs as a 320 MB in-memory array on a worker capped at 512 MB, and the array stays resident while the set is built. Design A builds an open-addressing hash set from that array at a 0.5 load factor, with 8-byte keys and 1 byte of metadata per slot. Design B sorts the same array in place. Which conclusion is correct?
MCQ-19A nightly dedup job reads 50 million 8-byte IDs into a `long[]` (400 MB) on a JVM with a 1 GB heap. It must report every duplicate and no unique ID. The current pass adds each ID to a `HashSet<Long>` and dies with `OutOfMemoryError` partway through. The array may be reordered. Which change lets the pass finish inside the same 1 GB heap?
MCQ-9Consider this Python 3 two-sum implementation: ```python def two_sum(nums, target): seen = {} for i, v in enumerate(nums): seen[v] = i if target - v in seen: return seen[target - v], i return None ``` It is called as `two_sum([3, 2, 4], 6)` and returns `(0, 0)`. Which change fixes the bug for all inputs while preserving the one-pass hash-map approach?
MCQ-11A metrics job counts contiguous windows of per-minute deltas whose net is exactly `k`. The engineer writes the standard prefix-sum + hash-map counter but seeds the map empty: `counts = {}` rather than `counts = {0: 1}`. Run on `nums = [2, -1, 2, 1, -2, 3]` with `k = 3`, what does the function return, and which qualifying window is lost?
MCQ-10A service loads an immutable, 0-indexed array of 10^6 integers, each in [0, 1000], and then answers 10^6 range-sum queries over arbitrary inclusive intervals [L, R]. The array is never modified, and the deployment allows at most 16 MB of auxiliary memory. Which preprocessing stays within the cap and gives the lowest per-query cost?
MCQ-20A cache keeps live keys in `items` (an array) and `index` (a dict from key to position) so add, remove, and uniform random eviction are all expected O(1). Its remove method is: ```python def remove(self, v): i = self.index.pop(v) last = self.items.pop() if i < len(self.items): self.items[i] = last self.index[last] = i ``` The cache starts with `items = [7, 2, 9, 4]` and `index = {7: 0, 2: 1, 9: 2, 4: 3}`. It evicts key 7, then evicts key 4. What are `items` and `index` afterward?
MCQ-22A dedup helper is written as: ```python def find_dupes(nums): out = [] for v in nums: i = abs(v) - 1 if nums[i] < 0: out.append(abs(v)) else: nums[i] = -nums[i] return out ``` A caller runs: ```python ids = [3, 1, 4, 2, 3] find_dupes(ids) print(ids) ``` What does the caller print?
MCQ-12A team implements two in-place rearrangements that use O(1) auxiliary space: a three-way Dutch National Flag partition and a cyclic sort that swaps each element toward its final index. Which invariant guarantees that the loops terminate without overwriting an element that has not been examined yet?
MCQ-25A service holds 10^6 distinct session IDs in a Python list sorted ascending. Of 10^6 queries per minute, 90% ask `is session s active?` and 10% ask `what is the smallest active session ID ≥ s?`. Both are answered with `bisect` on the list, about 20 comparisons each. Which change removes the most query CPU?
MCQ-17You are building an in-memory index for 100M timestamped events. The workload is 90% point lookups by exact timestamp and 10% successor/range queries: 'first event at or after t' and 'all events in [t1, t2]'. The SLO is p99 < 5 ms for point lookups and p99 < 20 ms for successor/range. The index receives 50k inserts/sec, each with a unique timestamp, and you have RAM for only one index. Which structure do you choose?