## Amazon Interview Question for Software Developers

Country: United States

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

I would solve this problem as below:

We need to find an order in releasing prisoners such that, minimum number of gold coins to be used.

Important points to note:-
1.Lets assume all the cells are array indices in P and each prisoner is a value in a cell.
2.When we release a prisoner, i.e., we are actually dividing the main array P into 2 sub arrays, P1 and P2.
3.Choosing the prisoner to release from Q should be such a way that it divides P into P1 and P2 where P1.size ~= P2.size. (I mean mod (P1.size / P2.size) should be greater of all the other possibilities)

This way each time we select any element in Q, it should satisfy the above rule.

By selecting 3 initially forms 2 sub arrays of length 2 and 17 and ratio is 2/17 = .117
By selecting 6 initially forms 2 sub arrays of length 5 and 14 and ratio is 5/14 = .357
By selecting 14 initially forms 2 sub arrays of length 13 and 6 and ratio is 6/13 = .461

So we select 14 to be released first and similarly we will select 6 and then 3.

Each iteration, gold coins used is equal to the sum of P1.size + P2.size

for 3 iterations,
1st iteration, it is 13 + 6 = 19
2nd -> 5 + 7 = 12 and
3rd -> 2 + 2 = 4

one important note is, for each iteration we should select the largest array to be the candidate to divide into 2.

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

My idea is to use recursion, in every recursion I split the number of cells in two equals halves or the most proportional/equal that can be split, in this implementation I chose the prisoner that gives me the the smaller difference between the number of left-right cells;

``````public int GetMinimumBribe(int numCells, int[] pricioners)
{
bool[] used = new bool[pricioners.Length];
return GetMinimumBribe(1, numCells, pricioners, used);
}

private int GetMinimumBribe(int start, int end, int[] pricioners, bool[] used)
{
if (end < start)
return 0;

int minDiff = int.MaxValue;
int index = -1;
for (int i = 0; i < pricioners.Length; i++)
{
int p = pricioners[i];
if (used[i] || p < start && p > end)
continue;

int left = p - start;
int rigth = end - p;
int diff = Math.Abs(rigth - left);
if (diff < minDiff)
{
minDiff = diff;
index = i;
}
}

if (index == -1)
return 0;
used[index] = true;
int total = end - start;;
int n = pricioners[index];

total += GetMinimumBribe(start, n-1, pricioners, used);
total += GetMinimumBribe(n + 1, end, pricioners, used);
}``````

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

O(prisoners_to_be_justified^3 * cells^2) time,
O(prisoners_to_be_justified^2, * cells^2) space
Better rewrite it without recursion in order to avoid stack overflow.

``````def compute_min_coins_helper(justified, first_justified, last_justified, first_cell, last_cell, cache):
if not first_justified < last_justified:
return 0
cache_key = (first_justified, last_justified, first_cell, last_cell)
result = cache.get(cache_key)
if result is not None:
return result
min_coins = None
for justified_idx in xrange(first_justified, last_justified):
prisoner_idx = justified[justified_idx]
coins = (
prisoner_idx - first_cell +
compute_min_coins_helper(justified, first_justified, justified_idx, first_cell, prisoner_idx, cache) +
last_cell - (prisoner_idx + 1) +
compute_min_coins_helper(justified, justified_idx + 1, last_justified, prisoner_idx + 1, last_cell, cache)
)
if min_coins is None or coins < min_coins:
min_coins = coins
cache[cache_key] = min_coins
return min_coins

def compute_min_coins(justified, cells):
return compute_min_coins_helper(
[j - 1 for j in justified],
0, len(justified),
0, cells,
cache={}
)

assert compute_min_coins([1,2,3], 3) == 2
assert compute_min_coins([3], 8) == 7
assert compute_min_coins([3, 6, 14], 20) == 35

import random
cells = 100
justified = random.sample(xrange(1, cells + 1), 50)
compute_min_coins(justified, cells)``````

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

My solution,

``````public static int goldCoins(int cells, int released, int[] cellNum){

boolean[] check = new boolean[cells+1];
int count = 0;

for (int i = 0; i <released ; i++) {
check[cellNum[i]] = true;
int lower = 1;
int upper = check.length -1;
//go left
for (int j = cellNum[i]; j > 0; j--) {
if(check[j]) lower = j;
}
//go right
for(int j = cellNum[i]; j < check.length; j++){
if(check[j]) upper = j;
}
int addendum = upper - lower -1;
}
return count;

}``````

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

My solution in O(n^2), easy to understand.

