For some reasons that I'd rather keep private, I got interested in the kind of questions google, microsoft, amazon and other tech companies are asking to candidate during the recruitment process. Most of these questions are oriented towards algorithmics or mathematics. Some other are logic questions or puzzles the candidate is expected to be able to solve in a dozen of minutes in front of the interviewer.
If found various sites online providing lists of typical interview questions. Other sites are discussing topics like "the ten toughest questions asked by google" or by microsoft, etc.
Then I wondered how many of them I could answer on my own without help. The truth is that while I can answer most of these questions by myself, I still needed help for almost as much as half of them.
Anyway, I have collected my answers to a hundred of these questions below.
For the questions for which I needed some help to build an answer, I clearly indicate the source where I found it.
1. You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
2. You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000
samples from this never ending set of data and then write code for it.
3. Given a large network of computers, each keeping log files of visited urls, find the top ten of the most visited urls.
(i.e. have many large <string (url) -> int (visits)> maps, calculate implicitly <string (url) -> int (sum of visits among all distributed maps)>, and get the top ten in the combined map)
The result list must be exact, and the maps are too large to transmit over the network (especially sending all of them to a central server or using MapReduce directly, is not allowed)
4. Merge two sorted linked lists
When you merge two "linked" lists, there tend to be problems with "conflicts" between the lists (because they have a specific order to them and you are messing with the order).
5. Given a set of intervals (time in seconds) find the set of intervals that overlap
6. If we had a list of n nodes, what are the maximum number of edges there can be for a directed acyclic graph?
You have to draw lines between nodes, but never have a clear path of returning to the original node regardless of where you're starting.
7. What's the difference between finally, final and finalize in Java?
8. Remove duplicate lines from a large text
9. Given a string, find the minimum window containing a given set of characters
10. Write a program to compute if one string is a rotation of another
For example, "strings" usually refer to lines of letters, words or something that is meant to be printed and seen. But they can also refer to matrices (a two-dimensional object) and other kinds of objects.
You have to check if you can rotate them and check them against existing strings
11. What is the sticky bit and why is it used?
Describe quicksort algorithm and explain in time and memory complexity
[Quick Sort and Partition algorithms]
13. Describe a partition-based selection algorithm
Given a list of integers that fall within a known short but unknown range of values, how to find the median value?
15. Given a set of intervals, find the interval which has the maximum number of intersections.
16.a. Let's defined an array of 100 integers from 1 to 100, shuffled. One integer is taken out, find that integer.
16.b. Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.
16.c. You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n).
17. You are given a number of identical balls and a building with N floors. You know that there is an integer X < N such that the ball will break if it is dropped
from any floor X or higher but will remain intact if dropped from a floor below X.
Given K balls and N how would you compute the minimum number of ball drops that are required to determine X in the worst-case?
18. Why are manhole covers round?
19.a. Given the time, devise an algorithm to calculate the angle between the hour and minute hands of an analog clock.
19.b. How many times a day does a clock's hands overlap?
20. What is a priority queue ? And what are the cost of the usual operations ?
21. Tree traversal
Describe and discuss common tree traversal algorithms
[Tree traversal algos]
22. Graph traversal
Describe and discuss common graph traversal algorithms
[Graph Search algo]
23. How to find Inorder Successor in Binary Search Tree
24. Write a method to pretty print a binary tree
25.a. What is dynamic programming ?
25.b. Write an algorithm to generate a fibonacci number sequence and discuss its time and space complexity.
25.c. Given an array, find the longest (non necessarily continuous) increasing subsequence.
Not to be confused with problem 66.c which adds a "continuous" constraint.
26. Describe and discuss the MergeSort algorithm
27. Given a circularly sorted array, describe the fastest way to locate the largest element.
28.a Reverse a linked list. Write code in C
28.b. How can you print singly linked list in reverse order? (it's a huge list and you cant use recursion)
28.c Write a function to reverse a singly linked list, given number of links to reverse.
29. Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.
30.a. The probability of a car passing a certain intersection in a 20 minute windows is 0.9. What is the probability of a car passing the intersection in a 5 minute window? (Assuming a constant probability throughout)
30.b. You are given biased coin. Find unbiased decision out of it?
31. What is the difference between a mutex and a semaphore?
Which one would you use to protect access to an increment operation?
32. Write a C program which measures the the speed of a context switch on a UNIX/Linux system.
33. Design a class library for writing card games.
34. Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.
35. Write some code to find all permutations of the letters in a particular string.
[Permutation generation algo]
36.a. What is a hash table ahd how is it typically implemented ?
[Hash Table principle]
36.b When would you use a binary tree vs. a hash map (hash table)?
37.a. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a
balance and only two weightings?
37.b. You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?
37.c. You have 12 balls. All of them are identical except one, which is either heavier or lighter than the rest - it is either hollow while the rest are solid,
or solid while the rest are hollow. You have a simple two-armed scale, and are permitted three weighings. Can you identify the odd ball, and determine whether it is hollow or solid.
38. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output will be multiplication of A to A[N-1] and Output will be multiplication of A and from A to A[N-1]. Solve it without division operator and in O(n).
39. Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.
40. How do you put a Binary Search Tree in an array in a efficient manner.
Hint : If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise) Its not the most efficient way.
41. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.
42. Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 -> iN c1 c2 c3 -> cN.
Write an in-place algorithm to rearrange the elements of the array as A = i1 c1 i2 c2 -> in cn
43. Use basic operations to create a square root function.
44. Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
45. Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
46.a. What is bactracking as an algorithmic technique ?
Give an example algorithm.
46.b Given an integer, return all sequences of numbers that sum to it. (Example: 3 -> (1, 2), (2, 1), (1, 1, 1))
46.c. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
47 Given an array of distinct integers, and a target integer t, compute all of the (continuous!) subsets of the array that sum to t, where order matters.
48. Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.
49. Write a function that flips the bits inside a byte (either in C++ or Java).
50. What's 2 to the power of 64?
51. Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?
52. Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n
53. Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element.
[Binary Search algo]
54. What sort would you use if you had a large data set on disk and a small amount of ram to work with?
55. What sort would you use if you required tight max time bounds and wanted highly regular performance.
56. Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes.
57. Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree
58. Given an arbitrarily connected graph, explain how to ascertain the reachability of a given node.
59. You are given 1001 numbers in an array. There are 1000 unique numbers and 1 duplicate. How do you locate the duplicate as quickly as possible?
60. Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.
61. If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers?
62.a Implement multiplication (without using the multiply operator, obviously).
62.b Implement division (without using the divide operator, obviously).
63. You are given with three sorted arrays ( in ascending order), you are required to find a triplet (one element from each array) such that distance is minimum.
Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k])).
Please give a solution in O(n) time complexity.
64. Given a binary search tree and an integer k, describe the most efficient way to locate two nodes of the tree that sum to k.
65. What is the KBL algorithm ?
66.a. You're given an array containing both positive and negative integers and required to find the subarray with the largest sum (O(N) a la KBL).
66.b. Given an array, find the longest continuous(!) increasing subsequence.
Not to be confused with problem 25.c which releases the "continuous" constraint.
67. Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.
68.a. Fastest algorithm or way to check a X's and 0's game (i.e. TIC TAC TOE) board.
68.b. In a X's and 0's game (i.e. TIC TAC TOE) if you write a program for this give a fast way to generate the moves by the computer.
I mean this should be the fastest way possible.
69. There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner.. what is the probability that they don't collide.
70. There are 4 men who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each man walks at a different speed. A pair must walk together at the rate of the slower mans pace.
Man 1: 1 minute to cross
Man 2: 2 minutes to cross
Man 3: 5 minutes to cross
Man 4: 10 minutes to cross
71. Give a one-line C expression to test whether a number is a power of 2. (No loops allowed - it's a simple test.)
72. Give a very good method to count the number of ones in a 32 bit number.
73. Given two strings S1 and S2. Delete from S2 all those characters which occur in S1 also and finally create a clean S2 with the relevant characters deleted.
74. Determine the 10 most frequent words given a terabyte of strings.
75.a Given only putchar (no sprintf, itoa, etc.) write a routine putlong that prints out an unsigned long in decimal.
75.b. Write a function to convert an int to a string.
76. How many points are there on the globe where by walking one mile south, one mile east and one mile north you reach the place where you started.
77. You have a cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.
78.a. Reverse each bit in a number.
78.b. How would you reverse the bits of a number with log N arithmetic operations, where N is the number of bits in the integer (eg 32,64..)
79. A character set has 1 and 2 byte characters. One byte characters have 0 as the first bit. You just keep accumulating the characters in a buffer.
Suppose at some point the user types a backspace, how can you remove the character efficiently.
(Note: You can't store the last character typed because the user can type in arbitrarily many backspaces)
80. What's the simplest way to check if the sum of two unsigned integers has resulted in an overflow.
81. Devise an algorithm for detecting whether a given string is a palindrome (spelled the same way forwards and backwards).
For example, "A man, a plan, a canal, Panama."
82. Write a function to find the depth of a binary tree.
83. Besides communication cost, what is the other source of inefficiency in RPC?
84.a. An array of integers of size n. Generate a random permutation of the array, given a function rand_n() that returns an integer between 1 and n, both inclusive, with equal probability.
84.b. Write an efficient algorithm and C code to shuffle a pack of cards
85a. Assuming that locks are the only reason due to which deadlocks can occur in a system. What would be a foolproof method of avoiding deadlocks in the system ?
85.b. What is the difference between a live-lock and a deadlock ?
86. Give a good data structure for having n queues ( n not fixed) in a finite memory segment. You can have some data-structure separate for each queue. Try to use at least 90% of the memory space.
87. Say you are implementing exponentiation for a certain processor. How would you minimize the number of multiplications required for this operation?
88. You have given an array. Find the maximum and minimum numbers in less number of comparisons.
89. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed.
How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
90. Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?
91. What is the birthday paradox ?
92.a What method would you use to look up a word in a dictionary?
92.b. How would you store 1 million phone numbers?
93. Describe an API for a cache, with all of the associated function signatures. Provide pseudocode for the simple one.
94.a. Implement a special type of integer iterator. It will be a wrapper over a regular integer iterator, except that this iterator will only iterate over negative numbers.
Show how you'd write the next() and hasNext() functions to work with the next negative integer instead of just the next integer.
94.b. How would you implement an Iterator for Binary tree inOrder traversal
95. You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?
96. Describe a data structure that accomplishes the functions INSERT and FIND-MEDIAN in the best possible asymptotic time.
97. Write a function (with helper functions if needed) called toExcel that takes an excel column value (A,B,C,D,...,AA,AB,AC,...,AAA,..) and returns a corresponding integer value (A=1,B=2,...,AA=26,...)?
98. What would you do if senior management demanded delivery of software in an impossible deadline?
99. How Old Are My Children? Knowing:
A) The product of their ages is 72 and the sum of their ages is the same as your birth date.
B) ... I still don't know .
A) My eldest kid just started taking piano lessons.
B) Now I know :-)
Don't hesitate to leave a comment or contact me should you see any error in here, or any improvement, better solution, etc. and I'll update the post accordingly.