Microsoft Interview Question for Software Engineer in Tests






Comment hidden because of low score. Click to expand.
0
of 0 vote

sounds like a linked list problem. Traverse the linked list.

while(!node.isEmpty()){
   //get file data from node like name of the file
   //and write it in the table you are creating.
   node = node.getNextBlock();
}

- Anonymous May 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You need to reconstruct the table that holds the files and links. Different blocks can belong to different files.

- prolific.coder May 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous May 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- prolific.coder May 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous May 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well for starters how can I get all the blocks of a file. The linked list is not constructed yet, we have to construct it. It would be very inefficient to fetch each block on demand, the list needs to be created before.

- prolific.coder May 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- d May 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- d May 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- prolific.coder May 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can u share the solution you proposed and the areas where the interviewer wanted you to improve upon?

- d May 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can u share the solution you proposed and the areas where the interviewer wanted you to improve upon?

- d May 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous May 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"Here I have to assume that file ends with empty block." Its not a valid assumption. As I said in the problem definition, a file can be in just one block with its nextblock() pointing to null.

- prolific.coder May 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

itterate through the nodes from i=1 to n;
if(!i.isEmpty())
eliminate from the bit array - i.getNext();
//if i.getNext()==NULL,it will not elmnt anythng
else
eliminate- i;


File startings are the node that has not been eliminated.

- Arka May 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }
    }

- prolific.coder May 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()
            }
}

- prolific.coder May 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- prolific.coder May 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- NewStart May 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- prolific.coder May 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sesh June 28, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous June 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Matt B September 08, 2010 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More