Geek asks and answers

Random line in file

This question was asked to me during an interview. The interview has been around for a long time, but I'm still thinking about the hte problem and listening to it:

You have a language that contains the following tools: a rand(), whileand forpaths, ifand a method readline()(similar to python readline()). Based on these tools, write an algorithm that returns a random string in the file. You do not know the file size, and you can only go around the contents of the file once.

+5
source share
3 answers

I do not know the desired answer, but my solution will be as follows:

chosen_line = ""
lines = 0

while (current_line = readline()):
    if (rand(0, lines) == 0):
        chosen_line = current_line

    lines++

return chosen_line

Edit: A good explanation of why this works has been posted in this comment .

+7
source

, :

(1) ( , , python list)

(2) rand(), 0 .

, :

. rand(). , .

0

Although Marcin is a similar third option, the Luc implementation always returns the first line when parsing the entire file.

It should be something like:

chosen_line = ""
treshold = 90 
max = 100

while chosen_line == "":
    current_line = readline()
    if (rand(0, max) > treshold):
        chosen_line = current_line

print chosen_line

You can also return current_line in case the line is not selected and you read the whole file.

-1
source

More articles:


All Articles