Amazon Interview Question for SDE-2s


Country: United States
Interview Type: Phone Interview




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

An array offers the constant time of O(1) for accessing an element using its ordinal index.
However, rarely do we know the ordinal index of the element that we are searching for. This forces us to search through the entire array to find an element.
Searching through an unsorted array has the complexity of O(n).
If the array is sorted, the complexity decreases to O(log n). However, this is still far from the desired O(1) that we would like to achieve.

An array that uses hashing to compress its indexers space is referred to as a hashtable. A hash function is the one which is used to do this transformation.

So, we can use any hashing function to reduce the indexers space. e.g. if we access the records based on SSN, we can select the hashing fuction to be the last-4 digits.

Now, as we can easily see, this would cause collisions i.e. the multiple elements would be competing for the same position in the hashed array. We can resolve collisions using the following methods:-
1) Linear probing ->
Inserting an element - If the position at the hashed value is occupied, move to the next position and store the value. Continue moving to the next position until a free space is found.
Searching for an element - Find the hashed element position, access that element from the hashtable, continue moving to the next position until the element is found.

This leads to clustering of data and is not a very effective collision resolution strategy.

2) Quadratic probing ->
Inserting an element - If the position at the hashed value is occupied, move to the next position in quadratic multiples e.g. (s - 1^2), (s + 1^2), (s - 2^2), (s + 2^2) and so on. Continue moving to the next position until a free space is found.
Searching for an element - Find the hashed element position, access that element from the hashtable, continue moving to the next position in quadratic multiples as used for inserting the value until the element is found.

This gives a better performance than Linear probing but still leads to clustering.

3) Rehasing -> This strategy is used by .NET framework for collision resolution in System.Collections.Hashtable class.
It uses the following hashing function

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

First H1 is used in the above hashing function, if a collision occurs H2 is tried till Hn.

4) Chaining -> This strategy is used by .NET framework for collision resolution in System.Collections.Generic.Dictionary class.
In this method, we just chain all the elements which are located in the same bucket after applying the hashing function.

These are the several methods using which we can build a Hashtable and achieve collision resolution in it.

- RKS October 31, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More