These problems are a sample of the 174 problems in the Algorithms For Interviews book - solutions to these problems are given in the book. 1. A triomino is formed by joining three unit-sized squares in an L-shape. A mutilated chessboard is made up of 64 unit-sized squares arranged in an 8-by-8 square, minus the top left square. Design an algorithm which computes a placement of 21 triominos that covers the mutilated chessboard. 2. The mathematician G. H. Hardy was on his way to visit his collaborator S. Ramanujan who was in the hospital. Hardy remarked to Ramanujan that he traveled in a taxi cab with license plate 1729, which seemed a dull number. To this, Ramanujan replied that 1729 was a very interesting number - it was the smallest number expressible as the sum of cubes of two numbers in two different ways. Indeed, 10x10x10 + 9x9x9 = 12x12x12 + 1x1x1 = 1729. Given an arbitrary positive integer, how would you determine if it can be expressed as a sum of two cubes? 3. There are fifty coins in a line---these could be pennies, nickels, dimes, or quarters. Two players, $F$ and $S$, take turns at choosing one coin each---they can only choose from the two coins at the ends of the line. The game ends when all the coins have been picked up. The player whose coins have the higher total value wins. Each player must select a coin when it is histurn, so the game ends in fifty turns. If you want to ensure you do not lose, would you rather go first or second? Design an efficient algorithm for computing the maximum amount of money the first player can win. 4. You are given two sorted arrays. Design an efficient algorithm for computing the k-th smallest element in the union of the two arrays. (Keep in mind that the elements may be repeated.)5. You are a photographer for a soccer meet. You will be taking pictures of the teams . Each team has 20 players on its roster. Each picture will consist of rows of players, one row for each of the teams. You want to place the players so that if A stands behind B, he must be taller than B. Design an efficient algorithm for computing the minimum number of subsets of teams so that the teams in each subset can be organized to appear in one photograph, subject to the placement constraint, and each team appears in some subset. 6. How would you determine the minimum number of multiplications to evaluate X to the power 30?7. Clump Enterprises has a large number of casinos. Their CEO wants to create a website by which gamblers can play poker online.Design an online poker playing service for Clump Enterprises. 8. 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? 9. Consider an object S which is read from and written to by many threads. You need to ensure that no thread may access S for reading or writing while another thread is writing to it. (Two or more readers may access S at the same time.) One way to achieve this is by protecting S with a mutex that ensures that no thread can access S at the same time as another writer. This solution is suboptimal because it is possible that a reader R1 has locked S and another reader R2 wants to access S. There is no need to make R2 wait until R1 is done reading; instead, R2 should start reading right away.Design a synchronization mechanism to protect S with the added constraint that no reader is to be kept waiting if S is currently opened for reading. 10. A deck of 52 playing cards is shuffled. The deck is placed face-down on a table. You can place a bet on the color of the top card at even odds. After you have placed your bet, the card is revealed to you and discarded. Betting continues till the deck is exhausted. On any card, you can bet any amount from 0 to all the money you have and the odds are always even.You begin with one dollar. It is known that if you can bet arbitrary fractions of the money you have, the maximum amount of money that you guarantee you can win, regardless of the order in which the cards appear, is 2 However you are allowed to bet only in penny increments. Write a program to compute a tight lower bound on the amount you can win under this restriction. Some terms to help with search engine queries: Software Interview Questions; Programming Questions; Google Interview Questions; Microsoft Interview Questions; Amazon Interview Questions; Facebook Interview Questions |