Monthly Archive: June, 2015

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

RingBuffer implementation

The ring buffer can be implemented using a simple array of items. We need to keep track of two indexes between which useful data is actually stored. The enqueue operation moves the last… 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

Circular stack implementation

We had a recent post regarding circular queues implementation. Let’s try to implement a circular stack. As previously, we have a pointer to the last element in the circular linked list. We can… 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

Circular queue implementation

The trick here is that you need a pointer to the last element in the circular linked list. Inserting items in the linked list can happen replacing the last element or after the… 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