Showing posts from April, 2012

Exchange gold coins

In a monetary system each coin has an integer number written on it. A coin 'n' can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down. You can also sell coins for dollars and their exchange rate is 1:1. You have one gold coin. What is the maximum amount of dollars you can get for it? eg: for a coin with value 120 you can get 144 dollars.Suggest an algorithm to solve the problem.

[Adobe]Search for an element in unsorted array

The successive elements of an unsorted array differ by either + 1 or -1. How will u search for an integer k in this array ?
eg: 4,5,4,4,5,6,7,8,7
for each element 'n' the next element is always n+1 or n-1.

Maximum sum 2-d subarray

Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size or greater located within the whole array. As an example, the maximal sub-rectangle of the array:
is in the lower-left-hand corner: and has the sum of 15.