CareerCup

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);

	}

}

I think that the problem can be solved easily converting the array in a graph where timestamps are the weight of the arcs. To find if a transaction is valid you can simply check if there is a path between two elements with growing costs of arcs.

import java.util.*;

public class ValidTransactions {

    public static void main(String[] args) {
        Transaction[] transArray = new Transaction[10];
        transArray[0] = new Transaction("A", "B", 0);
        transArray[1] = new Transaction("A", "C", 1);
        transArray[2] = new Transaction("B", "C", 2);
        transArray[3] = new Transaction("D", "A", 1);
        transArray[4] = new Transaction("B", "C", 1);
        transArray[5] = new Transaction("C", "D", 2);
        transArray[6] = new Transaction("B", "C", 3);
        transArray[7] = new Transaction("B", "D", 3);
        transArray[8] = new Transaction("C", "D", 2);
        transArray[9] = new Transaction("A", "C", 2);

        HashMap<String, List<Transaction>> transactions = createGraph(transArray);

        System.out.println("A->D = " + isTransactionValid(transactions, "A", "D"));
        System.out.println("A->C = " + isTransactionValid(transactions, "A", "C"));
        System.out.println("C->B = " + isTransactionValid(transactions, "C", "B"));
    }

    public static boolean isTransactionValid(HashMap<String, List<Transaction>> transactions, String sender,
            String receiver) {
        return isTransactionValid(transactions, sender, receiver, 0);
    }

    public static boolean isTransactionValid(HashMap<String, List<Transaction>> transactions, String sender,
            String receiver, int timestamp) {
        if (sender.equals(receiver)) {
            return true;
        } else {
            if (transactions.containsKey(sender)) {
                List<Transaction> boundary = transactions.get(sender);
                System.out.println("sender: " + sender + " - receiver: " + receiver);
                for (Transaction t : boundary) {
                    if (t.timestamp > timestamp
                            && isTransactionValid(transactions, t.receiver, receiver, t.timestamp)) {
                        return true;
                    }

                }
            }

            return false;
        }
    }

    public static HashMap<String, List<Transaction>> createGraph(Transaction[] transactions) {
        HashMap<String, List<Transaction>> graph = new HashMap<>();

        for (Transaction t : transactions) {
            List<Transaction> receivers = null;
            if (graph.containsKey(t.sender)) {
                receivers = graph.get(t.sender);
            } else {
                receivers = new LinkedList<>();
                graph.put(t.sender, receivers);
            }
            receivers.add(t);
        }
        return graph;
    }

    protected static class Transaction {
        String sender;
        String receiver;
        int timestamp;

        public Transaction(String s, String r, int t) {
            sender = s;
            receiver = r;
            timestamp = t;
        }
    }
}

public class Transaction {
String sender = "";
String receiver = "";
int timestamp = 0;
Transaction(String sender, String receiver, int timestamp) {
this.sender= sender;
this.receiver = receiver;
this.timestamp = timestamp;
}

public static boolean findIfTransactionValid(Map<String, Transaction> transactions, String sender, String receiver) {
if (!transactions.containsKey(sender)) {
return false;
}
Transaction sender1 = transactions.get(sender);
String receiver1 = sender1.receiver;
if (receiver1.equals(receiver)) {
return true;
}
if (!transactions.containsKey(receiver1)) {
return false;
}
Transaction sender2 = transactions.get(receiver1);
if (sender2.timestamp <= sender1.timestamp) {
return false;
}
return findIfTransactionValid(transactions, receiver1, receiver);

}
public static void main(String[] args) {
Map<String, Transaction> transaction = new HashMap<String, Transaction>();
transaction.put("A", new Transaction("A", "B", 0));
transaction.put("B", new Transaction("B", "C", 1));
transaction.put("C", new Transaction("C", "F", 0));
System.out.println(findIfTransactionValid(transaction, "A", "C"));
System.out.println(findIfTransactionValid(transaction, "A", "F"));
}
}

public class Transaction {
String sender = "";
String receiver = "";
int timestamp = 0;
Transaction(String sender, String receiver, int timestamp) {
this.sender= sender;
this.receiver = receiver;
this.timestamp = timestamp;
}

public static boolean findIfTransactionValid(Map<String, Transaction> transactions, String sender, String receiver) {
if (!transactions.containsKey(sender)) {
return false;
}
Transaction sender1 = transactions.get(sender);
String receiver1 = sender1.receiver;
if (receiver1.equals(receiver)) {
return true;
}
if (!transactions.containsKey(receiver1)) {
return false;
}
Transaction sender2 = transactions.get(receiver1);
if (sender2.timestamp <= sender1.timestamp) {
return false;
}
return findIfTransactionValid(transactions, receiver1, receiver);

}
public static void main(String[] args) {
Map<String, Transaction> transaction = new HashMap<String, Transaction>();
transaction.put("A", new Transaction("A", "B", 0));
transaction.put("B", new Transaction("B", "C", 1));
transaction.put("C", new Transaction("C", "F", 0));
System.out.println(findIfTransactionValid(transaction, "A", "C"));
System.out.println(findIfTransactionValid(transaction, "A", "F"));
}
}

#include <iostream>
#include <string>
#include <unordered_map>
#include <list>
#include <queue>

using namespace std;
unordered_map < string, list<pair<string, int>>> g;
class Transaction
{
public:
Transaction(string s, string r, int t)
{
snd = s;
recv = r;
timestamp = t;
}
Transaction()
{

}
string getSnd()
{
return snd;
}
string getRecv()
{
return recv;
}
int getTimeStamp()
{
return timestamp;
}
private:
string snd;
string recv;
int timestamp;
};

void insertInGraph(Transaction &t)
{
string s = t.getSnd();
string r = t.getRecv();
int transaction = t.getTimeStamp();
g[s].push_back(make_pair(r, transaction));
}

bool traverseGraph(string s, string r)
{
if (s.compare(r) == 0)
return true;
auto itr = g.find(s);
if (itr == g.end())
return false;
queue<string> q;
q.push(s);
int total_dist = 0;
int dist = 0;
while (!q.empty())
{
string node = q.front();
q.pop();
list<pair<string,int>> l = g[node];
for (auto itr = l.begin(); itr != l.end(); ++itr)
{
pair<string,int> p = *itr;
string s = p.first;
int d = p.second;
if ((d > dist) && (s.compare(r) == 0))
return false;
else
{
if ((d <= dist) && (s.compare(r) == 0))
return true;
}
q.push(s);
dist += d;
}
}
}

int main()
{
Transaction tran_list[7];

Transaction t1("A", "B", 0);
tran_list[0] = t1;

Transaction t2("B", "C", 1);
tran_list[1] = t2;

Transaction t3("B", "D", 2);
tran_list[2] = t3;

Transaction t4("D", "E", 1);
tran_list[3] = t4;

Transaction t5("D", "F", 0);
tran_list[4] = t5;

Transaction t6("D", "Z", 5);
tran_list[5] = t6;

Transaction t7("F", "Z", 5);
tran_list[6] = t7;
for (int i = 0; i < 7; ++i)
insertInGraph(tran_list[i]);
cout<<traverseGraph("A", "D");
}