Microsoft Interview Questions

1. reverse each word in a sentence
2. find longest word in a sentence
3. given an array of integers find triplets such that a^2 + b^2 = c^2.
4. 2 robots land on a planet that only has x coordinate (a line). The robots can only go either left or right. The planet has nothing on it except the parachute that each robot has used. You're asked to program the robot to meet each other in the shortest amount of time. You're only allowed to use if statement and "Go left" and "Go right". The if statement can only contain: if the robot meet each other, or if the robot see its own parachute.   
5. Write an algorithm to reverse an array? what is the time complexity?  
6. implement sqrt
7. Make a program that writes a Binary Search Tree to a file. Now create a program that reads those files and recreates a Binary Search Tree.   
8. How would you sort an array if you had infinite RAM? Infinite memory?
9. Create a Priority Queue with all methods.
10. Write program to print Binary Tree using breadth first search and depth first search   
11. Given an array of integers, positive and negative. find an interval in that array, whose elements constitutes the maximum sum
12. reverse linked list
13. recursion to swap binary tree
14. Given an array of ints, return the prime numbers of this array.
15. Given an array of ints, return any number repeated at least 3 times.
16. given a linked list which has two types of pointers, a normal next pointer which points to next element in the list and random pointer which points to random element in the list. Question was to clone this linked list  
17. Remove all duplicate words from a string of words. Not just the duplicate but all the instances of the duplicates need to be removed.
18. How to serialize an array of string? How to deserialize it ?
19. Write an algorithm to validate a palindrome
20. In place, move the duplicates in an array to the end.
21. given a function called drawpoint(x,y) write a function to draw a circle.
22. a few questions on what resolves to true and what resolves to false. will 0.5 resolve to true? if you use -0.75 in an comparison statement (if -0.75) what will be returned from that statement. etc... what else can be used as true, what can be used as false.
23. Pick out k random elements from a very long linked list  
24. There are different currencies being used all over the world. In Japan, it is Yen, in America, its $. America has coins in denominations of 1, 5, 10, 25 and 50. Say if the input is 36, then (1+10+25) = 36. So 36 can be got by suing 1 one coin, 1 ten coin and 1 twenty five coin. So for getting 36, I need to use three coins. Write a pgm for that in all currencies of the world.
25. you have an array of size N whose contents are either 0, 1 or 2 (repeated, of course). Sort the array in a single pass.
26. You have a tree with black and white nodes in it. The goal is to find the longest white path in a tree.
27. Given an array filled with 'n' random numbers, each number may or may not be repeated again in the array, (mix of duplicates and unique numbers) shift all non-duplicates to the start of the array. for example, if array is {4,2,17,2,56,2,4} output should be {4,2,17,56...} the remaining part of array can be modified to anything, doesnt matter
28. Given a string s of length n and an index i (0 <= i <= n). Using only constant extra space, how do you manipulate the string in-place to yield the string s[i, i+1, ... , n-1, 0, 1, ..., i-1]?
29. Pretty printing for polynomial equation
30. Given a string of alphabets, convert them inplace to their ascii values
31. Find the longest substring among two strings
32. Imagine there are n cities (say c1, c2....cn) connected circularly and each of them has a petrol bunk (say p1,p2...pn). The distance between each cities are d1, d2...dn. Here 1unit of petrol will be used to travel 1unit of distance. You can start from any city so that you can go through all of them and reach the same location (city). Find from where we've to begin the navigation.

FOR EXAMPLE:

c1-->c2-->c3-->c1

p1 has 2ltr

p2 has 10ltr

p3 has 4ltr

and the distance between each cities:

c1<-->c2: 3

c2<-->c3: 2

c3<-->c1: 8

Here we've to start at c2 in-order to come back again to the same place.

Explain the logic to find whether u can come back to the same location. Find where to start. Write a program for the same. Write test cases for the same.

33. You're converting a string (s1) into another (s2) by changing the characters in s1. You can do add/delete/replace the characters of s1 to get s2. The cost of any of those operation for a character is 1. Find the minimum cost to convert s1 into s2. Write program and test cases for the same.

