## Amazon Interview Question for Software Developers

Country: India

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

A greedy approach can work here. The idea is that we keep track of how many incomplete stacks there are to the left of position i (shortage array). Note that shortage[-1] - shortage[i] also gives us the information on the number of incomplete stacks to the right of position i. Then for every stack where we have some extra coins (>1) we calculate how many needs to be moved left / right based on our knowledge of incomplete stacks:

``````def findMinMovesToRedistributeCoins(coins):
shortage = [0 for _ in coins]
missing = 0
for i,x in enumerate(coins):
if not x:
missing += 1
shortage[i] = missing
ans = 0
while shortage[-1]:
for i,x in enumerate(coins):
extra = x - 1
if extra > 0 and i > 0 and shortage[i-1] > 0:
# move stack left
d = min(extra, shortage[i-1])
coins[i] -= d
if not coins[i-1]:
for j in range(i-1, len(coins)):
shortage[j] -= 1
coins[i-1] += d
# print coins
ans += 1
extra -= d
if extra > 0 and i+1<len(coins) and shortage[-1] != shortage[i]:
# move stack right
d = min(extra, shortage[-1] - shortage[i])
coins[i] -= d
if not coins[i+1]:
for j in range(i+1, len(coins)):
shortage[j] -= 1
coins[i+1] += d
# print coins
ans += 1
return ans``````

Test driver:

``````print findMinMovesToRedistributeCoins([0, 2])
[1, 1]
1

print findMinMovesToRedistributeCoins([0, 3, 1, 0, 3, 0, 0])
[1, 2, 1, 0, 3, 0, 0]
[1, 1, 2, 0, 3, 0, 0]
[1, 1, 1, 1, 3, 0, 0]
[1, 1, 1, 1, 1, 2, 0]
[1, 1, 1, 1, 1, 1, 1]
5``````

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

public static int moves(int COINS[]) {
int moves = 0;
for(int i =0; i < COINS.length-1; i++) {

if(COINS[i] > 0 && COINS[i+1] > 0) {
moves++;
}

if(COINS[i] == 0) {
moves++;
}
}

if(COINS[COINS.length-1] == 0) {
moves++;
}
return moves;
}

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

lavde chutiye

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

``````const coinSack = {};
coinSack.stacks = [0,1,2,3,0,0,25,2,1,0];
coinSack.getStackCount = () => coinSack.stacks.length;
coinSack.getCoinCount = () => coinSack.stacks.reduce((total, amount) => total + amount );
coinSack.getStackAverageCoinCount = () => (coinSack.getCoinCount() / coinSack.stacks.length).toFixed();
coinSack.calcDistributeCoinsTransactionCount = (minimumCoinsPerStack) => {

//check to see if there is enough coins to distribute based on minimumCoins per stack
if ((coinSack.getStackCount() * minimumCoinsPerStack) > coinSack.getCoinCount()) {
console.log('Not enough coins to distribute.');
return;
}

return coinSack.stacks.filter(stack => stack < minimumCoinsPerStack).length;
};

console.log(coinSack.calcDistributeCoinsTransactionCount(2));

});``````

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.