05 August 2008
A transaction is possibly invalid if:
the amount exceeds $1000, or; if it occurs within (and including) 60 minutes of another transaction with the same name in a different city. You are given an array of strings transaction where transactions[i] consists of comma-separated values representing the name, time (in minutes), amount, and city of the transaction.
Return a list of transactions that are possibly invalid. You may return the answer in any order.
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} consist of digits, and represent an integer between 0 and 1000. Each {amount} consist of digits, and represent an integer between 0 and 2000.
Map - In this solution a map is used to keep track of transactions with the same name, and a property on the transacton class keeps track of the invalid ones
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
private class Transaction {
public string name;
public int time;
public int amount;
public string city;
public string line;
public bool isInvalid = false;
public Transaction(string line) {
// Parse line contents
var parts = line.Split(",");
name = parts[0];
time = int.Parse(parts[1]);
amount = int.Parse(parts[2]);
city = parts[3];
// Save line contents
this.line = line;
}
}
public IList<string> InvalidTransactions(string[] transactions) {
var result = new List<string>();
var map = new Dictionary<string, List<Transaction>>();
// Save transactions into an object
foreach (var line in transactions) {
// Save transaction into an object
var current = new Transaction(line);
// Check if the current transaction amount exceeds 1000
if (current.amount > 1000) {
current.isInvalid = true;
result.Add(current.line);
}
if (!map.ContainsKey(current.name)) {
map[current.name] = new List<Transaction>() {current};
} else {
// Look for other transaction that occurs within 60 minutes
var transactionList = map[current.name];
// Go through each transaction looking for invalid ones
foreach (var search in transactionList) {
// Check if transaction with same name in different city occurs within 60 minutes
if (current.city != search.city && Math.Abs(current.time - search.time) <= 60) {
if (!search.isInvalid) {
search.isInvalid = true;
result.Add(search.line);
}
if (!current.isInvalid) {
current.isInvalid = true;
result.Add(current.line);
}
}
}
// Add current transaction to map
map[current.name].Add(current);
}
}
return result;
}
}
Map & bool array - This solution is similar to the one above, except a bool array keeps track of the invalid transactions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
private class Transaction {
public int id;
public string name;
public int time;
public int amount;
public string city;
public Transaction(int id, string line) {
this.id = id;
// Parse line contents
var parts = line.Split(",");
name = parts[0];
time = int.Parse(parts[1]);
amount = int.Parse(parts[2]);
city = parts[3];
}
}
public IList<string> InvalidTransactions(string[] transactions) {
var map = new Dictionary<string, List<Transaction>>();
var invalid = new bool[transactions.Length];
// Save transactions into an object
for (int index = 0; index < transactions.Length; ++index) {
// Save transactions into an object
var current = new Transaction(index, transactions[index]);
// Check if the current transaction amount exceeds 1000
if (current.amount > 1000) {
invalid[current.id] = true;
}
if (!map.ContainsKey(current.name)) {
map[current.name] = new List<Transaction>() {current};
} else {
// Look for other transaction that occurs within 60 minutes
var transactionList = map[current.name];
// Go through each transaction looking for invalid ones
foreach (var search in transactionList) {
// Check if transaction with same name in different city occurs within 60 minutes
if (current.city != search.city && Math.Abs(current.time - search.time) <= 60) {
invalid[current.id] = true;
invalid[search.id] = true;
}
}
// Add current transaction to map
map[current.name].Add(current);
}
}
// Save invalid transactions to result
var result = new List<string>();
for (int index = 0; index < invalid.Length; ++index) {
if (invalid[index]) {
result.Add(transactions[index]);
}
}
return result;
}
}
Using Basic Loops
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
private class Transaction {
public string name;
public int time;
public int amount;
public string city;
public string line;
public bool isInvalid = false;
public Transaction(string line) {
// Parse line contents
var parts = line.Split(",");
name = parts[0];
time = int.Parse(parts[1]);
amount = int.Parse(parts[2]);
city = parts[3];
// Save line contents
this.line = line;
}
}
public IList<string> InvalidTransactions(string[] transactions) {
var transactionList = new List<Transaction>();
// Save transactions into an object
foreach (var line in transactions) {
transactionList.Add(new Transaction(line));
}
// Go through each transaction looking for invalid ones
for (int index = 0; index < transactionList.Count; ++index) {
// Get the current transaction
var current = transactionList[index];
// Current transaction already marked as invalid
if (current.isInvalid) {
continue;
}
// Check if the current transaction amount exceeds 1000
if (current.amount > 1000) {
current.isInvalid = true;
}
// Look for other transaction that occurs within 60 minutes
for (int searchIndex = 0; searchIndex < transactionList.Count; ++searchIndex) {
// Skip current transaction
if (index == searchIndex) {
continue;
}
// Get the search transaction
var search = transactionList[searchIndex];
// Check if transaction with same name in different city occurs within 60 minutes
if (current.name == search.name && current.city != search.city && Math.Abs(current.time - search.time) <= 60) {
current.isInvalid = true;
search.isInvalid = true;
}
}
}
// Save invalid transactions to result
var result = new List<string>();
foreach (var transaction in transactionList) {
if (transaction.isInvalid) {
result.Add(transaction.line);
}
}
return result;
}
}