Category Archive: algorithms

Sorting a deck of cards

How can we sort a deck of cards knowing that we can only look at the top cards, exchange the top cards, and moving the top card to the bottom of the stack?… Continue reading

Bitonic search

Given a bitonic array, we need to determine if a number is part of the array or not. This is actually a triple binary search problem: finding the peak spot and then finding… Continue reading

4SUM implementation

Let’s try to solve the 4SUM problem. We will also take a look at 3SUM and 2SUM. I will propose two solutions, both in O(n 2). 1. This solution uses a temporary dictionary and therefore… Continue reading

Josephus problem

Josephus problem statement can be found here. We will try to solve this problem using dynamic programming. Other choice is to use queues or circular buffers to hold the participants. Let’s try an… Continue reading

Quick problem: reverse a String

Solution for strings that don’t contain surrogate keys etc. (UTF issues): public String reverse(final String s) { final char[] chars = s.toCharArray(); final int length = chars.length; for (int i = 0; i… Continue reading

Quick problem: reverse a linked list

The iterative solution:  Iterating through the list, we append the reversed result to the current node; then the reversed result encapsulates the current node; and finally, we advance in the list using a previously… Continue reading

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