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.

Google Interview Questions

1. two numbers sum up to some designated number.
2. find the minimum window in a string which contains a list of characters.
3. how to optimize/parallel a cache for an mobile app
4. how to design a excel
5. how to implement search in G+
6. check if a string matches a regular expression
7. how to best design a algorithm?
8. In a sorted matrix (sorted by rows and columns), find an element.
9. Merge two sorted arrays  
10. Two find the lowest common parent for two nodes in a BST  
11. Three coke machines. Each one has two values min & max, which means if you get coke from this machine it will load you a random volume in the range [min, max]. Given a cup size n and minimum soda volume m, show if it's possible to make it from these machines.

1. n-ary tree serialize and deserialize question. Write both methods.
2. Design a thread-safe circular queue using fixed size memory allocation. Any type of data could be pushed in. No overwrite is allowed. Further: Optimize performance, can you do it without lock?
3. A^2+B^2+C^2+D^2= N. Given a N, print out all possible combination for ABCD. Can utilize DP?
4. Extract all the the combinations of a target substring that appear in a source string. I.e: target: "abc", source:"abcdefgbcahijkacb12df", solution: {abc, bca, acb}
5. Given a rotated sorted array, find where it is rotated
6. If you have a computer with no division operator, how do you do it
7. How to reverse the words in a sentence in place?
8. All the possible ways to find the minimum values in an unsorted array.
9. Design an efficient service that allocates phone numbers to mobile customers.
10. Design a HashMap
11. Find out whether parentheses are right in a string
12. Select K largest number from N
13. What's the difference between a non-exclusive lock and an exclusive lock?
14. Write a memory manager oriented towards millions of very small allocations (less than 10 bytes)
15. Write an algorithm to print out all the words in a boggle board
16. Given a list of sorted words, output the order of the letters used to sort them.
17. You are given 2 strings. Find all symbols that are in both strings.
18. You are given a BST-tree. Find duplicated values.
19. Design cache with LRU policy. Elaborate on performance. O(1) time complexity was expected.
20. Write an algorithm to decide the shortest path from one letter to another letter on TV's remote control.
21. find a path between two nodes in a graph
22. Find the maximum consecutive sum of integers in an array.
23. Implement iterator for a list of lists which may contain empty lists.
24. How to inorder traverse binary tree without recursion?
25. You are given an array that represents bills in certain currency (For example 1, 2, 5, 10) and an amount, for example 17. You should output the number of possible combinations of bills that sum to the given amount. For example, {10, 5, 2} is valid combination, {10, 5, 1 ,1} also.
26. I did not ask questions like does the order of bills matter, i.e. is {10, 5, 2} same as {2, 10, 5}.
27. Write a program that reads a file, randomizes it's lines and writes the output to another file.
28. Design a system or algorithm to catalog all of the worlds books?
29. Find the balance point in an array. (The index where the sum of the elements to the left it is the same as the sum of the elements to the right of it.)
30. I was given a number of intervals on the integer number line and had to write a program in Java that takes two sets of intervals and creates a set of intervals that combines them
31. What data structures would you use to model a family tree? How can you determine whether two persons are related or not?
32. Implement a function boolean matches(String text, String pattern) to find match pattern in the string, pattern can be separated but the order of letters in pattern cannot be changed.
33. Implement an interface to statistics the frequency of new value added.
34. Make an algorithm to extract the skyline from the rectangles.
35. Estimate the total storage size of GMAIL  
36. Implement a blocking queue in Java.
37. Implement a system to serialize and deserialize strings
38. Design a 4-way software cache driver.
39. Compare HashTable and Binary Tree(pros and cons, why use binary tree in some place, the time complexity of insert, delete of hashtable and binarytree)
40. find the longest prefix
41. Find the intersection of two integer lists
42. If you have an unsorted array of numbers from 1-100, except 1 of those numbers is missing, how do you determine which number is missing  
43. How do you implement a hash?
44. Remove duplicate lines from an large text
45. Out of 10 coins, one weighs less then the others. You have a scale. How can you determine which one weighs less in 3 weighs? Now how would you do it if you didn't know if the odd coin weighs less or more?
46. Given inputs from Google Search, you have K chunks. Each chunk is individually alphabetically ordered (apple, banana, cat) ... (*apple, *banan, *cat). You want to merge all chunks into a single list. How would you do it? What limitations are there to your approach?
47. How to find the max number of a shift buffer queue. For instance, there is an array like 5, 6,8,11,1,2, how to find the max number, which is 11 in this example.
48. Judge if a Sudoku solution is right.
49. Write a program to compute if one string is a rotation of another.
50. Given two sorted integer arrays, write an algorithm to get back the intersection.  
51. Given the daily values of a stock, find how you can lose the most with one buy-sell trading.
52. Given a set of strings, a number 'n', and a function that takes a string and gives back a score, find the n largest scored strings in the set.
53. Describe what you will do to enhance the indexing performance of the map service.  
54. Reverse all the words in a string
55. Quad tree
56. Write the binary search.
57. Analyze quick sort.
58. Game of Life - write a function to calculate next state of the board based on current state
59. You have a n number of cities. Lets say city 1 has some information that needs to be sent to all other n-1 cities using minimal cost. Cost between each pair of cities is given. any number of cities can transmit the information once they receive the information but the overall total cost should be minimum
60. Given an array of structs: write a function that finds equal values in all the structs in the array
61. Implementing a system for fast anagrams retrieval given a large file of words
62. You have a n number of cities. Lets say city 1 has some information that needs to be sent to all other n-1 cities using minimal cost. Cost between each pair of cities is given. any number of cities can transmit the information once they receive the information but the overall total cost should be minimum  
63. Given two numbers m and n, write a method to return the first number r that is
64. divisible by both (e.g., the least common multiple).
65. Write a code to find out if two string words are anagrams
66. Create a graph class and graph traversal algorithms.
67. Maximum contiguous sub sequence sum problem.
68. What are the side effects of typing your password in the user name field?
69. Given a graph, find if it represents a tree
70. Card game, given 4 cards. If by +,-,/,* and () you can make 24, you win. Write a program to play this game.  
71. Find a number in a sorted array with duplicates in O(log n) time.
72. How would you determine if someone has won a game of tic-tac-toe on a board of any size?  
73. Given a string of characters, find the character with the highest frequency
74. Design a networked 'snake' multiplayer game. What are the problems and issues to be solved? When the network 'splits' I want the game to continue for all players.
75. Write a function to convert a collection of strings into a single string and a function to convert it back.
76. Given a bitmap of open and closed cells, where you can traverse through open cells but not closed ones and a set of origin points on the bitmap, write a program to find the shortest path to every reachable open cell from any of the origin points.
77. Find the largest 100 numbers out of a list of a trillion unsorted numbers
78. Implement a stack that pops out the most frequently added item.  
79. Write a function to perform incremental search
80. Given an unsorted array of integers, find first two numbers in the array that equal a given sum.
81. How to add a counter to www.google.com to track the billionth user.
82. You have a 64bit integer counter set to 0. How long it will take to overflow the counter given that you are incrementing it at 4Ghz speed.
83. Comparisons of trees and hash tables. What are the tradeoffs of using one versus another.  
84. Quickly estimate 2^64 without using a pen/paper.
85. Computing average power of last 5 minutes.
86. Serialize an array of integers in an arbitrary way. Imagine a 4x4 grid where the cells are visited in a snakelike pattern.
87. Given a list of integers, Print out all triples that sums to zero.
88. Write a function that will return the second longest string in a list of strings. You have to do a single pass on the list.
89. Given a 2D boolean array. Return the length of the biggest square where all elements inside it is true.
90. Implementing a system for fast anagrams retrieval given a large file of words
91. If you have a ransom letter and magazines, can you construct the ransom letter from the words in the magazine.
92. Discuss data structures for reading URL->File content (crawler data e.g.) and remove duplicates.
93. In a sorted array, find the number closest to a given number
94. Design the friend suggestion of facebook, write a code, complexity, reverse a sentence such that the ordering of words is reversed but the words aren't changed.
95. Explain pointer arithmetic
96. What guarantees does the synchronized keyword give when used on a method? When a thread calls the synchronized method, can another thread call a method that isn't synchronized on the same object?
97. Code game of life
98. Algorithm to get Index of a permutation when all permutations arranged in lexicographical order and its Complexity.
99. Discuss and implementation of flattening a binary search tree into string representations.
100. Given a sorted array A[1..n] with n integers, and an integer t, find all pairs (x,y) of elements in A such that x+y is smaller than t. 2. Can we do better if we seek (x,y) for which x+y=t?
101. print out the powerset of a set. use any programming language you want.
102. Write a function that computes the intersection of two arrays. The arrays are sorted. Then, what if one array is really larger than the other array?
103. Imagine you are creating a program that can handle multiple requests at a time and respond to them as they come. Define run time, classes, and methods.
104. Find the number of connected components in a Graph.   
105. Card game, given 4 cards. If by +,-,/,* and () you can make 24, you win. Write a program to play this game
106. Implement B+tree
107. How can you optimize the code written for B+ tree.   
108. Create a Java method that clones a DAG (Directed Acyclic Graph).
109. Given a tree and leaf node, write the code to make the leaf node as root of tree.
110. Write the code to check if graph is bipartite or not?
111. Write a stack that keeps track of min and max elements.
112. Write a priority queue<E> with three methods. Insert(E Element, int priority). E Pop(), update(E Element, int new_priority)
113. Giving a windows size K and an array of size N, find the minimum of each window as it slides through the array
114. Write the code for "moving of the robot": there is a "generator" -- each time generate 1/0, when 1 the robot will move up, when 0 will go down, write the function to make the robot move up forever.
115. Was asked how I would implement division without using division or mod operators. The answer should return in the form quotient r remainder.
116. Design the battle ship game
117. Btree traversal
118. Write code to shift a string with rotation [a, b, c << 2 = c, a, b]
119. Write classes representing expression tree for a simple calculator. You care only about constants and basic binary operators. Write function evaluating expressions.
120. How to count frequencies of characters in a string. What if the string is too huge? When is it reasonable to distribute across machines? How to find the most frequent character in the distributed scenario with a minimum data exchange between machines?
121. Convert a one dimensional array of Strings containing [a,b,c, d,e ...z] to 2 dimensional array of a2[aa,bb,cc]
122. Find the next larger node and write down code in BST
123. Search smallest value from a tree. What if you have enough memory, how to improve the speed?
124. Make an algorithm that, having N cards in N+1 slots (one slot empty), reach a final configuration (given initial one), showing all the steps. A move is valid only if it is moving one card from to the empty spot (letting the card's place now empty).
125. Find the number of inversions in an array (describe & code)
126. Find collinear points in a given set of 2D points (describe & code)
127. How much ways is it possible to use to go on the top of stairs with n stairs if we can go up by 1 or 2 steps?  
128. write a string splitting function that did not copy the string
129. How to build a distributed algorithm to compute the balance of the parentheses?
130. Given a sorted array A[1..n] with n integers, and an integer t, find all pairs (x,y) of elements in A such that x+y is smaller than t. Given a sorted array A[1..n] with n integers, and an integer t, find all pairs (x,y) of elements in A such that x+y is smaller than t.
131. You are given a text file too large to fit in memory and 3 strings A, B, C. For each string, you have a sorted array listing the positions of the string in the file (e.g., inverted indices). Find the smallest window containing the 3 strings. Order of appearance does not matter.
132. Many questions about advanced C++ language features such as solutions to the "diamond" multiple inheritance problem and how to implement a virtual constructor.
133. Remove a node from a singly linkedlist without knowing the head node. All you have is the node itself.
134. If you had a list of appointments (each appointment has a begin time, an end time, and a boolean hasConflict), how would you efficiently go through them and set the hasConflict boolean for each. You cannot assume they are sorted in any way. Keep in mind that one appointment may be very long, etc.
135. How do you find the median of a set of numbers?
136. What are the issues with floating point calculation? For example, 1.0f + e-30, is there any issue with the statement.
137. How would you sort a file which is too large to fit in memory.
138. Given a directory with lots of files, find the files that have the same content (the file names are different). I think file format is not considered, since when I said the size of the file with the same content should be the same, the interviewer did not deny it.
139. Partition an array in such way zeros to be moved on the left side of the array, other numbers on the right side of the array. Extra storage not allowed, only in-place.
140. write code to find the second shortest path between two given nodes in an undirected graph.  
141. You're given a string, and you want to split it into as few strings as possible such that each string is a palindrome.
142. How would you sort a file which is too large to fit in memory.
143. What are the issues with floating point calculation? For example, 1.0f + e-30, is there any issue with the statement.
144. when you are doing "read()" call what it happening under the hood in user space?
145. Given two binary search trees, write function which tells if two such trees are the same – (i.e. same info in the nodes, same branching to left and right at every node).
146. How to find a median in a large file of 64-bit integers
147. Input is a 4x4 table with letters. One starts from any of the 16 elements and can move in one step to any of the 8 neighboring cells not visited before (up, down, left, right, up-left, etc, no hyperspace jumps between rows 1 & 4, columns 1 & 4). Every time step is made letter in that cell is added so a word is built as we walk. These generated words are looked up in external dictionary (function to look up in the dictionary is provided, I did not understand significance of this dictionary well) and the goal of the exercise is to output all words generated by all possible table walks and which are contained in the dictionary.
148. It is a phone interview. Given a box of pencils with different colors, design an algorithm to find the duplicate pencils with the same color
149. write code to find the second shortest path between two given nodes in an undirected graph.
150. What are the issues with floating point calculation? For example, 1.0f + e-30, is there any issue with the statement.
151. We can calculate the variance of a set of number by first finding the average and then getting square of the differences with each number. Another way of doing this is to actually find the summation of square of all the numbers and then deducting an expression involving square of the average. The question was, what the flaw of using the second approach.
152. Remove a node from a singly linkedlist without knowing the head node. All you have is the node itself.
153. Partition an array in such way zeros to be moved on the left side of the array, other numbers on the right side of the array. Extra storage not allowed, only in-place.
154. Was asked how I would implement division without using division or mod operators. The answer should return in the form quotient r remainder.
155. Given a directory with lots of files, find the files that have the same content (the file names are different). I think file format is not considered, since when I said the size of the file with the same content should be the same, the interviewer did not deny it.
156. Write an algorithm to test if n is power of 2   
157. Given 2 numbers x and y, check if x is an integer power of y. For instance, x = 8, y = 2 would return true and x = 10 and y = 2 would return false since the first one is an integer power but the second isn't.
158. Given a dictionary of words, decrypt it using a given decrypt() function
159. If you had a days worth of queries, how would you sort the queries by the letter q, and then return a sufficiently random sample of 1000 queries. How do you ensure randomness?
160. Design an algorithm, which can record the largest number in an ever-upgrading sequence.   
161. How to choose pivot in quicksort
162. What happens when you enter a search query on google ? ideas about sorting results ?   
163. Reverse a linked list in place
164. The mouse in the maze problem. Shortest paths to reach outside
165. Reverse the bits in a 32 bit integer. Write C code for that.
166. Given a search terms, find the minimum window containing all the words
167. Given a grid that contains rectangles, write a function that will return all the rectangles that overlap with each other.
168. Suppose you have an arbitrarily connected graph with n nodes. Come up with an algorithm to identify each set of connected nodes (i.e. identify all the islands in the graph). What's the complexity? Can you find a solution in O(n log n)?
169. Sort the entries in database in single pass?
170. How would you implement Google spelling correction algorithms?
171. Implement a method that matches an entire string with star wildcard pattern, e.g. returns true for ("*ogle", "Google"), but false for ("fragile*", "agile") - without using regular expression language support.
172. Print all shortest paths in a grid (Cartesian), given the starting and the ending point.
173. Write code to check the validity of a suduko square
174. Implement the Iterator pattern with a class that will be constructed using two iterable objects and that will iterate through the elements of both objects
175. Give the descending order of the following 4 terms, assume that n is infinite. n!(n factorial), n^n, 2^n, n^(google)
176. Convert decimal number 99 to base 7.
177. Design the back-end for facebook.   
178. Design an iterator for a collection of collections in java. The iterator should hide the nesting, allowing you to iterate all of the elements belonging to all of the collections as if you were working with a single collection.  
179. efficiently search for an input word in an unbounded dictionary.
180. Imagine dropping a Rubik's Cube into a bucket of paint. How many of the cubes will get paint on them?  
181. Given a function double f(double x), 0<=x<=1, f(x) is increasing. f(0)<0, f(1)>0. Find x s.t. f(x)\approx 0.
182. What is the fastest way to sort 1 million integers when integers are from the range [1,100]?  
183. How would you count the frequency of letters in a word/ file?
184. Writing the code to convert numeric amount of price into English words.
185. Given the pre-order and in-order traversing result of a binary tree, write a function to rebuild the tree.   
186. How to reverse a tree  
187. How would you write a sort routine to ensure that identical elements in the input are maximally spread in the output?
188. Design a utility similar to Google suggest. How can you do it?
189. write a function to calculate X^N
190. use mutex and semaphore to implement producer-consumer problem  
191. There is a parking lot of cars that is full except for a single spot. Write some code to take it from one arbitrary configuration to another moving only one car at a time into the empty spot. Analyse the time complexity, how would you improve it, etc.
192. design algorithm to reverse the content in the memory.
193. Find the maximal and minimal number in an array of integers
194. How many rotations does earth make on its axis while going around the sun for one year.
195. Given a list, return the first pair of duplicates in the list.
196. Given an array of integers where each element points to the index of the next element how would you detect if there is a cycle in this array?
197. Given unsorted sequence of billions of numbers that cannot all fit in memory at the same time, find the median of these values.