Amazon Interview Question Software Engineer / Developers
Sorry, i missed something in the above solution, Here is one with the modification.
You maintain a buffer with storage capacity of 1 line. When you see i'th line, put the i'th line in the buffer "with probability 1/i ". At the end return the line stored in the buffer.
It is simple to calculate that, after having seen m lines of the text, the probability of any line being in the buffer is 1/m.
Well Mr Ajay, i guess you need to either explain your solution well or atleast so not blame without explaining.
1. Stream of lines, would mean you will not know the number of lines.
2. What does "i" mean, where did you get "i" from what is the value of "i" ?
Try answering this , in a linked list how will you find a random node.
Start from basics when answering. If you say have a buffer and when you get the ith line put in the buffer, so does that mean i am traversing through the lines ? And i put every line in buffer , so the last line read will be in the buffer, how does that help me in getting a random line out ?
Guys, if you don't understand something... just ask them properly. no, your sarcasm is unwarranted here. There are lots of questions on this site where people give absolutely bullshit answers. Ajay's was, in the very least, giving a faint idea of how to proceed. Yes, its true that if people were more elaborate then it would be better for all of us using these forums, but I guess we can't expect everybody to take so much pains and spoon feed all of us who require it. Ajay's definitely made sense... if it didn't to you, just ask.
Completely agree with nevermind.
In fact, Ajay's post of July 27 made sense enough to give the right answer.
People claiming that it is stupid, 'go check your answer' etc need to get a lesson in reading comprehension.
If you don't understand a solution (unless clearly wrong), ask for clarification before bashing it, at least you will sound sincere, rather than an arrogant, ignorant jerk.
And, if you think a solution is wrong, say _why_ it is wrong, rather than just saying it is wrong. I admit, in some cases, people post utter nonsense.
In this case, though, "no" has some justification for his posts before July 27. Ajay's post of July 24 was quite unclear, IMO. Why don't people at least try to understand what they wrote, before posting?
Anyway...
_rant.Off();
also you speak about "m" what is this "m" ? dont you need to atleast let others know what you are talking about .. i can give a better solution
take k lines and the move j lines ahead and do this p times. once you have p-j lines read then there are d lines in the p buffer with 1/k and 1/r probablity and hence a 1/stream size which is not that much probable , so we have d here, that will work. so add p+u and i will be the solution.
If only you read carefully - I have defined m as "after having seen m lines of the text, the probability of any line being in the buffer is 1/m". and have defined i likewise.
You have a lines of text and you know how many lines you have seen till now. and you just need storage for a single line!
You maintain a buffer with storage capacity of 1 line. When you see i'th line, put the i'th line in the buffer. At the end return the line stored in the buffer.
- Ajay Mishra July 24, 2008It is simple to calculate that, after having seen m lines of the text, the probability of any line being in the buffer is 1/m.