Hash Table Interview Questions
- 1of 1 vote
AnswersFind the Kth most Frequent Number in an Array.
Example:arr[] = {1, 2, 3, 2, 1, 2, 2, 2, 3} k = 2 Result: 3 Because '3' is the second most occurring element.
Follow up: What if the array is extremely large?
- CodeNinja January 04, 2018 in United States for Marketplace| Report Duplicate | Flag | PURGE
Uber Software Engineer Hash Table - 0of 0 votes
AnswersYou are given a Log that contains UserId, ProcessId, Start Time, End Time and Resource Consumption during that time, you need to find out the user who has utilized the most resources.
Example:UID PID StartTime EndTime Consumption
1 1 200 300 100
2 2 230 340 80
1 3 245 315 50
1 4 305 330 20
Time 200 signifies: 02:00.
- CodeNinja September 10, 2017 in United States for AWS
Output: UID# 1
UserID 1 because he has consumed the most number of resources between 200 to 315 (Resource Consumption: 150).| Report Duplicate | Flag | PURGE
Amazon SDE-2 Hash Table Problem Solving - 0of 0 votes
AnswersThe following is the design question I was asked.
- gopi.komanduri July 26, 2016 in India
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?| Report Duplicate | Flag | PURGE
StartUp Analyst Algorithm Business Question Cache Computer Architecture & Low Level Data Structures Distributed Computing Hash Table Ideas System Design - 1of 1 vote
AnswersGiven 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)
- AirWind April 15, 2016 in United States
bool
isUniqueDictionaryWord(char *str)
If the strings are in a file and you load it when the program loads, how will you store it ?| Report Duplicate | Flag | PURGE
Google Software Engineer Hash Table - 0of 0 votes
AnswersFind if the characters of the sample string is in the same order in the text string.. Give a simple algo..
- sachin.and3 October 18, 2015 in United States
Eg.. TextString: abcNjhgAhGjhfhAljhRkhgRbhjbevfhO
Sample string :NAGARRO| Report Duplicate | Flag | PURGE
Nagarro Java Developer Algorithm Arrays Brain Storming Brain Teasers Coding Hash Table String Manipulation - 0of 0 votes
AnswersDesign a unique hash function for every tweet in Twitter which will be used as part of a service.
- Ray October 04, 2015 in United States| Report Duplicate | Flag | PURGE
Twitter SDE1 Hash Table - 0of 0 votes
Answerswhat's use of equals and hashcode function?
- Tom Walker June 07, 2015 in United States| Report Duplicate | Flag | PURGE
Ebay Software Developer Coding Hash Table Java Object Oriented Design - 0of 0 votes
Answershashmap implementation?
- Tom Walker June 07, 2015 in United States| Report Duplicate | Flag | PURGE
Ebay Software Developer Algorithm Coding Hash Table Java - 0of 0 votes
Answerhashtable vs hashmap
- Tom Walker June 07, 2015 in United States| Report Duplicate | Flag | PURGE
Ebay Software Developer Coding Hash Table Java - 0of 0 votes
AnswersSecond round was intersting: that guy gave me a situation, like I have a file with columns product_id, qty, date, product_name.
- darpanshah08 March 24, 2015 in United States for Amazon Prime
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.| Report Duplicate | Flag | PURGE
US Software Engineer Algorithm Hash Table - 0of 0 votes
AnswersRemove 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).
- sush February 27, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Developer Hash Table - 2of 2 votes
Answersthere are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who)
- srcnaks February 02, 2015 in -
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| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Hash Table - 0of 0 votes
Answers[Phone screen]
- utopia August 12, 2014 in United States
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.)| Report Duplicate | Flag | PURGE
Goldman Sachs Software Engineer / Developer Algorithm Hash Table - 2of 2 votes
AnswerLet'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?
- utopia August 12, 2014 in United States
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.)| Report Duplicate | Flag | PURGE
Goldman Sachs Software Engineer / Developer Algorithm Hash Table - 0of 2 votes
AnswersDesign 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 .
- gopi.komanduri August 02, 2014 in United States| Report Duplicate | Flag | PURGE
Computer Scientist Algorithm Android Application / UI Design Arrays Bit Manipulation C# C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Database Distributed Computing Dynamic Programming Hash Table Java Large Scale Computing Linked Lists Math & Computation Object Oriented Design Problem Solving Sorting SQL Stacks System Design Trees and Graphs XML - 0of 2 votes
AnswersHow 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.
- gopi.komanduri July 05, 2014 in India| Report Duplicate | Flag | PURGE
Analyst Algorithm Arrays C# C++ Coding Data Structures Dynamic Programming Experience Hash Table Large Scale Computing Linked Lists Problem Solving Sorting Trees and Graphs - 1of 3 votes
AnswersDesign 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.
- gopi.komanduri July 04, 2014 in India
later added more complexity like do the same for organisation where even it contains designations. so this should be searchable with designations.| Report Duplicate | Flag | PURGE
Analyst Algorithm Arrays C C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Dynamic Programming Hash Table Ideas Large Scale Computing Linked Lists Object Oriented Design Problem Solving Trees and Graphs - -3of 3 votes
AnswersHaving 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] ?
- Johnb March 12, 2014 in United States| Report Duplicate | Flag | PURGE
Algorithm Arrays Hash Table - 0of 0 votes
AnswersHow do you implement a HashTable? What data structures are used internally to implement this HashTable?
- kitilicous December 27, 2013 in United States| Report Duplicate | Flag | PURGE
Hash Table - 0of 0 votes
AnswersGiven following definition, implement hashmap
- juny December 12, 2013 in United States for TrafficPublic class HashMap { Public void put(object key, object value); Public void get(object value); }
| Report Duplicate | Flag | PURGE
Ebay SDE-2 Hash Table - 1of 1 vote
AnswersFind the first non-repeating character in a stream of characters?
- samotgun November 18, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Hash Table Software Engineer / Developer Algorithm - -1of 1 vote
AnswersWhat is a hash table? Explain how they work (hash function and buckets).
- unicorn November 07, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Hash Table - 10of 10 votes
AnswersConsider 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.
- seanren7 August 13, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Hash Table - 0of 0 votes
AnswersPrint 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 "-").
- Jeanclaude June 16, 2013 in United States for Windows Phone| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Hash Table - -5of 7 votes
Answersneed to implement a weather report functionality. user will provide the city name , need to return the weather report.
- gopi.komanduri May 29, 2013 in India
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.| Report Duplicate | Flag | PURGE
Mentor Graphics Analyst Algorithm Arrays Bit Manipulation Brain Teasers C C# C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Dynamic Programming General Questions and Comments Graphics Hash Table Ideas Linked Lists Math & Computation Object Oriented Design Problem Solving Sets Sorting Stacks String Manipulation Terminology & Trivia Threads Trees and Graphs XML - 0of 0 votes
AnswersWhat should be the output of the following code.
- Neo March 07, 2013 in United States for Web Service
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
}
}| Report Duplicate | Flag | PURGE
Amazon Intern Hash Table - 0of 2 votes
AnswerExplain how hashtables work internally. How is hashcode generated and what wiill happen to hash code when 2 values are same.
- abcd March 06, 2013 in United States| Report Duplicate | Flag | PURGE
Ebay Software Engineer / Developer Hash Table - 1of 1 vote
AnswersGiven an array which contains the parent of the ith element in the n-ary tree.Parent[i] = -1 for root.
- grave July 07, 2012 in India
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.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures Hash Table Trees and Graphs - 0of 0 votes
AnswerConsider a hash table of size N, numbered 0 to N-1. You have to insert integers into this table using the
- dev May 27, 2012 in United States
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| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Java Developer Hash Table