1. Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife ?
  2. 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). Write a routine in C for the above.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. A version of the "There are three persons X Y Z, one of which always lies"..
  8. 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.
  9. If you are on a boat and you throw out a suitcase, Will the level of water increase.
  10. 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
  11. 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?
  12. One train leaves Los Angeles at 15 MPH heading for New York. Another train leaves from New York at 20mph heading for Los Angeles on the same track. If a bird, flying at 25mph, leaves from Los Angeles at the same time as the train and flies back and forth between the two trains until they collide, how far will the bird have traveled?
  13. Imagine that you have 26 constants, labelled A through Z. Each constant is assigned a value in the following way: A = 1; the rest of the values equal their position in the alphabet (B corresponds to the second position so it equals 2, C = 3, etc.) raised to the power of the preceeding constant value. So, B = 2 ^ (A's value), or B = 2^1 = 2. C = 3^2 = 9. D = 4^9, etc., etc. Find the exact numerical value to the following equation: 
    (X - A) * (X - B) * (X - C) * ... * (X - Y) * (X - Z)
  14. 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.