Amazon Interview Question Software Developers
Country: United States
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);
return total;
}
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)
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;
count+= addendum;
}
return count;
}
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;
count+= addendum;
}
return count;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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.
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);
}
}
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))
return totalCount
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))
return totalCount
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.
I would solve this problem as below:
- Kiran Tirupati May 12, 2016We 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.