CODEWITHSUNDEEP
calgorithmdata-structures
Anshul
Anshul

Reputation: 1446

how to read last n lines from a file in C

Its a microsoft interview question.

Read last n lines of file using C (precisely)

Well there could be so many ways to achieve this , few of them could be :

-> Simplest of all, in first pass , count the number of lines in the file and in second pass display the last n lines.

-> Or may be maintain a doubly linked-list for every line and display the last n lines by back traversing the linkedlist till nth last node.

-> Implement something of sort tail -n fname

-> In order to optimize it more we can have double pointer with length as n and every line stored dynamically in a round robin fashion till we reach the end of file.

for example if there are 10 lines in file and want to read last 3 lines. then we could create a array of buffer as buf[3][] and at run time would keep on mallocing and freeing the buffer in circular way till we reach the last line and keep a counter to know the current index of array.

Can anyone please help me with more optimized solution or atleast guide me if any of the above approaches can help me get the correct answer or any other popular approach/method for such kind of questions.

Upvotes: 6

Views: 2329

Answers (3)

phoeagon
phoeagon

Reputation: 2088

How about using memory mapped file and scan the file from backward? This eliminates the hard work of updating the buffer window each time every time if the lines happened to be longer than your buffer space. Then, when you found a \n, push the position into a stack. This works in O(L) where L is the number of characters to output. So there is nothing really better than that is it?

Upvotes: 1

Hitesh Menghani
Hitesh Menghani

Reputation: 987

You can have two file pointers initially pointing to beginning of file.

Keep on incrementing first pointer till it find '\n' character also stores the instance of file pointer when it find '\n'.

Once it find (n+1)th '\n',assign first stored instance of file pointer which we previously saved,to second file pointer.Keep on doing the same till EOF.

So when first file pointer is on EOF,second will be on n '\n' back.Then print all characters from second file pointer to EOF.

So this is solution which can print last n lines in file in single pass.

Upvotes: 4

perreal
perreal

Reputation: 98118

You can use a queue and to store the last n lines seen in this queue. When you see the eof just print the queue.

Another way is reading a blocks of 1024 bytes from the end of file towards the beginning. Stop when you find n \n characters and print out the last n lines.

Upvotes: 9

Related Questions