For example: Convert "Hi" into "Hey". This would require minimum two cost.

1. Replace 'i' with 'e' in s1

2. Add 'y' to s1.

Now we've s2

34. Write a program to iterate through a 2D grid in a spiral way. Since I can't attach images here, I'll explain it using an array. Imagine you've a nxm matrix of bytes. you've iterate through it in a spiral way. It means, iterate the first row (left to right), then iterate through the right most column (top-bottom) then iterate the bottom most row (right-left) until you reach the center of the matrix. Hope its clear now.
35. You've a singly linked list where every node in the list has a field "random" which points to other node in the same list. Write a function to clone this list (create a new copy of the same). Don't use extra space (just the pointer variables are fine).  
36. Given a BST and a range, print all the numbers that comes in that range.

Ex: the function will be something like: print(node * head, int x, int y);

37. It has to print all numbers within the rage x&y
38. Print max height (level) of a binary search tree.
39. Given an array of integers, determine the sub array which makes max sum.
40. Find LCA of the binary search tree.
41. There is a long contact list in a mobile phone storing Name and other details. Your task is to give the data structure and algorithm for efficient searching among the contacts. As the user types the letters in the text field, the screen should show all the names beginning with those letters (of either first or last name or any other word in the name).
42. Find the 20 longest strings in a text file.
43. Write a function that puts 2 unordered arrays into a 3rd order array   
44. How to write a string class   
45. How to test a file IO save solution (example was the save/load for excel)   
46. How to write the string to float function atof()  
47. Stack to queue   
48. Find all words the input numbers on a phone may represent
49. Given some hardware, design and code a file system (of course, very high level).
50. convert a binary search tree to double linked list.
51. Given a 32-bit integer, return a list of all bit positions of that integer that are set to 1.  
52. deep copy a graph
53. find all palindromes in a string.  
54. how to optimize the memory in finding the frequency of some number in the given long array
55. how to use bst to find the exact number
56. N-Queen problem
57. A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source and has to reach destination. The rat can move only in two directions: forward and down.

In the maze matrix, 0 means the block is dead end and 1 means the block can be used in the path from source to destination. Note that this is a simple version of the typical Maze problem. For example, a more complex version can be that the rat can move in 4 directions and a more complex version can be with limited number of moves.  

58. given a data structure .one node with 2 pointers.. determine whether it is a doubly linked list , tree or nothing
59. Swap nodes of a linked list.
60. Implement a class that lets you define user defined data types (the class should let the user input the number of bits and it should construct a data type having that many number of bits )
61. Given a tic-tac-toe board determine of it had a winner or not
62. Design Minesweeper Game
63. A general discussion on how to decide aspect ratio and how to determine scroll bar is to text it covers ratio for different monitor sizes ,
64. given two nodes in binary tree , how to determine if two nodes are adjacent or not ,
65. Create a data structure that minimizes time complexity of retrieving median and inserting new element. Getting median should be O(1) and insertion should be O(log(n)).
66. string compression: aaabbbbcc ->a3b4c2
67. You have two linked lists that merge at some node. The lists could be billions of nodes long. Find the node where the lists merge in the most optimal time while using a low amount of memory.
68. Write an algorithm to separate all zeroes and ones in an array   
69. Write an algorithm to find the depth of a binary tree
70. Remove a node from Linked list when address of same node is given
71. Split the given linked list into two based on given key - one list containing numbers greater than the key and the other one lesser than it.
72. Remove duplicates in unsorted linked list.
73. Print the matrix helictically
74. Implement the circular queue using array
75. Find whether there exist a path in binary tree whose sum is equal to given number.
76. Optimize it if you know that elements in tree are all positive
77. Test the elevator
78. Given Binary tree. Find the maximum balance binary subtree of the tree.
79. If from 0 to 9, each digit represents set of characters like

0- {a,b,c}

1-{d,e,f}

…

...

