There was an OA, and then, if you pass, you get invited to a phone screen round with a recruiter. If you pass that, you're invited to an onsite with multiple interviewers. Finally, if you pass that, a recruiter will contact you.

Explain how to design a HashMap with collisions and memory.

Designing a HashMap involves considering two primary aspects:

• Handling Collisions: When multiple keys hash to the same index in the underlying array, a collision occurs. Common strategies to resolve collisions include:

  • Separate Chaining: Each array index points to a linked list (or another data structure like a balanced tree) that stores all key-value pairs hashing to that index.
  • Open Addressing: If an index is occupied, probe for the next available slot using various methods:
    • Linear Probing: Check the next sequential slot.
    • Quadratic Probing: Check slots at increasing quadratic offsets.
    • Double Hashing: Use a second hash function to determine the probe step size.

• Memory Management:

  • Load Factor: This is the ratio of the number of elements to the size of the hash table. A high load factor increases the likelihood of collisions and degrades performance. A load factor threshold is typically set, triggering a resize operation when exceeded.
  • Resizing: When the load factor is exceeded, the HashMap's internal array is resized (usually doubled), and all existing elements are rehashed into the new, larger array. This operation can be costly but is essential for maintaining performance.
  • Initial Capacity: The initial size of the underlying array. Choosing an appropriate initial capacity can reduce the number of resize operations needed.