goyalshub
BAN USER
- 2
0of 0 votes
AnswersI am given an array of Transactions in a ledger. A Transaction object has three things.
- goyalshub in United States
1. Sender (which means who started this transaction)
2. Receiver (means who is the destination of transaction)
3. Timestamp (at what time this transaction was executed)
Now I need to write a method findIfTransactionIsValid() which will have the array of all transactions, one sender, one receiver. A transaction is valid is following cases:
1. if sender and receiver are same
2. The timestamp should be increasing (what I mean here is if A -> B happens at Time 2 and B-> C happens at Time 1, then A->C is not a valid transaction, however if B -> C happens at Time 3 then A--> C is a valid transaction)
Example:
Transaction
{
Sender;
Receiver;
Timestamp;
}
Example: [T is timestamp here]
A -> B (T=0)
B -> C (T=1)
C -> F (T=0)
findIfTransactionIsValid(A, C) -> this should return true
findIfTransactionIsValid(B,F) -> false (time is backwards)
If the question is still not clear, please see the solution I wrote. I have written a recursive solution and is working but I am seeing help to improve the solution.| Report Duplicate | Flag | PURGE
unknown Software Engineer Algorithm
public class transaction_ledger {
public static class Transaction {
char sender;
char receiver;
int timestamp;
Transaction(char s, char r, int t) {
this.sender = s;
this.receiver = r;
this.timestamp = t;
}
}
public static boolean findIfTransactionIsValid(Transaction[] arr, char start, char end) {
if (start == end)
return true;
sortTransactions(arr);
return findHelper(arr, start, end, 0);
}
public static boolean findHelper(Transaction[] arr, char start, char end, int index) {
if (index >= arr.length)
return false;
for (int i = index; i < arr.length; i++) {
Transaction T = arr[i];
if (T.sender == start) {
if (T.receiver == end)
return true;
else {
return findHelper(arr, T.receiver, end, index++) || findHelper(arr, T.sender, end, index++);
}
}
}
return false;
}
public static Transaction[] sortTransactions(Transaction[] arr) {
Arrays.sort(arr, (t1, t2) -> t1.timestamp - t2.timestamp);
return arr;
}
public static void main(String[] args) {
Transaction[] tran_list = new Transaction[7];
Transaction t1 = new Transaction('A', 'B', 0);
tran_list[0] = t1;
Transaction t2 = new Transaction('B', 'C', 1);
tran_list[6] = t2;
Transaction t3 = new Transaction('B', 'D', 2);
tran_list[2] = t3;
Transaction t4 = new Transaction('D', 'E', 1);
tran_list[3] = t4;
Transaction t5 = new Transaction('D', 'F', 0);
tran_list[4] = t5;
Transaction t6 = new Transaction('D', 'Z', 5);
tran_list[5] = t6;
Transaction t7 = new Transaction('F', 'Z', 5);
tran_list[1] = t7;
// sortTransactions(tran_list);
long start = System.currentTimeMillis();
System.out.println(findIfTransactionIsValid(tran_list, 'A', 'A'));
System.out.println(findIfTransactionIsValid(tran_list, 'A', 'B'));
System.out.println(findIfTransactionIsValid(tran_list, 'A', 'C'));
System.out.println(findIfTransactionIsValid(tran_list, 'A', 'D'));
System.out.println(findIfTransactionIsValid(tran_list, 'A', 'E'));
System.out.println(findIfTransactionIsValid(tran_list, 'A', 'F'));
System.out.println(findIfTransactionIsValid(tran_list, 'A', 'Z'));
System.out.println(findIfTransactionIsValid(tran_list, 'A', 'T'));
System.out.println(System.currentTimeMillis() - start);
}
}
- 0
Rep
- 0
Repsharonpkarr, None at BT
Hi! My name is Mary. I am a writer for a variety of web and multi-platform applications.I am a ...
- 320
Repbilliejeckley, SEO at Flipkart
Spent 2002-2008 testing the market for spit-takes in Los Angeles, CA. Spent 2001-2004 deploying how to get boyfriend back by ...
This solution seems to be working but I am seeing help to improve efficiency. I think I am making unnecessary recursive calls. Can someone help with a better solution?
- goyalshub February 17, 2019