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

Box Stacking

Box Stacking :  You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.

Longest Increasing Subsequence

Longest Increasing Subsequence :  Given a sequence of n real numbers A(1) ... A(n), determine a subsequence (not necessarily contiguous) of maximum length in which the values in the subsequence form a strictly increasing sequence.

Maximum Value Contiguous Subsequence :  Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized.

Kadane's algorithm

Kadane's algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position. Thus, the problem can be solved with the following code, expressed here in Python:

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

How to find list of possible words from a letter matrix

F X I E
A M L O
E W B X
A S T U

The goal of the game is to find as many words as you can that can be formed by chaining letters together. You can start with any letter, and all the letters that surround it are fair game, and then once you move on to the next letter, all the letters that surround that letter are fair game, except for any previously used letters. So in the grid above, for example, I could come up with the words LOB, TUX, SEA, FAME, etc. Words must be at least 3 characters, and no more than NxN characters, which would be 16 in this game but can vary in some implementations. While this game is fun and addictive, I am apparently not very good at it and I wanted to cheat a little bit by making a program that would give me the best possible words (the longer the word the more points you get).

Refer : http://stackoverflow.com/questions/746082/how-to-find-list-of-possible-words-from-a-letter-matrix-boggle-solver/13338904#13338904

Max sum from Coins in a line

Optimal Strategy for a Game : Consider a row of n coins of values v(1) ... v(n), where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.

Refer here for explanative answer : http://leetcode.com/2011/02/coins-in-line.html

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

1. Would you rather go first or second? Does it matter?
2. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

Consider the two coins the opponent will possibly take, A_i+1 and A_j. If the opponent takes A_i+1, the remaining coins are { A_i+2 … A_j }, which our maximum is denoted by P(i+2, j). On the other hand, if the opponent takes A_j, our maximum is P(i+1, j-1). Since the opponent is as smart as you, he would have chosen the choice that yields the minimum amount to you.

Therefore, the maximum amount you can get when you choose A_i is:

P1 = Ai + min { P(i+2, j), P(i+1, j-1) }

Similarly, the maximum amount you can get when you choose A_j is:

P2 = Aj + min { P(i+1, j-1), P(i, j-2) }

Therefore,

P(i, j) = max { P1, P2 }
        = max { Ai + min { P(i+2, j),   P(i+1, j-1) },
                Aj + min { P(i+1, j-1), P(i,   j-2) } }

Gray code Sequence generation

Constructing an n-bit Gray code[edit]

The first few steps of the reflect-and-prefix method.

4-bit Gray code permutation

The binary-reflected Gray code list for n bits can be generated recursively from the list for n−1 bits by reflecting the list (i.e. listing the entries in reverse order), concatenating the original list with the reversed list, prefixing the entries in the original list with a binary 0, and then prefixing the entries in the reflected list with a binary 1.^[6] For example, generating the n = 3 list from the n = 2 list:

2-bit list:	00, 01, 11, 10
Reflected:		10, 11, 01, 00
Prefix old entries with 0:	000, 001, 011, 010,
Prefix new entries with 1:		110, 111, 101, 100
Concatenated:	000, 001, 011, 010,	110, 111, 101, 100

The one-bit Gray code is G₁ = (0, 1). This can be thought of as built recursively as above from a zero-bit Gray code G₀ = { Λ } consisting of a single entry of zero length. This iterative process of generating G_n+1from G_n makes the following properties of the standard reflecting code clear:

• G_n is a permutation of the numbers 0, ..., 2ⁿ−1. (Each number appears exactly once in the list.)
• G_n is embedded as the first half of G_n+1.
• Therefore the coding is stable, in the sense that once a binary number appears in G_n it appears in the same position in all longer lists; so it makes sense to talk about the reflective Gray code value of a number: G(m) = the m-th reflecting Gray code, counting from 0.
• Each entry in G_n differs by only one bit from the previous entry. (The Hamming distance is 1.)
• The last entry in G_n differs by only one bit from the first entry. (The code is cyclic.)

Circular loop among petrol pumps

Best days to sell and buy stock, if array of stock prices given

Edit distance

Edit Distance Calculation : 

Edit Distance Algorithm : 

Rotate matrix by 90 degrees

Minimum number of jumps to reach last element

Nested loop weight sum

Find The Presence Of A Given Word In A Given Grid