Count All Valid Pickup and Delivery Options

Count All Valid Pickup and Delivery Options

What is this problem about?

The Count All Valid Pickup and Delivery Options coding problem asks you to find the total number of ways to sequence n orders, where each order consists of one pickup (P) and one delivery (D). The only rule is that for each order i, the pickup Pi must occur before the delivery Di. You need to return the total count modulo 10^9 + 7.

Why is this asked in interviews?

DoorDash and Google ask the Count All Valid Pickup and Delivery Options interview question to test your knowledge of combinatorics and dynamic programming. It’s a "Hard" problem that requires you to derive a mathematical recurrence rather than just writing a simple loop. It evaluates your ability to break down a permutation problem with constraints into a solvable pattern.

Algorithmic pattern used

This is a Combinatorics / Dynamic Programming problem.

• For n orders, there are 2n total slots.
• For the first order, you have 2n choices for the pickup and 2n-1 choices for the delivery, but since P must be before D, only half of those (2n * (2n-1)) / 2 are valid.
• The formula for n orders is f(n) = f(n-1) * (2n * (2n-1)) / 2.
• Alternatively, you can think of it as: (2n)! / 2^n.

Example explanation

n = 2 (Two orders: 1 and 2)

1. Order 1 has slots P1, D1. (1 way).
2. For Order 2, there are 2 slots already taken. Total 4 slots available.
3. Number of ways to place P2 and D2 in 4 slots such that P2 < D2 is 4 * 3 / 2 = 6.
4. Total ways = 1 * 6 = 6. The valid sequences are: (P1, D1, P2, D2), (P1, P2, D1, D2), (P1, P2, D2, D1), (P2, D2, P1, D1), (P2, P1, D2, D1), (P2, P1, D1, D2).

Common mistakes candidates make

• Forgetting Modulo: Not applying 10^9 + 7 at each multiplication step, leading to integer overflow.
• Brute Force: Trying to generate all permutations (O(N!)), which is impossible for even n=10.
• Logic Error: Thinking the answer is just (2n)! without accounting for the P before D constraint.

Interview preparation tip

Combinatorics problems often have an O(N) solution once you find the recurrence. If you're stuck, try calculating the results for n=1, 2, 3 and look for a pattern in the multipliers (1, 6, 15...).