## Amazon Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
5
of 5 vote

To prevent the deadlock, could we define an order for the account ID or the account itself, make sure it is transitive, means, Order(A)>Order(B), Order(B)>Order(C), ==> Order(A)>Order(C), and Order(A)==Order(B) ==> A==B. Then you can lock each Accounts following their orders.

Comment hidden because of low score. Click to expand.
0

Can you put that up in code? Not sure what you mean by order here.

Comment hidden because of low score. Click to expand.
1
of 1 vote

When i am thinking about the order of each Account, I suppose there is some unique Identifier for each account, and normally it is account number. Account Number usually is a string of numbers, people could implement a function into an U64 value, and then synchronize each account according to order of this value. For example, you lock account with bigger account number first. the lock smaller account number later. If the account number in U64 form will not repeat, then it will not form a loop of lock.

Comment hidden because of low score. Click to expand.
0

When you acquire multiple resources, deadlock prevention requires that each entity acquire the locks in the same order. So, the solution is to try to acquire the locks in order; if any one lock is not acquired, release all the locks and circle back. Then, there is no deadlock.

Comment hidden because of low score. Click to expand.
0

@Venkat the problem with synchronizing on the accounts is one caller may be transferring from account A to B while another is transferring from B to A. In this case they will be locking in reverse order and a deadlock can occur.

Unlocking and circling back can just cause the same problem to happen over and over.

Comment hidden because of low score. Click to expand.
0

@Barry, Vekat is saying that you should only acquire locks in a predefined order (such as largest account number first).

For example, let A = 1 and B = 2. Then if you have transfer(A, B) and transfer (B, A) they will both attempt to lock B and then A (since 2 > 1) - not lock based on the order of the parameters which is the naive implementation. This way, they cannot deadlock.

Comment hidden because of low score. Click to expand.
0

@jay Good point. However in this particular case I might still lock the critical block because the code within is extremely fast.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Reference: Java Concurrency in Practice, pg: 209

The answer to the 3rd part of the question is...inducing a lock ordering to avoid deadlock.

int fromHash = System.identityHashCode(a1)
int toHash = System.identityHashCode(a2)

if(fromHash < toHash){
synchronized(a1){
synchronized(a2){
.... swap amounts
}
}
}

else if(fromHash > toHash){
synchronized(a2){
synchronized(a1){
.... swap amounts
}
}
}

else{
synchronized(tieLock){
synchronized(a1){
synchronized(a2){
.... swap amounts
}
}
}
}

Comment hidden because of low score. Click to expand.
0

This is basically the same as the solution given above, except you seem to have a tieLock which is pointless in this situation, because that would only be used in the case where you are swapping the account with itself, which should never happen.

Comment hidden because of low score. Click to expand.
0

private static final final Object tieLock = new Object();

In the rare case that two objects have the same hash code, we must use an arbitrary means of ordering the lock acquisitions, and this reintroduces the possibility of deadlock.

Don't just agree with my comment.. first go through the section 10.1.2 Dynamic lock order deadlocks from ref: Java concurrency in Practice. it will be clear on why we need a tieLock & hashcode

Comment hidden because of low score. Click to expand.
-1
of 1 vote

"In the rare case that two objects have the same hash code" translates to "in the rare cases the accounts are the same" (assuming you have a good non-colliding hash). Swapping the balance from A to A makes no sense: if the objects have the same hash, then don't do any swapping, just return. That is why there is no need for a tieLock.

What did I miss?

(Don't worry, I won't 'just agree with your comment' ;-))

Comment hidden because of low score. Click to expand.
0
of 2 vote

Don't synchronize the entire method, just the critical block:

``````Public void TransferAccount(AccountID  id1, AccountID id2){
Account a1 = id1.GetAccount();
Account a2 = id2.GetAccount();

//Swap amounts.
synchronized (this) {
// This section should execute very quickly and affect performance very little
Temp = a1.Balance;
a1.Balance = a2.Balance;
a2.Balance = Temp;
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

This code doesn't scale - if you have to complete 1,000 transfers per second on all different accounts, each and every one of the transfers will be executed serially despite the fact they would never overlap.

Comment hidden because of low score. Click to expand.
0

@jay You're right. Sequential locking is the way to go.

Comment hidden because of low score. Click to expand.
0
of 0 vote

In a banking scenario, you often have these conditions:

1) Individual accounts have very little activity.
2) Accessing accounts has very high latency.

