Categories
interview

Maximum Water Capacity in a Histogram

bar graph

Calculate the maximum amount of water that can held within a bar graph without overflow.
The amount of water that can be held at any point is the difference of the minimum of the maximum of left bars and maximum of right bars and the height of that point.
If we don’t precompute the maximum values on left and right for every index, the time complexity becomes O(n^2). So we go with the precompute option.

Time Complexity O(n)
Space Complexity O(n)

Code

Output

Categories
interview

Find the maximum product of 3 integers in a list

The following code handles negatives as well.

Time Complexity O(n)
Space Complexity O(1)

Code

Output

Categories
interview

code jam Tidy Numbers

Question

Demo

Categories
interview

Find the maximum size of square of side ‘X’ in a matrix

We use dynamic programming to solve this.
Space complexity = O(2*n)
Time complexity = O(n^3).

Output

Categories
interview

Knapsack Bounded(1/0), Unbounded, Bounded/Fraction, Unbounded/Fraction Solutions

Bounded Knapsack (1/0) Solution in Java using Dynamic Programming
There are few items with weights and values, we need to find the items that contribute the maximum value that can be stored in knapsack of a particular capacity.
There are only 2 choices for each item, i.e. it can either be included or excluded from the bag.
Space complexity O(i*(capacity+1))
Time complexity
O(i*(capacity+1))

Output

Using Recursion

This is very inefficient.

Output

Time Complexity = O(2^n).

Bounded Knapsack with Fractions allowed
In the above problem if we are allowed to include fractions, then we sort the items based on their value to weight ratios in descending order and include them in the knapsack, until it is full.

Output

Unbounded Knapsack solution
In this approach we use Dynamic programming to store the capacities incrementally to get the required maximum value at capacity.
Time complexity = O(i*(c+1))
Space complexity = O(c+1)

Output

Unbounded Knapsack with Fractions allowed
This is a straightforward implementation, as we need to find the maximum ratio among the given items (value/weight) and then multiply it with the capacity of the bag.
Time complexity = O(i)
Space complexity = O(1)

Output