FastPrepCount Inversions
Problems/Count Inversions

Count Inversions

Expedia logoExpedia● MediumINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A report on Expedia's 2024 campus hiring for SDE interns lists this as one of two coding questions in an online test. The problem card it links counts each pair where a bigger number sits before a smaller one. The numbers are all different, there are at most 10^5 of them, and each is between 1 and 10^9. The candidate solved it with merge sort. A 2022 report from a US intern assessment also mentions an inversion question, with no details.

Neither report gives a function or examples, so we wrote those, and you return the count as a 64-bit integer. We read the 2022 mention as the same pair count.

Our version is about 95% the same as the 2024 report.

You are given an integer array arr whose values are all different. Two positions i < j form an inversion if arr[i] > arr[j], so a larger value comes before a smaller one.

Count every such pair and return the total.

The answer can be larger than 2^31 - 1, so return it as a 64-bit integer.

Function

countInversions(arr: int[]) → long

Examples

Example 1

arr = [4,1,3,2]return = 4

There are six pairs of positions. Four of them have the larger value first: (4, 1), (4, 3), (4, 2) and (3, 2). The pairs (1, 3) and (1, 2) are already in order, so the answer is 4.

Example 2

arr = [5,10,15]return = 0

Each value is larger than every value before it, so no pair is an inversion.

Example 3

arr = [9,7,5,3]return = 6

The values only go down, so every pair is an inversion. Four values make 4 * 3 / 2 = 6 pairs.

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^9
  • All values in arr are different.

More Expedia Online Assessment questions

  • Balanced NumbersOA · Seen Aug 2026
  • REST API: Discounted PriceOA · Seen Aug 2026
  • Maximum Team SizeOA · Seen Mar 2026
  • Per-Domain Request LimiterOA · Seen Oct 2025
  • Count Equal-Frequency SubsequencesOA · Seen Mar 2025
  • Count Increasing Stock PeriodsOA · Seen Mar 2025
  • Get Minimum StepsOA · Seen Oct 2024
  • Rank Songs by PopularityOA · Seen Oct 2024
  • Calculate the SumOA · Seen Oct 2024
  • Get Maximum EfficiencyOA · Seen Oct 2024

Similar questions at other companies

  • Count InversionsNutanix · OANutanix interview questions
  • Temporal AnomaliesInMobi · OAInMobi interview questions
  • Minimum Euclidean Distance Between PointsLuma AI · OALuma AI interview questions
  • Merge Sort Report with a Noisy ComparatorMercor · ONSITE INTERVIEWMercor interview questions
  • K Largest Elements with QuickselectAMD · ONSITE INTERVIEWAMD interview questions
  • Implement Merge SortSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Closest Pair of PointsCitadel · PHONE SCREENCitadel interview questions
  • Generalized N-SumBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
  • Count Inversions With Merge SortAdobe · PHONE SCREENAdobe interview questions
  • Capping Portfolio WeightsCapstone Investment Advisors · OA

Interview reports that mention this question

  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public long countInversions(int[] arr) {
        // Write your code here.
    }
}
Checking account…