Microsoft Interview Question
I will assume that we can access any block randomly. And we can know the filename by checking the first block it points to.
Define inPointer[N], outPointer[N], initialized to false.
Then, traverse from block 1 until block N.
if block i points to another block j then
outPointer[i] = true;
inPointer[j] = true;
Now, traverse the blocks again
if outPointer[i] == ture and inPointer[i] == false then
create index and value
It takes 2N time.
Tracking out-pointers is not necessary.
Let A be an N-bit array
1) Initialize all bits in A to 1.
/* assume all blocks are starting blocks */
2) For i from 1 to N
if Block[i] unused bit is set A[i] = 0
else if Block[i] next pointer is NULL
continue
else if Block[i] next pointer points to block j
A[j] = 0 // j is not a starting block
3) file=1;
For i from 1 to N
if A[i] = 1
index[file++] = i;
// here file-name is replaced with an integer which can
// modified to contain names
Space complexity would be less in this algo, Omega(N). The run time would be 2N.
i think we should track the ointers. file can be nore than 2 blocks
N long bit vector to set the already used block while following the file
allocate for the table N/2 array (of file names and beginning blovk number) if we will find more than N/2 files add N/4 array (can declare array of arrays pointer)
Please, let me know what do you think
Eila,
The problem, as stated, boils down to identifying the starting blocks. Which is exactly what my algorithm does.
Sorry I could not understand what you want to say.
What I have done is eliminated the outPointer array of Kevin's solution. That is what I mean by 'tracking out pointers is not necessary'.
My algo takes care that file can be >= 1 blocks. Look at the 3 conditions
[1] if Block[i] unused bit is set A[i] = 0
---> this takes care of unused blocks
[2] else if Block[i] next pointer is NULL
continue
---> this also takes care of 1-block file
[3] else if Block[i] next pointer points to block j
A[j] = 0
---> if j is pointed to by someone j cannot be a starting block.
Since I initialize all bits to 1, after the algo ends the only bits which will remain 1 are the ones which are used and not pointed to by any other block.
Hope this helps.
In my understanding, there are no in-pointer can be tracked since this is never mentioned in the question. In other words, in a block, there is only one (or zero) pointer points to the next part of a file, but we don't know who points to this block now.
To analyze the problem, we can classify those blocks to 4 types:
1. Start: Which is the start block of a file. In this kind of block, there is no unused bit and there is a pointer points to the next part of the file.
2. Body: Which is the middle parts of a file, which has no unused bit and a pointer points to the next part of a file.
3. End: which is the end part of a file, in which, there are some (or no) unused bit in the block and there is no pointer points to the next block.
4. Null: which is null block in the N blocks, it has no used bit and no pointer.
So the first step is to find those "Start" of files, base on the feature of the "Start" block we analyzed before, we can do:
//Initialize a N bit bool array and find "file start" blocks
bool [] fileStart = new bool[];
for (i=0; i<N; i++)
{
// When a block is pointed by another block, it won't be a Start;
// Also, when a block has no used bit(empty block), it won't be a Start;
if ( block[i] has a pointer points to block[x] OR block[x]_unused_bit ==0) { fileStart[x] = False; }
else {fileStart[x] = True;}
}
This step actually fill a table as the following (with fake value):
block 1: true
block 2: false
block 3: true
.
.
block N: false
So after we get this table, we can rebuld the index again:
Initialize index_table indexTable;
for (i=0; i<N; i++)
{
if (fileStart[i])
{
trace the pointer and update indexTable;
}
}
This solution cost N*2 and it might not be the most efficient solution.
nobody discuss about this problem, too easy??????
- anonymous May 24, 2006