Solving Array and Hash Problems
Fast recall
Quick revision
Core answer
Whether you use a hash as a frequency map / O(1) lookup and know the patterns (two pointers, sliding window) and Enumerable helpers (tally).
Using an O(n) array search where a hash gives O(1), or nested loops (O(n^2)) where a hash makes it O(n).
Use a hash as a frequency map (tally) or O(1) lookup (seen[x]); arrays for order/index. Patterns: two pointers, sliding window. Enumerable writes it concisely.
Interview-ready guide
Interview answer
Arrays and hashes solve different access problems. An Array is the natural input when order and index matter. A Hash is useful when the algorithm repeatedly asks “have I seen this key?” or “what value belongs to this key?” without scanning all earlier elements again.
The pattern is to decide what fact must survive from one iteration to the next. For duplicate detection the hash can act as a set; for frequency problems it maps value to count; for two-sum it can map a seen value to its index. The stored value should have a clear purpose rather than copying the entire input.
For example, with numbers [4, 7, 1, 9] and target 10, I scan from left to right. At 4, the complement 6 is absent, so I remember 4 => 0. At 7, 3 is absent. At 1, complement 9 has not appeared yet. At 9, complement 1 maps to index 2, so the answer is [2, 3].
Checking before insertion prevents one element from matching itself when the target is twice its value. If duplicates are allowed, the stored index also determines which valid pair is returned. A two-pass design can work, but it needs an explicit rule to avoid reusing the same index.
The nested-search version takes O(n²) time in the worst case. The hash scan uses expected O(n) time and O(n) additional space in normal Ruby implementations. I would state that trade-off, then test no solution, duplicates, negative values, and a pair whose members appear in either order.
Solving Array and Hash Problems
Direct Answer
Use an Array when order, position, or repeated values are part of the problem; use a Hash when the next decision needs a fast lookup by key. A common interview transformation is to scan an array once while a hash remembers what has already been seen—for example, value to index, item to count, or prefix value to position. This often changes a repeated linear search from quadratic time to expected linear time at the cost of linear extra space.
Deep Dive & Architecture
Start by writing the question asked inside the loop. If every current value triggers a scan of all previous values, that repeated search is the likely bottleneck. A lookup structure can replace it only when the earlier data can be represented by a stable key.
In two-sum, the current number x needs to know whether target - x appeared earlier. The invariant after processing position i is that the hash contains exactly the values from positions before the next index, paired with enough information to build the answer. This invariant explains both correctness and the order of check then store.
A Hash is not automatically the right choice. If sorted output, adjacent order, or every duplicate occurrence matters, an array may remain the primary structure and the hash only an index. Hash lookup is expected constant time for ordinary keys, but memory, hashing cost, and hostile collision behaviour still exist.
Ruby details matter at the boundary. hash[key] returns the configured default for a missing key, often nil; fetch(key) distinguishes absence by raising or using an explicit fallback. When nil is a valid stored value, key? or fetch avoids confusing a present nil with a missing key.
Code Example
def two_sum_indices(numbers, target)
index_by_value = {}
numbers.each_with_index do |number, index|
needed = target - number
return [index_by_value.fetch(needed), index] if index_by_value.key?(needed)
index_by_value[number] = index
end
nil
end
raise unless two_sum_indices([4, 7, 1, 9], 10) == [2, 3]
raise unless two_sum_indices([5, 5], 10) == [0, 1]
raise unless two_sum_indices([1, 2], 9).nil?
Common Mistakes & Pitfalls
Using an O(n) array search where a hash gives O(1), or nested loops (O(n^2)) where a hash makes it O(n).
Check your understanding
Answer these without looking back at the article.
- Why must the complement be checked before the current value is stored?
- When do `Hash#key?` and `Hash#fetch` avoid a missing-key bug?
- How would the solution change if every valid pair were required?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.