Microsoft Interview Question
Software Engineer in TestsYou need to reconstruct the table that holds the files and links. Different blocks can belong to different files.
so it sounds like you have a table where the key is fileName and the value is an Object - which is like a LinkedList (first Node and this node has next Node if file exists in the next block as well).
In this case you will have a for loop, 1 to n and for each file populate the table.
Does this sound right?
Yes, almost right. The interviewer actually explained this to me on the board so it was simpler :)
The table need not have filename as the key it just has the filename and the associated list of blocks. And the first blocks can know its following blocks through nextBlock. The challenge here is
F1 => n3->n5 // simple case
F2 => n7->n2->n1->n0 //complicated case
we have to reconstruct this table. And since in the node there is no way to identify the filename just assume that you can rename the files as you wish.
Looks like to me you only need to store starting block of a file and a file Identifier? Correct?
Because first block has link to its next blocks - so we should not worry about storing such info in the table.
So then what info do we need in the table besides first block?
Lets say before the table got corrupted it had 2 files
file A spanned from node 45 thru 1 to node 56 and had the foll entry in table before it got corrupted
A -- 8->9->1->11->3->12->NULL
file B spanned from node 23 thru 2 to node 5 and had the entry in table before it got corrupted as
B -- 10->7->6->4->2->15->5->NULL
The idea is to start from node 1 and traverse the list that passed thru node 1 (if node 1 is not empty)
Maintain two sets -
lets say set "X" for storing all the nodes encountered and
set "Y" for storing the head node of all the lists traversed.
since we started from 1 (which is non null), the current head of list thru node 1 is 1
continue the foll steps till node n
for node i starting from 1 till n-
check if "i" is not null
if "i" exists in set X
then continue to next node
else
add i to set Y
traverse thru the linked list that passes thru node "i"
for each node ("j") encountered in the list check
if the node "j" exists in set Y
merge the current list with list starting from "j"
- remove j from set Y, since the list whose head was "j"
will have its head as "i"
else
add the node to set X
else
move to next node
construct new table by iterating thru nodes in set Y and list them against dummy file name
following the example
starting it from node 1 to node 15
1st iter - list would be 1->11->3->12->NULL
set X - 1, 11, 3, 12
set Y - 1
2nd iter - list would be 2->15->5->NULL
set X - 1, 11, 3, 12, 2, 15, 5
set Y - 1, 2
3rd iter - 3 is available in set X so move to node 4
4th iter - list would be 4->2->15->5->NULL
set X - 1, 11, 3, 12, 2, 15, 5, 4
set Y - 1, 4
5th iter - 5 is available in set X so move to node 6
6th iter - list would be 6->4->2->15->5->NULL
set X - 1, 11, 3, 12, 2, 15, 5, 4, 6
set Y - 1, 6
7th iter - list is 7->6->4->2->15->5->NULL
set X - 1, 11, 3, 12, 2, 15, 5, 4, 6, 7
set Y - 1, 7
8th iter - list is 8->9->1->11->3->12->NULL
set X - 1, 11, 3, 12, 2, 15, 5, 4, 6, 7, 8, 9
set Y - 8, 7
9th iter - 9 is in set X continue to 10
10th iter - list is 10->7->6->4->2->15->5->NULL
set X - 1, 11, 3, 12, 2, 15, 5, 4, 6, 7, 8, 9, 10
set Y - 8, 10
11th, 12th, - 11, 12 is in set X
13th, 14th are NULL continue to 15
15th is in set X
Lets say before the table got corrupted it had 2 files
file A spanned from node 45 thru 1 to node 56 and had the foll entry in table before it got corrupted
A -- 8->9->1->11->3->12->NULL
file B spanned from node 23 thru 2 to node 5 and had the entry in table before it got corrupted as
B -- 10->7->6->4->2->15->5->NULL
The idea is to start from node 1 and traverse the list that passed thru node 1 (if node 1 is not empty)
Maintain two sets -
lets say set "X" for storing all the nodes encountered and
set "Y" for storing the head node of all the lists traversed.
since we started from 1 (which is non null), the current head of list thru node 1 is 1
continue the foll steps till node n
for node i starting from 1 till n-
check if "i" is not null
if "i" exists in set X
then continue to next node
else
add i to set Y
traverse thru the linked list that passes thru node "i"
for each node ("j") encountered in the list check
if the node "j" exists in set Y
merge the current list with list starting from "j"
- remove j from set Y, since the list whose head was "j"
will have its head as "i"
else
add the node to set X
else
move to next node
construct new table by iterating thru nodes in set Y and list them against dummy file name
following the example
starting it from node 1 to node 15
1st iter - list would be 1->11->3->12->NULL
set X - 1, 11, 3, 12
set Y - 1
2nd iter - list would be 2->15->5->NULL
set X - 1, 11, 3, 12, 2, 15, 5
set Y - 1, 2
3rd iter - 3 is available in set X so move to node 4
4th iter - list would be 4->2->15->5->NULL
set X - 1, 11, 3, 12, 2, 15, 5, 4
set Y - 1, 4
5th iter - 5 is available in set X so move to node 6
6th iter - list would be 6->4->2->15->5->NULL
set X - 1, 11, 3, 12, 2, 15, 5, 4, 6
set Y - 1, 6
7th iter - list is 7->6->4->2->15->5->NULL
set X - 1, 11, 3, 12, 2, 15, 5, 4, 6, 7
set Y - 1, 7
8th iter - list is 8->9->1->11->3->12->NULL
set X - 1, 11, 3, 12, 2, 15, 5, 4, 6, 7, 8, 9
set Y - 8, 7
9th iter - 9 is in set X continue to 10
10th iter - list is 10->7->6->4->2->15->5->NULL
set X - 1, 11, 3, 12, 2, 15, 5, 4, 6, 7, 8, 9, 10
set Y - 8, 10
11th, 12th, - 11, 12 is in set X
13th, 14th are NULL continue to 15
15th is in set X
The pseudo-code looks good but imagine what it would have taken me to get to this solution and write code and test it during the interview. This is not the exact solution I got initially using similar data structures but somewhat different. But he wanted better, so there is more elegant solution that I came up with but even then the interviewer does not seem satisfied. Woof, so much for a tech screen!
Basically we need to find out all the non-empty nodes with only output arrow.
So, have a bit array of N init to false;
for node i from 1 to N,
{
int idx = i;
if(bits[idx]==true) continue;//already visited
while(true)
{
if node[idx] is empty, bits[idx]=true; break;//assuming file ends with empty block
idx = node[idx].GetNext();
bits[idx]=true;
}
}
scan the bits for bits[i]==false; the corresponding i should be the head node;
Here I have to assume that file ends with empty block.
The OP doens't tell us how to determine the end of a file.
This is the solution I came up with during the interview. There is one serious bug that I failed to uncover then and one consideration that I did not go through.
public Dictionary<string,List<Block> > ReCreateTable(List<Block> hardDisk)
{
int[] flags = new int[hardDisk.Count];
Dictionary<string, List<Block>> table = new Dictionary<string, List<Block> >();
for(int i=0;i<hardDisk.Count;i++)
{
if(hardDisk[i].IsEmpty)
{
flags[i]=2;
continue;
}
//This is the bug I had during the actual coding
//else if(hardDisk[i].NextBlock=null)
//flags[i]=0;
else if(hardDisk[i].NextBlock!=null)
{
Block temp=hardDisk[i];
while(temp.NextBlock!=null)
{
int num= (int)Char.GetNumericValue(temp.NextBlock.Name[temp.NextBlock.Name.Length-1]);
flags[num]=1;
temp=temp.NextBlock;
}
}
}
int cnt = 1;
for (int i = 0; i < flags.Length; i++)
{
if(flags[i]==0)
{
Block b=hardDisk[i];
string filename = "File" + cnt.ToString();
//During the interview I was only returning the first block of a //file. This is a better solution.
List<Block> fp = new List<Block>();
fp.Add(b);
while (b.NextBlock != null)
{
fp.Add(b.NextBlock);
b = b.NextBlock;
}
table.Add(filename, fp);
cnt++;
}
}
return table;
}
}
Actually to test this problem we need significant scaffolding. For those of whom are interested.
Lets assume we are a testing a Block b0->b8 such that
b1->b4->b7
b3->b2
b6->b5
b8
b0 is empty
public class Block
{
internal string Name { set; get; }
internal bool IsEmpty { set; get; }
internal Block NextBlock { set; get; }
public Block() { }
public Block(string name, bool isEmpty, Block nextBlock)
{
this.Name = name;
this.IsEmpty = isEmpty;
this.NextBlock = nextBlock;
}
public override string ToString()
{
return Name;
}
}
static void Main()
{
Block b8 = new Block("b8", false, null);
Block b7 = new Block("b7", false, null);
Block b5 = new Block("b5", false, null);
Block b6 = new Block("b6", false, b5);
Block b2 = new Block("b2", false, null);
Block b3 = new Block("b3", false, b2);
Block b4 = new Block("b4", false, b7);
Block b1 = new Block("b1", false, b4);
List<Block> harDisk = new List<Block>();
harDisk.Add(new Block("b0",true,null));
harDisk.Add(b1);
harDisk.Add(b2);
harDisk.Add(b3);
harDisk.Add(b4);
harDisk.Add(b5);
harDisk.Add(b6);
harDisk.Add(b7);
harDisk.Add(b8);
Dictionary<string, List<Block>> table = p.ReCreateTable(harDisk);
foreach (var item in table)
{
Console.Write(item.Key+ " ");
foreach (var block in item.Value)
Console.Write(block + " -> ");
Console.WriteLine()
}
}
The interviewer sent me a reject and other than that he mislead during the interview. I should agree that I made some mistakes
1. I did not write down the structure of the block like I did now. This is important according to gayle
2. I had a frivolous bug that I was not able to uncover after running through with 3 test cases!! This shows lack of attention
3. I was returning only the first block along with the filename when the interviewer asked me to re-create the table explicitly. He could have pointed it out but it shows my lack of attention again.
Hopefully, I wont these mistakes again and land up in a job soon.
maybe my thoughts are wrong but couldn't you attack this problem another way. I would have two maps. StartBlocks and EverythingElseBlocks. I am assuming that a block is comprised of multiple nodes where each node points to the next node in some other block. If I have misunderstood the "design" this can be adjusted accordingly.
1. go through block by block analyzing each "node" in that block.
2. For each node, If node is found in my EverythingElse map then skip it.
3. Add node to "StartNodes"
3. Walk the line for this file and add sub nodes to "EveryThingElse" map. With each node encountered, check against StartNodes. If found, remove and stop (the rest of that file is already in the "EverythingElse".
at the end, I will have discovered all start nodes (in map StartNodes) and a fast lookup to where the rest of the nodes live.
am I way off?
I am trying to follow your logic but couple things. There is no concept of a node "within" a block. Sorry if I misled you and the interviewer at the end of my solution was like aren't you wasting space with the additional flags array? So he is not linient with space constraints.. whatever.
I think newStart is correct. The problem is simply to identify all the 'head' blocks in the group of given blocks and add them to the file table. For this, you start with the first of given blocks and then use the rejection criteria:
a. node is empty.
b. some other node is pointing to this node.
Since we have N blocks, we can use a bitmask as follows to solve the problem:
1. initialize all bits in the mask to 1
2. for block # x, turn off the bit at position x if
block.IsEmpty() == true
3. Also turn off the bit corresponding to the block to which this is pointing
turnOffBit(block->next);
4. once done with all bits, loop through the bit mask and add those blocks whose bit pos is still turned On. these are the head blocks.
MS IDC makes fool of people.
People have to come to office on weekends due to workload and do night outs, no work life balance. They pay 10-20% more make people labour.
Do take the feedback from employees before joining MS.
And work is junk, all junk wor from Redmond is transferred to IDC. Ask any team, whether they design, implement products or just do porting or maintenance or make tools.
The solutions that use a bit array of size equal to the number of blocks of the disk - isn't this a bad idea as it would require the same amount of memory as the original hard disk? Surely there are solutions that don't require O(n) memory.
In addition the question as written says that only the first blocks matter in the table.
sounds like a linked list problem. Traverse the linked list.
- Anonymous May 15, 2010