Find invalid transactions in time-sorted input

Q: Find invalid transactions in time-sorted input

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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:

amount > 1000 , or
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)

Find invalid transactions in time-sorted input

Overview

Problem

Requirements

Example

Comments (0)