Interview Cheat Sheets | Hashmaps Cheat Sheet
December 27th, 2023
Introduction
This article will serve to further summarize the excellent overview of hash maps from the tech interview handbook.
Overview
- A
hash table, orhash map, efficiently maps keys to values using a hash function. It employs a space-time tradeoff, offeringO(1)average time complexity for lookups compared to linear search. - Hashing involves computing a hash code to determine the index (hash) in an array of buckets, making value retrieval efficient.
Collision Resolution Techniques
- In case of collisions:
- Separate Chaining: Uses linked lists for each value, storing collided items together.
- Open Addressing: All entry records are stored in the bucket array; new entries find unoccupied slots based on a probe sequence.
Time Complexity
| Operation | Big-O | Note |
|---|---|---|
| Access | N/A | Accessing not possible as the hash code is not known |
| Search | O(1) | Average case, relevant for interviews |
| Insert | O(1) | Average case, relevant for interviews |
| Remove | O(1) | Average case, relevant for interviews |
Sample Questions
- Describe an implementation of a least-used cache and big-O notation of it.
- A question involving an API’s integration with a hash map where the buckets of the hash map are made up of linked lists.
Essential Questions
- Two Sum: My solution
- Ransom Note: My solution
Recommended Practice Questions
- Group Anagrams
- Insert Delete GetRandom O(1)
- First Missing Positive
- LRU Cache
- All O one Data Structure