[ALGO] Water jugs problem

Suppose that you are given 'n' red and 'n' blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. For every red jug, there is a blue jug that holds the same amount of water & vice versa.

How can you find the grouping of the jugs into pairs of red & blue jugs that hold the same amount of water, in the minimum number of comparisons.

Operations allowed

1. always compare between a red and a blue jar (no two reds, no two blues)
2. fill water in red / blue jug
3. pour from red jug to blue (& vice versa). This will help compare the capacity of the jugs.
   

Source : Introduction to Algorithms (by Cormen..., Problem 8-4)

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

Sort on second key when, first key in a set is sorted

Assume that we are given as input n pairs of items, where

1. the first item is a number
2. the second item is one of three colors (red, blue, or yellow).

Further, assume that the items are sorted by number. Give an O(n) algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.

For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).

Find if summation of numbers from two lists is given number

Problem: Given two lists A & B define an algo, which will identify two numbers 'a' and 'b', such that a + b = x, where 'x' is the input.

Wife?

Got this from a colleague of mine. Found it hilarious...

Open Source Developers @ Google Speaker Series

Open Source Developers @ Google Speaker Series: Ben Collins-Sussman and Brian Fitzpatrick

Open Source Speaker Series: Practical MythTV video on Google Videos :
http://video.google.com/videoplay?docid=-6641045817693171683