Microsoft IDC Academic Intern program questions

Microsoft with a team of 7 people came to our college for recruiting candidates for both Internship Program and Full-Time Employee(FTE) on 4th January, 2010. Good news, I am now somehow associated with the 9 lettered company 'Micro$oft' (Internship).
Lets get to the selection procedure. Selection consisted of 5 rounds (1 written and 4 interviews)

Written Round (1 hr):

1. Recursion question. You need to find the output (question was very lengthy)


2. Given an integer array, find the lowest n integers


3. Find successor and predecessor of a node in BST


4. There is a live streaming file, a program displays the last n lines of the file, you need to find the test cases for the program


5. Port a drawing and paint tool in Mobile phones

Interview Round:

1. Reverse an integer array, without using additional array


2. Given 2 linked list having integer values (0-9) in each node, you need to add the linked list assuming each linked list represent a number


3. Given an integer array with both +ve and -ve numbers, you need to find the highest sum of the sub array in O(n) time


4. Given a function which finds a given sub sting from a given mother string, give the Test Cases


5. Given a string with more than 1 space between words, compact the spaces without using additional array and in O(n) time. Example:
   Given: foo    bar  hello   world
   Output: foo bar hello world
   


6. Given a character matrix with random letter in each cell. Give a algo for finding if 'microsoft' is present in the matrix, there is no order in which the string exists, only given is each consecutive letter in present in the neighbouring cell of the previous letter.


7. Given an integer matrix mxn with random integers in each cell, print the matrix in spiral order


8. Given a string, you need to reverse each word in that string in O(n) time and without using additional string. Example:
   Given: Hello World
   Output: olleH dlroW


9. A game program was given, I won't be able to explain it here, but the task was to automate the moves of a player

In all it was less of interview and more of a conservation but fully technical. And the most important thing was there was always one interviewer for each candidate in each session.