Quick problem: find kth element from the end of a linked list

The solution to this problem requires the use of two pointers. The first pointer will be advanced k times from the start of the linked list. Afterwards, the second pointer will be advanced from… Continue reading

Quick problem: circular rotation of string

Finding if a string S1 is a circular rotation of another, given string S2, is a matter of finding S2 in S1+S1. (indexOf) Other solutions involve string search algorithms. public static boolean isCircularRotation(final String… Continue reading

How to properly shuffle an array

Shuffling an array can be tricky exercise since you need to take care to have equal probabilities for all cases. The solution is the Fisher-Yates algorithm, which is implemented below. First method, randomInteger(…), returns… Continue reading

Median of numbers (part two) / k-th smallest value

The median of numbers problem was presented in the previous posts (here and here) as being solved using a combination of two heaps. There is another solution for this problem, solution shared also by… Continue reading

Median of numbers (part one take two): max-heap + min-heap = ♥

The first solution of this problem can be found here. The problem of finding the median value in a bounded array of items can be solved, again, by using a min heap and… Continue reading

Median of numbers (part one): max-heap + min-heap = ♥

Finding the median of an unsorted array of numbers is seen as a special case of the selection algorithm. There are at least three ways in which the problem can be solved: Quickselect, based… Continue reading

Fun with binary search

Everybody knows binary search. Now, two problems with a twist: Count the number of elements smaller than a given value in a sorted array Count the number of elements equal to a given… Continue reading

Binomial distribution

Starting from the following implementation of binomial distribution, public static double binomial(final int n, final int k, final double p) { if (n == 0 && k == 0) { return 1; }… Continue reading