Invalid Transactions

Moderate

0/80

Average time to solve is 30m

Contributed by

14 upvotes

Asked in company

Problem statement

You are the manager of a bank. You have seen the database of the bank and have seen ‘N’ transactions. Each transaction has a customer id, transaction amount, time of the transaction, and the city code of the transaction. Now a transaction is invalid if the transaction amount exceeds Rs 1000 or the transaction occurs within 60 minutes of another transaction with the same customer id but in a different city. Find the number of invalid transactions.

Example:-

N = 3
TRANSACTIONS = [(1,20,100,1),(2,30,24,1),(1,60,90,2)]  [For the first transaction, customer_id is 1, the time of transaction is 20 minutes, the amount of transaction is Rs 100 and the city code where the transaction took place is 1, so the tuples are in the form (customer_id, time_fo_transaction, amount_of_transaction, city_code)].

ANSWER:- The invalid transactions are [(1,20,100,1),(1,60,90,2)] as the transactions are under the same customer id and have occurred in different cities within 60 minutes

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of every test case contains an integer ‘N’ denoting the number of transactions.

The next ‘N’ lines of every test case contain four integers ‘CUST_ID’, ‘TIME’, ‘AMOUNT’, ‘CITY’ denoting the customer id, time of the transaction, amount of transaction, and the city code of transaction respectively of the ith transaction.

Output Format :

For each test case, return the invalid transactions from the list of transactions.

The output of each test case should be printed in a separate line.

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10
1 <= N <= 10^3
1 <= CUST_ID <=10^9
1 <= TIME <= 10^9
1 <= AMOUNT <= 10^9
1 <= CITY <= 10^9

Time Limit = 1 sec

Sample Input 1 :

2
2
1 20 800 1
1 30 1200 1
2
2 30 1500 1
1 20 500 2

Sample Output 1 :

1 30 1200 1
2 30 1500 1

Explanation for Sample Output 1 :

In the first test case, the second transaction is invalid because the transaction amount exceeds Rs 1000. 
 In the first test case, the first transaction is invalid because the transaction amount exceeds Rs 1000.

Sample Input 2 :

1
2
1 30 1500 1
1 20 500 2

Sample Output 2 :

1 30 1500 1
1 20 500 2

Hint 1

Hint 2

Check every pair of transactions for validity.

Approaches (2)

Approach 1

Approach 2

Brute Force

Check if a transaction is valid by comparing it with all other transactions and if it’s invalid, add the transaction to the answer.

Algorithm:-

Initialize an array named ANS to store the final answer.
Iterate from 0 to N.(Let’s say the iterator is i)
1. Iterate from 0 to N.(Let’s say the iterator be j).
  1. If the time difference between the ith transaction and the jth transaction is under 60 minutes and the transactions are in different cities, add the transaction to ANS.
  2. If the amount of the jth transaction exceeds Rs 1000, add the transaction to ANS.
Return ANS.

Time Complexity

O(N^2), where N is the number of transactions.

We are iterating through the transactions in two nested loops, so the time complexity is O(N^2).

Space Complexity

O(N), where N is the number of transactions.

We are using an array of size ‘N’ to store the invalid transactions, so the space complexity is O(N).

(100% EXP penalty)

Invalid Transactions

Console