Is a binary tree a red-black tree? algorithm puzzle

Red black trees are quite widely used.

A red black tree is a binary search tree, but with some additional colour constraints on the nodes (swiped from the wiki page).

• Each node is coloured either red or black.
• The root is coloured black.
• All NULL nodes are coloured black.
• Every red coloured node must have two black children.
• Every path from a given node to any of it's descendant NULL nodes must have the same number of black nodes.

These constraints ensure that the height of a red black tree on $n$ nodes is $O(\log n)$, and these constraints can be enforced during insertion and deletion, thus making insert/delete/search operations $O(\log n)$ each.

Now for the puzzle.

Suppose you are given a binary tree on $n$ nodes, without any colours on it. Can you determine if there is a red-black colouring of the nodes, which follows the above constraints? i.e. is the binary tree actually a red-black tree?

An $O(n)$ time algorithm is possible, but $O(n \log n)$ is ok too.

[Solution]

Equal Coins, math puzzle

An interesting problem, which has multiple solutions.

Suppose you are given $2n+1$ coins $c_1, c_2, \dots, c_{2n+1}$, of positive real weights $w_1, w_2, \dots, w_{2n+1}$.

These coins have the property that if you remove any coin, then the remaining $2n$ coins can be split into two groups of exactly $n$ coins each, such that the sum of weights of coins in one group, is same as the sum of weights of coins in the other.

Show that $w_i = w_j$ for any $i, j$.

i.e. all the coins must be of equal weight.

[Solution]

Are you alert enough? (bridge hand)

Playing a very casual bridge game (it happened during one of the informal lunch bridge sessions when I was at Microsoft).

You reach a small slam in hearts, and LHO leads the heart 5.

This is what you see:

IMPS None	Dummy ♠ J96 ♥ 94 ♦ 874 ♣ AK875
	You ♠ KT5 ♥ AKQT8762 ♦ AK ♣ -

How will you play?


Solution (Posted too late)

---

Look at the heart spots! You are missing the J,5 and 3.

Put up the 9 on the 5! If RHO covers, you can draw the last trump by playing the 2 to the 4. If not, you can cash AK of clubs, pitching your spade losers.

Solution to rearrange the array, algorithm puzzle.

This is a solution to the rearrange array puzzle posted earlier.

A brief description:

Suppose you are given an array of $2n$ objects

$$[a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n] $$

You need to reorder the array to be

$$[b_1, a_1, b_2, a_2, \dots, b_k, a_k, \dots, b_n, a_n] $$

Hard version: Do this in-place (preferably $O(1)$ space in WORD RAM model), and O(n) time.

(Medium version: Do it in $O(n\log n)$ time, and in-place).

Solution

---

This puzzle is surprisingly difficult (the $O(n)$ time, in-place version). It seems that we should easily be able to do it, but most first approaches fail. The in-place constraint is what makes it difficult (otherwise we can just make a new array and copy the elements easily).

This puzzle was given to me when I was at Microsoft, the problem apparently being open at the time (at least within the set of people at Microsoft who came across the puzzle).

I was able to solve it, and I was encouraged (by someone on an online forum) to write a paper on it. It only took me 4 years to write, but I finally managed to write it, and it is on arxiv now.

This is the paper: A Simple In-Place Algorithm for In-Shuffle. It is only 3 pages long, and should serve as a solution :-) [ok, I am feeling a bit lazy to write it here too.]

The $\Theta(n\log n)$ version also falls out from the paper.

Please feel free to comment if you have any questions regarding the solution in the paper.

Solution to Unit fraction chord lengths.

This is a solution to the unit fraction chord length puzzle.

A brief description:

Any continuous function $f:[0,1] \to \mathbb{R}$ such that $f(0) = f(1)$, has a chord of length $\frac{1}{n}$ where $n$ is a positive integer.

Any other chord length (non unit fraction lengths) have functions which don't have those chord lengths.

Solution

---

Let $g(x) = f(x) - f\left(x + \frac{1}{n}\right)$.

Then we have that

$$g(0)+ g(1/n) + \dots + g((n-1)/n) = f(0) - f(1) = 0 $$