like that total 30 characters. write program for a given number ex:945690123. print all possible strings we can form replacing with characters from above set.

80. Given the coordinates of the buildings as (Si, Ei, Hi) represent start, end, height of building. Write program to print the set of (Xi, Hi) coordinates to draw the skyline of the buildings.
81. How do you design in windows to add an extra attribute to files and design such a way to get the search of the file based on that attribute should be efficient.
82. How do you sort a linked list using the most efficient algorithm?
83. what is method overloading and overriding? Difference? Give examples.  
84. Describe the accessibility modifier "protected internal"   
85. What is interface? Give me an example of using interface.   
86. What is thread? Write code sample for a simple thread.   
87. What are the differences between value types and reference types? Give examples of value types and reference types.  
88. Check if a string is a palindrome.
89. Find the intersection point if two linked list
90. Given coordinates, check if a drawing a triangle is possible.
91. Binary tree pre-order traversal without recursion.
92. how to determine if 2 linked lists are merged at a common node in O(n) time
93. construct a data structure that, given a dictionary of words, can form all words while traversing a "boggle grid"
94. Print the binary tree in zig-zag order.
95. Write a function to determine if a binary tree is balanced or not.  
96. Write a function to convert a number in Roman numeral form to a decimal representation.   
97. Write a function to print out the contents of a singly-linked list in reverse order.  
98. Write a function to find the location of k consecutive 0's in a bitstream of length n  
99. Write a function to solve a problem given one set of constraints, then, changing some (but not all of) the constraints, decide how you will change your function, and see if that function still handles the initial set of constraints.  
100. Find count of unique characters in a given string
101. find median of two sorted arrays
102. In a sequence of alphabets (like aaabbddaabbcc) write a program to find the number of the consecutive alphabets in and print the alphabet and number. example :if input is aaabbddaabbcc then output should be 3a, 2b, 2d, 2a, 2b, 2c   
103. Write a program to find out in a sorted array the sum of any two numbers present in the array is closest to the a number given. if you have an array 4, 6, 8,24,36 and the given number is 31 then output should be 24 + 6 = 30  
104. Sort a list of numbers in ascending order using two stacks
105. How to detect the starting point of loop in a linked list which has a loop
106. Consider n people with random birthdays. How large does n need to be before there is at least a 50% chance that two people have the same birthday?  
107. Sort in linear time but without extra space as in counting sort  
108. Given an integer, write a function that rotates the digits to the right.
109. You have a building with 100 stories. You also have two glass balls. You can drop the glass balls as many times as you want before they break. How can you find the floor at which they start breaking with the fewest number of drops?
110. Print Level order of Binary tree.  
111. Prove that there will only one tree possible from a given In-order and Pre-order.
112. Some thread and virtual memory related questions.   Answer Question
113. Iterative In-order, Post-order and Pre-order. bonus points if you are not using extra space.   
114. Implement a Tic Tac Toe game to be played between a user and a computer.
115. N people are sitting in a circle labelled 1 through n. They being counting 1,2,3,.... in a clockwise manner and every person that gets a number divisible by 3 is eliminated. Write a program to figure out which numbered person will remain. What's the time and space complexity?
116. Questions on object oriented programming concepts such as polymorphism, multiple inheritance, and virtual functions.
117. Model the animals in a zoo and draw the class diagrams. Questions regarding when it's right to inherit from a class as opposed to adding a property in the current class, and so on. When to use multiple inheritance, which classes should be abstract, etc.  
118. Implement a solution to the shortest path problem in a weighted directed graph. (Obviously, the question wasn't framed like this, they gave me a map of cities with distances and asked how to get from city A to city B with the smallest distance traveled, and then to write code for it)
119. Write a method that finds all the unique unsorted combinations of a unknown element list without using any loops.
120. Write a function that finds all the times a clocks hours and minutes hand are at 90 degrees.
121. Write a function that reverses the letters in each word using only one char buffer. E.g.: "I work at Microsoft" to "I krow ta tfosorciM"   
122. Discuss how a queue works and how to add and remove items from the queue.