← Turing Interview Insights

Turing·Software Engineer·Online Assessment (OA)·Intermediate

IntermediatePrefer not to say
Mar 2026Remote

Summary

Got a coding problem from Turing that was basically LC 629 in disguise. Standard DP inverse pairs problem, nothing too surprising if you've seen it before.

Questions Asked (1)

Q1

Given two integers m and n, count the number of permutations of length m that contain exactly n inverse pairs (where an inverse pair is a pair of indices x < y such that the value at x is greater than the value at y). Return the result modulo 10^9 + 7.

Algorithms & Data Structures
Author's notes

I recognized this pretty quickly as a DP problem but still fumbled the transition for a few minutes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use dynamic programming where dp[i][j] represents the number of permutations of length i with exactly j inverse pairs. The recurrence is dp[i][j] = sum_{k=0}^{min(j, i-1)} dp[i-1][j-k], which can be optimized with prefix sums to O(m*n) time. Return dp[m][n] modulo 10^9+7.

Pro tip: Mention that the recurrence can be optimized using a sliding window (prefix sums) to avoid O(m*n^2) time, and clarify that the answer is 0 if n exceeds the maximum possible inversions m*(m-1)/2.

1. Define the DP state

Let dp[i][j] be the number of permutations of length i with exactly j inverse pairs. Initialize dp[0][0] = 1 and all other entries to 0.

2. Derive the recurrence

When inserting the largest element i into a permutation of length i-1, it can create between 0 and i-1 new inverse pairs. Thus, dp[i][j] = sum_{k=0}^{min(j, i-1)} dp[i-1][j-k].

3. Optimize with prefix sums

Compute prefix sums of dp[i-1] to calculate each dp[i][j] in O(1) time, reducing the overall time complexity to O(m*n).

4. Handle edge cases and modulo

If n > m*(m-1)/2, return 0. Apply modulo 10^9+7 at each addition to prevent overflow.

5. Return the result

After filling the DP table up to m and n, return dp[m][n] modulo 10^9+7.

Key Points to Mention

  • Dynamic programming state definition and recurrence relation
  • Time and space complexity: O(m*n) time and O(n) space with rolling array optimization
  • Maximum possible inversions is m*(m-1)/2, so if n exceeds this, answer is 0
  • Use of prefix sums to optimize the recurrence from O(m*n^2) to O(m*n)
  • Modulo arithmetic to handle large numbers (10^9+7)
  • Edge cases: m=0, n=0, and n > max inversions

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.