Leetcode: Invalid Transactions

 

This question is asked often at Bloomberg. The transaction is invalid if the amount exceeds $1,000 or it occurs within 60 minutes of another transaction with the same name in a different city. 

You are given an array of strings where transactions consist of comma-separated values representing the name, time, amount, and city of the transaction. 

We want to return the lists of transactions that are possibly invalid. 

Example 1:

Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]

Output: ["alice,20,800,mtv","alice,50,100,beijing"]

Explanation: The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.

Example 2:

Input: transactions = ["alice,20,800,mtv","alice,50,1200,mtv"]

Output: ["alice,50,1200,mtv"]

Example 3:

Input: transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]

Output: ["bob,50,1200,mtv"]

 

Constraints:

transactions.length <= 1000

Each transactions[i] takes the form "{name},{time},{amount},{city}"

Each {name} and {city} consist of lowercase English letters, and have lengths between 1 and 10.

Each {time} consists of digits and represents an integer between 0 and 1000.

Each {amount} consists of digits and represents an integer between 0 and 2000.

We want to make a class. The time complexity is O(N^2) or you can define a class called transaction so I can deserialize the comma-separated line into a transaction. 

So we're going to implement a transaction class as a result. 

class Solution {

    public List<String> invalidTransactions(final String[] transactions) {

        //initialize ArrayList and HashMap

        final List<String> invalid = new ArrayList<>();

        final Map<String, List<Transaction>> map = new HashMap<>();

        for(final String transaction : transactions) {

            //go through each transaction

            final Transaction tran = new Transaction(transaction);

            //if hashmap contains a key then add the key value pair with the transaction

            if(map.containsKey(tran.name)) {

                map.get(tran.name).add(tran);

            } else {

                //else, initialize the key value pair and add such transaction.

                final List<Transaction> list = new ArrayList<>();

                list.add(tran);

                map.put(tran.name, list);

            }

        }

        //for every transaction

        for(final String transaction : transactions) {

            final Transaction tran = new Transaction(transaction);

            //add the invalid transactions

            if(!isValid(map.get(tran.name), tran)){

                invalid.add(transaction);

            } 

        }

        return invalid; 

    }

    public boolean isValid(final List<Transaction> transactions, final Transaction transaction) {

        //if there is only 1 transaction with less than 1000 assume it is valid

        if(transactions.size() <= 1 && transaction.amount < 1000) 

            return true;

        //else for all transactions if one of the transactions are invalid then this transaction is invalid as well.

        for(final Transaction tran : transactions) {

            if(transaction.invalidTransaction(tran.city, tran.time)){

                return false;

            }

        }

        //else, just assume the transaction is valid.

        return true;

    }

    class Transaction {

        String name;

        int time;

        int amount;

        String city;

        public Transaction(final String transaction) {

            //parse the name, time, amount, and city from the array. 

            final String[] t= transaction.split(",");

            this.name = t[0];

            this.time = Integer.parseInt(t[1]);

            this.amount = Integer.parseInt(t[2]);

            this.city = t[3];

        }

        public boolean invalidTransaction(final String city, final int time) {

        //see if there is over 1,000 dollars or if transactions are within different cities 60 minutes away from each other.

        return invalidAmount() || differentCity(city, time); 

    }

        private boolean differentCity(final String city, final int time) {

        //see if 2 transactions occur within 60 minutes of each other and in different cities and mark these as suspicious. 

        return !this.city.equals(city) && Math.abs(this.time - time) <= 60;

    }

        private boolean invalidAmount() {

            //see if the transaction covers over 1000 dollars

            return this.amount > 1000;

    }

    }

}