StartUp Interview Question
Developer Program EngineersCountry: United States
Interview Type: In-Person
The simplest hash map is an array. Assuming that there is sufficient space, on a collision, you can increment in a predictable way to the next empy slot and put the value there. In all cases you need to put both key and value into the array.
As long as the method to increment is the same for insert and search, and you compare the key, you can take care of conflicts that way.
But you need to create a randomizer function that will give the same value for the same key.
Which company was this for?
- puneet.sohi December 03, 2015The aim of a Hashmap would be to store key-val pairs and allow search, insert and del operations in constant O(1) time.
A simplest implementation of a hashmap would be using a Hash Function H which gives you the index i using the key ( i = H(key) ). Using the index we will store the key-val at the appropriate place. However, if the index location is not empty, the simplest solution is to link the new key-val entry to the old one using a Linked List. Ofcourse, there are other solutions as probing and double hashing.