Top Percentile Fraud - Solution & Explanation

Problem Overview: You need to identify records that fall within the top fraud percentile based on a fraud-related metric (for example fraud rate, fraud score, or suspicious transaction count). The task is essentially a ranking problem: compute the relative position of each record and return only those that fall within the highest percentile threshold.

Approach 1: Aggregate + Threshold Subquery (O(n log n) time, O(n) space)

A straightforward approach computes the fraud metric for each entity (user, merchant, or account) using GROUP BY. After generating the aggregated results, sort them by the fraud metric and determine the cutoff for the desired percentile using a subquery. For example, you can compute the value at the 90th or 95th percentile and filter rows where the metric is greater than or equal to that threshold.

This approach works in most SQL systems but often requires multiple passes over the data. One query computes aggregated fraud metrics, another determines the percentile cutoff, and the outer query filters results. The database must perform sorting to determine percentile boundaries, giving roughly O(n log n) time due to ordering and O(n) space for intermediate results. This method is easy to reason about but becomes verbose and less flexible when you need multiple percentile-based filters.

Approach 2: Window Function Ranking (O(n log n) time, O(n) space)

The cleaner solution uses SQL window functions to compute the percentile rank directly for each row. After computing the fraud metric per entity, apply functions like PERCENT_RANK() or CUME_DIST() over an ordered window such as OVER (ORDER BY fraud_metric DESC). This assigns a percentile position between 0 and 1 to every record.

Once the percentile rank is available, filtering becomes trivial: keep rows where the percentile is greater than or equal to the required threshold (for example >= 0.9 for the top 10%). The database engine performs a single ranking pass after sorting the results. Sorting dominates the runtime, so the overall complexity is O(n log n), with O(n) space used for the ranking window.

This method is concise and expressive. It keeps the entire computation inside one query and avoids manually calculating percentile boundaries. Window functions are widely used in analytical SQL problems and are a core technique in database interview questions.

Recommended for interviews: The window function approach is the expected solution. Interviewers want to see that you understand ranking functions like PERCENT_RANK or CUME_DIST and can apply them to percentile-based filtering. Mentioning the aggregation + threshold method first shows you understand the baseline approach, but using a window function demonstrates stronger SQL skills and familiarity with modern analytical queries often used in SQL data analysis tasks.