Author |
Topic: appending a file (Read 584 times) |
|
ic10503
Junior Member
Gender: 
Posts: 57
|
 |
appending a file
« on: Jun 25th, 2008, 3:02pm » |
 Quote  Modify
|
There are two files A and B both of sizes 5 GB each in a 10 GB harddisk.. You have some amount of ram space. Given functions for opening-closing a file, seeking anywhere in a file and a function truncate() which truncates the last n lines of a file.. We have to develop an algorithm to append file B to file A... please also give the complexity of your solution
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: appending a file
« Reply #1 on: Jun 25th, 2008, 3:39pm » |
Quote Modify
|
How are files allocated in the system? Is insertion before the first location allowed?
Assuming, we can only write to the end of a file, the process can be divided into,
1. Fill the ram with last 'n' lines of B (however many fits)
2. Truncate those lines from B
3. Write a file C in where the lines are in reverse order
4. Repeat till the entire B is removed and its reverse ordered C is obtained
5. Fill the ram with last 'n' lines of C (however many fits)
6. Truncate those many lines from C
7. Write those lines to A in reverse order
8. Repeat the process till the entire C is removed and you are left with file A which is `cat A B`.
If we can insert records before the first line, the reversal can avoided by prepending A to B.
Time complexity :
#lines(B) = m
readtime_of_n_lines = t1
writetime_of_n_lines = t2
Then, ~ O((m/n) (t1 + t2) + m)
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print