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)
Quick Answer: 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.