Katkat
Back

Implement a hash table with put/get

ParadromicsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates implementation and design skills for hash-based data structures, testing competency in data structures, hashing, collision handling, and achieving expected O(1) put/get performance in the Coding & Algorithms domain.

Problem

Implement a simplified hash table (hash map) data structure from scratch.

Required API

Design a class HashTable with:

  • HashTable(int numBuckets) (constructor): initialize internal storage with a fixed number of buckets.
  • void put(K key, V value): insert a key/value pair. If the key already exists, overwrite its value.
  • V get(K key): return the value for key, or a sentinel (e.g., null / -1) if the key is not present.

Note: delete/remove is not required.

Assumptions / Constraints

  • You may assume keys are non-null.
  • You must handle hash collisions correctly.
  • Target average time complexity: O(1) for put and get (amortized/expected).
  • You may not use a built-in hash map/dictionary.

Follow-up discussion (conceptual)

  1. What makes a hash function “good,” and how does key distribution affect performance?
  2. How does the choice of numBuckets (and the load factor) impact collisions and runtime?
  3. Compare common collision-resolution strategies:
  • Separate chaining (buckets)
  • Open addressing (e.g., linear/quadratic probing, double hashing)
  1. If using open addressing, describe how probing (“hopping”) works and what pitfalls it introduces (e.g., clustering, tombstones).