Handshakes That Don't Cross

Handshakes That Don't Cross

What is this problem about?

The Handshakes That Don't Cross coding problem asks you to find the number of ways $n$ people sitting around a circular table can shake hands such that no two handshakes cross each other. Each person shakes hands with exactly one other person, so $n$ must be even. The result can be very large, so you need to return it modulo $10^9 + 7$.

Why is this asked in interviews?

Amazon and other companies use this problem to test a candidate's knowledge of Combinatorics and Dynamic Programming. It is a classic application of Catalan Numbers. It evaluations your ability to break a circular problem into independent sub-problems by fixing one handshake and observing how it divides the remaining people into two isolated groups.

Algorithmic pattern used

This problem follows the Dynamic Programming pattern.

1. Let dp[i] be the number of ways $i$ people can shake hands without crossing.
2. Fix one person (person 1) and pick another person (person $j$) to shake hands with.
3. For the handshakes not to cross, $j$ must be chosen such that the number of people on either side of the $(1, j)$ line is even.
4. If person 1 shakes hands with person $j$, the table is split into two groups: one with $j-2$ people and one with $n-j$ people.
5. Recurrence: dp[n] = sum(dp[j-2] * dp[n-j]) for all valid $j$. This is the recursive formula for Catalan Numbers.

Example explanation

$n = 4$ people.

1. Person 1 can shake hands with Person 2. This leaves 0 people on one side and 2 people on the other. Ways: dp[0] * dp[2] = 1 * 1 = 1.
2. Person 1 can shake hands with Person 4. This leaves 2 people on one side and 0 on the other. Ways: dp[2] * dp[0] = 1 * 1 = 1.
3. Person 1 cannot shake hands with Person 3 because it would leave 1 person on each side, who would be forced to cross the (1,3) line to shake hands. Total ways: $1 + 1 = 2$.

Common mistakes candidates make

• Ignoring the "Even" constraint: Not realizing that each handshake must leave an even number of people in the resulting partitions to allow for valid pairings.
• Forgetting Modulo: Not applying the modulo operation at each addition, leading to integer overflow.
• Brute Force Recursion: Implementing the recurrence without memoization, leading to exponential time complexity.

Interview preparation tip

Familiarize yourself with the Catalan Number sequence (1, 1, 2, 5, 14...). It appears in many interview problems, such as "Counting valid parentheses," "Ways to triangulate a polygon," and "Number of unique Binary Search Trees." Recognizing the pattern early can save you significant time.