Lab · Data Structures and Algorithms (DSA) for interviews
Lab: cleaning a day of UPI payments
The brief
A tiffin service gets UPI payment alerts all day, and some arrive twice. Find the repeated UTRs with a set, total each customer without double counting, match two payments to an amount with two pointers, and spot bursts of payments with a sliding window.
Why it matters
Payment companies, banks and every shop's accounting app must never count a payment twice, and fraud teams watch for bursts of transfers. Hash sets, two pointers and sliding windows are how this runs in O(n), and these three patterns are asked in almost every first coding round.
Skills you practise
- hash sets
- dictionaries for totals
- two pointers on a sorted list
- variable sliding window
What you will have at the end
upi.py: a small reconciliation tool that removes duplicate UPI alerts, totals each customer and flags bursts, all in O(n).
How it is marked (rubric, 100 points)
| Correct resultsEvery check passes, including repeats that arrive three times and empty lists. | 45 |
|---|---|
| Right pattern for each jobA set for repeats, a dictionary for totals, two pointers for the pair and a sliding window for bursts. | 30 |
| Clear codeTuples unpacked into named variables; no copy-paste between functions. | 10 |
| Can explain itYou can say why each pointer only moving forward makes the window O(n). | 15 |
0/4 steps done
Step 1 of 4
Find repeated UTRs
duplicate_utrs(payments) returns the UTRs that arrive more than once, in the order their first repeat arrives, each listed once.
A UTR (Unique Transaction Reference) is meant to be unique, so a second copy is a duplicate alert, not a new payment. Keep a set of UTRs seen so far: checking "in seen" is O(1) on average, so one pass over the day is O(n) time and O(n) space.
A UTR can arrive three times. Add it to the answer only the first time it repeats.
Run shows what your code prints. Check runs the step's tests. Ctrl+Enter checks too.