unknown Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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");
}
- goyalshub February 16, 2019