Popular Microsoft Interview Questions

By Himanshu Arora

  1. Find and remove a loop from a linked list.
  2. Merge 2 sorted linked lists.
    3. algo - Sorting Algorithms

  3. Implement your own i. atoi ii. atof functions. Write solid secure code.
  4. Find the largest and second largest element in an array.
  5. Find maximum sum of a sub-array in O(N2) and O(N) as well.
  6. Find the kth smallest element of an array.
  7. Linked List A is the subset of Linked List B. Remove all the elements of A from B.
  8. Find the median of 2 sorted array in O(Log(N)).
  9. Unset the highest bit of a number X.
  10. Find the first repeating character in the given string.
  11. Find first non-repeating character in the given string. .
  12. An array of N integers contain numbers from 1 to N-1 and one extra element. Find that extra element.
  13. Given inorder and preorder traversal of a tree, find the original tree.
  14. Implement BFS (Breadth First Search).
  15. Given any node of a linked list, delete that current node.
  16. Find the maximum of three integers, without using any of the comparison operators.
  17. *Find the next number to a number X having same no of binary 1s. E.g. for 3(11) next number having same no of binary 1 will be 5(101).
  18. Find the minimum element in a Binary Search Tree.
  19. Implement Queue using stacks.
  20. Print nodes of level n in a Binary Search Tree.
  21. Print alternate nodes in a linked list in a reverse manner.(Also take the case when last element of the linked list is always included.)
  22. Find the multiple of a no. (in form 2^n) just greater than any no X.
  23. Check if the linked list is a palindrome or not.
  24. Implement partitioning function which is used in quick-sort taking first element as pivot.
  25. In a doubly linked list you have a pointer to the last node. Print the nth node from the beginning.
  26. Check divisibility of a no X by (2^n -1).
  27. 2 Color sort problem i.e. Given an array containing only 0s and 1s. Now bring all 0s to one side and 1s to another just in one pass.
  28. 3 Color sort problem. Do the above problem for 3 numbers i.e. 0s,1s and 2s.
  29. Find the next higher power of 2^n.
  30. Given any node of a linked list(address), remove that node from a linked list.
  31. Reverse the linked list given its head without using recursion.
  32. Reverse the linked list using recursion.
  33. Simple insertion and deletion in a BST.
  34. Find the depth of a given tree T.
  35. Implement Towers of Hanoi using recursion.
  36. Given 2 strings. Remove letters of one from another. For example for “program” and “oat” output: prgrm.
  37. Implement your own realloc function.
  38. Implement simple insertion/selection/bubble sort.
  39. Find center of a linked list in just one pass.
  40. Recursively find maximum and minimum of an array.
  41. A character occurs more than N/2 times in a string. Find that character.
  42. Convert a given equation to a postfix/prefix expressions.
  43. Check if a given binary tree is a BST or not.
  44. Find the lowest common ancestor of given two numbers in a BST.
  45. Check if 2 linked list merges at a common node.
  46. Implement your own pow function for integers.
  47. Reverse the order of words in a given string. For example for “this is a great place” output should be “place great a is this”.
  48. Given a depth d of a complete BST. How many nodes does this BST contains.
  49. Diagrammatically explain how would you insert numbers 92,24,6,7,11,8,22,45,16,19,20,78 in a B-Tree.
  50. Merge 2 sorted arrays of size m & n to another array of size m+n.
  51. There are 2 sorted arrays. First one is of size m+n containing only m elements. Another one is of size n and contains n elements. Merge 2 arrays into sorted array of size m+n in the first array itself.
  52. Implement Binary Search i. using recursion ii. without using recursion.
  53. Find no. of nodes in a BST.
  54. Fundamentals and implementation of Permutations and combinations.
  55. An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand.
    So for instance, 1 2 3 4 5 might become 3 4 5 1 2.
    Now devise a way to find an element in the rotated array in O(log n) time.
  56. A boy has an option to climb either 1 or 2 steps of a stairs at a time. In how many ways can he climb stairs having n steps.
  57. Traverse a Binary Tree (not necessarily BST) in inorder, preorder and postorder manner without using recursion.
  58. Reduce a number X into only one number. E.g. 12345678=>1+2+3+4+5+6+7+8 => 36=> 3+6 => 9
  59. Find kth smallest element in a BST.
  60. Find the lowest common ancestor of a Binary Tree (not necessarily a BST).
  61. You are facing a wall stretching infinitely. There’s a door in the wall, but you don’t know where is it. You can see the door only when you are right next to it. Design an efficient algorithm that enables you to reach the door by walking at most O(N) steps where N is unknown.
  62. Find all the pairs of a no. in a given array that adds to X.
  63. Implement your own memcpy.
  64. Check for the divisibility of a number by 3.
  65. Find square root of a number in O(Log(N)).
  66. Given an array having 16000 unique integers each lying within a range 1 to 20000. How do you sort it under the constraint that we can load only 1000 no.s at a time in a memory.
  67. There are u points in a 3D space. Find the k closest points to the origin.
  68. Given a median of an array. find k no.s closest to the median in the same array.
  69. Given 2 arrays. Find if the arrays contain same elements (may not be in same order).
  70. A DS similar to linked lists is given , it also contains down pointer in addition to the next pointer. A down pointer too can contain nodes just as it in next pointer. Now flatten this DS and make it similar to linked list.
  71. Format the sorted string “aabbbbcccdd” to i. “abcd” ii. “a2b4c3d2″ . Assume that there’s no character repeating itself more than 9 times in second case.
  72. Print the elements of an array in the decreasing frequency but the order should be the same. E.g. 2 5 2 8 5 6 8 8 output: 8 8 8 2 2 5 5 6
  73. Do the above question if an array is a character string.
  74. Find the first 4 character substring in a given string that occurs more than once. and return its starting index. E.g. for “abcdebcxbcdebyz” output should be “bcde” and index is 1.
  75. Given a linked list, write a function to reverse every k nodes (where k is an input to the function). Eg. input 1->2->3->4->5->6->7->8->NULL output for k=3 should be 3->2->1->6->5->4->8->7->NULL.
  76. Give one line C expression to test whether a number is a power of 2. (No loops allowed)
  77. Give a fast way to multiply a no by 7(2^n -1 form).
  78. Given that:
    a) An ASCII character is one byte long and the most significant bit in the byte is always ‘0′.
    b) A Kanji character is two bytes long. The only characteristic of a Kanji character is that in its first byte the most significant bit is ‘1′.
    Now you are given an array of a characters (both ASCII and Kanji) and, an index into the array. The index points to the start of some character.Now you need to write a function to do a backspace (i.e. delete the character before the given index).
  79. Write a routine to draw a circle (x *x + y *y = r *r) without making use of any floating point computations at all.

Also read: Cracking the Coding Interview Book