A small problem to avoid is the race where the same account is being incremented/decrement at the exact same millisecond. This can be handled with a simple mutex.

The bigger problem is that additions/subtractions to an account can't actually be committed until the remote account confirms the trade.

From a practical standpoint, the bank wants to err on the side of rejecting transactions prematurely. In other words, it wants to avoid ever promising funds from an account that has uncommitted credits, but it is also wants to avoid promising funds where provisional debits would lessen the balance upon commit.

So let's say Alice agrees to transfer \$100 to Bob's account, and the transaction is initiated from a data center remote to both banks. The financial soundness of the transaction only hinges on Alice having sufficient funds in her account, so the remote data center notifies Alice's bank of the desired transfer. If Alice's provisional balance is too low, the transaction is immediately rejected. Otherwise, her available balance is immediately debited, and you make sure the transaction can be committed on Bob's end (i.e. his account is active, the network is available, etc.). At this point, the transaction is sound from a financial standpoint, but you can't commit it until Bob eventually gets the money in his bank. So, then you post the transfer to Bob's account, and if he confirms it, you then commit the transfer on Alice's end.

Remember that I said that individual accounts have very little activity, so for each account, you can inexpensively manage a data structure of all the uncommitted transfers. In some cases uncommitted transfers will be explicitly rolled back by the other party, but you also have to account for data failures, so you will have expiration logic. Here, you need to be very careful managing funds availability. Alice's bank can't release funds for her until it's certain that Bob hasn't been credited. On the other hand, Bob's bank can roll back his credit after a timeout.

Asking this problem in terms of Java is kind of contrived, because this is really more of a systems engineering question than a coding question. With a single data center, you would be more likely to using a locking model than a phased commit model, but bank transactions typically involve lots of latency between banks.

Comment hidden because of low score. Click to expand.
0

@showell30@yahoo.com Your solution is extremely robust but I think they were looking for a fix to the given Java class rather than the design for a large distributed banking system, don't you?

Comment hidden because of low score. Click to expand.
1
of 1 vote

Like I said, I think the problem is a bit contrived. For a really simple use case, it's probably more than sufficient to simply synchronize TransferAccount, as you're probably gonna have bottlenecks elsewhere. And as soon as you start introducing real world problems like connecting to databases that might be down, etc., the problem gets more complex than simply ordering locks.

