Amazon Interview Report
- 0of 0 votes
AnswersBar raiser round
- sachin323 June 03, 2013 in United States
Write code to return Kth smallest node from BST| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersWrite a Program for Dictionary which has functionality of lookup and insert . This program should be able to add words on the fly
- sachin323 June 03, 2013 in United States
I wrote simple code using HashTable
follow up
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| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersWrite code to Print the power set of given string
- sachin323 June 03, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm