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…

## Searching for an element in array with successive elements atmost 1 distance apart

Given an array of integers where each element has a difference of atmost 1 with it’s neighbors, we need to find the given element. For example, consider the array [1, 2, 2, 1, 2, 3, 2, 1], and the element to be searched is 3, we need to return the index 5. This is just…

## Searching for a word in a grid

Given a two dimensional table of letters, and a word to be searched, design an algorithm to check if it is present in the grid. The word can be formed in any of the 8 possible directions as shown below. Here is how I solved this problem. Write a function which takes the string to…

## Minimum number after removing K digits

Given a number N, and a number K, find the minimum number that can be formed by deleting K digits. The order of the digits should not be changed. For example consider N = 234987, K = 2, we can remove 9,8 and the resulting number is 2347.The solution is based on the following observation,…

## Maximum number of 1s in any row of a boolean matrix

Given a matrix consisting of only 0,1s, with each of it’s row sorted (i.e all 0s appear before 1s). The problem is to efficiently find the maximum number of 1s present in any row. For example consider the following matrix. 0 0 1 10 0 0 10 1 1 10 0 0 0 The maximum…

## Type casting in C++ – Part 1

Type casting frequently arises in real life programming. This post concentrates on type conversion of fundamental data types. Type casting is the process of converting from one data type to another. In C++, type casting is automatic in some situations. These are called implicit conversions. For example char c = ‘A’; int ch_code = c;…