Dynamic Programming - Min Cost of Releasing Prisoners

1. Problem Description
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
*/

- xankar May 12, 2016 in United States | Report Duplicate | Flag 
".

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);

    }

}

Compare Exotic String

1. Problem Description
This is a Google interview question for software engineer from careercup. Here is the description from the original thread,
"

Provide a function that allow to compare two strings lexicography, having in mind that these words may contain digraphs (two letters together represents a single one i.e in Spanish ch is a single character ). 

This in order to be able to sort a list of words.

- urodba April 07, 2016 in United States | Report Duplicate | Flag ".

2. Data Structure and Algorithm
The idea follows
    - Build all possible characters into a Trie structure
    - Build a hash map for each valid entry in Trie, for exmaple
        * The pointer in Trie as the key and has a integer as value
        * Character "a" as 65 (in ASCII table)
        * Character "cz" as 100 (any number to represent its value comparing to other characters)
    - Search a valid entry from the starting of the string in the Trie until failed to find or reach the end
        * Find the longest valid entry in Trie
        * Compare two valid entries in two given strings
            ~ Return a positive value if lhs > rhs
            ~ Return a negative value if lhs < rhs
            ~ Return 0 if equal

Initially I was thinking to use a hash map instead of Trie to build up the character table. But the disadvantage of hash map is that have to continue searching for the valid entry in the character table up the maximal key size. For example if a valid entry can be made up to 10 English character, then have to search 10 times (equal to the maximal key size) to enumerate all the possibility. In the case of just one valid entry is 10 characters long ("abcdefghij") in the character table. Still need to search 10 times even starting with "x".
A character table of Trie structure does not have this problem. And in computation wise Trie search needs only one pointer checking and should outpaces harsh map, which needs to compute hash code then pointer checking.

3. C++ Implementation
The Trie structure used in this implemented can be found in Data Structure and Algorithm - Trie, Data Structure and Algorithm - Trie and Palindrome (Google Interview Question) and Trie - Live Stream Words Detector.

// ********************************************************************************
// Implementation
// ********************************************************************************

// header
#include "DictionaryTrie.h"

#include <exception>
#include <string>
#include <unordered_map>
#include <vector>

struct ExoticChar
{
    ExoticChar(const std::string &ec, const int v)
        : eChar(ec), val(v)
    {}

    ExoticChar& operator=(const ExoticChar &rhs) {
        this->eChar = rhs.eChar;
        this->val = rhs.val;
        return *this;
    }

    std::string eChar;
    int val;
};

class EscException : public std::exception
{
public:
    EscException(const std::string &msg)
        : m_Msg(msg)
    {}

    const char* what() const {
        return m_Msg.c_str();
    }

private:
    const std::string m_Msg;
};

class ExoticStringComparator
{
public:
    ExoticStringComparator(const std::vector<ExoticChar> &staticTable);
    ~ExoticStringComparator();

    int CompareExoticString(const std::string &lhs, const std::string &rhs) const;
private:
    DictionaryTrie* m_StaticMapRoot;
    std::unordered_map<DictionaryTrie*, int> m_KeyValMap;
};

// cpp

#include "ExoticStringComparator.h"

ExoticStringComparator::ExoticStringComparator(const std::vector<ExoticChar> &staticTable)

    : m_StaticMapRoot(NULL)

{

    if (staticTable.empty()) {

        throw EscException("ExoticStringComparator creation - empty table");

    }

    m_StaticMapRoot = new DictionaryTrie();

    DictionaryTrie *tempPtr;

    for (auto it = staticTable.begin(); it != staticTable.end(); ++it) {

        tempPtr = AddWord(m_StaticMapRoot, it->eChar.c_str());

        if (tempPtr) {

            m_KeyValMap.insert(std::make_pair(tempPtr, it->val));

        }

    }

}

ExoticStringComparator::~ExoticStringComparator()

{

    DestoryDictionaryTrie(m_StaticMapRoot);

    m_StaticMapRoot = NULL;

}

int ExoticStringComparator::CompareExoticString(const std::string &lhs, const std::string &rhs) const

