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

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