## Hash Table Interview Questions

- 0of 0 votes
The following is the design question I was asked.

Design a dash board.

Should be very realistic.

Should be scalabe .

Should have very less latency .

Can expect millions of updates per second.

Dash board should show :

for each day :

1. city name ,

2.total trips in that city for that day ,

3.total fare it could collect in that city on that day,

4. fare collected from old clients

5. fare collected from new clients (new client is the client who is having his first ride in Uber after registration)

Input : we get two strings s1 , s2.

the format of s1 : trip_id , client_id , city , datetime

the format of s2 : trip_id , fare.

Could you please suggest how to proceed for this kind of question?

- 1of 1 vote
Given multiple strings like "candy", "carry", "dummy", etc. These strings are stored as c3y, c3y and d3y etc. Write a function which returns a boolean if the string (like "carry" is unique in the dictionary)

bool

isUniqueDictionaryWord(char *str)

If the strings are in a file and you load it when the program loads, how will you store it ?

- 0of 0 votes
Find if the characters of the sample string is in the same order in the text string.. Give a simple algo..

Eg.. TextString: abcNjhgAhGjhfhAljhRkhgRbhjbevfhO

Sample string :NAGARRO

- 0of 0 votes
Design a unique hash function for every tweet in Twitter which will be used as part of a service.

- 0of 0 votes
Write a function that takes two integer-valued arrays A and Q and computes a minimum length subarray A[i:j] that sequentially covers Q. Assume all elements in Q are distinct.

- 0of 0 votes
what's use of equals and hashcode function?

- 0of 0 votes
hashmap implementation?

- 0of 0 votes
hashtable vs hashmap

- 0of 0 votes
Second round was intersting: that guy gave me a situation, like I have a file with columns product_id, qty, date, product_name.

I need to sort them based on qty that has been sold out on day. For example, this product has been sold highest on this day.

- 0of 0 votes
Remove duplicates in an array of numbers. You can use a second array or the same array, as the output array. (I used a hash table to do this).

- 2of 2 votes
there are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who)

Write two methods called "getNumber" and "requestNumber" as follows

Number getNumber();

boolean requestNumber(Number number);

getNumber method should find out a number that did not assigened than marks it as assiged and return that number.

requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true.

design a data sturucture to keep those numbers and implement those methods

- 0of 0 votes
[Phone screen]

Let's say I gave you a long String and I wanted you to tell me the most common word in that String. How would you do that?

follow-up: OK, how would you estimate the size and time complexity of this solution? How would you estimate the ACTUAL size usage? (Hint: how many words are in the English language? Would having a dictionary in front of you help?)

follow-up #2: OK, how about if I gave you the entire works of Alexandre Dumas, one of the most prolific authors in history. How would your solution work? How could you change it to solve this more specific problem?

follow-up #3: Now, what if we wanted to find the most common PHRASE in his writings. (Upon clarification, the interviewer wouldn't give a specific length, so I clarified to finding as long as a common 10 word phrase, because anything longer is unlikely.)

- 1of 1 vote
Let's say I gave you a long String and I wanted you to tell me the most common word in that String. How would you do that?

follow-up: OK, how would you estimate the size and time complexity of this solution? How would you estimate the ACTUAL size usage? (Hint: how many words are in the English language? Would having a dictionary in front of you help?)

follow-up #2: OK, how about if I gave you the entire works of Alexandre Dumas, one of the most prolific authors in history. How would your solution work? How could you change it to solve this more specific problem?

follow-up #3: Now, what if we wanted to find the most common PHRASE in his writings. (Upon clarification, the interviewer wouldn't give a specific length, so I clarified to finding as long as a common 10 word phrase, because anything longer is unlikely.)

- -1of 1 vote
Design a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .

