Reverse words in a sentence

Given an array of characters, reverse the words in the sentence.
For example, if the sentence is "Reverse these words", then the output should be "words these reverse".

Source : this interview q

Walk the bridge, in pairs as fast a possible

There are 4 women who want to cross a bridge. They all begin on the same side. There is one flashlight. A maximum of two people can cross at one time. It is night. 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 woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission.

Find jar with the contaminated pills

You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?

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

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/

Rope Escape

Rajeev is trapped atop a building 200m high. He has with him a rope 150m long.There is a hook at the top where he stands.

Looking down, he notices that midway between him and the ground, at a height of 100m, there is a ledge with another hook. In his pocket lies a Swiss knife.

How might he be able to come down using the rope, the two hooks and the Swiss knife?

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

[ALGO] Six Colored Balls

We have two red, two green and two yellow balls. For each color, one ball is heavy and the other is light. All heavy balls weigh the same. All light balls weigh the same. How many weighings on a beam balance are necessary to identify the three heavy balls?

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

Find if there is only one bit set in a number

In the bit representation of a number, find if there is exactly one bit that is set.

e.g. your approach should say true for the following numbers :
1,2,4,8,16
and false for the following numbers :
3,5,7,10

[PS] Catch the Fox

Consider five holes in a line. One of them is occupied by a fox. Each night, the fox moves to a neighboring hole, either to the left or to the right. Each morning, you get to inspect a hole of your choice. What strategy would ensure that the fox is eventually caught?

All purpose problem solving algorithm

LOL - Only if he had put in all that logic into solving the real problem ;-)

Find if number occurs exactly n/2 times in an array

You have an array of number/characters. If there is a number which occurs exactly n/2 times.
and all other elements in the set/array are distinct, can you find the the repeating number?

Expected time complexity : O(n)
Expected space complexity : O(1)

What if the other members are not distinct?
Can we solve the problem in O(log n) time complexity? (distinct and / or not distinct)

Source : http://inder-gnu.blogspot.com/2009/08/number-occuring-n2-times.html

Dividing array into groups

Divide a list of numbers into groups of consecutive numbers but their original order should be preserved.

Example:
<8,2,4,7,1,0,3,6>

should be divided into two groups like this:
<2,4,1,0,3> <8,7,6>

Source : http://discuss.techinterview.org/default.asp?interview.11.770712.8