Katkat
Back

When to use a dictionary vs an array?

ImcSoftware Engineer · HR Screen
HardSoftware EngineerHR ScreenSoftware Engineering Fundamentals

Last updated

This question tests your understanding of the underlying trade-offs between contiguous memory structures (arrays) and hash-based key-value stores (dictionaries), focusing on performance, memory usage, and structural requirements.

The Scenario

You are building a high-frequency trading platform component that tracks the current state of thousands of order books. You need to choose between a contiguous array and a hash-based dictionary for storing order data.

The Task

Compare and contrast arrays (or dynamic lists) and dictionaries (hash maps) based on the following criteria. Provide a technical justification for when you would favor one over the other in a production environment:

  1. Time Complexity: Compare the average and worst-case time complexity for search, insert, and delete operations.
  2. Memory Overhead: Explain why a dictionary generally has higher memory overhead than an array for the same number of elements.
  3. Ordering and Data Locality: Discuss the impact of CPU cache hits/misses when iterating through these structures. How does the concept of memory contiguousness influence your choice?
  4. Design Decision: Suppose you have a set of unique integer IDs ranging from 0 to 1,000,000, but at any given time, only 1,000 of them are active. Which structure would you use to store the metadata for these active IDs, and why?

Example Context

  • Input: A stream of incoming trades with order_id (integer) and price (float).
  • Constraints: If the order_id is always a dense, contiguous integer range (e.g., 0 to 1,000), an array is highly efficient. If the order_id is a sparse, high-cardinality long integer, a dictionary becomes necessary.

Hints

Hint 1

Consider how hash maps handle collisions and why they require a larger allocated capacity than the number of stored items (load factor).

Hint 2

Think about how the CPU prefetcher interacts with arrays versus the scattered memory access typical of a linked-list-based hash map implementation.

Hint 3

Reflect on the 'space-time tradeoff': are you willing to sacrifice memory to achieve constant-time lookups for sparse, non-contiguous data?

Follow-up questions

  • How does the choice change if the number of elements is small enough to fit into the L1 CPU cache?
  • What are the implications of choosing a hash map when order of insertion must be strictly preserved?
  • If you were to implement a custom hash map, how would you handle the performance degradation caused by a high collision rate?