- 0of 2 votes
How to design a multi key hash map ( key count can be dynamic. if there are two keys , initiallly which can be used to find the value , keys can be increased to three as well ex: consider school structure. Intially , consider , student id is key , later , should be searchable even with key name , later with grade.

- 1of 3 votes
Design a telephone directory for large ppl (he gave example like design for India). fields will be , first name , last name , number . this should be searchable with first name , last name , number as welll.

later added more complexity like do the same for organisation where even it contains designations. so this should be searchable with designations.

- -3of 3 votes
Having trouble with this array pair difference problem (NOT array pair sum) because of a certain edge case.

Example is: k = 4 a = [ 1, 1, 5, 6, 9, 16, 27] output: 3 (Due to 2x [1, 5], and [5, 9])

So, find the difference that equals to k. I used this code in my interview but realized it was wrong hours later unfortunately. It only gives 2.`public static int arrayPairDifference(int[] a, int k) { HashMap<Integer, Integer> hashMap = new HashMap<>(); int count = 0; for (int i = 0; i < a.length; i++) { if (hashMap.containsValue(a[i] - k)) { count++; } hashMap.put(i, a[i]); } return count; }`

How to account for the edge case of the 2x [1, 5] ?

- 0of 0 votes
How do you implement a HashTable? What data structures are used internally to implement this HashTable?

- 0of 0 votes
Given following definition, implement hashmap

`Public class HashMap { Public void put(object key, object value); Public void get(object value); }`

- 1of 1 vote
Find the first non-repeating character in a stream of characters?

- -1of 1 vote
What is a hash table? Explain how they work (hash function and buckets).

- 10of 10 votes
Consider a hash table with M slots. Suppose hash value is uniformly distributed between 1 to M, and it uses linked list to handle conflicts (if two keys hashed to the same slot). Suppose we put N keys into this M-slotted hash table, what is the probability that there will be a slot with i elements? i could vary from 0 to N.

- 0of 0 votes
Print the actual phone number when given an alphanumeric phone number. For e.g. an input of 1-800-COM-CAST should give output as 18002662278 (note: output also does not contain any special characters like "-").

- -5of 7 votes
need to implement a weather report functionality. user will provide the city name , need to return the weather report.

if weather station exists n functioning properly , will return the weather report of that station .

else ,

will return the nearest available weather station report.

interviewer looking for optimized manner.

looking for datastructures to stores the cities n algo to return the report.

- 0of 0 votes
What should be the output of the following code.

class Test {

public int i=0;

@Override

public int hashCode() {

return i;

}

}

Class a{

psvm(){

HashMap <Test, String> hm = new HashMap();

Test t1 = new Test();

hm.put(t1,”success”);

sysout(hm.get(t1)); //print success

t1.i = 10;

sysout(hm.get(t1)); //NULL

}

}

- 0of 2 votes
Explain how hashtables work internally. How is hashcode generated and what wiill happen to hash code when 2 values are same.

- 1of 1 vote
Given an array which contains the parent of the ith element in the n-ary tree.Parent[i] = -1 for root.

Find the height of the tree.

Gave O(n2) ,space O(1).

Expected Complexity- Linear

You can use extra space if you want.

Example-

{-1 0 1 6 6 0 0 2 7}

0 1 2 3 4 5 6 7 8

0 is the root here.

0 is the parent of 1 5 6

1 is parnt of 2

6 is parent of 3 4

2 is of 7 which is parent of 8.

- 0of 0 votes
Consider a hash table of size N, numbered 0 to N-1. You have to insert integers into this table using the

hashing technique given below:

Let i be the integer to be inserted. Compute the index j of the location where the insertion is to be made as j

= i mod N. If this location is empty then put the element at this position else recompute the next location as

follows:

Remove the right most digit of i. Using the new value of i, recompute j = i mod N.

If the digit removed was odd, then move j locations forward from the current location else move j locations

backward from the current location (assume 0 as even). Note that this move will wrap around both the edges

of the table.

Keep doing this till you either find a free location or all the digits of i have been removed. When i comes to

only one digit, and its rightmost digit is removed, the number remaining is zero - therefore, this will lead to a

zero-step move.

If all digits of i have been removed and yet unable to find a free location, from the last location tried, start

moving in the direction corresponding to the last digit removed. Keep moving till you detect a free location.

Assume that the number of integers inserted is not more than the table size.

Input Specification

The first line will contain just one integer. This will give the table size, N. On the next line will be the list of

positive integers that need to be inserted into the table. The integers will be separated by a space each, and

the last integer will be -1 indicating end of input. (-1 is not to be inserted into the table).

Output Specification

The output should contain, for each integer, the locations that were checked while inserting that integer

(including the location in which the integer was finally inserted). The locations checked for each of the

integers should be output on a line by itself, separated by one space each, each line being terminated by a

new line.

Sample Input/Output

Input

7

38 52 145 16 179 4 -1

Output

3

3 5

5 5 4

2

4 0

4 4 3 2 1

- 0of 0 votes
Q: Given a collection of records which have fields like first name, last name, describe how would you store them in a hash table. Each object passed is to be stored in the hash table and the key has to be returned for subsequent retrieval.

A: Explained about how hash tables work, hash function, what should be the table size (prime number), organization of the hash tables(whether each location in the table stores set of values or single value), from there moved on to collision, collision resolution techniques like open addressing, linear chaining etc.

- 0of 0 votes
Develop a hashing algorithm for strings.

I replied saying MD5 hashing and converting the hash to a BigInt implementation.