{

    auto lhsTempIt = lhs.begin();

    auto rhsTempIt = rhs.begin();

    int result = 0;

    DictionaryTrie *lhsTemp, *lhsCur;

    DictionaryTrie *rhsTemp, *rhsCur;

    //while (lhsCurIt != lhs.end() && rhsCurIt != rhs.end()) {

    while (lhsTempIt != lhs.end() && rhsTempIt != rhs.end()) {

        lhsTemp = m_StaticMapRoot;

        while (lhsTemp = FindPath(lhsTemp, *lhsTempIt)) {

            if (lhsTemp->str) {

                lhsCur = lhsTemp;

            }

            ++lhsTempIt;

            if (lhsTempIt == lhs.end()) {

                break;

            }

        }

        rhsTemp = m_StaticMapRoot;

        while (rhsTemp = FindPath(rhsTemp, *rhsTempIt)) {

            if (rhsTemp->str) {

                rhsCur = rhsTemp;

            }

            ++rhsTempIt;

            if (rhsTempIt == rhs.end()) {

                break;

            }

        }

        auto lhsValIt = m_KeyValMap.find(lhsCur);

        auto rhsValIt = m_KeyValMap.find(rhsCur);

        if (lhsValIt == m_KeyValMap.end() || rhsValIt == m_KeyValMap.end()) {

            throw EscException("CompareExoticString: invalid map");

        }

        result = lhsValIt->second - rhsValIt->second;

        if (result != 0) {

            return result;

        }

    }

    if (lhsTempIt != lhs.end()) {

        return 1;

    }

    else if (rhsTempIt != rhs.end()) {

        return -1;

    }

    return result;

}

// ********************************************************************************
// Test
// ********************************************************************************
void TestExoticStringComparator()
{
    {
        // non-exotic testing
        const std::vector<ExoticChar> charTable = {
            { "a", 'a' },
            { "b", 'b' },
            { "c", 'c' },
            { "d", 'd' },
            { "e", 'e' },
            { "f", 'f' },
            { "g", 'g' },
            { "h", 'h' },
            { "i", 'i' },
            { "j", 'j' },
            { "k", 'k' },
            { "l", 'l' },
            { "m", 'm' },
            { "n", 'n' },
            { "o", 'o' },
            { "p", 'p' },
            { "q", 'q' },
            { "r", 'r' },
            { "s", 's' },
            { "t", 't' },
            { "u", 'u' },
            { "v", 'v' },
            { "w", 'w' },
            { "x", 'x' },
            { "y", 'y' },
            { "z", 'z' } };
           
        ExoticStringComparator esc(charTable);
        assert(esc.CompareExoticString("lkasdfajsd", "lkasdfajsd") == 0);
        assert(esc.CompareExoticString("lkasdfajsd", "lkasdfahsd") > 0);
        assert(esc.CompareExoticString("lkasdfajsd", "lkasdfaxsd") < 0);
        assert(esc.CompareExoticString("lkasdfajsdz", "lkasdfajsd") > 0);
        assert(esc.CompareExoticString("lkasdfajsd", "lkasdfajsdz") < 0);
   
    }

    {
        // exotic testing
        const std::vector<ExoticChar> charTable = {
            { "a", 'a' },
            { "b", 'b' },
            { "c", 'c' },
            { "d", 'd' },
            { "e", 'e' },
            { "f", 'f' },
            { "g", 'g' },
            { "h", 'h' },
            { "i", 'i' },
            { "j", 'j' },
            { "k", 'k' },
            { "l", 'l' },
            { "m", 'm' },
            { "n", 'n' },
            { "o", 'o' },
            { "p", 'p' },
            { "q", 'q' },
            { "r", 'r' },
            { "s", 's' },
            { "t", 't' },
            { "u", 'u' },
            { "v", 'v' },
            { "w", 'w' },
            { "x", 'x' },
            { "y", 'y' },
            { "z", 'z' },
            { "ae", 'z' + 1 },
            { "oe", 'z' + 2 },
            { "ue", 'a' - 1 },
            { "sch", 'a' - 2 }, };

        ExoticStringComparator esc(charTable);
        assert(esc.CompareExoticString("ae", "oe") < 0);
        assert(esc.CompareExoticString("ae", "ue") > 0);
        assert(esc.CompareExoticString("oe", "sch") > 0);
        assert(esc.CompareExoticString("oe", "ue") > 0);
        assert(esc.CompareExoticString("lkasdfaesd", "lkasdfajsdz") > 0);
        assert(esc.CompareExoticString("lkasdfschaesd", "lkasdfaajsdz") < 0);
        assert(esc.CompareExoticString("lkasdfschaesd", "lkasdfschoesd") < 0);

    }
}