``````public static int goldCoins(int cells, int released, int[] cellNum){

boolean[] check = new boolean[cells+1];
int count = 0;

for (int i = 0; i <released ; i++) {
check[cellNum[i]] = true;
int lower = 1;
int upper = check.length -1;
//go left
for (int j = cellNum[i]; j > 0; j--) {
if(check[j]) lower = j;
}
//go right
for(int j = cellNum[i]; j < check.length; j++){
if(check[j]) upper = j;
}
int addendum = upper - lower -1;
}
return count;

}``````

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

``````public  static int counttwo(int n){
int count =0;
String arrayLength="";
for (int i = 0; i < n; i++) {
arrayLength=arrayLength+i;
}
String [] countTwoArray = arrayLength.split(String.valueOf('2'));
if(countTwoArray!=null){
char[] array =String.valueOf(n).toCharArray();
for (char i = 0; i < array.length; i++) {
if(array[i]=='2'){
count=count+1;
}
}
count=countTwoArray.length-1+count;
}
return count;
}``````

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

public static int counttwo(int n){
int count =0;
String arrayLength="";
for (int i = 0; i < n; i++) {
arrayLength=arrayLength+i;
}
String [] countTwoArray = arrayLength.split(String.valueOf('2'));
if(countTwoArray!=null){
char[] array =String.valueOf(n).toCharArray();
for (char i = 0; i < array.length; i++) {
if(array[i]=='2'){
count=count+1;
}
}
count=countTwoArray.length-1+count;
}
return count;
}

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

public static int counttwo(int n){
int count =0;
String arrayLength="";
for (int i = 0; i < n; i++) {
arrayLength=arrayLength+i;
}
String [] countTwoArray = arrayLength.split(String.valueOf('2'));
if(countTwoArray!=null){
char[] array =String.valueOf(n).toCharArray();
for (char i = 0; i < array.length; i++) {
if(array[i]=='2'){
count=count+1;
}
}
count=countTwoArray.length-1+count;
}
return count;
}

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

``````public  static int counttwo(int n){
int count =0;
String arrayLength="";
for (int i = 0; i < n; i++) {
arrayLength=arrayLength+i;
}
String [] countTwoArray = arrayLength.split(String.valueOf('2'));
if(countTwoArray!=null){
char[] array =String.valueOf(n).toCharArray();
for (char i = 0; i < array.length; i++) {
if(array[i]=='2'){
count=count+1;
}
}
count=countTwoArray.length-1+count;
}
return count;
}``````

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

This works in O(lg(n)) complexity with the assumption that all prisoners can be bribed for the same value k (k=1).

``````function findMinCoins(numCells, memo) {
if (numCells < 2) {
return 0;
}

if(memo[numCells]) {
return memo[numCells];
}

var mid = Math.ceil(numCells / 2);
var coins = numCells - 1 + findMinCoins(mid, memo);

if (numCells % 2 === 1) {
coins += findMinCoins(mid, memo);
} else {
coins += findMinCoins(mid - 1, memo); // Even numbers have one less cell on the left
}

memo[numCells] = coins;

return coins;
}``````

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

My Idea is to release for the side which results in maximum isolation

``````int findGoldCoinCount(int startIndex, int endIndex, const int *prisoners, int prisonerCount){
int goldCount = endIndex - startIndex - 1;
if(prisonerCount <= 1) {
printf("gold count=%d release %d\n",goldCount, prisoners[0]);
return goldCount;
}
prisonerCount--;
int startDiff = prisoners[0] - startIndex;
int endDiff = endIndex - prisoners[prisonerCount];
if(startDiff > endDiff){
printf("gold count=%d release %d\n",goldCount, prisoners[0]);
goldCount += findGoldCoinCount(prisoners[0]+1, endIndex, prisoners+1, prisonerCount);
} else {
printf("gold count=%d release %d\n",goldCount, prisoners[prisonerCount]);
goldCount += findGoldCoinCount(startIndex, prisoners[prisonerCount]-1, prisoners, prisonerCount);
}
return goldCount;
}``````

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

non recursive version of the same

``````int findGoldCoinCount(int totalPrisonerCount, const int *prisoners, int prisonerCount){
int goldCount = 0;
int startIndex = 0;
int endIndex = totalPrisonerCount;
while(prisonerCount > 0){
goldCount += (endIndex - startIndex - 1);
prisonerCount--;
int startDiff = prisoners[0] - startIndex;
int endDiff = endIndex - prisoners[prisonerCount];
if(startDiff > endDiff){
printf("gold count=%d release %d\n",goldCount, prisoners[0]);
startIndex = prisoners[0]+1;
prisoners++;
} else {
printf("gold count=%d release %d\n",goldCount, prisoners[prisonerCount]);
endIndex = prisoners[prisonerCount]-1;
}
}
return goldCount;
}``````

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