But you're right, I'm a little off topic. :) I just upvoted the lock ordering solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void TransferAccount(AccountID  id1, AccountID id2)
{
//The idea is not to use the exclusive lock simultaneously which can cause deadlock.
Account a1 = id1.GetAccount();
Account a2 = id2.GetAccount();

//Get an exclusive lock on id1 and not so exclusive(read on id2 - will make sure that id2 value doesnt change and lock can be held by multiple threads.)
id1.writeLock().lock();
temp = a1.getBalance();
a1.Balance = a2.Balance;
id1.writeLock().unlock();

//Get exclusive lock on id2 to write to it.
id2.writeLock().lock();
a2.Balance = temp;
id2.writeLock().unlock();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void TransferAccount(AccountID  id1, AccountID id2)
{
//The idea is not to get the exclusve lock which can cause deadlock.
Account a1 = id1.GetAccount();
Account a2 = id2.GetAccount();

//Get an exclusive lock on id1 and not so exclusive(read on id2 - will make sure that id2 value doesnt change and lock can be held by multiple threads.)
id1.writeLock().lock();
temp = a1.getBalance();
a1.Balance = a2.Balance;
id1.writeLock().unlock();

//Get exclusive lock on id2 to write to it.
id2.writeLock().lock();
a2.Balance = temp;
id2.writeLock().unlock();
}``````

Comment hidden because of low score. Click to expand.
0

Isn't there a race condition between releasing id2's read lock and opening id2's write lock? During that time somebody else could adjust a2's balance, only to have it wiped out by the assignment to temp.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ok so you don’t want to lock around the entire method since AccountID.GetAccount() is external code and you have no idea what it is doing. You don’t want to lock on the Ids or the Accounts for the same reason they are coming from elsewhere and may or may not be the same instance every time the method is called. If they are not the same instance every time then your locking does not work and you get straight into the locked code twice if lock on them. We only want to lock around code we have complete control of.

If we keep a collection of accounts that we are currently working on then we can use that to make sure that we do not try the same account twice at the same time. We can also then do our checks for both accounts within one lock.

``````//make a hash set
private HashSet<AccountID> m_CheckedOutAccounts = new HashSet<AccountID>();
// create lock object
private object m_Lock = new object();

public bool TryCheckoutAccounts(AccountID one, AccountID two)
{
// take lock
lock(m_Lock)
{
// if m_CheckoutOutAccounts does not contain one and two
bool accountsAvailable = !m_CheckedOutAccounts.Contains(one) && !m_CheckedOutAccounts.Contains(two);
if(accountsAvailable )
{
// add one and two to m_CheckedOutAccounts
// end if
}
// return true if accounts were added otherwise false
return accountsAvailable;
// end lock
}
}

public void FreeAccounts(AccountID one, AccountID two)
{
//take lock
lock(m_Lock)
{
// remove one and tow from m_CheckedOutAccounts
m_CheckedOutAccounts.Remove(one);
m_CheckedOutAccounts.Remove(two);
// end lock
}
}
public void TransferAccount(AccountID  id1, AccountID id2)
{
// while the accounts are not checked out
while(!TryCheckoutAccounts(id1, id2))
{
// wait for monitor use a timeout just incase
// this could just as easilly work without the monitor it is just a bit nicer on the cpu
Monitor.Wait(this, 1000);
// end while
}

Account a1 = id1.GetAccount();
Account a2 = id2.GetAccount();

//Swap amounts.

Temp = a1.Balance;
a1.Balance = a2.Balance;
a2.Balance = Temp;

FreeAccounts(id1, id2);
// pulse monitor
Monitor.Pulse(this);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Thank you for posting this problem!! It pushed me to read about alternatives for using locks.

For situations where you need good scalability with respect to the number of threads and the 'size' of the critical section, using a lock is not the correct way to go.

Using wait-free and lock-free approach may help alleviate the problem here. Use Compare And Swap (CAS) or its variants. Since I am still learning about CAS and it use, here are some pointers to help you guys out. [ibm].com/developerworks/library/j-jtp11234/]
[http:][//audidude][.com/?p=363]

Java has a .util.concurrency.atomic package provides support for wait-free and lock-free approaches.
I will post out a solution as soon as I get a grip on the CAS idea and its likes.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Account {

private Lock balanceLock;
private double balance;

public Account()
{
balanceLock = new ReentrantLock();
}

public synchronized setAccount(double newBal)
{
balance = newBal;
}

public synchronized double getBalance()
{
return balance;
}

}

public void TransferAccount(AccountID  id1, AccountID id2){
Account a1 = id1.GetAccount();
Account a2 = id2.GetAccount();

//Swap amounts.

double temp = a1.getBalance();
a1.setBalance(a2.getBalance());
/**  will get a2 balance until synchronization ends, then will run a1.setBalance() **/
double temp2 = a2.getBalance(); // if a2.getBalance() as a parameter causes deadlock, but it shouldn't
a2.setBalance(temp);
}``````

Comment hidden because of low score. Click to expand.
0

``````//Didn't use the actual lock methodology, so here's another account class

class Account {

private Lock balanceLock;
private double balance;

public Account()
{
balanceLock = new ReentrantLock();
}

public void setAccount(double newBal)
{
balanceLock.lock();
try
{
balance = newBal;
}
catch(Exception e){
balanceLock.signalAll();
}
finally
{
balanceLock.unlock();
}
}

public double getBalance()
{
double toReturn = 0.0;
balanceLock.lock();
try
{
toReturn = balance;
}
catch(Exception e){
balanceLock.signalAll();
}
finally
{
balanceLock.unlock();
return balance;
}
}

}

/** then make the transfer as the other one did above **/``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Are these questions asked during the interview for SDE internship or just SDE full-time job?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there are anyway two read and write operations in one atomic process, so it is obviously not CAS, and also can't be solved by the way ConcurrentHashMap and AtomicXXX did.
If those two accounts have the reference pointing to the same object like user, we may use user object for locking, otherwise I did not figure out a high efficient way to do it.

Comment hidden because of low score. Click to expand.
-1
of 3 vote

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.