In order to get ready for a technical interview, I’ll post some of the topics related to my blog. The content that I got is all from HackerRank’s Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell YouTube Video which is linked. Their videos are extremely helpful and everything I posted down below is my notes on it.
What is a hash table?
A hash table basically maps key to values.
Given a key associate a value for it for a quick lookup.
The basic concept is that each key, which in this case is represented as a string, is mapped to a hashcode to an index.
We jump from a string to an index in an array through hashcode.
int hashCode(String s){ // Some implementations }
String → Hashcode → Index
Collisions
There will be problems that we can run into when using hashtables. The number one is that there will be collisions.
Collisions happen when 2 different keys can have the same hash codes but the same index.
One solution to this is “Chaining,” where you put the values in linked lists.
Here’s a sample code:
class Hashtable { Linked List[] data // array of Linked Lists of values boolean put(String key, Person value){ int hashcode = getHashCode(key) int index = convertToIndex(hashCode) LinkedList list = data[index] list.insert(key,value) } }
Runtime:
O(1) for a “good” hash table, Usually what we assume for interviews
O(n) for a terrible hash table, i.e. lots of collisions
Honestly, in reality, the runtime depends on a number of other factors as well.
Topics to dive into deeper (I’ll make blog posts about later)
- Collision handling for Hash Tables
- How Hash Tables grow/shrink
- Implement a simple Hash Table
- Practice Questions!