My software development journey
Given some amount N, and a set of denominations, how do you find the number of ways to make change for N? Let us assume that there is infinite supply of coins for each denomination. For example, if we have to make change for 4, and the given denominations are {1, 2, 3}, the possibilities…
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…
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 tree, how do we find the longest distance between any two nodes in it? Some times this is referred to as the diameter of the tree.For example consider the below binary tree The longest path in this tree is 1 – 2 – 3 – 5 – 8 – 6 – 7.…
Given two numbers N and K, how do we print all the K-combinations of numbers from the set {1,2,…N}. For example consider N = 4, K = 3, the possible combinations are [ [1, 2, 3] [1, 2, 4] [2, 3, 4] [1, 3, 4] ] Let us look how to solve this combination problem.…
Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.If there no such element in the array…
Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure. There are three main traversals of the binary tree. Namely In-order traversal Post-order traversal Pre-order traversal In addition to these, there are inverses of the above algorithms, and there is a level order traversal. In this post…
Given a binary tree how to find the height of the tree. It is defined as the number of nodes in the longest path from root to any leaf. We can assume that the height of empty tree is 0 and the height of a tree with just root node as 1. For example the…
The following function is simply based on recursion mechanism. We write a function printReverse(). Initially we call this function by passing a pointer to the first character of the string. We keep calling this function recursively by incrementing the pointer until we reach the null character (End of the string). If we reach null, the…
This is one of the famous programming problems. In this post, we discuss an algorithm to generate all permutations of a given array and how to implement the same in Java.This is also one of the beautiful example to understand recursion.We discuss a recursive algorithm as it is simple to understand and implement. Let us…