Find invalid transactions in time-sorted input
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
You are given a list of transaction records, already sorted in **non-decreasing order by time**.
Each transaction is a string in the form:
`"name,time,amount,city"`
- `name`: lowercase string identifier
- `time`: integer minutes
- `amount`: integer
- `city`: lowercase string
A transaction is **invalid** if **either** of the following holds:
1. `amount > 1000`, or
2. There exists **another** transaction with the **same** `name` that occurred within **60 minutes** (inclusive) of this transaction, but in a **different** `city`.
Return **all invalid transactions** (as the original strings). Order does not matter.
## Requirements
- Input is globally time-sorted.
- Target time complexity: **O(n)** (or close to it, amortized).
## Example
Input:
- `["alice,20,800,mtv","alice,50,100,beijing","bob,50,1200,mtv"]`
Output could include:
- `"alice,20,800,mtv"` (diff city within 60)
- `"alice,50,100,beijing"` (diff city within 60)
- `"bob,50,1200,mtv"` (amount > 1000)
Overview: This question evaluates string parsing, temporal reasoning, and algorithmic efficiency by requiring identification of transactions that exceed a numeric threshold or violate cross-city time-window constraints in already time-sorted input; it tests knowledge in Coding & Algorithms with emphasis on algorithm design and data-structure use for time-window processing. It is commonly asked because it measures the ability to process ordered or streaming data while meeting a linear-time complexity target, reflecting practical implementation and algorithmic problem-solving skills rather than purely theoretical concepts.
Community answers
Answer by prateeksinghiit99
Parse each transaction string into a structured object to easily check conditions. Use a hash map grouping transactions by person (name). For each new transaction, check if the amount exceeds 1000, and iterate through all previous transactions of the same person to flag invalid pairs that occur in different cities within 60 minutes.
class Solution {
public:
class Transaction{
public:
string name;
int time;
int amount;
string city;
bool isValid;
string transaction_string;
Transaction(string transaction_string){
stringstream ss(transaction_string);
string cur;
vector parts;
while(getline(ss, cur, ',' )){
parts.push_back(cur);
}
this->name = parts[0];
this->time = stoi(parts[1]);
this->amount = stoi(parts[2]);
this->city = parts[3];
this->isValid = true;
this->transaction_string = transaction_string;
}
};
vector invalidTransactions(vector& transactions) {
unordered_map> person_transactions_map;
for(string transaction : transactions){
Transaction* cur = new Transaction(transaction);
if(cur->amount > 1000)
cur->isValid = false;
for(Transaction* t : person_transactions_map[cur->name]){
if((t->city != cur->city) && (abs(t->time - cur->time) <= 60)){
t->isValid = false;
cur->isValid = false;
}
}
person_transactions_map[cur->name].push_back(cur);
}
vector ans;
for(auto entry : person_transactions_map){
for(Transaction* t : entry.second){
if(!t->isValid)
ans.push_back(t->transaction_string);
}
}
return ans;
}
};
https://leetcode.com/problems/invalid-transactions/
Complexity
Time Comple