Arrays, strings and hashing

Why it matters

Most interview problems arrive as an array or a string, and many are solved by asking: what would I need to look up in O(1) to delete the inner loop? Hash maps and sets are the usual answer. They are just as central in production code (caches, deduplication, joins, indexes, rate limiters), and knowing what their O(1) assumes is part of using them responsibly.

Core ideas

Pattern: Hash map / set lookup. Replace a search with a lookup. In Two Sum, instead of testing every pair (O(n²)), store each value's index and ask whether target - x was already seen: one pass, O(n) expected time, O(n) space. The invariant: when you process index i, the map holds exactly the elements before i. Variants store a first-seen index, a last-seen index or a count, depending on the question. Longest Consecutive Sequence uses a set and starts counting only at values whose predecessor is absent, so each run is walked once.

Pattern: Frequency counting. Count occurrences, then compare or query the counts. Two strings are anagrams exactly when their count tables are equal. With a known small alphabet (26 lowercase letters) a fixed array of counts is faster and uses O(1) space; with general Unicode use a map. Counting also drives majority detection, first-unique queries and window validity in sliding windows.

Canonical keys. To group equivalent items, map each one to a representative that all equivalent items share: the sorted characters ("eat" and "tea" both become "aet", O(L log L) per word) or a tuple of 26 counts (O(L)). The key must be hashable and its equality must match your intent: a tuple rather than a list in Python, and a string or number rather than an array in a JavaScript Map, which compares arrays by identity.

How a hash table works. A hash function maps each key to a bucket; collisions are resolved by chaining (a small list per bucket) or open addressing (probing other slots of one array). Operations stay O(1) on average while the load factor (items per slot) is bounded, which is why tables grow by a constant factor when they fill, giving amortized O(1) insertion. All of this assumes keys hash well: with adversarial keys everything can collide and operations degrade to O(n), which is why some runtimes randomize string hashing. Hashing a key of length L costs O(L).

In-place techniques. Keep a write index w and a read index r with the invariant "everything before w is the finished output; everything between w and r can be overwritten" (Move Zeroes, Remove Duplicates). When values lie in 1..n, the array can serve as its own hash table: mark that value v is present by negating a[v - 1], or swap each value into its home slot. First Missing Positive reaches O(n) time and O(1) extra space this way.

Strings. Strings are immutable in Python, Java, JavaScript and Go, so build results in a list or builder and join once. Know what indexing returns in your language (characters, UTF-16 code units in JavaScript, bytes in Go), which matters as soon as input is not ASCII.

Common misconceptions

• "Hash lookups are always O(1)." They are expected O(1) with a good hash and bounded load factor, plus O(L) to hash a key of length L; the worst case is O(n).
• "Sorting is never competitive with hashing." Sorting costs O(n log n) but can use little extra memory, behaves deterministically and leaves ordered output; prefer it when memory is tight or order matters.
• "Anything can be a key." Keys must be immutable or at least never mutated while stored, and equality must mean what you intend; mutable lists cannot be Python dict keys.
• "A 26-entry count array always works." Only when the alphabet is guaranteed; otherwise ask, or use a map.
• "In-place means no extra memory at all." It usually means O(1) auxiliary space; recursion and some library sorts still use O(log n) or more.

How to approach it

Ask about the alphabet, duplicates, negative values and empty input first. Then state the brute force and name the inner loop you want to remove; a map or set usually removes it. Say what the map stores (value to index, value to count, key to group) and its invariant before coding. For in-place work, draw the regions of the array and keep them true. Interviewers probe the worst case of hashing, whether sorting would do instead, and memory at scale (what if the data does not fit in memory?). Practice for transfer rather than recall: an unseen problem is solved by recognizing which lookup removes the inner loop, not by memorizing employer-specific question lists.