Common Interview Patterns

1. Introduction

What are Hash Map Interview Patterns?

Hash Map Interview Patterns are structural combinations that pair HashMaps or HashSets with other concepts (like arrays, prefix sums, or sliding windows) to solve search, range, and sequence problems in O(N) linear time.

Why study them?

Many problems seem to require nested loops (O(N²) brute force). By using a HashMap or HashSet as a memory lookup cache, we can remember past values and search targets instantly.

Where is it Used?

Financial Stream Processing: Identifying sliding windows of transaction records summing to a target fraud value.

Streak Trackers: Calculating consecutive user login days in database schemas.

---

2. Mental Model: The Memory Lock

Imagine you are looking for two keys that fit together:

As you walk through a drawer of keys, instead of trying every key against every other key (O(N²) checks), you keep a list in your hand (the HashMap) of all keys you have seen so far.

For each new key x you pick up, you calculate the exact description of its matching partner: partner = target - x.

You check your list. If the partner is on it, you instantly pull both keys out!

---

3. Core Patterns & Implementations

1. Two Sum Complement Pattern

For any element x, check if its complement target - x is in the map. If yes, return their indices. If no, insert x with its index.

2. Subarray Sum Equals K Pattern

Find the total number of continuous subarrays that sum up to K.

We calculate a running prefix sum curSum.

A subarray ending at index i has sum K if there exists a previous prefix sum prevSum such that:

We store the frequencies of all previous prefix sums in a HashMap. If curSum - K exists in the map, we add its frequency to our result.

Initialization: We must seed the map with (0, 1) to handle subarrays starting from index 0.

3. Longest Consecutive Sequence

Given an unsorted array, find the length of the longest consecutive elements sequence.

Insert all numbers into a HashSet to enable O(1) lookups.

For each number x, check if it is the start of a sequence by confirming that x - 1 is not in the set.

If it is the start, count up (x + 1, x + 2, ...) until the sequence breaks, updating the maximum length.

---

4. Visual Trace: Subarray Sum Equals K

Let's find subarrays summing to K = 3 in array [1, 2, 3]:

prefixSums initialized to {0: 1} (meaning prefix sum 0 has occurred 1 time).

---

5. Real-World Applications

Database Login Streaks: Calculating the longest consecutive active days of users in SQL logs (analogous to Longest Consecutive Sequence).

Sub-segment Metrics: Tracking periods in network requests logs where request failures exactly match threshold limits.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test whether you can recognize the running prefix sum pattern:

"Find the length of the longest subarray with sum equal to K." -> Store {prefixSum: firstOccurrenceIndex} in a map. Length is i - map.get(sum - k).

"Check if there is a subarray that sums to a multiple of K." -> Store {prefixSum % K: index} in a map.

Common Mistakes

> 2. Wrong Longest Consecutive Complexity: Incrementing checks for every element x leads to O(N²) worst-case. Only count when x - 1 is not in the set, ensuring each sequence element is visited at most twice (giving guaranteed O(N) time).

---

7. Summary

Two Sum: Complement lookup target - x gives O(N) search.

Subarray Sum: Storing cumulative prefix sums in a frequency map maps subarray intervals in O(N) time.

Streaks: Use HashSets and look for the start of sequences (x - 1 not present) to find streaks in O(N) time.

---

8. Quiz

Question 1: Why is the Longest Consecutive Sequence algorithm O(N) when there is a while loop inside the for loop?

Answer: Because the inner while loop only executes if x - 1 is not in the set (i.e. x is the absolute start of a sequence). For other elements inside a sequence, the condition fails instantly. As a result, each element is visited at most twice (once during set conversion, and once during sequence traversal), giving O(N) overall time.

Question 2: What is the purpose of storing prefix sums in a HashMap for subarray sum queries?

Answer: If the sum of elements from index 0 to j is S_j and the sum to i is S_i (for i < j), then the sum of the subarray [i + 1, j] is S_j - S_i. Setting this difference equal to K means we are looking for a past prefix sum equal to S_j - K. Storing these sums in a map allows O(1) lookup.

Question 3: If an array contains positive numbers only, is HashMap the best way to find Subarray Sum Equals K?

Answer: No. If all numbers are positive, the prefix sum is strictly increasing. You can use the Sliding Window (Two Pointers) technique, which reduces space complexity to O(1) while maintaining O(N) time. The HashMap approach is necessary when the array can contain negative numbers.

Question 4: True or False: For two-sum index queries, the HashMap approach works even if there are duplicate values in the input array.

Answer: True. Since we check target - x before storing x, if we encounter a duplicate that pairs with an already-stored value, the match is found immediately.

Question 5: What is the output of subarraySum([1, -1, 1, -1], 0)?

Answer: 4. The prefix sums are [1, 0, 1, 0]. Seeding 0: 1 in the map, we count 4 matches. Subarrays are [1, -1], [-1, 1], [1, -1] (at end), and [1, -1, 1, -1].