Quick Overview

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.

Explain hash maps and solve array intersection

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

1) Explain the internal implementation of a hash map: underlying array/bucket layout, hash function choice, collision resolution strategies (separate chaining vs. open addressing), load factor thresholds and resizing/rehashing, deletion semantics, expected vs. worst-case time complexities, and typical memory trade-offs. 2) Given k integer arrays, return the sorted list of integers that appear in every array. Then extend your solution to return the integers that appear in at least t of the k arrays (1 ≤ t ≤ k). Provide algorithms, analyze time and space complexity, and discuss edge cases (e.g., duplicates within an array, empty arrays).

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

Implement a simplified integer-to-integer hash map without using Python's built-in dict for storage. The map uses an underlying bucket array with separate chaining for collisions. The initial capacity is 4. The bucket index is key modulo capacity, normalized to a non-negative index. When inserting a new key causes size / capacity to become greater than 0.75, double the capacity and rehash all existing entries. Updating an existing key does not change the size and must not trigger resizing. Deletions remove the key-value pair from its chain, and the table does not shrink.

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.

Hints

  1. Represent each bucket as a list of key-value pairs. On 'put', scan only that bucket to decide whether to update or append.
  2. 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

Given k integer arrays, return the sorted list of distinct integers that appear in every array. Duplicates within the same array should not affect the result: a number either appears in an array or it does not.

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.

Hints

  1. Convert each array to a set so duplicates within that array disappear.
  2. 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

Given k integer arrays and an integer t, return the sorted list of distinct integers that appear in at least t different arrays. Duplicates within one array count only once toward the number of arrays containing that integer.

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.

Hints

  1. For each array, first take its set of unique values, then increment a global count for each unique value.
  2. After processing all arrays, keep exactly the numbers whose global count is at least t.

Loading coding console...