This is an Amazon interview question for software developer from careercup. Here is the original thead,
"
/*
Prison cell question
In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbors." A wall with a window separates adjacent cells, and neighbors can communicate through that window.
All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbors find out, and each communicates this to his other neighbor. That prisoner passes it on to his other neighbor, and so on until they reach a prisoner with no other neighbor (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.
Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.
Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.
Task: find the minimum amount of gold we need to bribe the prisoners so that the chosen prisoners can be released without causing cell destruction.
Input example:
8 cells, 1 prisoner has to be released. The prisoner to be released is the 3rd one.
|1|2|3|4|5|6|7|8|
7 gold coins
another example:
20 cells, 3 prisoners to be released: 3, 6 and 14
|1|2| |4|5| |7|8|9|10|11|12|13| |15|16|17|18|19|20|
release prisoner 3: 19 gold coins
release prisoner 6: 16 gold coins
release prisoner 14: 13 gold coins
release 14: 19 gold coins
release 6: 12 gold coins
release 3: 4 gold coins
input:
number of cells
prisoners that need to be released
output:
least number of gold coins we need to give
*/
Prison cell question
In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbors." A wall with a window separates adjacent cells, and neighbors can communicate through that window.
All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbors find out, and each communicates this to his other neighbor. That prisoner passes it on to his other neighbor, and so on until they reach a prisoner with no other neighbor (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.
Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.
Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.
Task: find the minimum amount of gold we need to bribe the prisoners so that the chosen prisoners can be released without causing cell destruction.
Input example:
8 cells, 1 prisoner has to be released. The prisoner to be released is the 3rd one.
|1|2|3|4|5|6|7|8|
7 gold coins
another example:
20 cells, 3 prisoners to be released: 3, 6 and 14
|1|2| |4|5| |7|8|9|10|11|12|13| |15|16|17|18|19|20|
release prisoner 3: 19 gold coins
release prisoner 6: 16 gold coins
release prisoner 14: 13 gold coins
release 14: 19 gold coins
release 6: 12 gold coins
release 3: 4 gold coins
input:
number of cells
prisoners that need to be released
output:
least number of gold coins we need to give
*/
".
2. Data Structure and Algorithm
Given P prison cells [1, 2, ..., p] and Q cells [x, y, ..., q], bear in mind that Q is a a subset of P. And P and Q are in the ascending order. Assume that i in Q is released. Then the cost will be
P - 1 + minCost([1, ..., i -1], [x, ...q1]) + minCost([i+1, ..., p, [q2, ..., q], where
q1 and q2 are the neighbor cells in Q.
This problem is a minimization problem. The above tells that how to compute the cost of any cell in Q. Go through Q, [x, y, ..., q] and keep track the minimal value,
minCost(P - 1 + minCost([1,..., i-1], [x, ...q1]) + minCost([i+1, ..., p], [q2, ...,q])), where
i belongs to [x, y, ..., q]
The above tells us that this can solved by dynamic problem. The problem can be solved by two sub-problems. Take any prisoner i out, then prisoners and cells on the left hand side of i become a sub-problem and those on the right hand side of i become another sub-problem.
Again caching techniques are used in the solution, take the combination of {P, Q} as the hash key and the min cost as the value.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <unordered_map>
#include <vector>
struct PrisonCellKey
{
PrisonCellKey(const std::vector<size_t> &c,
const std::vector<size_t> &r)
: cells(c)
, releases(r)
{}
std::vector<size_t> cells;
std::vector<size_t> releases;
bool operator==(const PrisonCellKey& rhs) const {
return cells == rhs.cells && releases == rhs.releases;
}
};
size_t SizetVectorHash(const std::vector<size_t> &input)
{
size_t hash = 0;
for (auto it = input.begin(); it != input.end(); ++it) {
hash = hash^std::hash<size_t>()(*it);
}
return hash;
}
struct PrisionCellHashFunc
{
const static size_t PrimeOfCells = 2909;
const static size_t PrimeOfReleases = 4021;
size_t operator()(const PrisonCellKey &key) const {
size_t cellsHash = SizetVectorHash(key.cells);
size_t releasesHash = SizetVectorHash(key.releases);
return std::hash<size_t>()(
cellsHash*PrimeOfCells + releasesHash*PrimeOfReleases);
}
bool operator()(const PrisonCellKey &lhs, const PrisonCellKey &rhs) const {
return lhs.operator==(rhs);
}
};
using PrisonCellHashMap = std::unordered_map<PrisonCellKey, size_t, PrisionCellHashFunc, PrisionCellHashFunc>;
size_t MinCostOfReleasingCells_R(const std::vector<size_t> &cells,
const std::vector<size_t> &toRelease,
PrisonCellHashMap &cache)
{
const size_t NRelease = toRelease.size();
if (NRelease == 0) {
return 0;
}
else if (NRelease == 1) {
return cells.size() - 1;
}
const PrisonCellKey key(cells, toRelease);
auto it = cache.find(key);
if (it != cache.end()) {
return it->second;
}
const size_t NCells = cells.size();
auto itEnd = toRelease.end();
size_t minCost = -1;
size_t tempCost;
for (auto it = toRelease.begin(); it != itEnd; ++it) {
tempCost = NCells - 1;
{
auto tmpIt = cells.begin();
std::advance(tmpIt, *it);
std::vector<size_t> LeftCells(cells.begin(), tmpIt);
std::vector<size_t> LeftToRelease(toRelease.begin(), it);
tempCost += MinCostOfReleasingCells_R(LeftCells, LeftToRelease, cache);
}
{
std::vector<size_t> RightCells;
for (int i = *it + 1; i < NCells; ++i) {
RightCells.push_back(i - *it - 1);
}
std::vector<size_t> RightToRelease;
for (auto tmpIt = it + 1; tmpIt != toRelease.end(); ++tmpIt) {
RightToRelease.push_back(*tmpIt - *it - 1);
}
tempCost += MinCostOfReleasingCells_R(RightCells, RightToRelease, cache);
}
if (tempCost < minCost) {
minCost = tempCost;
}
}
cache.insert(std::make_pair(key, minCost));
return minCost;
}
size_t MinCostOfReleasingCells(const std::vector<size_t> &cells,
const std::vector<size_t> &toRelease)
{
PrisonCellHashMap cache;
return MinCostOfReleasingCells_R(cells, toRelease, cache);
}
// ********************************************************************************
// 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);
}
}
No comments:
Post a Comment