If I've understood the problem correctly, we must release Q prisoners in Q days, that means 1 prisoner a day (at a time) could be a constraint.

Given this, I believe this is a divide and conquer technique.

So if we have 100 prisoners and wish to release 4, then we release the 4th prisoner first, followed be half of 4, 2nd prisoner, followed by half of 2, 1st prisoner, then similar approach on the right sub array.

This maximizes the profit or should I say minimizes the loss.

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

It is a typical dynamic programming question. Use the P and Q together as the key and its minimal case as the value to cache the result. Details: cpluspluslearning-petert.blogspot.co.uk/2016/05/dynamic-programming-min-cost-of.html

Test

``````#include <cassert>
void TestPrisionCellQ()
{
const std::vector<size_t> cells = {0, 1, 2, 3, 4, 5, 6, 7, 8};
{
const std::vector<size_t> releases = { 1 };
assert(MinCostOfReleasingCells(cells, releases) == 8);
}
{
const std::vector<size_t> releases = { 8 };
assert(MinCostOfReleasingCells(cells, releases) == 8);
}
{
const std::vector<size_t> releases = { 1, 6 };
assert(MinCostOfReleasingCells(cells, releases) == 13);
}
{
const std::vector<size_t> releases = { 1, 3 };
assert(MinCostOfReleasingCells(cells, releases) == 10);
}
{
const std::vector<size_t> releases = { 1, 3, 8 };
assert(MinCostOfReleasingCells(cells, releases) == 14);
}
{
const std::vector<size_t> releases = { 1, 3, 5 };
assert(MinCostOfReleasingCells(cells, releases) == 14);
}
{
const std::vector<size_t> releases = { 3, 4, 5 };
assert(MinCostOfReleasingCells(cells, releases) == 12);
}
{
const std::vector<size_t> releases = { 3, 4, 5, 8 };
assert(MinCostOfReleasingCells(cells, releases) == 14);
}
{
const std::vector<size_t> releases = { 0, 3, 4, 5, 8 };
assert(MinCostOfReleasingCells(cells, releases) == 16);
}
}``````

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

``````class Solution(object):
def recursiveSolution(self, start_index, end_index, prisoners):
"""
:type start_index: int
:type end_index: int
:prisoners: list of integers
"""
if len(prisoners) == 1:
return end_index - start_index
if len(prisoners) == 0 or start_index >= end_index:
return 0
totalCount = float("inf")
splitProduct, splitIndex = 0,0
for i,p in enumerate(prisoners): # Determine best split - O(n)
# Determine the prisoners who are in left or right-partitions - O(n)
left_cells, right_cells = prisoners[0:i],prisoners[i+1:]
totalCount =  min(totalCount,(end_index - start_index) +  self.recursiveSolution(start_index,prisoners[i]-1,left_cells) + self.recursiveSolution(prisoners[i]+1,end_index,right_cells))

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

``````class Solution(object):
def recursiveSolution(self, start_index, end_index, prisoners):
"""
:type start_index: int
:type end_index: int
:prisoners: list of integers
"""
if len(prisoners) == 1:
return end_index - start_index
if len(prisoners) == 0 or start_index >= end_index:
return 0
totalCount = float("inf")
splitProduct, splitIndex = 0,0
for i,p in enumerate(prisoners): # Determine best split - O(n)
# Determine the prisoners who are in left or right-partitions - O(n)
left_cells, right_cells = prisoners[0:i],prisoners[i+1:]
totalCount =  min(totalCount,(end_index - start_index) +  self.recursiveSolution(start_index,prisoners[i]-1,left_cells) + self.recursiveSolution(prisoners[i]+1,end_index,right_cells))

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

I think Kiran's approach fails in some cases.
For example, take n=9 prisoners and 3 prisoners to be released are 4,5,6 (1 based indexing)
According to this, answer should be 14 (right?) because initially selecting 5 (as it has the highest ratio = 4/4) and then selecting 4 and 6. Hence, gold coins required are 8+3+3 = 14.

But,
First Selecting 4 (coins required = 8),
then Selecting 6 (coins required = 4),
then Selecting 5 (coins required = 0)
Minimum coins required = 12 should be the answer.

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.