## Amazon Interview Question for SDE-2s

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

All of the operations being O(1) looks like the interviewer is asking for a hashmap implementation.
Simplest way of implementing a hashtable/map requires two things:

1. Data structure to store key value pairs, we take array named A of size = sz
2. A hash function F.

So, our Hashtable will store key value pairs and allow Insert, Delete, Search and getRandom in O(1) time.

``````Insert:

Using the Hash function F, find the index(idx) where the key-val pair will be stored i.e.
idx  = F(key)
and store the key-val pair over there
H[idx] = key+val
Now, if that position is already occupied, it means we have a collision. Collisions can be handled in
multiple ways. One simple way is to keep increasing the index till an empty space found (linear probing):
while ( H[idx] != empty && idx < size) {idx++;}. When empty cell found, insert the key-val pair.

Search and Delete are along the same lines. Just find the idx using F(key) and see if it matches the input key
For delete, just insert an special value (called tombstone) to prevent our linear probing from going wrong.``````

getRandom:
Bascially return any random entry from the array. Pick a random number using random number generator and use
the modulus operator to convert it into a suitable index i.e. idx = random_number % size
Now, return the key-val pair at this size.

Comment hidden because of low score. Click to expand.
0
of 4 vote

Store hash map from items to index in array. For insertion just push back item to the array and add corresponding record to hash map. For deletion determine position of deleted item in array and in array perform swap this item with last item. Decrement size of array and reflect swap changes in hash map.

Comment hidden because of low score. Click to expand.
1
of 1 vote

For deletion determining the position of element in the array is not O(1).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we use built-in data structures to define our own? i.e. if I use a vector or map in my structure, will it be the violation of rules or not?

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is certainly HashMap/HashTable implementation.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.