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…

## Comparing different types in python

If someone already have experience with languages like C/C++, Java, C# comparison between two variables of different types results in a compile error. But in Python this will simply evaluate to false. So beware when comparing a string and int containg same values. when we print, they look the same. I actually faced this issue…

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

## Maximum number of contiguous ones with K zeros

Given an array of size N, containing only 0’s and 1’s, and a number K, what is the maximum length of the sub-array with contiguous 1’s with at most K 0’s? For example consider the array A = [1, 1, 0, 1, 0, 0, 1], K = 2, the maximum length is 5. i.e the…

## Maximum elements of array

Given an array A of size N, We want to perform several iterations as described below. Select any index i such that 1 <= i <= N, Mark A[i] = 0, move left by filling each element one greater than it’s right Similarly move right, and fill each element which is one greater than it’s…

## Path length between two binary tree nodes

Given a full binary tree (all nodes except leaf nodes have left and right child) represented as shown below. If the root is labelled i, it’s left child is labelled 2*i and right child is labelled as 2*i+1. 1 /   \ 2     3 /  \   / \ 4  5  6   7 Given two nodes from…

## Billing algorithm

This problem is from Codechef. I am re-wording it for more clarity. A garments shop has “Buy 2, Get 2” offer for it’s customers. Whatever the items may be, they charge for costliest items from an order and give the cheapest ones free. However we can divide the items into multiple orders to save more.…

## Minimum number of jumps to reach top

There are N steps in a staircase, and a person can jump 5 steps at max, i.e he can jump any number of steps between 1 and 5. What is the minumum number of jumps he has to make to reach the top? A simple math problem which can be solved using a simple greedy…

## Partial sum queries

Given an array of numbers, we need to answer many queries of the form Sum(A[i]…A[j]), For example, let the array be [15, 6, 1, 12, 7, 4, 10] Sum(A[1:3]) = 15+6+1 = 22 Sum(A[4:6]) = 12+7+4 = 23 … The simplest solution is to iterate through the elements from i to j and return the…