Thus if $g(k/n) \ne 0$, then there are some $i, j$ such that $g(i/n) \lt 0$ and $g(j/n) \gt 0$, and thus by the mean value theorem, some point $c$ where $g(c) = 0$.

For the other part, given any non unit fraction $r$, the function

$$ f_r(x) = \sin^2\left(\frac{\pi x}{r}\right) - x \sin^2\left(\frac{\pi}{r}\right)$$

is a counter-example.

This result is apparently called the Universal Chord Theorem.

Rearrange the array, algorithm puzzle

This is one of my favourite algorithm puzzles.

Suppose you are given an array of $2n$ objects

$$[a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n] $$

You need to reorder the array to be

$$[b_1, a_1, b_2, a_2, \dots, b_k, a_k, \dots, b_n, a_n] $$

The algorithm should be in-place: i.e. space usage must be $O(\log^k n)$ words (in the WORD RAM model), for some constant $k$ (preferably $O(1)$ space, but $k \le 2$ will do too). Assume that each object ($a_i$ or $b_i$) takes up $O(1)$ space and copying them around is $O(1)$ time and space.

Medium:

Can you give an $O(n \log n)$ time algorithm?

Hard:

Can you give an $O(n)$ time algorithm?


[Solution]

Unit fraction chord lengths

Another interesting property of unit fractions (numbers of the form $\dfrac{1}{n}$ for positive integer $n$).

Part A)

Suppose $f:[0,1] \to \mathbb{R}$ is any continuous function such that $f(0) = f(1)$.

Show that for every natural number $n \gt 0$, there is some $c \in [0,1]$ ($c$ dependent on $n$ and $f$) such that $f(c) = f\left(c + \dfrac{1}{n}\right)$

Basically the graph of $f$ has a chord of length $\dfrac{1}{n}$.

Part B)

Suppose $r \in (0,1)$ is a real number such that $r$ is not a unit fraction.

Show that there is some continuous function $f_r$ (dependent on $r$) such that

$f_r:[0,1] \to \mathbb{R}$, $f_r(0) = f_r(1)$ and for any $c \in [0,1-r]$, $f_r(c) \ne f_r(c+r)$.

i.e the graph of $f_r$ has no chord of length $r$.

[Solution]

6D making 6!!!!! [A hand played by Belladonna]

This hand was played by Giorgio Belladonna as part of one of the Omar Sharif Circus matches in 1970. This hand has probably appeared in multiple books: 'Bridge with the Blue Team', 'The Hands of Time', to name a couple.

The title (exclamation marks and all) of this blog post is from the actual hand-written surprise written by Maureen Kaufmann on the monitor sheet (source: 'The Hands of Time').

This was the hand:

IMPS N/S	Garozzo ♠ 7654 ♥ A83 ♦ J32 ♣ KQ5
Eisenberg ♠ KJ92 ♥ QJT6 ♦ 854 ♣ 86		Goldman ♠ 83 ♥ 92 ♦ 9 ♣ AJT97432
	Belladonna ♠ AQT ♥ K754 ♦ AKQT76 ♣ -

W	N	E	S
P	P	4C	5C
P	5S	P	6D
all	pass

Eisenberg led the club 8. Belladona played the K, covered by Goldman and ruffed.

[Think about how you will play looking at the just the North and South hands]

At this point Belladonna got up, went to the coffee table, and lit up a cigarette and walked back and forth with his head in hand, puffing away.

He then came back, played the DA and diamond to J. Cashed the CQ pitching the ST, ruffed a club high and ran trumps to arrive at this position:

IMPS N/S	Garozzo ♠ 7654 ♥ A83 ♦ - ♣ -
Eisenberg ♠ KJ9 ♥ QJT6 ♦ - ♣ -		Goldman ♠ 83 ♥ 92 ♦ - ♣ JT9
	Belladonna ♠ AQ ♥ K754 ♦ T ♣ -

On the last trump, Eisenberg was caught in a strange squeeze.

If he pitched a heart, Belladona would play AK heart and small heart, setting up a heart, and endplaying Eisenberg to lead into the spade AQ.

