Tuesday, August 01, 2006

Cellphone - Algo

Consider a cellphone that has buttons/keys 0, 1, 2, 3... 9 on it and the same button can be used to type a set of alphabets.

For egs:
button which has number '1' on it also can be used to type = a, b, c
2 = d, e, f
...

Given a phone number (say - 2330493), write an algo to return all possible alphabetical combinations equivalent to the number, which are in a particular dictionary.

For egs:
I/p - 121
Possiblities can be - ada, adb, adc, aea, aeb, bdb....
If dictionary contians only - "ada", "adc" and "fuk".

O/p should be - ada and adc.

Write an algo to do this with least time complexity.

Algorithm - Strings

Given two sentences as strings, write an alogrithm (with the least time complexity) to find the number of occurances of each word of string1 in string2.

For Egs:

Inputs:
string1: Cat eats rat.
string2: Tiger belongs to cat family but it's strange that tiger eats cat.

Output:
cat - 2
eats - 1
rat - 0

Algorithmic Puzzle - Nuts and bolts

There are some nuts and some bolts in random order.

1) You cannot compare nuts with nuts and bolts with bolts.
2) It is guaranteed that a nut will fit in one or more bolts.

Now you have to sort both nuts and bolts separately in minimum complexity.

A simple Program

For any given input -'n', print the numbers from 1 to n and then from 'n-1' to 1 using only a single loop without any explicit if-else or ternary operator and not using any other memory other than the loop variable.

For Egs: If input is 4
OutPut : 1 2 3 4 3 2 1

Pirates Puzzle

I thought I will use this blog to post some good puzzles or algos that I come across. Here is my first attempt.

There are 5 pirates who jointly looted 100 gold coins. The pirate-A has 1 year of experience, the pirate-B has 2 years of experience... and the fifth pirate-E has 5 years of experience.

Below is the agreement b/w the pirates in sharing the gold coins among them.

1) Pirate E would propose an approach to share the 100 gold coins. If atleast 50% (means 50% or above) of the pirates agree on his approach, then his approach would be followed in spliting the 100 gold coins. If his proposal doesn't get the majority, then he would be killed and the next most experienced guy (ie. Pirate D) would propose his approach and all the rules apply to him as well.

2) Each of the pirate would try to get maximum number of gold coins possible.

Given this, what should the pirate-E propose so that he can save his skin by winning the majority as well as get the maximum number of gold coins?

PS: The question has a very logical answer. I will post the answer tomorrow.