Saturday, July 16, 2011

Programming interview tip : Combinations from a list

This question will be discussed in python, since it is uber simple to write functioning yet short programs in :)

Say you have a list of n items e.g.
seq = [1,2,3]

Find products of all items with each other
This is the simplest question.
Solution:


This gives the following output:
1 * 1 = 1
1 * 2 = 2
1 * 3 = 3
2 * 1 = 2
2 * 2 = 4
2 * 3 = 6
3 * 1 = 3
3 * 2 = 6
3 * 3 = 9

Find unique products of the items with each other
This means that you need that you can only have 1*2 or 2*1 etc
Solution: Really simple to do. Each time in the inner loop start at i rather than 0 as shown:


This gives the following output:
1 * 1 = 1
1 * 2 = 2
1 * 3 = 3
2 * 2 = 4
2 * 3 = 6
3 * 3 = 9
Basically notice at each increment of i we do not allow j to go back.

Find unique products and do not multiply a list item with itself
This means that you cannot have 1*1 , 2*2 etc.
Solution: In the inner loop you need to avoid starting at i and rather start at i+1 (since this is the i*i case we need to avoid).

Also if this is all you do at i = n the inner loop will not run so its better to stop the outer loop at n-1


In both cases the output will be:
1 * 2 = 2
1 * 3 = 3
2 * 3 = 6
Enjoy!