Arrays & Hashing
Contiguous storage, O(1) average-case lookups via hash maps, and the frequency-counting patterns they enable.
Try answering in your head first, then click a question to check the model answer.
Q1.Walk through the O(n) hash map approach to the two-sum problem.(show answer)
Iterate through the array once; for each element, compute its complement (target - element) and check if that complement is already in a hash map of previously seen values. If found, you have your pair. If not, add the current element to the map and continue. This trades O(n) extra space for reducing time from O(n²) (checking every pair) to O(n) (one pass).
Q2.Why is a hash map's O(1) lookup only an *average*-case guarantee, not worst-case?(show answer)
If many keys hash to the same bucket (collisions), that bucket degrades into a linear structure (a list or tree, depending on implementation) that must be searched linearly, so worst-case lookup can be O(n). In practice, a good hash function and automatic resizing keep collisions rare, making O(1) a reliable average, but adversarial input specifically crafted to collide can trigger the worst case.
Q3.How would you group a list of words into anagram groups efficiently?(show answer)
For each word, compute a canonical key — either its characters sorted alphabetically, or a fixed-size count of each letter's frequency — and use a hash map from that key to a list of words sharing it. Words that are anagrams of each other produce the identical key, so this groups them in O(n · k log k) time (k = average word length for the sort-based key), versus comparing every pair of words directly.
Q4.When would an array-based frequency count (using indices) be preferred over a hash map for counting characters?(show answer)
When the key space is small and fixed and known in advance — e.g. counting lowercase English letters — a fixed-size array of 26 counters indexed by char - 'a' avoids the overhead of hashing entirely, giving true O(1) worst-case access and slightly better constant-factor performance than a general-purpose hash map for that specific case.