Find invalid transactions in time-sorted input
Problem Description
You are provided with a list of transaction records, where each record is a string formatted as "name,time,amount,city". The input list is guaranteed to be sorted in non-decreasing order by time.
Each transaction string contains:
name: A lowercase string identifier for the person.time: An integer representing minutes.amount: An integer representing the transaction value.city: A lowercase string representing the city where the transaction occurred.
A transaction is considered invalid if it meets either of the following criteria:
- Its
amountis strictly greater than1000. - There exists another transaction with the same
namethat occurred within 60 minutes (inclusive, i.e.,|current_time - other_time| <= 60) of this transaction, but in a differentcity.
Your task is to return all invalid transactions as their original string representations. The order of the returned invalid transactions does not matter.
Requirements
- The input list of transactions is globally sorted by time in non-decreasing order.
- The target time complexity for your solution should be O(n), or close to it (amortized), where
nis the total number of transactions.
Example
Input:
["alice,20,800,mtv", "alice,50,100,beijing", "bob,50,1200,mtv"]
Output (order may vary):
"alice,20,800,mtv"(Invalid due to different city within 60 minutes with "alice,50,100,beijing")"alice,50,100,beijing"(Invalid due to different city within 60 minutes with "alice,20,800,mtv")"bob,50,1200,mtv"(Invalid due to amount > 1000)
AI interview prep
Core dilemma
Efficiently identifying all transactions that are invalid due to a 'same name, different city, within 60 minutes' rule, while adhering to an O(N) time complexity, given that a transaction can invalidate both past and future transactions within its time window.
2 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Find invalid transactions in time-sorted input
Problem Description
You are provided with a list of transaction records, where each record is a string formatted as "name,time,amount,city". The input list is guaranteed to be sorted in non-decreasing order by time.
Each transaction string contains:
name: A lowercase string identifier for the person.time: An integer representing minutes.amount: An integer representing the transaction value.city: A lowercase string representing the city where the transaction occurred.
A transaction is considered invalid if it meets either of the following criteria:
- Its
amountis strictly greater than1000. - There exists another transaction with the same
namethat occurred within 60 minutes (inclusive, i.e.,|current_time - other_time| <= 60) of this transaction, but in a differentcity.
Your task is to return all invalid transactions as their original string representations. The order of the returned invalid transactions does not matter.
Requirements
- The input list of transactions is globally sorted by time in non-decreasing order.
- The target time complexity for your solution should be O(n), or close to it (amortized), where
nis the total number of transactions.
Example
Input:
["alice,20,800,mtv", "alice,50,100,beijing", "bob,50,1200,mtv"]
Output (order may vary):
"alice,20,800,mtv"(Invalid due to different city within 60 minutes with "alice,50,100,beijing")"alice,50,100,beijing"(Invalid due to different city within 60 minutes with "alice,20,800,mtv")"bob,50,1200,mtv"(Invalid due to amount > 1000)