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…

## How does a radix sort work?

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…

## Minimum number of chages to make equal groups

Given an array of numbers, how do we find the minimum number of changes(additions/subtractions) to the elements so that each number in the array is same or equal. For example given the array {1, 2, 3, 4}, the minimum number of changes are 3. i.e we can choose any of the four elements and make…

## Finding a sub list with least max-min difference – Codeforces puzzle

This is a problem from Codeforces. Please follow this link to solve this problem on your own. The abridged problem statement is as follows. You are given an list of numbers, and sub-list size as input. The challenge is to find a sub-list such that the difference between the maximum and minimum numbers in that…

## Joining an array of numbers to form the biggest number

Given an array numbers, we have to join them in such a way that it forms the biggest number. For example consider the simple three element array [10,3,2], they can be joined in following ways 1032, 1023, 2103, 2310, 3102, 3210. Among these numbers 3210 is the biggest number. To solve this problem we definitely…

## Counting triplets with given sum

Given an array of distinct numbers, how do we count the number of triplets with given sum? For example let us consider the array {5, 2, 7, 8, 4, 3} and the sum is 14, There are 3 triplets with the given sum(2,5,7)(2,4,8)(3,4,7) A brute-force algorithm will take O(n3) time. But this problem can also be…

## Number of pairs with sum less than or equal to given value

Given an array of numbers, Count the number of pairs with sum less than or equal to K For example consider the array {5, 1, 12, 3, 6},  pairs with sum <= 10 are {(1,3), (1,5), (1,6), (3,5), (3,6)}.  So there are 5 pairs with the given constraint. In one of the previous posts, we…

## Finding all Pythagorean triples in an array

Given an array of unique elements, Write a program to print all Pythagorean triples in it. A Pythagorean triple is a set of three numbers such that square of one number is the sum of squares of the other two. For example (3,4,5) is Pythagorean triple because 52 = 32 + 42 Consider the array {5, 6, 3,…

## Maximum number of overlapping intervals

Given a set of intervals, how do we find the maximum number of intervals overlapping at any point of time. For example let us consider the following intervals. { (0,2), (3, 7), (4,6), (7,8), (1,5) } The maximum number of intervals overlapped is 3 during (4,5). This can be asked in many forms in a…