← Amazon questions

Inversion count and LCS

Filed under Amazon

Free read 3 of 3

Understand inputs, output formats, and performance constraints to avoid recursion limits.

The question

Given an array of integers, find its inversion count (number of pairs (i, j) such that i < j and arr[i] > arr[j]). Additionally, find the length of the Longest Common Subsequence (LCS) of two given strings.

Constraints

  • Array length up to 10^5
  • String lengths up to 1000
  • Avoid recursive solutions

Examples

Input
arr = [2, 4, 1, 3, 5], text1 = "abcde", text2 = "ace"
Output
Inversions = 3, LCS = 3
Why
Inversion pairs are (2,1), (4,1), (4,3). LCS is "ace" of length 3.

Approach

  1. Understand inputs, output formats, and performance constraints to avoid recursion limits.

Tips

  • What they are testing: Test with strictly increasing/decreasing arrays and completely disjoint strings.
  • Common mistake: Using naive O(n^2) nested loops for inversion counting instead of modified merge sort.

Related Amazon questions

Collected from public candidate posts and coding forums. Updated Nov 2026.