My software development journey
Given an array, how do we sort the elements by descending order of their frequency? Also if two elements appear for same number of times, one which appeared first in the input array should be placed first. For example, if A = [7, 6, 1, 7, 1, 3, 6, 6, 2] The output should be…
In Java there are two ways to impose ordering on objects. One is through Comparator interface, and the other is through Comparable interface. Let us see the similarities and differences between them and when should we use them. If we are defining a class, and we want a natural ordering of a collection of the…
Given two strings, how do we check if their edit distance is 1?Edit distance is defined as the number of characters that needs to be modified, inserted or deleted from one string to transform into the other string.For example let us consider two strings “java”, “lava” they both differ by just one character. we can…
Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]The algorithm here is simple. Let us assume two…
Given an array of numbers ( minimum length 3), find an index such that all the elements to the left of it are less than or equal, and all the elements to the right of it are greater than it. For example in the array [1, 2, 3], the pivot element is 2, as all…
Given an array of numbers A, which might contain duplicate elements, How do we find if there are two elements A[i], A[j] such that i, j are distinct and the difference between them is at most k? Look at the following examples.1. A = [9, 5, 6, 9, 3, 0, 1], K =3The answer is…
Given a binary tree, how to convert it to it’s mirror image?For example consider the following binary tree and it’s mirror image. Here simply, the left and right sub trees of each node are inverted. So we have to simply invert the given binary tree. It is a simple implementation problem. Using recursion we can…
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 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…