My software development journey
Given a number N, how do we generate all possible valid expressions with N pairs of brackets?For example for N = 2, there are 2 such expressions ()()(())For N = 3, there are 5 expressions((()))(()())(())()()(())()()()We have a simple solution to this problem by using recursion. We design this method as follows. It takes two parameters…
Radix sort is an integer sorting algorithm. As it’s name indicates, it sorts a list of numbers based on the digits of the numbers. It’s a linear time sorting algorithm which is different from the comparison based sorting algorithms like quick sort or heap sort. Counting sort is also a linear time sorting algorithm which…
Given a binary tree, how do we write a program to check if it is the mirror image of itself. This binary tree is also called a symmetric tree. A binary tree is called a symmetric tree if it’s left and right sub-trees are mirror images of each other. For example Let us…
Given a binary tree, how do we print the nodes in level order starting from the bottom. For example for the following tree, the output should be 2 3 1 1 / 2 3An obvious solution is to first find the maximum levels of the tree. we can print the nodes from maximum level…
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…
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 / / …
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…
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…
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…
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…