The title has no link whatsoever with the rest of the post unless I compare Microsoft with the lion. Well , after a sumptuous Italian dinner I was all ready to turn in but then sleep doesn't seem to be coming easy today. (So I probably have become nocturnal finally......)
I faced the famous Microsoft interview today. It was every bit as interesting for me as it was I am sure ..."boring and frustrating " for the interviewer. I managed a solution to the question asked but inspite of hints from him, could not hit upon an efficient solution. I probably deserve to be kicked for this, but it was the same question which was asked in yesterday's interview to others and I had been lazy enough (maybe scared ...whenever I am scared I have a tendency of burying my head in the sand like the ostrich) not to prepare it and go.
The question was simple, sorting a colored balls array so that all the like colors are grouped together. And ofcourse, it was fun for me because at every step the interviewer would make it one step tougher, by increasing the number of colors , or reducing the memory available. :) It was as dynamic as I have heard and read Microsoft interviews are and......I messed it up.
The experience was worth it but I wasn't worth the interview :).....and well it happened that Sudhir gave his job-treat today. Hence the great Italian food and my first Lasagna...(pronounced lasagnia).
Two days back, I made Reliance very happy by expunging(I am hoping expunge is the correct word in this context) my phone bill. I caught up with a lot of friends in India. One thing it did make me feel............ I am happy to be doing what I am doing ...pursuing my Master's. I am lucky to be doing it and I am proud that I have a great family who support me throughout. Kind of like one of the Oscar speeches eh!, .............and yes in a way it probably speaks of my selfishness in not giving up my interests.
What could be a better example than throwing tantrums at home to get a pet dog, ending up buying my golden retriever Bruno when I was in Class 9, spending only three years at home after that and literally dumping him on my mom after that and leaving for my Bachelor's, job and now Master's. When I see him on my web-cam and his golden brown coat which becomes a dark chocolate in winter - I know what I am missing and I know that I will never be able to bring this back - the time that I am not spending with him......at home. Bruno deserves a whole chapter to himself and I don't want this to be the one. Unless you have a pet in your house, you won't realize how easily they steal your heart. They have this way of becoming a part of your lives by unconditionally loving you. And that makes things harder.
Sometimes its really hard to weigh the balance, is it worth it , staying so far away and working towards a dream, not being able to spend time with the people you most want to........................
that is something I will always envy my friends in India for............... and somehow I wish I could put everything together. But that is never possible is it!
Home-sick suddenly ...yes , I guess Bruno was the cause. :)
7 comments:
My thought on Microsoft question
Take a linked list.Keep adding balls one after other.Keep track of last ball of each color in separate pointers.If latest ball is of different color then call insert between using the pointer of that color and update the last ball pointer.At the end u will be having all color balls grouped.
Sweet Simple short algorithm :-)
Though open for bugs and performance tuning in this ...;-)
Easier solution, first scan : count number of balls of different colors, second scan : keep copying to another array. Incase of two colors , becomes easy, just copy to beginning of array for red and end of array for blue and using the counters to keep track. Else also , counters can be used as guide to copy into another array.
This solution takes more memory and also time.As you have to count number of balls of different colors which takes one complete iteration.
In my solution you don't have to count as pointers to last color ball can be tracked which saves you through one complete iteration.If number of color increases u just have to increase number of pointers.So for 256 different colors only 256 additional pointers are required.In this case dynamic array of pointers should be taken.No extra array no counters no extra iteration!!!!!
:-)
Cheers
Saurabh
PC - arrays? in number questions ? tchh tchh
Saurabh - whats the Order of your solution? O(n2) i suppose, if not worse !?
Well is it any different from a general sorting problem??..No, i presume..In sorting also, we have to arrange numbers..Coloured balls can be mapped onto numbers..But the problem is that we will have to first assign numbers to the colours, which will take one iteration thorugh the list of balls..Or we can do it on the fly, but that will make the life complex for the coder..So leave this approach..
My solution kind of gibes with that of saurabh's...
The solution is that define a structure with three fields
struct node
{
char* colour;
struct node* diffCOlptr;
struct node* sameColPtr;
};
Colour will hold the colour info...My solution takes just one iteraion through the input..Basically mainatining a linked list...
Let me cite the approach using the following input sequence...
Red, Blue, Blue,Green, Red, Green..
Now when i start , i encounter Red..Create an instance of the structure..
Now do the following::
structure.colour = "Red";
structure.diffCOlptr = NULL;
structure.sameColPtr = NULL;
Now second one in the sequence is Blue...
Now create one more structure..Initialise its fields as::
structure.colour = "Blue";
structure.diffCOlptr = NULL;
structure.sameColPtr = NULL;
( hey too much of boring details )..
Now compare the colour fields, they don't match..So make the red ball's structure's diffCOlptr point to this blue ball's structure..
Now the third is Blue..Traverse the list now till either the diffCOlptr field is NULL or it matches with some colour field..Now there are two cases::
1. If it matches the colour field, then maintain a separate linked list for the balls of this colour..As in
Make the sameColPtr point to this newly created structure...
2. If structure.diffCOlptr is NULL, then append this node to the list of different coloured fields as we did for the second ball, as in first blue ball..
So we have are maintaing different linked lists..One for the different colours in the input and other lists for the balls of the same colour...Sounds more or less like a hashing function...
Now how to traverse the list..It is simple
Traverse the list of the first coloured balls' list,
if(structure.sameCOlptr != NULL), traverse till ( structure.sameColptr!= NULL)
When this is done, return to the point in the different colours' list..Can save the ptr value in a variable for this...
Now go a step ahead, to the next colour...Repeat the traversal for the nodes of this colour..
Repeat till
(structure.diffCOlptr != NULL)..
Hope the procedure is clear...Though comparisons are there, but those are not equal to the number of elements traversed till now..In the worst case, when we have all balls of differnt colours, we have a the following no of ::
1 + 2 + 3 + .....+ (n-1)..Means, total of n(n-1)/2 comparisons..SO worst case somplexity if O(n^2)..And the best case would be O(n), (n-1) comparisons, when all the balls are of the same colour...SO average would hover between n and n^2...A bit lazy to come up with the average case anaylsis..Maybe don't want to tax my brains much, or maybe don't know how to go about doing it :-)..
That reminds me of our t&p days during placements :) I sure have the ostrich syndrome too, and darn, I begin to hate such on non-sensical questions :D
So let us know the outcome of your job quest, and good luck on that!
O(n) for all cases...
Since the balls are added/arranged dynamically there is no need to iterate again for that ball.Only catch is the ability to handle last color ball pointer locations which can be done by vectors / maps.So in one iteration every ball is processed (only once).
Cheers
Saurabh
Post a Comment