Explain hash maps and solve array intersection
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
Quick Answer: This question evaluates a candidate's understanding of hash map internals — including array/bucket layout, hash function selection, collision resolution strategies, load factor and resizing behavior, deletion semantics, time-space trade-offs — alongside algorithmic problem-solving for computing intersections across k integer arrays and the generalization to elements appearing in at least t arrays, with attention to duplicates and edge cases. It is commonly asked to assess mastery of core data structures, algorithm design and complexity analysis within the Coding & Algorithms domain, testing both conceptual understanding of data-structure internals and practical application of algorithmic reasoning and performance trade-offs.
Part 1: Implement a Mini Hash Map with Buckets and Resizing
Constraints
- 0 <= len(commands) <= 200000
- len(commands) == len(keys) == len(values)
- commands[i] is one of 'put', 'get', 'remove', 'size', or 'capacity'
- -10^9 <= keys[i] <= 10^9
- 0 <= values[i] <= 10^9 for 'put' operations; -1 is reserved as the missing-value sentinel
- Initial capacity is 4; resize by doubling after a new insertion makes load factor greater than 0.75
Examples
Input: (['put', 'put', 'get', 'get', 'put', 'get', 'size', 'capacity'], [1, 5, 1, 5, 1, 1, 0, 0], [10, 50, 0, 0, 11, 0, 0, 0])
Expected Output: [10, 50, 11, 2, 4]
Explanation: Keys 1 and 5 collide when capacity is 4. Updating key 1 changes its value without increasing size.
Input: (['put', 'put', 'put', 'capacity', 'put', 'capacity', 'get', 'get', 'get', 'get'], [1, 2, 3, 0, 4, 0, 1, 2, 3, 4], [10, 20, 30, 0, 40, 0, 0, 0, 0, 0])
Expected Output: [4, 8, 10, 20, 30, 40]
Explanation: Three entries in capacity 4 gives load factor 0.75, so no resize. The fourth new entry makes the load factor greater than 0.75, so capacity doubles to 8.
Input: (['put', 'put', 'remove', 'get', 'get', 'remove', 'size'], [-1, 3, -1, -1, 3, 42, 0], [7, 9, 0, 0, 0, 0, 0])
Expected Output: [7, -1, 9, -1, 1]
Explanation: Removing key -1 returns its old value. Key 3 remains accessible even though it collided with -1 in the same bucket.
Input: ([], [], [])
Expected Output: []
Explanation: No operations produce no outputs.
Hints
- Represent each bucket as a list of key-value pairs. On 'put', scan only that bucket to decide whether to update or append.
- After resizing, every key must be placed into a new bucket because key modulo capacity may have changed.
Part 2: Sorted Intersection of K Arrays
Constraints
- 0 <= len(arrays) <= 100000
- 0 <= total number of integers across all arrays <= 200000
- -10^9 <= arrays[i][j] <= 10^9
- Duplicates inside a single array count only once
- The returned list must be sorted in ascending order
Examples
Input: ([[1, 2, 2, 3], [2, 2, 3, 4], [0, 2, 3, 3]],)
Expected Output: [2, 3]
Explanation: Only 2 and 3 appear in all three arrays.
Input: ([[], [1, 2]],)
Expected Output: []
Explanation: An empty array makes the intersection empty.
Input: ([[5, 5, 5]],)
Expected Output: [5]
Explanation: With one array, the answer is its distinct values sorted.
Input: ([],)
Expected Output: []
Explanation: There are no arrays, so there are no integers that appear in every array.
Input: ([[-1, 0, 1], [1, -1, 2], [-1, 1, 1]],)
Expected Output: [-1, 1]
Explanation: Negative numbers are handled normally, and duplicates do not change membership.
Hints
- Convert each array to a set so duplicates within that array disappear.
- Start with the first array's set and repeatedly intersect it with the next array's set.
Part 3: Sorted Integers Appearing in at Least T Arrays
Constraints
- 1 <= len(arrays) <= 100000
- 1 <= t <= len(arrays)
- 0 <= total number of integers across all arrays <= 200000
- -10^9 <= arrays[i][j] <= 10^9
- Duplicates inside a single array count only once
- The returned list must be sorted in ascending order
Examples
Input: ([[1, 2, 2, 3], [2, 4], [2, 3, 4], [5]], 2)
Expected Output: [2, 3, 4]
Explanation: 2 appears in three arrays; 3 and 4 each appear in two arrays.
Input: ([[1, 2], [2, 3], [2]], 3)
Expected Output: [2]
Explanation: When t equals k, this becomes the ordinary intersection problem.
Input: ([[7, 7], [], [8, 7]], 1)
Expected Output: [7, 8]
Explanation: When t is 1, the result is the sorted union of all arrays.
Input: ([[], []], 1)
Expected Output: []
Explanation: All arrays are empty, so no integer appears in at least one array.
Input: ([[-1, 0], [-1, -1, 2], [0, 2], [-1, 2]], 3)
Expected Output: [-1, 2]
Explanation: -1 appears in three arrays and 2 appears in three arrays; 0 appears in only two.
Hints
- For each array, first take its set of unique values, then increment a global count for each unique value.
- After processing all arrays, keep exactly the numbers whose global count is at least t.