Invalid Transactions

Invalid Transactions

1. What is this problem about?

The Invalid Transactions interview question asks you to identify transactions from a list that are potentially fraudulent. A transaction is "invalid" if:

1. The amount exceeds 1000.
2. It occurs within 60 minutes of another transaction with the same name but a different city. You need to return a list of all strings representing these invalid transactions.

2. Why is this asked in interviews?

Companies like Bloomberg, PayPal, and Microsoft ask this to test your ability to handle data cleaning and multi-condition filtering. It evaluations whether you can use Hash Table interview patterns to group data and then apply a sliding-window or range-check logic to find conflicts. It’s a highly practical, real-world scenario.

3. Algorithmic pattern used

This is a Data Grouping and Verification problem.

1. Parsing: Split each input string into its components: name, time, amount, city.
2. Grouping: Use a Hash Map to group all transactions by name.
3. Validation:
   • Iterate through every transaction. If amount > 1000, mark it invalid.
   • For each person, compare every pair of their transactions $(T1, T2)$. If |T1.time - T2.time| <= 60 and T1.city != T2.city, mark BOTH as invalid.
4. Deduplication: Use a boolean array or a set to keep track of which original indices were marked invalid to avoid duplicates in the output.

4. Example explanation

["alice,20,800,mtv", "alice,50,100,beijing"]

1. First transaction: Amount 800 (OK).
2. Second transaction: Amount 100 (OK).
3. Conflict check:
   • Both are by "alice".
   • Times are 20 and 50. Difference is 30 ($\leq 60$).
   • Cities are "mtv" and "beijing" (Different). Result: Both strings are returned as invalid.

5. Common mistakes candidates make

• Only marking one: Forgetting that if T1 and T2 conflict, both must be reported, not just the one being currently checked.
• Sorting confusion: Thinking you only need to check adjacent transactions after sorting by time. A transaction at minute 10 could conflict with one at minute 20 AND one at minute 50.
• String Formatting: Errors in parsing the CSV-like strings or rebuilding the output list.

6. Interview preparation tip

Always look for the "All-Pairs" vs. "Sliding Window" distinction. If the window is small (60 minutes) but many transactions can happen within it, a simple nested loop over the transactions of the same person is often efficient enough given the constraints.