Assume a company buys long steel rods and cuts them into shorter rods for sale to its customers. If each cut is free and rods of different lengths can be sold for different amounts, we wish to determine how to best cut the original rods to maximize the revenue.

# Learning programming....

## Thursday, 27 November 2014

## Saturday, 22 November 2014

### Count the number of possible triangles

Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as three sides of triangles. For a triangle to be possible from 3 values, the sum of any two values (or sides) must be greater than the third value (or third side).

Ex : if the input array is {4, 6, 3, 7}, the output should be 3. There are three triangles possible {3, 4, 6}, {4, 6, 7} and {3, 6, 7}. Note that {3, 4, 7} is not a possible triangle.

As another example, consider the array {10, 21, 22, 100, 101, 200, 300}. There can be 6 possible triangles: {10, 21, 22}, {21, 100, 101}, {22, 100, 101}, {10, 100, 101}, {100, 101, 200} and {101, 200, 300}

Ex : if the input array is {4, 6, 3, 7}, the output should be 3. There are three triangles possible {3, 4, 6}, {4, 6, 7} and {3, 6, 7}. Note that {3, 4, 7} is not a possible triangle.

As another example, consider the array {10, 21, 22, 100, 101, 200, 300}. There can be 6 possible triangles: {10, 21, 22}, {21, 100, 101}, {22, 100, 101}, {10, 100, 101}, {100, 101, 200} and {101, 200, 300}

### Excel Sheet Row Numbers

Given the sequence

Refer: http://leetcode.com/2010/10/amazon-bar-raiser-interview-question.html

**S1**= {a,b,c,d,…,x,y,z,aa,ab,ac…. } and given that this sequence corresponds (term for term) to the sequence**S2**= {0,1,2,3,….}. Write code to convert an element of**S2**to the corresponding element of**S1**.Equation(1)n= 26 + 26^{2}+ ... + 26^{k-1}+a_{0}+a_{1}*26 +a_{2}*26^{2}+ ... +a_{k-1}*26^{k-1}=a_{0}+ (a_{1}+ 1) 26 + (a_{2}+ 1) 26^{2}+ ... + (a_{k-1}+ 1) 26^{k-1}wherea_{i}ranges from 0-25 (each representing a letter ins_{1}),kis the number of letters ins_{1}.

To solve the above equation, we have to find the values of

*a*_{0}*, a*_{1}*, …, a*_{k-1}. Once we solve this equation, we are able to determine the string of letters of**directly.***s*_{1}*a*

_{0}can be solved by taking

*n*% 26. Why? Because

*a*

_{0}ranges from 0-25, which is not divisible by 26, while the rest are factor of 26. After we obtained the value of

*a*

_{0}, we divide

*n*by 26. This will yield the number

*n'* = (*a*_{1} + 1) + (*a*_{2} + 1) 26 + ... + (*a*_{k-1} + 1) 26^{k-2}

You might think that

*a*_{1}+ 1 =*n’*% 26. This is wrong. What happens when*a*_{1}= 25? For sure,*a*_{1}+1 is divisible by 26, and thus the mentioned equation is invalid. We can easily resolve this by doing*a*_{1}= (*n’*– 1) % 26.
The rest is easy, we continue further with

*n”*= (*n’*– 1) / 26 and*a*_{2}= (*n”*– 1) % 26, up until*a*_{k-1}.### Counting Boolean Parenthesizations

**Counting Boolean Parenthesizations:**You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example, there are 2 ways to parenthesize 'true and false xor true' such that it evaluates to true.

*The cost is :*checking subwords of size 1 + checking subwords of size 2 + ... + checking subwords of size N

= N + N-1 + 2*(N-2) + 2*(N-2) + .. + (N-1)*(1)

= O(N^3)

Auxiliary Space: O(n

^{2})

## Friday, 21 November 2014

### Balanced Partition

**Balanced Partition:**You have a set of n integers each in the range 0 ... K. Partition these integers into two subsets such that you minimize |S1 - S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.

**Equal Partition :**

Given a set of integers we need to find out all subsets of it which have sum equal to a number. Generic case would be given a set of integers and an integers S, find all subsets which have sum equal to S.

Note : We can achieve this solution by little modification of above problem

### Knapsack problem

Integer Knapsack Problem (Duplicate Items Forbidden): This is the same problem as the example above, except here it is forbidden to use more than one instance of each type of item.

### Building Bridges

Building Bridges : Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a(1) ... a(n) and n cities on the northern bank with x-coordinates b(1) ... b(n). You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city i on the northern bank to city i on the southern bank. (Note: this problem was incorrectly stated on the paper copies of the handout given in recitation.)

Subscribe to:
Posts (Atom)