If Eisenberg pitched a spade, Belladona would play SA and SQ, setting up the 7 and 6 in the dummy!

6D made 6!!!!!

Solution to streaming pivot, algorithm puzzle

The problem was posted earlier.

A brief description:

Find a pivot in a stream of distinct numbers, using sub-linear space.

Pivot = all numbers that came before it are smaller than it, all numbers that came after it are greater.

Solution

---

The algorithm will find the leftmost/earliest pivot, if a pivot exists.

If A[j] is a pivot, then A[j] = maximum of A[1], A[2], ..., A[j].

We keep track of the maximum seen so far, and a candidate leftmost pivot, which has the above property.

Once we have a candidate leftmost pivot, we check each subsequent number against that candidate. If we get a number which is smaller than the candidate pivot, then none of the numbers seen so far can be the leftmost pivot! Now we reset and look for a new leftmost candidate using the maximum seen so far property.

This gives us an O(1) space algorithm.

Solution to sum of unit fractions puzzle

This is a solution to the sum of unit fractions puzzle posted earlier.

The problem:

Show that every positive rational number can be written as a sum a finite number of distinct unit fractions (unit fraction = number of the form 1/n).

Solution

---

[This proof appears in the classic number theory book by Niven and Zuckerman]

First, consider rationals $\lt 1$ in the reduced form $\frac{a}{b}$, with $0 \lt a \lt b$ and $\gcd(a,b) = 1$.

We prove by strong induction on $a$.

If $a = 1$, there is nothing to prove.

If $a = 2$, then $b$ must be odd (say $2x+1$).

Then we can use the identity

$$\frac{2}{2x+1} = \frac{1}{x+1} + \frac{1}{(x+1)(2x+1)}$$

Now given $\dfrac{a}{b}$ (in reduced form)

Let $c$ be the smallest integer such that $ac \gt b$.

Then we must have that $ac = b + r$, for some $0 \lt r \lt a$.

If $r \gt a$, then $c$ won't be the smallest integer such that $ac \gt b$.

Now consider $\dfrac{ca}{b} = 1 + \dfrac{r}{b}$.

Thus

$\dfrac{a}{b} = \dfrac{1}{c} + \dfrac{r}{bc}$

By induction hypothesis, $\dfrac{r}{bc}$ can be written as a sum of distinct unit fractions.

Now $\dfrac{r}{bc} \lt \dfrac{1}{c}$, so none of those unit fractions can be $\dfrac{1}{c}$.

Thus $\dfrac{a}{b}$ can be written as a sum of distinct unit fractions.

Now, if $r$ is any rational $\gt 1$, then since the series $\sum_{k=1}^{\infty} \frac{1}{k}$ diverges, there is some m such that

$$ 1 + \frac{1}{2} + \dots + \frac{1}{m} \le r \lt 1 + \frac{1}{2} + \dots + \frac{1}{m+1}$$

Consider $ r - (1 + \dfrac{1}{2} + \dots + \dfrac{1}{m})$, this is a rational number < $\dfrac{1}{m+1}$, and so can be written as a sum of distinct unit fractions, and each denominator will be $\gt m$.

Thus we are done.

Streaming pivot, algorithm puzzle

In an array A[1], A[2], ..., A[n] of distinct numbers, A[p] is called a pivot if all numbers to left of A[p] are less than A[p] and all numbers to right of A[p] are greater than A[p].

i.e. for any i < p, A[i] < A[p] and for any j > p, A[p] < A[j].

Basically, if we sort the sub-array A[1], A[2], ..., A[p-1] and sub-array A[p+1], .., A[n] independently, then whole array will be sorted (this must remind you of quicksort).

Now suppose you were given the array A as a stream of numbers A[1], A[2], ... i.e. you can access A by accessing only A[1] first, then A[2], and so on. Once you access A[5], you cannot access A[4] again (unless you save it) etc.

Given a stream of distinct numbers, can you find a pivot (or say if there is none) using an algorithm which uses sub-linear space?

[The optimal algorithm will use O(1) space, and O(n) time total: Solution]