## Hash Table Interview Questions

- 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.)

- 0of 0 votes
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.)

- 0of 0 votes
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 .

- 1of 1 vote
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 1 vote
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).

- 9of 9 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 "-").

- -4of 6 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.

- 0of 0 votes
When would you use a hash table? Specific situations were asked

- 0of 0 votes
There is a website and clients visit it multiple times. Also a log file which keep track of client id, visited url, date visited. Print the client id, url, no of times it is visited on a particular day.

- 0of 0 votes
What is the possible problem if Hash Table grows more than 30 gb (ignore problems like bad hash function )

- 0of 0 votes
Wht is Hastable and give time complexity to insert, lookup , wat is characteristic of good hash function..

- 0of 0 votes
3) In terms of practicality, describe a hash table.

- 0of 0 votes
what is the most significant advantage of hashtable

- 0of 0 votes
what is the difference between hashmap and map

- 0of 0 votes
Explain about hashing. Give one example of a hash function and explain how collision is handled.

- 0of 0 votes
What is a hash table? Why is it better than other data structures? Compare hash table with tree? Discuss advantages of one over the other.

- 0of 0 votes
What is the difference between hashtable and encryption.

Note: These questions were asked just to screen out non-eligible candidates and not during any phone interview or at onsite(are u kidding me :))

- 0of 0 votes
What is the difference between hash table and binary search tree? Give an example that we prefer to use binary search tree rather than hash table.