Creating a balanced binary search tree from sorted array

Given a sorted array, how do we create binary search which height balanced.

For example the array [1,2,3,4,5] must be transformed to the following binary tree

3
/
2    4
/
1        5

We can use the divide and conquer approach to solve this problem. To create a balanced tree, the number of nodes on the left sub-tree should be almost equal to that of right sub-tree.

How do we do it?

The create method is provided the lower and higher index parameters in addition to the actual array. We create the root node with the middle element and create the left and right sub trees with the left and right portions of the array.

Here is the C++ code.

Checking if a binary tree is balanced

Given a binary tree, how do we check if it is balanced or not?
We say that a binary tree is balanced if height difference of left  and the right sub-trees is at most 1 at  any node.

Consider the following examples

1          1               1             1
/                       /
2   3          2           2                 2
/
3
Balanced    Balanced     Balanced       Unbalanced

Solution:

We can simply implement a recursive solution based on the above definition of balance. At each node we check the height of the left sub tree and the right sub-tree and call the same function for it’s left child and right child recursively. But this is inefficient because we calculate the height repeatedly. This solution is O(n2).

Because we are calculating the height at each node, we can reuse the height of sub-tree to check the balance at the root node. Here is how we can do it.

We write a method called balance. This method returns the actual height of the tree if it is balanced. Otherwise it returns -1. So at any point if the balance of left or right sub-tree is -1 or their difference is greater than 1, we can simply return false.

Here is the C++ implementation of this algorithm. It runs in O(n) time.

Finding the kth element in Binary search tree

Given a binary search tree, how do we find a kth smallest or kth largest element?
For example, given the following binary search tree.
Third largest element is 6
Second smallest element is 2
Fifth largest element is 5 and so on…

Solution:

We can solve this problem by modifying the the in-order traversal method of a binary tree. In addition to the root node, we can pass two more parameters one is K, and current count of the nodes visited as a reference parameter. When the current count reaches K we found the kth order element.

To find out the kth smallest element, we need to visit left sub-tree, then root and then the right sub-tree as usual. To find the kth largest element we need to do reverse in-order traversal i.e First visit right sub-tree, then root and then the left sub-tree.

Here is the C++ implementation. This includes the recursive and iteration versions of finding kth smallest and kth largest elements. The iterative version is simply the manual implementation of a recursion using a stack.

Longest sub array with zero sum

Given an array of integers (positive and negative), how do we find a longest sub-array with zero sum?

For example, consider the example [5, 0, -1, 3, -2, 4], the longest sub array with zero sum contains 4 elements.

The straight forward approach is to check the sum of all possible arrays and find out the maximum length sub array. This will run in O(n3) time.

Can we do better than this?

Yes, by using dynamic programming we can do that. Take an array which is of same size. We can find this in n iterations.

In the first iteration, we find the length of longest sub sequence with zero sum beginning with the first element.

In the second iteration, we find the length of longest sub sequence with zero sum beginning with second element and so on.

Let us calculate this array for the above example

Iteration 1:
Cumulative Sum = 5 5 4 7 5 9
Max Length     = 0 0 0 0 0 0

Iteration 2:
Cumulative Sum = _ 0 -1 2 0 4
Max Length     = 0 1  0 0 4 0

Iteration 3:
Cumulative Sum = _ _ -1 2 0 4
Max Length     = 0 1  0 0 4 0

and so on.

At the end of all this, maximum of this array contains the result.

Here is the C++ code.

Programming puzzle – calculating product array

Given an array of numbers A[1:N], we have to generate a product array P[1:N] such that P[i] contains the product A[1]*…A[i-1]*A[i+1]…A[N]

That means each entry in the product array should contain product off all the elements except the one at that particular index.

For example let us consider the array [4, 2, 10, 5], the output should be {100, 200, 40, 80}.

The restriction here is that we have to device an algorithm without using division operation. Had it been allowed, we would have simply calculated the product of all the elements and fill the product array by dividing this with the current element.

Here is the solution approach.

We do this using two iterations one forward and the other backward.

• In the forward iteration, we fill the product array by filling each entry with product of all the elements before it.
• In the backward iteration, we multiply each element with product of all the elements to the right of it.

Here is the C++ implementation for this. The time complexity is O(n).

Infinite house of pancakes – Google Codejam 2015 Qualification round problem 2

Here is the link to the original problem. Let us try to simplify the problem statement a little bit.

There is a dinner house of infinite number of guests but finite number of pancakes. Each of them hold a plate which is either empty or has some pancakes in them. Every minute, one of the following actions can happen.
1. Each guest eats one pancake per minute.
2. The server will declare it as a special minute during which all guests stop eating, and the server will choose a guest with non-zero pancakes and transfer some cakes from that guest to the another guest.
The problem is to optimize the number of special minutes so that the total time to finish all the cakes is minimum.

We are given the number of pancakes on each plate initially.

