Microsoft interview program list

1. Design a game of Tic-Tac-Toe. Only instead of 3x3, this is a game on n x n board. Two manual players play the game. A player wins if there are all "X" or all "O" in either of n rows, n columns or 2 diagonals. What are the classes and data structure you will define? After each move/turn of a player, it is checked whether the player won the game. Minimize this time. Assume having no space constraint.

 2. Given a positive integer, decode it into a string in following way :-
1 - a, 2 - b,3 - c,...26 - z, 27 - aa, 28 - ab........and so on.

3. With a pointer to head node of a linked list as argument, write a function to swap the consecutive elements of the list and return the head node. (Do note change values of any node, only change the links.)
Example :-
1->2->3->4->5->6->7
2->1->4->3->6->5->7

4. Given an array of integers, give the most efficient algorithm to find if the array has a majority element. If the array has a majority element, find this element. (Note : The majority element is the element that occurs more than half of the size of the array)

5. WAP to print the node values of a binary tree

- Even level starting from right to left
- Odd level starting from left to right
Assume that level of root is 1.
a
b c
d e f g
Output: a c b d e f g

6. Assume you have a integer matrix (m x n) sorted over column wise & row wise. WAP to find the kth smallest element from the matrix.

E.g.
int[][] a =
2, 5, 8, 10
4, 7, 9, 12
6, 15, 20, 22
So 5th smallest element is: 7


7. Write code to sort an integer array of size N which has only three unique values 0,1,2 duplicated & randomly placed over the entire array.
- Memory used should be O(1)
- Run time should be O(N)

8. Assume that a binary tree is drawn over a Cartesian coordinate system (with X & Y axis) where the leftmost node is placed at point (0,0). So, we need to traverse the nodes and print in following manner:
For e.g., for this tree
a
b c
d e f g
Output should be:
d,0,0
b,1,1
e,2,0
a,3,2
f,4,0
c,5,1
g,6,0  

9.
Compute the number of connected component in a matrix, saying M. Given two items with coordinates [x1, y1] and [x2, y2] in M, M(x1, y1) == -1 && M(x2, y2) == -1 && |x1-x2|+|y1-y2|=1 <=> they are connected
Example:
-1 0 -1 0 0
-1 -1 0 -1 -1
0 0 0 0 -1
0 0 0 -1 -1
0 0 0 -1 0
0 -1 0 0 0
0 -1 0 0 0
Output: 4. And they are:
-1
-1 -1
-1
-1 -1
-1
-1 -1
-1

-1
-1

10. Given 2 strings, return the max number that can be formed by joining them.
For example, if the strings are:
45 and 456
2 numbers are possible
45456
45645
The output should be
45645

11. Given an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141

12. Given an unsorted array.
With each number, we can associated a sum which is equal to the sum of all the numbers, less than the current number.
We've to find the total sum of all those numbers.
e.g. unsorted array :1, 5, 3, 6, 4.
for a[0]=1, sum[0]=0
for a[1]=5, sum[1]=1
for a[2]=3, sum[2]=1
for a[3]=6, sum[3]=1+5+3
for a[4]=4, sum[4]=1+3
total sum =sum[0]+sum[1]+sum[2]+sum[3]+sum[4] = 15

13. Given a sum find(print) all 2 numbers and their index positions from an un-ordered array that add up the sum value. 1 4 4 3 7 5 8 as array and sum =8 .
So here the code should print 1 (index 0) + 7(index 4)
4(index 1)+ 4(index2), and so on..

14. Given an array { -2 3 5 0 -3 7 -1}. Sort the array in such a way that array should contain -ve numbers first and then zero and then all +ve numbers. (Note: order of +ve number and order of -ve numbers should be same after sorting). For ex: the o/p of above array is {-2 -3 -1 0 3 5 7}

http://www.careercup.com