Citadel·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Citadel SWE interview with two fairly meaty technical questions. One was a deep dive on hash map internals and the other was an array intersection problem with a tricky generalization. Left feeling like I could've gone deeper on a few things.

Questions Asked (2)

Walk me through how a hash map works under the hood: the bucket structure, how the hash function is chosen, how collisions are handled, when and how resizing happens, how deletion works, and what the real time and memory trade-offs look like.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

This felt like it was going to be easy and then just kept going.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start with a high-level overview of the hash map's purpose and core components, then systematically dive into each aspect: bucket structure, hash function, collision handling, resizing, deletion, and trade-offs. Use concrete examples and quantify trade-offs (e.g., time vs. memory) to demonstrate depth. Conclude by summarizing the key design decisions and their implications.

Pro tip: Emphasize that the choice of hash function and collision resolution strategy depends on the specific use case and constraints (e.g., security, performance, memory). Mention real-world implementations like Java's HashMap or Python's dict to show practical awareness.

1. Overview and Bucket Structure

Explain that a hash map stores key-value pairs in an array of buckets (or slots). Each bucket can hold one or more entries, depending on the collision resolution method.

2. Hash Function and Index Calculation

Describe how a hash function converts a key into an integer hash code, which is then mapped to an index using modulo or bitwise operations. Discuss desirable properties: uniform distribution, speed, and determinism.

3. Collision Handling

Explain common strategies: separate chaining (linked lists or trees per bucket) and open addressing (linear/quadratic probing, double hashing). Compare their trade-offs in terms of performance and memory.

4. Resizing and Load Factor

Describe how the load factor (entries/buckets) triggers resizing when it exceeds a threshold (e.g., 0.75). Explain that resizing involves allocating a larger array and rehashing all existing entries, which is O(n) but amortized O(1).

5. Deletion and Trade-offs

Explain deletion: in chaining, remove from list; in open addressing, use tombstones or backward-shift. Discuss time complexity (average O(1), worst O(n)) and memory overhead (e.g., load factor, pointers).

Key Points to Mention

Bucket array and index calculation (hash & (n-1) for power-of-two sizes)
Collision resolution: separate chaining vs. open addressing, and their performance characteristics
Load factor and resizing: threshold, rehashing cost, and amortized analysis
Hash function design: uniform distribution, cryptographic vs. non-cryptographic, and handling of mutable keys
Deletion strategies: tombstones in open addressing, and their impact on performance
Time and memory trade-offs: average vs. worst-case time, memory overhead of pointers and empty buckets, and alternatives like perfect hashing

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Given k integer arrays, find all integers that appear in every single array. Then generalize: return integers that appear in at least t of the k arrays, where t can be any value from 1 to k. Analyze complexity and handle edge cases like duplicates within a single array or empty arrays.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The first part I got without much trouble, sort each array and use a frequency map keyed on value across arrays, dedup within each array first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then propose a hash map solution that counts occurrences of each integer across arrays, using a set per array to handle duplicates. For the generalized version, filter counts by threshold t, and analyze time and space complexity.

Pro tip: Mention that using a set per array avoids duplicate counting and that the solution can be optimized for memory by processing arrays sequentially and discarding sets after updating counts.

1. Clarify requirements and edge cases

Ask about input constraints, whether arrays can be empty, contain duplicates, or have negative numbers, and confirm the output format.

2. Design the counting approach

Use a hash map to count in how many arrays each integer appears, ensuring each array contributes at most once per integer by converting it to a set first.

3. Implement the generalized solution

Iterate through the hash map and collect integers with count >= t, returning them in any order.

4. Analyze complexity

Time complexity is O(N) where N is total number of elements across all arrays; space complexity is O(U) where U is number of unique integers across all arrays.

5. Discuss optimizations and trade-offs

Consider memory optimizations like processing arrays one by one and discarding sets, or using a min-heap if t is large, and discuss trade-offs.

Key Points to Mention

Use a set per array to handle duplicates within a single array.
Handle empty arrays gracefully; they contribute no elements.
Time complexity: O(N) where N is total elements; space complexity: O(U) where U is unique integers.
For t=1, return all unique integers; for t=k, return intersection.
Edge case: if t > k, return empty list.
Potential optimization: early termination if an integer's count cannot reach t.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.