Let us walk through a small example.
[1, 2, 4] – If we don’t declare any special minutes, all the cakes will be finished in 4 minutes which is the maximum cakes.
What is we declare a special minute and take out 2 cakes from the 3rd guest and keep it in an empty plate?

[1,2,2,2] – Now we can finish all the cakes in 2 minutes + 1 special minute. So we can finish all the cakes in 3 minutes itself.
Note that we can not reduce the time any further because if we do so, we have to declare 3 special minutes (for moving one cake from each of the plate with 2 cakes) which outweigh the actual eating time which is 2 minutes.

Without the loss of generality we assume that we can minimize the number of pancakes to be eaten by moving them from the maximum plate to a zero plate.

A simple brute force algorithm would suffice because the restriction on the input is small (1000).
• Let us calculate the frequency of pancakes in each plate.
• For each of the sizes between 1 and 1000
• Move the excess cakes (p[i] – size) in each plate to an empty plate and sum up the number of moves required.
• Add the size to the number of moves, you will get the time required to finish.
• Update the minimum time.
Let us trace the algorithm for the above example.
[1,2,4]
• Divide them into size 1 chunks – [1,1,1,1,1,1,1] – 4 moves+ 1 = 5 minutes.
• Divide them into size 2 chunks – [1,2,2] – 1 move + 2 = 3 minutes
• Divide them into size 3 chunks – [1,2,3,1] – 1 move + 3 = 4 minutes
The minimum among them is 3 minutes. For simplicity I have not shown the division for size greater than 3. Even if we calculate they return the same output of 4.

The maximum time it takes for any combination is the maximum number of cakes in any plate.

Here is the C++ implementation of the same.
Note: I did not solve this problem in the competition. But I got inspired by the solutions (user: kyc) who successfully solved the problem. I only composed the solution analysis. If somebody has a better solution, please feel free to post it in a comment.

Standing Ovation: Google codejam 2015 Qualification round problem

Every year Google conducts a competition called Codejam for programming enthusiasts. The qualification round for the year 2015 got finished yesterday. In this post, I am going to explain the solution approach for the first problem.

You can read the problem from this link. I will try to give the abridged problem statement below.

There are a group of N people in a stadium with their shyness levels represented by a String S of digits(0-9). The digit at each index represents the number of persons with shyness level equal to the index.

For example S[0] represents the number persons with shyness ‘0’.
S[1] represent the number of persons with shyness ‘1’ and so on.

Persons with shyness level ‘L’ will not standup and clap until ‘L’ other people standup and clap before them. For example, in order for a person with shyness level 3 to standup and clap, 3 other people must do that before him.

Now the problem is to find whether the all the people in the given group gives a standing ovation on its own? or What is the minimum number of people to add to the group to ensure that they give a standing ovation.

Let us consider a couple of simple examples.

1. [1, 1, 2]: There is one person with shyness level 0 who will clap first. After seeing him, the second person with shyness 1 will also clap. Then the last two people with shyness 2 will also clap. So there is no need to add any people to give a standing ovation.
2. [1, 0, 1]: In this case, we need one person with shyness 0 or 1 to be added to the group because the last person will not standup until 2 other people clap.

A simple greedy approach will solve the problem. Here is the algorithm.

Start at the first person and count the number of people stood up before him. If this count is not enough for the current person to standup, count the difference needed.  Accordingly increment the people currently standing.

Here is the C++ implementation of the above approach. This runs in O(n) time.

Generating next bigger palindrome of a number

Given a number, how do we generate a smallest number which is greater than the given number and is a palindrome?

Consider the following examples

Input    Output
3         4
9         11
13        22
767       777
594       595
898       909
999       1001

Here is the solution approach. This problem has multiple cases to be considered.

Case 1:
If all the digits in the number are ‘9’, the output is simply 1 followed by (d-1) 0’s followed by 1, where d is the number of digits in the original number.

Example: 9999, d = 4, so the output is 10001

Case 2:
How do we get a palindrome from a given number with least number of changes?
If the given number itself is a palindrome, obviously we need not make any changes.
Otherwise there are two ways to do that. Replicate the right half with left or replicate the left half with right.

Consider the number 230847, the two possibilities are 230032 and 748847
for 6195824, the two possibilities are 6195916 and 4285824.

Observe that if we replicate left half with right half, we are getting the numbers far from the given number. This is because as we move from right to left, the place value of the digit increases. But we want the number which is just greater than the given number with least difference.

So we have to replicate the right half with left half.

Are we done if we just replace the right half with left half? No.

Let us see the same example of 230847, if we replicate as said above, the result is 230032.
What is the problem with this number? It is a palindrome; but it is smaller than the given number. We wanted a number which is just greater.

So how to make this number just bigger?

Increment the middle digit(s) and propagate the carry if any towards the left and the right.

If the number has even number of digits, there will be two middle digits; otherwise it has just one middle digit.

230032 becomes 231132 and that is the required answer.

Let us consider one more example with carry propagation, 849948. After incrementing middle digits, it becomes 850058.

Here is the C++ implementation of the above algorithm.