Frontend School

Recent Duplicate Transaction Detector

DSA
medium

Recent Duplicate Transaction Detector

Medium
Arrays
Hash Table
Sliding Window

Overview

Intuit handles millions of financial transactions daily. Detecting unusual patterns, such as duplicate transaction amounts occurring too frequently, is crucial for fraud detection and maintaining data integrity. This problem simulates a scenario where we need to identify suspicious transactions based on recent duplicates.

What you need to do / Task

You are tasked with implementing a function findSuspiciousTransactions that identifies transactions whose amounts have been seen recently. A transaction is considered "suspicious" if:

  1. Its amount is not zero.
  2. Its amount is identical to the amount of a previous transaction T_j (where j < i), and the index difference i - j is less than or equal to a given windowSize. If there are multiple previous transactions with the same amount, we only consider the most recent one (i.e., the one with the largest j).

Your function should return a list of the ids of all suspicious transactions, in the order they appear in the input.

Input & output

Input:

  • transactions: An array of Transaction objects. Each Transaction object has two properties:
    • id: A string representing a unique transaction identifier.
    • amount: A number representing the transaction amount.
  • windowSize: A number representing the maximum allowed index difference for a duplicate amount to be considered "recent".

Output:

  • An array of strings, where each string is the id of a suspicious transaction.

Clarifications

  • An amount of 0 is never considered suspicious, even if duplicated.
  • The windowSize will always be a positive integer.
  • The input transactions array can be empty. If so, return an empty array.
  • Transaction ids are unique.
  • The problem asks for the IDs of all suspicious transactions, not just the first one found.

Examples

1

Example 1

Input:

transactions = [{"id": "T1", "amount": 100}, {"id": "T2", "amount": 200}, {"id": "T3", "amount": 100}, {"id": "T4", "amount": 300}, {"id": "T5", "amount": 100}], windowSize = 2

Output:

["T3","T5"]

Note:

T3 (amount 100, index 2) is suspicious because T1 (amount 100, index 0) is within windowSize (2-0 = 2 <= 2). T5 (amount 100, index 4) is suspicious because T3 (amount 100, index 2) is within windowSize (4-2 = 2 <= 2).

2

Example 2

Input:

transactions = [{"id": "A", "amount": 50}, {"id": "B", "amount": 0}, {"id": "C", "amount": 50}, {"id": "D", "amount": 10}, {"id": "E", "amount": 50}], windowSize = 1

Output:

[]

Note:

B is skipped due to zero amount. For C (amount 50, index 2), the most recent previous 50 was A (index 0). 2-0 = 2, which is > windowSize (1). Not suspicious. For E (amount 50, index 4), the most recent previous 50 was C (index 2). 4-2 = 2, which is > windowSize (1). Not suspicious.

3

Example 3

Input:

transactions = [{"id": "X", "amount": 10}, {"id": "Y", "amount": 20}, {"id": "Z", "amount": 10}], windowSize = 100

Output:

["Z"]

Note:

Z (amount 10, index 2) is suspicious because X (amount 10, index 0) is within windowSize (2-0 = 2 <= 100).

Constraints

Constraints & assumptions

  • 1 <= transactions.length <= 10^5
  • 1 <= windowSize <= transactions.length
  • -10^9 <= transaction.amount <= 10^9
  • transaction.id will be a non-empty string.
  • The order of ids in the output array must match their order of appearance in the input transactions array.

What interviewers evaluate

  • Correctness: Does the solution correctly identify all suspicious transactions according to the given criteria?
  • Efficiency: Does the solution achieve optimal time and space complexity for the given constraints?
  • Code Quality: Is the code well-structured, readable, and appropriately uses data structures?
  • Edge Cases: Does the solution handle edge cases like empty input, zero amounts, or windowSize equal to 1?

Loading editor...