Close

## 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…

## 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  /                       /              …

## 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…

## 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…

## 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…

## 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…

## 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…

## 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 examplesInput    Output3         49         1113        22767       777594       595898       909999       1001Here 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…