Hacking a Google Interview
Classic Question #1:
Coin Puzzle You have 8 coins which are all the same weight, except for one which is slightly heavier than the others (you don't know which coin is heavier). You also have an old‐style balance, which allows you to weigh two piles of coins to see which one is heavier (or if they are of equal weight). What is the fewest number of weighings that you can make which will tell you which coin is the heavier one?
Good answer: Weigh 3 coins against 3 coins. If one of the groups is heavier, weigh one of its coins against another one of its coins; this allows you to identify the heavy coin. If the two groups balance, weigh the two leftover coins.
Not so good answer: Weigh 4 coins against 4 coins. Discard the lighter coins, and weigh 2 coins against 2 coins. Discard the lighter coins and weigh the remaining two coins.
http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_2.pdf
Classic Question #4: Reversing the words in a string
Question: Nearest Neighbor
Say you have an array containing information regarding n people. Each person is described using a string (their name) and a number (their position along a number line). Each person has three friends, which are the three people whose number is nearest their own. Describe an algorithm to identify each person's three friends.
Good answer: Sort the array in ascending order of the people's number. For each person, check the three people immediately before and after them. Their three friends will be among these six people. This algorithm takes O(n log n) time, since sorting the people takes that much time.
Classic Question #5: Cycle in a Linked List
Classic Question #6: Data structure for anagrams
Given an English word in the form of a string, how can you quickly find all valid anagrams for that string (all valid rearrangements of the letters that form valid English words)?
Then for the pre‐computing step, go through each word in the dictionary, sort the letters of the word in alphabetical order (so "hacking" would become "acghikn") and add the sorted letters as a key in the table and the original word as one of the values in a list of values for that key. For example, the entry for "opst" would be the list ["opts", "post", "stop", "pots", "tops", "spot"]. Then, whenever you get a string, you simply sort the letters of the string and look up the value in the hash table. The running time is O(n log n) for sorting the string (which is relatively small) and approximately O(1) for the lookup in the hash table.
Question: Factorial Zeros
Without using a calculator, how many zeros are at the end of "100!"? (that's 100*99*98*...*3*2*1)
There are a bunch more 2s than 5s, so the number of 5s is also the number of 10s in the factorization. There is one 5 for every factor of 5 in our factorial multiplication (1*2*...*5*...*10*...*15*...) and an extra 5 for 25, 50, 75, and 100. Therefore we have 20+4 = 24 zeros at the end of 100!
http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_3.pdf
Question: Deck Shuffling Given an array of distinct integers, give an algorithm to randomly reorder the integers so that each possible reordering is equally likely.
Good answer: Go through the elements in order, swapping each element with a random element in the array that does not appear earlier than the element. This takes O(n) time.
Binary Search Trees
To remove an element from a binary search tree, we first find the node containing that element. If the node has zero children, we simply remove it. If it has one child, we replace the node with its child. If it has two children, we identify the nextsmaller or next‐larger element in the tree (it doesn't matter which), using an algorithm which we do not describe here for the sake of brevity. We set the element stored in the node to this value. Then, we splice the node that contained the value from the tree. This will be relatively easy, since the node will have at most one child.
Question: Path Between Nodes in a Binary Tree Design an algorithm to find a path from one node in a binary tree to another.
Good Answer: There will always be exactly one path: from the starting node to the lowest common ancestor of the nodes to the second node. The goal is to identify the lowest common ancestor.
For each node, keep track of a set of nodes in the binary tree (using a hash table or a BST) as well as a current node. At each iteration, for each of the two current nodes, change the current node to be its parent and add it to the appropriate set. The first element that is added to one set when it is already present in the other set is the lowest common ancestor. This algorithm takes O(n) time, where n is the length of the path.
Bitwise Operations
Question: Is Power of 2
Question: Compute 2^x
Question: Beating the Stock Market
Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.
Good answer: Go through the array in order, keeping track of the lowest stock price and the best deal you've seen so far. Whenever the current stock price minus the current lowest stock price is better than the current best deal, update the best deal to this new value.
Classic Question #7: Ransom Note
http://massivealgorithms.blogspot.com/2014/07/algorithms-and-me-strings-ransom-note.html
We don't scan magazine string and ransom note separately but simultaneously. We scan character from ransom note, and check in hash table, if we find good. If not, we scan magazine string till we find the desired character.
If we reach end of magazine string, return false.
If we reach end of ransom note, return true.
Question: AxisAligned Rectangles
Describe an algorithm that takes an unsorted array of axis‐aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair.
Good Answer: Create a sorted array of the x coordinates of the left and right edges of the rectangles. Then, use a "scanline" to move from left to right through the rectangles. Keep a binary search tree containing the y coordinates of the top and bottom edges of the rectangles that overlap the scanline. For each element of the array, check whether it is a left or right edge. If it is a right edge, remove the corresponding top and bottom edges from the BST. If it is a left edge, search the BST for rectangles that overlap the current rectangle; if there is one, return the overlap.
Then, add the y coordinates of the top and bottom edges of the rectangle to the BST.
The search takes O(n log n) time, since it takes O(n log n) time to sort the rectangles and each of the 2n iterations takes O(log n) time.
ModelViewController:
Model‐view‐controller (MVC) is a design pattern commonly used in user interfaces. Its goal is to keep the "data" separate from the user interface.
A program that uses model‐view‐controller uses separate programming entities to store the data (the "model"), to display the data (the "view"), and to modify the data (the "controller"). In model‐view‐controller, the view usually makes heavy use of
listeners to listen to changes and events in the model or the controller.
Model‐view‐controller is a good buzzword to whip out when you're asked a design question relating to a user interface.
Classic Question #1:
Coin Puzzle You have 8 coins which are all the same weight, except for one which is slightly heavier than the others (you don't know which coin is heavier). You also have an old‐style balance, which allows you to weigh two piles of coins to see which one is heavier (or if they are of equal weight). What is the fewest number of weighings that you can make which will tell you which coin is the heavier one?
Good answer: Weigh 3 coins against 3 coins. If one of the groups is heavier, weigh one of its coins against another one of its coins; this allows you to identify the heavy coin. If the two groups balance, weigh the two leftover coins.
Not so good answer: Weigh 4 coins against 4 coins. Discard the lighter coins, and weigh 2 coins against 2 coins. Discard the lighter coins and weigh the remaining two coins.
http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_2.pdf
Classic Question #4: Reversing the words in a string
Question: Nearest Neighbor
Say you have an array containing information regarding n people. Each person is described using a string (their name) and a number (their position along a number line). Each person has three friends, which are the three people whose number is nearest their own. Describe an algorithm to identify each person's three friends.
Good answer: Sort the array in ascending order of the people's number. For each person, check the three people immediately before and after them. Their three friends will be among these six people. This algorithm takes O(n log n) time, since sorting the people takes that much time.
Classic Question #5: Cycle in a Linked List
Classic Question #6: Data structure for anagrams
Given an English word in the form of a string, how can you quickly find all valid anagrams for that string (all valid rearrangements of the letters that form valid English words)?
Then for the pre‐computing step, go through each word in the dictionary, sort the letters of the word in alphabetical order (so "hacking" would become "acghikn") and add the sorted letters as a key in the table and the original word as one of the values in a list of values for that key. For example, the entry for "opst" would be the list ["opts", "post", "stop", "pots", "tops", "spot"]. Then, whenever you get a string, you simply sort the letters of the string and look up the value in the hash table. The running time is O(n log n) for sorting the string (which is relatively small) and approximately O(1) for the lookup in the hash table.
Question: Factorial Zeros
Without using a calculator, how many zeros are at the end of "100!"? (that's 100*99*98*...*3*2*1)
There are a bunch more 2s than 5s, so the number of 5s is also the number of 10s in the factorization. There is one 5 for every factor of 5 in our factorial multiplication (1*2*...*5*...*10*...*15*...) and an extra 5 for 25, 50, 75, and 100. Therefore we have 20+4 = 24 zeros at the end of 100!
http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_3.pdf
Question: Deck Shuffling Given an array of distinct integers, give an algorithm to randomly reorder the integers so that each possible reordering is equally likely.
Good answer: Go through the elements in order, swapping each element with a random element in the array that does not appear earlier than the element. This takes O(n) time.
Binary Search Trees
To remove an element from a binary search tree, we first find the node containing that element. If the node has zero children, we simply remove it. If it has one child, we replace the node with its child. If it has two children, we identify the nextsmaller or next‐larger element in the tree (it doesn't matter which), using an algorithm which we do not describe here for the sake of brevity. We set the element stored in the node to this value. Then, we splice the node that contained the value from the tree. This will be relatively easy, since the node will have at most one child.
Question: Path Between Nodes in a Binary Tree Design an algorithm to find a path from one node in a binary tree to another.
Good Answer: There will always be exactly one path: from the starting node to the lowest common ancestor of the nodes to the second node. The goal is to identify the lowest common ancestor.
For each node, keep track of a set of nodes in the binary tree (using a hash table or a BST) as well as a current node. At each iteration, for each of the two current nodes, change the current node to be its parent and add it to the appropriate set. The first element that is added to one set when it is already present in the other set is the lowest common ancestor. This algorithm takes O(n) time, where n is the length of the path.
Bitwise Operations
Question: Is Power of 2
Question: Compute 2^x
Question: Beating the Stock Market
Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.
Good answer: Go through the array in order, keeping track of the lowest stock price and the best deal you've seen so far. Whenever the current stock price minus the current lowest stock price is better than the current best deal, update the best deal to this new value.
Classic Question #7: Ransom Note
http://massivealgorithms.blogspot.com/2014/07/algorithms-and-me-strings-ransom-note.html
We don't scan magazine string and ransom note separately but simultaneously. We scan character from ransom note, and check in hash table, if we find good. If not, we scan magazine string till we find the desired character.
If we reach end of magazine string, return false.
If we reach end of ransom note, return true.
Question: AxisAligned Rectangles
Describe an algorithm that takes an unsorted array of axis‐aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair.
Good Answer: Create a sorted array of the x coordinates of the left and right edges of the rectangles. Then, use a "scanline" to move from left to right through the rectangles. Keep a binary search tree containing the y coordinates of the top and bottom edges of the rectangles that overlap the scanline. For each element of the array, check whether it is a left or right edge. If it is a right edge, remove the corresponding top and bottom edges from the BST. If it is a left edge, search the BST for rectangles that overlap the current rectangle; if there is one, return the overlap.
Then, add the y coordinates of the top and bottom edges of the rectangle to the BST.
The search takes O(n log n) time, since it takes O(n log n) time to sort the rectangles and each of the 2n iterations takes O(log n) time.
ModelViewController:
Model‐view‐controller (MVC) is a design pattern commonly used in user interfaces. Its goal is to keep the "data" separate from the user interface.
A program that uses model‐view‐controller uses separate programming entities to store the data (the "model"), to display the data (the "view"), and to modify the data (the "controller"). In model‐view‐controller, the view usually makes heavy use of
listeners to listen to changes and events in the model or the controller.
Model‐view‐controller is a good buzzword to whip out when you're asked a design question relating to a user interface.
