Algorithms from "100 Interview Questions for Software Developers" : Part 3

Find repeating element in array

I felt this  question deserves a post of its own. So here it is :

 Q5. In an array from 1 to n, one number is present twice. How to do you determine which one?

There are multiple answers - all correct. We would, obviously, aim for the optimized one - benchmark parameters being time & space complexity

Source : Algorithms from 100 Interview Questions for Software Developers

Algorithms from "100 Interview Questions for Software Developers" : Part 2

Q3. How do you find the middle item in a link list?
Q4. How would you write a function to reverse a string? Can you do it without a temporary string?

Source : Algorithms from 100 Interview Questions for Software Developers

Find the bulb for the switch

There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can't change them. Identify each switch with its bulb.

Source : My brother & http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

Find direction of rotation

Imagine a disk spinning like a record player turn table. Half of the disk is black and the other is white. Assume you have an unlimited number of color sensors. How many sensors would you have to place around the disk to determine the direction the disk is spinning? Where would they be placed?

Source : http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

Pay for 7 days using 1 7-segment gold bar and 2 cuts

You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?

Source : http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

[Probability] Divide 100 marbles into two piles

How would you divide 50 black and 50 white marbles into two piles so that the probability of picking a white marble as follows is maximized: we first pick one of the piles uniformly at random, then we pick a marble in that pile uniformly at random?

Source : http://gurmeetsingh.wordpress.com/puzzles/

Find the poisoned wine barrel

An enemy spy has poisoned one out of 1000 barrels of wine in a king’s cellar. Even a sip of the poisoned wine has potency to kill. However, the effects of the poison show only in 30 days. The king asks the royal jailor to identify the poisoned barrel within 30 days. What is the least number of prisoners the jailor must employ to identify the poisoned barrel

Source : http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-poisoned-wine-barrels/