Amazon Interview Question for Software Engineer / Developers
- 5of 9 votes
Write a Program for Dictionary which has functionality of lookup and insert . This program should be able to add words on the fly- Guy February 05, 2014 in United States
I wrote simple code using HashTable
1) Now we are getting too many words what happens
me: Hashtable will dynamically resize resulting into performance hit . Also they might get hashed to same location as well as we might run out of main memory
2) Okay you are out of main memory , How will you scale this program
me: I will create buckets of HashTable lets say 26 buckets for one for each alphabet and would put them on different machines
3) Lets say you are out of memory on those machines too
me: Okay I need to put them on secondary storage . Here we can have fileSystem or Database . I chose database . I will create simple DB schema of BucketNumber and word .
I will use buckets on main memory as cache , if we are not able to find a word in the bucket then query databse with bucket number and words then remove the least number times looked up word (every time we lookup a word we increament the count i.e value in key,value pair on hashtable) from that bucket and add this word .
I mentioned that bottleneck in this case will be every time a word is not present we need to query DB which usually has high latency which will result into performance hit
4) Lets say we are okay with latency but what if we are getting inserting words between that are only between only in two buckets ex. words starting from a and b only.
Now that I think about it, is it better to do this in a trie? What do you guys think?
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer System Design
Interview Type: In-Person
Open Chat in New Window