?
Solved

Algoriothm/puzzle

Posted on 2008-10-03
5
Medium Priority
?
432 Views
Last Modified: 2010-10-05
Assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability.
0
Comment
Question by:shwetasingh206
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
5 Comments
 
LVL 84

Accepted Solution

by:
ozo earned 672 total points
ID: 22632035
perldoc -q "How do I select a random line from a file"
       How do I select a random line from a file?

       Here's an algorithm from the Camel Book:

               rand($.) < 1 && ($line = $_) while <>;

       This has a significant advantage in space over reading the whole file
       in.  You can find a proof of this method in The Art of Computer
       Programming, Volume 2, Section 3.4.2, by Donald E. Knuth.
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 664 total points
ID: 22632041
>> a character out of the stream with equal probability.

with equal probability ? What do you mean ? You want a uniformly random character from the stream without knowing the size of the stream ?

If so, simply do something like this :

1st character : save it in the buffer
2nd character : save it in the buffer with 1/2 probability
3rd character : save it in the buffer with 1/3 probability
...
nth character : save it in the buffer with 1/n probability
...
0
 
LVL 84

Expert Comment

by:ozo
ID: 22632078
So for single characters
stream | perl -ne 'BEGIN{$/=\1}$char = $_ if rand($.) < 1;END{print $char}'
0
 
LVL 22

Assisted Solution

by:NovaDenizen
NovaDenizen earned 664 total points
ID: 22636477
This is the way to do it, but it requires additional storage to hold the count of the number of characters you've read.  There is a counter behind $., or perl is using ftell() and the counter is hidden in the runtime libraries.

So really you need something like ceil(lg(n)) + 8 bits of storage to handle up to n characters of input.
0

Featured Post

Will your db performance match your db growth?

In Percona’s white paper “Performance at Scale: Keeping Your Database on Its Toes,” we take a high-level approach to what you need to think about when planning for database scalability.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Michael from AdRem Software outlines event notifications and Automatic Corrective Actions in network monitoring. Automatic Corrective Actions are scripts, which can automatically run upon discovery of a certain undesirable condition in your network.…
Suggested Courses

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question