Tower of Hanoi with a restriction of no direct transfers

We need to solve the Tower of Hanoi problem, with this additional restriction : direct moves between the origin and destination towers is disallowed. All other restrictions still apply  as-is.

For example, if a single disk is to be moved from Tower A to Tower B (using Tower C), then moving the disk directly from A to B is not allowed. The disk must be first transferred to Tower C and then to Tower B.

The purpose is to find the shortest sequence / number of moves we can do this in : 

• T(0) = 0 (basis case, nothing to move)
• T(1) = 2 (from above)
• T(n-discs) = ???

Source : Concrete Mathematics (2nd Edition) Ex. 1.2

Unimodal Search

An array A[1...n] is unimodal if it consists of an increasing sequence followed by a decreasing sequence. More precisely, if there is an index m in {1, 2, ... n} such that
A[i] < A[i+1] for 1 <= i < m and
A[i] > A[i+1] for m <= i < n

In particular, A[m] is the maximum element, and it is the unique "locally maximum" element surrounded by smaller elements.

Give an algorithm to compute the maximum element of a unimodal input array A[1...n] in O(lg n) time.

Source: Problem 1-3.from MIT OpenCourseWare Course - 6.046J / 18.410J Introduction to Algorithms (SMA 5503)

[ALGO] Find the string in 2 dimensional matrix

Given a 2-dim matrix of characters 'm' and a string 's' - find if the string 's' is present in the matrix. Only characters in the neighboring cells of a cell can contribute to the string.

For example, for the case below B,D,F,G are neighbors of X. From 'X' possible strings (or substrings) are XB, XD, XF, XH.
|-----|-----|-----|
|  A  |  B  |  C  |
|-----|-----|-----|
|  H  |  X  |  D  |
|-----|-----|-----|
|  G  |  F  |  E  |
|-----|-----|-----|

Finally, an example. Given the matrix

(0,0)
    |-----|-----|-----|-----|
    |  y  |  a  |  a  |  o  |
    |-----|-----|-----|-----|
    |  a  |  o  |  a  |  o  |
    |-----|-----|-----|-----|
    |  y  |  a  |  o  |  o  |
    |-----|-----|-----|-----|
    |  h  |  a  |  a  |  o  |
    |-----|-----|-----|-----|
    |  y  |  a  |  h  |  o  |
    |-----|-----|-----|-----|
                            (3,3)

and asked to check for the string 'yahoo' the solution is true :
y - (3,0)
a - (3,1)
h - (3,2)
o - (3,3)
o - (2,3)

[ALGO] Random number generator, with equal probability

RANDOM(a.b) is a random number generator that generates integers between a and b (inclusive), all equally likely.

Assuming we have an implementation of RANDOM(0.1), how can we implement RANDOM(a.b) - i.e. given we have a function that returns 0 OR 1 both with a probability of 1/2, how can we implement a function that returns integers from a to b (b > a), all with a probability of 1/n, where n = (b-a+1)

Source : Cormen - Problem 5.1-2 (randomized algorithms)


Similar problem :
At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin?

Its on Gurmeet's site here  http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-tossing-with-one-third-probability/

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 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/

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

Q1. How do you find out if a number is a power of 2?
Q2. And how do you know if it is an odd number?

Source : Algorithms from 100 Interview Questions for Software Developers

All purpose problem solving algorithm

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

[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.