Close

## Sorting the elements by frequency

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…

## Comparator and Comparable interfaces in Java

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…

## Edit distance 1

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

## How to check if sequence is a sub sequence of another

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…

## Finding the pivot element

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

## Duplicate elements in array at given distance

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…

## Mirror image of a binary tree

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…

## Generating all possible parenthesis expressions

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…

## Check if a binary tree is the mirror image of itself

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 consider the…

## Level order traversal of the binary tree from the bottom

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…