Monday, April 6, 2009

Reverse a 100 GB file.

How will you reverse the 100 GB file (word by word).
keep in mind the memory constraint. Its a ACSII file. Optimum solution ??

Answer1:
Here's an idea:

Assume the file has N entries. Assume your memory has space for only M, M << N entries.

Read the M/2 last entries of the file and the M/2 first entries. Read then in a order so you don't have to order them or anything. Now write the last M/2 entries at the beginning of the file and the first M/2 at the end of the file. Repeat the processes assuming your file now is smaller: missing M/2 entries at the start and missing M/2 entries at the end.

I know there's a better way to do this ... used to know it ... but it has been a couple years since I used it ... just search for file structures and stuff like that.



Answer2:
 have solution to this :- 
For reversing 100 GB file.... memory constraints will be there to handle... for this suppose at a time you can handle 1 GB of data.. divide the file in 100 sections of 1 GB each (using LSEEK) then reverse the words in each sections and make a Dictionary type (hash table) data structures in which make an entry of the word and its reverse value. When ever you try to reverse any word check the entry in DS if it is there take the value otherwise reverse it and make a entry in DS.

Do we have any other optimized solution to this ??


No comments:

Post a Comment

Note: Only a member of this blog may post a comment.