Uruppadiya Something

This being my 50th post, I thought I'd write something useful, something that help someone, somewhere, trying to do something. Something like "How I got my Microsoft Internship".
The first round was held on the 24th of July. It was a written round concentrating on more maths than programming, so clearing it was luck. There were 30 aptitude questions and 20 programming questions. I felt the programming questions were easier. One particularly nice question was.
x=3.
x=x<<1<<2;
Value of x?
A : 24. Same operator precedes left to right so, its (3<<1)<<2 = 6<<2 = 24. And not, 3<<(1<<2) = 3<<4 = 48.
Got results at 7 30 p.m. after a looooong and frustrating wait. Plans with Mom for the evening went up in smoke. At least as compensation, I'd made it to the next round.
The next round was held the following day, where we had to write 2 sets of question papers, due to a mistake of the examiners (very frustrating, it was). It was 6 programming questions.
1) Enumerate the characters of a string.
Example
I/P - rajkiran
O/P - aijknr
Used a count array.
2) Insert into a sorted circular singly linked list.
Straight forward implementation with 2 pointers, current and previous.
3) Convert a doubly linked list into a BST.
Step 1 - Find median of the list using fast-slow pointer method.
Step 2 - Make it root.
Step 3 - Append children by finding median of left list and right list. Repeat recursively.
4) Find the leftmost node of a level in a BST where the given value 'n' resides.
Bread-first-search with front of queue being the answer. A slight modification to the implementation of the queue to include a find() method though.
5) Find the pairs of values in a given array which differ by given 'n' value.
SPOJ problem. Sort and search. Or, if val < 10^6 use a vector<bool> count array.
6) In a given array, a certain subarray is reversed. Find and mend.
Example
I/P - 1 2 3 4 5 6 8 7 9 10
O/P - 1 2 3 4 5 6 7 8 9 10
Finished this round and came out with absolutely no confidence. Felt as though, it was my worst birthday ever. (Yeah, it was my birthday :P )
They said results would take a while. So, I decided to forget about it and enjoy the rest of the day which I very sincerely tried to, by sleeping like a buffalo.
Results came by the next Monday, 30th, and surprisingly, I'd made it to round 3. Round 3 was again written but this time guys from Microsoft conducted it, as opposed to the outsourcing that was done for the first 2 rounds.
It was held at 6:30 p.m. and I was almost half asleep when the test began.( Full working days are bad for health :D ) There were 2 questions.
1) Given a number 'n', find the equivalent column name in an excel sheet.
Example
I/P 1
O/P A
I/P 2
O/P B
I/P 27
O/P AA
I/P 702
O/P ZZ
2) In a given BST, exactly 2 nodes are out of place. Find and swap.
The problem with this round was, you had to write code and explain to one from the team. So, bad code = screwed up!
For the first question, I told him that I'd solved a similar question on SPOJ called ITRIX_B, which was base 4, and so I extended it to base 26 here.
( Original problem statement was 2,3,5,7,22,23,25,27 etc hence base 4)
Second question, I did an inorder traversal and put the values in an array, swept through it for a unsorted tuple, found my pair and swapped only the node->element values to arrive at the solution. Though comparing the inorder successor and predecessor was a better solution( which I found out only after coming outside ), the guy was happy with my performance.
After about 45 minutes, results came. A bit confident this time. Cleared. *sigh*
No relief yet, cleared meant interview the next day.
Reached home by 10 and slept off. Next day, hurriedly rummaged through notes for the TOC assessment that coming up in an hour and rushed to the exam hall. ( Yes, this was in the middle of assessment exams. )
Immediately after the test, went to CUIC and waited for my turn. It came up about half an hour later. I was interviewed by a lady.
Oh dear Lord, what nervousness! Trust me, very very nervous.
Two questions.
First one was to delete every kth element from a singly linked list. She was more interested in me writing test cases for it than the actual code itself though she did ask me for working code, which I promptly gave.
Tricky test cases that came to my mind were,
1) k=0, no need to delete anything.
2) k=1, delete all nodes.
3) k>=size_of_list/2, only 1 node will get deleted.
I told this, and she was quite satisfied. Moved onto the next question.
Given 2 sorted arrays, find their median.
Mergesort struck my mind, and I suggested it to her. She said, "Don't think, code.". And, I was like, "Aiyo, mergesort lam 2 semester aache! Marandhu poche."
Remembered the last part of it and tried to code. Presented it to her and she immediately found a bug. (Oh, shit. )
She was a little disappointed. She said, "There's a O(lg n) approach to this. Anyway, your code bug removed, will work. Will you try that?"
I was almost confident that I couldn't find it easily, so I replied (a little diplomatically I think of myself), "Ma'am, if there's a O(lg n) approach, then why waste time repairing a slower code."
She was like, "Umm, ok, tell me how to go about it, O(lg n)"
I thought for a while and gave a modified version of binary search, leaving out a part of search space, based on an assumed mean value. She wasn't ok with it. Eventually, I ran out of time and was asked to wait outside.
I later found that my approach was correct except for the fact that, I should've just searched based on middle index of array considered.
After about 1 hour, amidst the growling of my stomach, I was asked to go to the new CUIC. The last round was up. In half an hour.
It was a single question and there were the 3 of us. Ashwin, Mani and me. Reverse the words of a sentence.
Example
I/P - I am Rajkiran
O/P - Rajkiran am I
This was a written round  and the examiner was satisfied with a straightforward implementation with reversing the whole array first and then delimiter-wise.
After 15 mins, he said the golden words. "You're hired as an intern."
Joyful to hear it indeed! One birthday hadn't gone waste after all. Haha.
And, so ends this really long post. If you read this far, thank you :-)
P.S.: Everytime I see that T-shirt, I kinda feel proud of myself ;-)