Count inversions in an array efficiently
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
Given the array [5, 7, 9, 2, 3, 12, 8, 4], compute the number of inversion pairs (i, j) where i < j and arr[i] > arr[j]. Describe both a naive O(n^
2) approach and an O(n log n) divide-and-conquer method, and analyze their complexities.
Quick Answer: This question evaluates understanding of inversion counting and algorithmic design, specifically comparing naive O(n^2) approaches with O(n log n) divide-and-conquer strategies while requiring analysis of time and space complexity.