Cutting a Rod

Problem : 

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.

Solution :

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}

Excel Sheet Row Numbers

Given the sequence 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 + 262 + ... + 26k-1 + a0 + a1*26 + a2*262 + ... + ak-1*26k-1
  = a0 + (a1 + 1) 26 + (a2 + 1) 262 + ... + (ak-1 + 1) 26k-1 

where 
ai ranges from 0-25 (each representing a letter in s1), 
k is the number of letters in s1.

To solve the above equation, we have to find the values of a₀, a₁, …, a_k-1. Once we solve this equation, we are able to determine the string of letters of s₁ directly.

a₀ can be solved by taking n % 26. Why? Because a₀ ranges from 0-25, which is not divisible by 26, while the rest are factor of 26. After we obtained the value of a₀, we divide n by 26. This will yield the number

n' = (a1 + 1) + (a2 + 1) 26 + ... + (ak-1 + 1) 26k-2

You might think that a₁ + 1 = n’ % 26. This is wrong. What happens when a₁ = 25? For sure, a₁ +1 is divisible by 26, and thus the mentioned equation is invalid. We can easily resolve this by doing a₁ = (n’ – 1) % 26.

The rest is easy, we continue further with n” = (n’ – 1) / 26 and a₂ = (n” – 1) % 26, up until a_k-1.

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

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²)

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