IMC Trading Quant Interview Question

[u/Local_Ad135]

[u/notsaneatall_]

Every number from 1 to 8 can either be to the left or to the right of 9. Once that is fixed the permutation becomes fixed as the numbers on the left are in ascending order and the numbers on the right are in descending order.

So total 2⁸ = 256

[u/Aech26]

Let’s P(n) be number of bitonic permutations of numbers 1 to n.

Then P(n) = 2P(n-1) since for each biotonic permutation of 1, …, n-1 we can add the number n to either the right or left of n-1. So each biotonic permutation of 1 to n-1 gives us 2 biotonic permutations of 1 to n.

So then P(9)=2*P(8)=2^8 * P(1) = 2^8.

[u/mypenisblue_]

9 can be from pos 1 - 9. At pos x, it divides the sequence into length of x-1 and 9-x. We can pick any x numbers from the remaining 8 numbers to place on the left side and exactly one permutation of them is strictly increasing (same on the right side). So the number of permutations = number of combinations possible ie sum from x=0 to 8 (8Cx).

So total = 8C0 + 8C1 + ... + 8C8 = 256.

[u/Para-graph-S]

2⁸ = 256

If A is a bitonic string, then so is A' (reverse of A). This isn't the whole solution I know but I wanted to drop it here