1. Problem Description
This is a Facebook interview question for software developers from careercup. Here is the original thread,
"
There are N coins with coordinates (x, y) where x >0 and y >0
You start at (0, 0) and you can only do steps of form (dx, dy) where dx >0 and dy > 0
Print the maximum number of coins that you can collect.
Clarification: you can do as many moves as you wish, the point is to collect maximum number of coins. If you are located at position (a, b) you may jump to position (a+dx, b+dy) for all dx > 0 and dy > 0
@krbchd: Your algorithm may output incorrect values. Suppose there are points (5, 7), (5, 8), (5, 9) for y coordinates LIS will output 7, 8, 9, however since these points are on the same x axis, you can choose only one of them.
".
2. Sub-problem
It is a optimization problem to find the maximal possible coins that a path can collect coins. Given position C1, C2, ..., Cn, which has a coin on it at position (Xi, Yi).
- f(C1, ..., Cn) = max(1 + f(C1, ..., Ci-1, Ci+1, Cn) ), where i with range of [1, n]
As the problem stated that the path has to be in strictly ascending order. Path P (Ca, Cb, ..., Cm) has to meet the pre-condition of (Xa, Ya) < (Xb, Yb) < ... < (Xm, Ym), where operator "<" means that Xa < Xb and Ya < Yb for instance.
Therefore f(C1, ..., Ci-1, Ci+1, Cn) can be limited to coins that are greater than Ci,
- f(C1, ..., Ci-1, Ci+1, Cn) = f(CollectionOfConis > Ci).
- f(C1, ..., Cn) = max(1 + f(CollectionOfCoins > Ci) where i with range of [1, n]
Again caching technique is used in this case as the searching along the paths, the result is cached to avoid the duplicate calculation.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <unordered_map>
#include <vector>
struct Position
{
Position()
: x(0.0)
, y(0.0)
{}
Position(double _x, double _y)
: x(_x)
, y(_y)
{}
double x;
double y;
bool operator >(const Position &rhs) const {
return x > rhs.x && y > rhs.y;
}
bool operator <(const Position &rhs) const {
return x < rhs.x && y < rhs.y;
}
bool operator ==(const Position &rhs) const {
return x == rhs.x && y == rhs.y;
}
};
struct PositionHashFunc
{
size_t operator()(const Position &p) {
return std::hash<double>()(p.x) ^ std::hash<double>()(p.y);
}
bool operator ()(const Position &lhs, const Position &rhs) const {
return lhs == rhs;
}
};
std::vector<size_t> FindLargerPositions(const std::vector<Position> &input,
const Position &pivotal)
{
auto itEnd = input.end();
size_t index = 0;
std::vector<size_t> result;
result.reserve(input.size());
for (auto it = input.begin(); it != itEnd; ++it, ++index) {
if (it->operator>(pivotal)) {
result.push_back(index);
}
}
return result;
}
std::vector<size_t> FindLargerPositions(const std::vector<Position> &input,
const std::vector<size_t> &searchIn,
const Position &pivotal)
{
std::vector<size_t> result;
result.reserve(searchIn.size());
auto itEnd = searchIn.end();
for (auto it = searchIn.begin(); it != itEnd; ++it) {
auto&& tempPos = input[*it];
if (tempPos.operator>(pivotal)) {
result.emplace_back(*it);
}
}
return result;
}
using HashMap = std::unordered_map<Position, size_t, PositionHashFunc, PositionHashFunc>;
size_t PickMaximalCoins_R(const std::vector<Position> &coins,
const std::vector<size_t> &subProbelm,
const Position &pivotal,
HashMap &hash)
{
if (subProbelm.empty()) {
return 0;
}
auto it = hash.find(pivotal);
if (it != hash.end()) {
return it->second;
}
size_t maximal = 0;
auto itEnd = subProbelm.end();
for (auto it = subProbelm.begin(); it != itEnd; ++it) {
auto& position = coins[*it];
const std::vector<size_t> subproblem = FindLargerPositions(coins, subProbelm, position);
const size_t temp = 1 + PickMaximalCoins_R(coins, subproblem, position, hash);
if (maximal < temp) {
maximal = temp;
}
}
hash[pivotal] = maximal;
return maximal;
}
size_t PickMaximalCoins_R(const std::vector<Position> &coins)
{
if (coins.empty()) {
return 0;
}
HashMap hm;
size_t maximal = 0;
auto itEnd = coins.end();
for (auto it = coins.begin(); it != itEnd; ++it) {
const std::vector<size_t> subProblem = FindLargerPositions(coins, *it);
const size_t temp = 1 + PickMaximalCoins_R(coins, subProblem, *it, hm);
if (maximal < temp) {
maximal = temp;
}
}
return maximal;
}
// ********************************************************************************
// Test
// ********************************************************************************
#include <cassert>
void TestPickMaximalCoins()
{
{
const std::vector<Position> coins;
assert(PickMaximalCoins_R(coins) == 0);
}
{
const std::vector<Position> coins = { { 5, 5 }, { 1.5, 3.5 }, { 2, 2 }, { 2.0, 4.0 },
{ 4, 4 }, { 5.0, 2.0 }, { 3, 3 }, { 4.0, 1.0 }, { 1, 1 }};
assert(PickMaximalCoins_R(coins) == 5);
}
{
const std::vector<Position> coins = {
{ 6.1, 2.1 }, { 2.2, 6.2 }, { 5.2, 5.2 }, { 6.2, 2.2 },
{ 2.3, 6.3 }, { 5.3, 5.3 }, { 6.3, 2.3 }, { 5.4, 5.4 },
{ 1.0, 1.0 }, { 2.0, 6.0 }, { 5.0, 5.0 }, { 6.0, 2.0 },
{ 2.1, 6.1 }, { 5.1, 5.1 } };
assert(PickMaximalCoins_R(coins) == 6);
}
{
const std::vector<Position> coins = {
{ 6.1, 2.1 }, { 2.2, 6.2 }, { 5.2, 5.2 }, { 6.2, 2.2 },
{ 2.3, 6.3 }, { 5.3, 5.3 }, { 6.3, 2.3 }, { 4.0, 5.3 },
{ 5.4, 5.4 }, { 1.0, 1.0 }, { 2.0, 6.0 }, { 5.0, 5.0 },
{ 6.0, 2.0 }, { 2.1, 6.1 }, { 5.1, 5.1 }, { 5.3, 4.0 } };
assert(PickMaximalCoins_R(coins) == 6);
}
}
Sunday, 31 July 2016
Wednesday, 22 June 2016
C++ - Restrict Creation of Objects
1. Problem Description
This is a Microsoft interview question from careercup. Here is the description of the original thread,
"
2. Scope
This is a very vague question. Here I am going to concentrate on the process of the object creation and the object deletion. The first stage is compiler has to know all the data types of the class before creating an object out of it. It includes all its own member variables and the data members of its base class(es). The second stage is the order of object creation and object deletion. It starts from the member variables of its base classes to the constructor(s) of the base class then in the order of hierarchy of inheritance to its own member variables and therefore its own constructor. The object deletion is the exactly the opposite way of creation. The solutions will be focusing on the chain of these two stages.
3. Template
This solution is on the first stage. The types of the class has to be resolved before object creation. Any ambiguity will stop creating objects.
template <typename T>
class Foo
{
Foo() {
std::cout << "Foo()" << std::endl;
}
~Foo() {
std::cout << "~Foo()" << std::endl;
}
public:
static void Bar() {
Foo f;
}
};
class Foo
{
int &m_Val;
Foo() {
std::cout << "Foo()" << std::endl;
}
~Foo() {
std::cout << "~Foo()" << std::endl;
}
public:
static void Bar() {
Foo f;
}
};
This is a Microsoft interview question from careercup. Here is the description of the original thread,
"
how to restrict creation of object inside the function fun
although destructor and constructor is private??
#include <iostream>
class ABC
{
private :
~ABC()
{
}
ABC()
{
std::cout <<"ABC";
}
public:
static void fun()
{
ABC t;
}
};
int main()
{
ABC::fun();
}
- jkl June 19, 2016 in India #include <iostream>
class ABC
{
private :
~ABC()
{
}
ABC()
{
std::cout <<"ABC";
}
public:
static void fun()
{
ABC t;
}
};
int main()
{
ABC::fun();
}
2. Scope
This is a very vague question. Here I am going to concentrate on the process of the object creation and the object deletion. The first stage is compiler has to know all the data types of the class before creating an object out of it. It includes all its own member variables and the data members of its base class(es). The second stage is the order of object creation and object deletion. It starts from the member variables of its base classes to the constructor(s) of the base class then in the order of hierarchy of inheritance to its own member variables and therefore its own constructor. The object deletion is the exactly the opposite way of creation. The solutions will be focusing on the chain of these two stages.
3. Template
This solution is on the first stage. The types of the class has to be resolved before object creation. Any ambiguity will stop creating objects.
template <typename T>
class Foo
{
Foo() {
std::cout << "Foo()" << std::endl;
}
~Foo() {
std::cout << "~Foo()" << std::endl;
}
public:
static void Bar() {
Foo f;
}
};
Templatized this class stops creating objects because "Foo f;" does not provide any information for compiler to deduce template type and generate the instance of class.
4. Member Variables
As the code only provides default constructor, any member variables that cannot be initialized/created via its default constructor will stop creating Foo object. This means that all types of its member variables including the member variables of its base class(es) have to provide default constructors.class Foo
{
int &m_Val;
Foo() {
std::cout << "Foo()" << std::endl;
}
~Foo() {
std::cout << "~Foo()" << std::endl;
}
public:
static void Bar() {
Foo f;
}
};
Reference type does not provide default constructor and it has to be initialized via existing variables in the initialization list of constructor. m_Val will stop creating Foo objects.
class Abc
{
public:
Abc(int x)
{}
};
class Foo
{
Abc m_Abc;
Foo() {
std::cout << "Foo()" << std::endl;
}
~Foo() {
std::cout << "~Foo()" << std::endl;
}
public:
static void Bar() {
Foo f;
}
};
The same reason m_Abc can't be initialized because class Abc does not provide a default constructor. The fix will have to provide a default constructor of Abc or initialize m_Abc in Foo's initialization list.
Any member variables like above m_Abc appearing in Foo's base class which has no default constructor implementation will propagate the creation failure to Foo object.
5. Access Control
Here it refers to the constructor and destructor access control of its base class, which have to be accessible in object creation and deletion of derived class. In Foo::Bar() function it can access Foo's constructor and destructor because Bar() is a member function of Foo even though Foo's constructor and destructor are declared private. But if Foo has base class(es), hiding the access of either constructor or destructor of its base class(es) will stop Foo object creation.
class Interface
{
Interface();
~Interface();
};
class Foo : public Interface
{
Foo() {
std::cout << "Foo()" << std::endl;
}
~Foo() {
std::cout << "~Foo()" << std::endl;
}
public:
static void Bar() {
Foo f;
}
};
Declaring either constructor or destructor of Interface will stop creating Foo objects, because Foo cannot access its bases classes private section.
6. Constructor Signature Mismatch
If there is no default constructor is implemented in base classes, then the constructor of base class(es) has to be specifically appearing in initialization list in order to be called. Otherwise it breaks the object creation process. Simply compiler does not how to initialize member variables or status in generally of its base class(es).
class Abc
{
public:
Abc(int x)
{}
};
class Foo : public Abc
{
Foo() {
std::cout << "Foo()" << std::endl;
}
~Foo() {
std::cout << "~Foo()" << std::endl;
}
public:
static void Bar() {
Foo f;
}
};
The fix is to call Abc's constructor in the initialization list of Foo.
7. Abstract Classes
The object of absctract classes cannot be created because compiler has no where to populate the virtual table. Any derived class that does not implement all abstract virtual function will remain as abstract classes and therefore cannot create objects out of it.
class Foo
{
Foo() {
std::cout << "Foo()" << std::endl;
}
~Foo() {
std::cout << "~Foo()" << std::endl;
}
public:
static void Bar() {
Foo f;
}
virtual void PrintSelf() = 0;
};
Foo has an abstract virtual function PrintSelf() and therefore cannot create objects out it.
class Interface
{
virtual int GetVersion() = 0;
};
class Foo : public Interface
{
Foo() {
std::cout << "Foo()" << std::endl;
}
~Foo() {
std::cout << "~Foo()" << std::endl;
}
public:
static void Bar() {
Foo f;
}
};
Foo inherits from an abstract class Interface but does not implement the abstract virtual function. Therefore it remains as an abstract function and cannot create objects out of it.
Thursday, 16 June 2016
Data Structure and Algorithm - Find the Shortest Path in Grid
1. Problem Description
This is a Facebook interview question for Android developer from careercup. Here is the original thread,
"
".
2. Data Structure and Algorithm
Mapping of the museum:
Given a museum there are 3 things to represent, open ground, guard and wall. The key here is to use wise data structure to represent museum in memory. In a common-sense scenario there are a few guards and plenty of open guards. Instead of a full size of grid to model museum two hash sets are to represent guards and walls.
- Location: row and column
- A hash set of locations to represent guards's position in museum
- A hash set of locations to represent wall's position in museum
- A hash map of locations as key and distance to guard as value to represent open group to guard
- Any open group not appearing in above hash map means isolated to guards
Algorithm:
Each guard has children nodes in the grid of possible directions to reach them (in the case of implementation in this post 4 directions - left, right, up and down). Therefore it is not hard to link to graph problem. Each node is linked to 4 neighbors (left, right , up and down). Each iteration expand one step from guards. Terminate expanding if reaches wall/guard/open-ground-already-visited and take the result (location + breadth-of-traverse) if reaches an open ground. In this case it is breath-first traverse the museum, which guarantees that the shortest path from open ground to its reachable guards.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <list>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
enum class MuseumItem
{
WALL = 0,
OPEN,
GUARD
};
struct LocHashFunc
{
size_t operator()(const std::tuple<size_t, size_t> &loc) const {
size_t row, col;
std::tie<size_t, size_t>(row, col) = loc;
return std::hash<size_t>()(row) ^ std::hash<size_t>()(col);
}
bool operator()(const std::tuple<size_t, size_t> &lhs,
const std::tuple<size_t, size_t> &rhs) const {
return lhs == rhs;
}
};
using LocationMap = std::unordered_set<std::tuple<size_t, size_t>, LocHashFunc, LocHashFunc>;
using LocAndDistMap = std::unordered_map<std::tuple<size_t, size_t>, int, LocHashFunc, LocHashFunc>;
bool ParserMuseumMap(const std::vector<std::vector<MuseumItem>> &museum,
LocationMap &guards,
LocationMap &walls)
{
// for this implementation, the mesum must be square
const size_t ROWS = museum.size();
if (ROWS == 0) {
return false;
}
const size_t COLS = museum[0].size();
auto itEnd = museum.end();
size_t row = 0, col = 0;
for (auto it = museum.begin(); it != itEnd; ++it, ++row) {
if (it->size() != COLS) {
return false; // enforce square map
}
auto itRowEnd = it->end();
col = 0;
for (auto itRow = it->begin(); itRow != itRowEnd; ++itRow, ++col) {
switch (*itRow) {
case MuseumItem::WALL:
walls.insert(std::make_tuple(row, col));
break;
case MuseumItem::OPEN:
break;
case MuseumItem::GUARD:
guards.insert(std::make_tuple(row, col));
break;
default:
return false;
}
}
}
return true;
}
void ExpandSeach(const std::tuple<size_t, size_t> &loc,
const LocationMap &guards,
const LocationMap &walls,
const size_t distance,
LocAndDistMap & distances,
std::list < std::tuple<size_t, size_t> > &toVisits)
{
if (walls.find(loc) != walls.end()) {
return;
}
if (guards.find(loc) != guards.end()) {
return;
}
if (distances.find(loc) == distances.end()) {
distances.insert(std::make_pair(loc, distance));
toVisits.push_back(loc);
}
}
const LocAndDistMap GetDistances(const size_t ROWS,
const size_t COLS,
const LocationMap &guards,
const LocationMap &walls)
{
LocAndDistMap distances;
std::list<std::tuple<size_t, size_t>> toVisits(guards.begin(), guards.end());
toVisits.push_back(std::tuple<size_t, size_t>{-1, -1});
LocationMap visited;
size_t dist = 1;
size_t row, col;
size_t distance = 1;
while (!toVisits.empty()) {
std::tie<size_t, size_t>(row, col) = toVisits.front();
if (row == -1 && col == -1) {
++distance;
toVisits.pop_front();
if (toVisits.empty()) {
break;
}
toVisits.push_back(std::make_tuple(-1, -1));
}
else {
if (row > 0) {
auto loc = std::make_tuple( row - 1, col );
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
if (row != (ROWS - 1)) {
auto loc = std::make_tuple(row + 1, col);
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
if (col > 0) {
auto loc = std::make_tuple(row, col - 1);
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
if (col != (COLS - 1)) {
auto loc = std::make_tuple(row, col + 1);
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
toVisits.pop_front();
}
}
return distances;
}
const LocAndDistMap GetDistances(const std::vector<std::vector<MuseumItem>> &museum)
{
LocationMap guards;
LocationMap walls;
if (!ParserMuseumMap(museum, guards, walls)) {
return LocAndDistMap();
}
const size_t ROWS = museum.size();
const size_t COLS = museum[0].size();
return GetDistances(ROWS, COLS, guards, walls);
}
This is a Facebook interview question for Android developer from careercup. Here is the original thread,
"
A museum was represented by a square matrix that was filled with O, G, and W where O represented open space G represented guards, and W represented walls. Write a function that accepts the square matrix and returns another square matrix where all of the O's in the matrix are replaced with the number of how many spaces they are away from a guard, without being able to go through any walls.
".
2. Data Structure and Algorithm
Mapping of the museum:
Given a museum there are 3 things to represent, open ground, guard and wall. The key here is to use wise data structure to represent museum in memory. In a common-sense scenario there are a few guards and plenty of open guards. Instead of a full size of grid to model museum two hash sets are to represent guards and walls.
- Location: row and column
- A hash set of locations to represent guards's position in museum
- A hash set of locations to represent wall's position in museum
- A hash map of locations as key and distance to guard as value to represent open group to guard
- Any open group not appearing in above hash map means isolated to guards
Algorithm:
Each guard has children nodes in the grid of possible directions to reach them (in the case of implementation in this post 4 directions - left, right, up and down). Therefore it is not hard to link to graph problem. Each node is linked to 4 neighbors (left, right , up and down). Each iteration expand one step from guards. Terminate expanding if reaches wall/guard/open-ground-already-visited and take the result (location + breadth-of-traverse) if reaches an open ground. In this case it is breath-first traverse the museum, which guarantees that the shortest path from open ground to its reachable guards.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <list>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
enum class MuseumItem
{
WALL = 0,
OPEN,
GUARD
};
struct LocHashFunc
{
size_t operator()(const std::tuple<size_t, size_t> &loc) const {
size_t row, col;
std::tie<size_t, size_t>(row, col) = loc;
return std::hash<size_t>()(row) ^ std::hash<size_t>()(col);
}
bool operator()(const std::tuple<size_t, size_t> &lhs,
const std::tuple<size_t, size_t> &rhs) const {
return lhs == rhs;
}
};
using LocationMap = std::unordered_set<std::tuple<size_t, size_t>, LocHashFunc, LocHashFunc>;
using LocAndDistMap = std::unordered_map<std::tuple<size_t, size_t>, int, LocHashFunc, LocHashFunc>;
bool ParserMuseumMap(const std::vector<std::vector<MuseumItem>> &museum,
LocationMap &guards,
LocationMap &walls)
{
// for this implementation, the mesum must be square
const size_t ROWS = museum.size();
if (ROWS == 0) {
return false;
}
const size_t COLS = museum[0].size();
auto itEnd = museum.end();
size_t row = 0, col = 0;
for (auto it = museum.begin(); it != itEnd; ++it, ++row) {
if (it->size() != COLS) {
return false; // enforce square map
}
auto itRowEnd = it->end();
col = 0;
for (auto itRow = it->begin(); itRow != itRowEnd; ++itRow, ++col) {
switch (*itRow) {
case MuseumItem::WALL:
walls.insert(std::make_tuple(row, col));
break;
case MuseumItem::OPEN:
break;
case MuseumItem::GUARD:
guards.insert(std::make_tuple(row, col));
break;
default:
return false;
}
}
}
return true;
}
void ExpandSeach(const std::tuple<size_t, size_t> &loc,
const LocationMap &guards,
const LocationMap &walls,
const size_t distance,
LocAndDistMap & distances,
std::list < std::tuple<size_t, size_t> > &toVisits)
{
if (walls.find(loc) != walls.end()) {
return;
}
if (guards.find(loc) != guards.end()) {
return;
}
if (distances.find(loc) == distances.end()) {
distances.insert(std::make_pair(loc, distance));
toVisits.push_back(loc);
}
}
const LocAndDistMap GetDistances(const size_t ROWS,
const size_t COLS,
const LocationMap &guards,
const LocationMap &walls)
{
LocAndDistMap distances;
std::list<std::tuple<size_t, size_t>> toVisits(guards.begin(), guards.end());
toVisits.push_back(std::tuple<size_t, size_t>{-1, -1});
LocationMap visited;
size_t dist = 1;
size_t row, col;
size_t distance = 1;
while (!toVisits.empty()) {
std::tie<size_t, size_t>(row, col) = toVisits.front();
if (row == -1 && col == -1) {
++distance;
toVisits.pop_front();
if (toVisits.empty()) {
break;
}
toVisits.push_back(std::make_tuple(-1, -1));
}
else {
if (row > 0) {
auto loc = std::make_tuple( row - 1, col );
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
if (row != (ROWS - 1)) {
auto loc = std::make_tuple(row + 1, col);
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
if (col > 0) {
auto loc = std::make_tuple(row, col - 1);
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
if (col != (COLS - 1)) {
auto loc = std::make_tuple(row, col + 1);
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
toVisits.pop_front();
}
}
return distances;
}
const LocAndDistMap GetDistances(const std::vector<std::vector<MuseumItem>> &museum)
{
LocationMap guards;
LocationMap walls;
if (!ParserMuseumMap(museum, guards, walls)) {
return LocAndDistMap();
}
const size_t ROWS = museum.size();
const size_t COLS = museum[0].size();
return GetDistances(ROWS, COLS, guards, walls);
}
// ********************************************************************************
// Test
// ********************************************************************************
#include <cassert>
void TestGetDistances()
{
{
const std::vector<std::vector<MuseumItem>> museum =
{{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN} };
LocAndDistMap distances = GetDistances(museum);
assert(distances.find(std::make_tuple(0, 0))->second == 4);
assert(distances.find(std::make_tuple(1, 0))->second == 3);
assert(distances.find(std::make_tuple(2, 0))->second == 2);
assert(distances.find(std::make_tuple(3, 0))->second == 3);
assert(distances.find(std::make_tuple(4, 0))->second == 4);
assert(distances.find(std::make_tuple(0, 1))->second == 3);
assert(distances.find(std::make_tuple(1, 1))->second == 2);
assert(distances.find(std::make_tuple(2, 1))->second == 1);
assert(distances.find(std::make_tuple(3, 1))->second == 2);
assert(distances.find(std::make_tuple(4, 1))->second == 3);
assert(distances.find(std::make_tuple(0, 2))->second == 2);
assert(distances.find(std::make_tuple(1, 2))->second == 1);
assert(distances.find(std::make_tuple(2, 2)) == distances.end());
assert(distances.find(std::make_tuple(3, 2))->second == 1);
assert(distances.find(std::make_tuple(4, 2))->second == 2);
assert(distances.find(std::make_tuple(0, 3))->second == 3);
assert(distances.find(std::make_tuple(1, 3))->second == 2);
assert(distances.find(std::make_tuple(2, 3))->second == 1);
assert(distances.find(std::make_tuple(3, 3))->second == 2);
assert(distances.find(std::make_tuple(4, 3))->second == 3);
assert(distances.find(std::make_tuple(0, 4))->second == 4);
assert(distances.find(std::make_tuple(1, 4))->second == 3);
assert(distances.find(std::make_tuple(2, 4))->second == 2);
assert(distances.find(std::make_tuple(3, 4))->second == 3);
assert(distances.find(std::make_tuple(4, 4))->second == 4);
}
{
const std::vector<std::vector<MuseumItem>> museum =
{ { MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN } };
LocAndDistMap distances = GetDistances(museum);
assert(distances.find(std::make_tuple(0, 0)) == distances.end());
assert(distances.find(std::make_tuple(1, 0)) == distances.end());
assert(distances.find(std::make_tuple(2, 0)) == distances.end());
assert(distances.find(std::make_tuple(3, 0)) == distances.end());
assert(distances.find(std::make_tuple(4, 0)) == distances.end());
assert(distances.find(std::make_tuple(0, 1)) == distances.end());
assert(distances.find(std::make_tuple(1, 1)) == distances.end());
assert(distances.find(std::make_tuple(2, 1)) == distances.end());
assert(distances.find(std::make_tuple(3, 1)) == distances.end());
assert(distances.find(std::make_tuple(4, 1)) == distances.end());
assert(distances.find(std::make_tuple(0, 2))->second == 2);
assert(distances.find(std::make_tuple(1, 2))->second == 1);
assert(distances.find(std::make_tuple(2, 2)) == distances.end());
assert(distances.find(std::make_tuple(3, 2))->second == 1);
assert(distances.find(std::make_tuple(4, 2))->second == 2);
assert(distances.find(std::make_tuple(0, 3))->second == 3);
assert(distances.find(std::make_tuple(1, 3))->second == 2);
assert(distances.find(std::make_tuple(2, 3))->second == 1);
assert(distances.find(std::make_tuple(3, 3))->second == 2);
assert(distances.find(std::make_tuple(4, 3))->second == 3);
assert(distances.find(std::make_tuple(0, 4))->second == 4);
assert(distances.find(std::make_tuple(1, 4))->second == 3);
assert(distances.find(std::make_tuple(2, 4))->second == 2);
assert(distances.find(std::make_tuple(3, 4))->second == 3);
assert(distances.find(std::make_tuple(4, 4))->second == 4);
}
{
const std::vector<std::vector<MuseumItem>> museum =
{ { MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::GUARD, MuseumItem::OPEN },
{ MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN } };
LocAndDistMap distances = GetDistances(museum);
assert(distances.find(std::make_tuple(0, 0)) == distances.end());
assert(distances.find(std::make_tuple(1, 0))->second == 1);
assert(distances.find(std::make_tuple(2, 0))->second == 1);
assert(distances.find(std::make_tuple(3, 0)) == distances.end());
assert(distances.find(std::make_tuple(4, 0))->second == 1);
assert(distances.find(std::make_tuple(0, 1))->second == 1);
assert(distances.find(std::make_tuple(1, 1))->second == 2);
assert(distances.find(std::make_tuple(2, 1))->second == 2);
assert(distances.find(std::make_tuple(3, 1))->second == 1);
assert(distances.find(std::make_tuple(4, 1))->second == 2);
assert(distances.find(std::make_tuple(0, 2)) == distances.end());
assert(distances.find(std::make_tuple(1, 2)) == distances.end());
assert(distances.find(std::make_tuple(2, 2))->second == 1);
assert(distances.find(std::make_tuple(3, 2)) == distances.end());
assert(distances.find(std::make_tuple(4, 2)) == distances.end());
assert(distances.find(std::make_tuple(0, 3))->second == 2);
assert(distances.find(std::make_tuple(1, 3))->second == 1);
assert(distances.find(std::make_tuple(2, 3)) == distances.end());
assert(distances.find(std::make_tuple(3, 3))->second == 1);
assert(distances.find(std::make_tuple(4, 3))->second == 2);
assert(distances.find(std::make_tuple(0, 4))->second == 3);
assert(distances.find(std::make_tuple(1, 4))->second == 2);
assert(distances.find(std::make_tuple(2, 4))->second == 1);
assert(distances.find(std::make_tuple(3, 4))->second == 2);
assert(distances.find(std::make_tuple(4, 4))->second == 3);
}
}
Thursday, 2 June 2016
Dynamic Programming - String Decoder
1. Problem Description
This is a Facebook interview question for software engineers from careercup. Here is the original thread,
"
For ex. given string "123" we can form 3 string "abc"(1,2,3), "lc" (i.e 12,3), "aw"(1,23).
for string "1234" we have following possible combinations, I might be missing some of them but you get the idea
{12, 3, 4}
{1, 23, 4}
{1, 2, 3, 4}
- sachin323 May 16, 2016 in United States
2. Data Structure and Algorithm
Some contributors mentioned on the thread that this is a dynamic problem. In fact the sub-problem is also reasonably obvious to spot. Given an input of number string, for instance "567123432234543789", assume that at position i of this string. Any single number can always be mapped into letters (a-z), ranges from [1, 26], therefore one sub-problem will be finding the decoding of the rest string from i+1 to the end. The second sub-problem may or may not exist, depending on the value at i and its subsequent value in i+1. If they are ranging from [10, 26], representing [j, z], then the second sub-problem exists - find the decoding of i+2 to the rest of string. If they are ranging out of [10, 26], then does not exist a second sub-problem.
For instance "36......", at position "3" only has one sub-problem of "6......"; "2415......" at position "2" has two sub problems "425......" and "15......".
A special number in the number string is "0", because "0" does not represent any letter, [a, z]. Any problem starting with "0" does not have any sub-problems and it can be terminated because it has not valid decoding.
For instance any input number string starting with "0......", does not have any valid decoding to represent any letter string.
As usual, cache technique is used in my dynamic-programming solution. It takes the sub-problem, the number string, as the key and take how many ways of decoding as value.
3. C++ Implementation
The return value of function "StringDecoder(" will be either greater than 0 or less than 0. A return value greater than 0 indicates how many ways of decoding. And a negative return value indicates failure to find an decoding.
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <string>
#include <unordered_map>
bool ValidStringNumber(const std::string &plainText)
{
if (plainText.empty()) {
return false;
}
{
auto itEnd = plainText.end();
for (auto it = plainText.begin(); it != itEnd; ++it) {
if (*it > '9' || *it < '0') {
return false;
}
}
}
return true;
}
using StringDecoderMap = std::unordered_map<std::string, ptrdiff_t>;
ptrdiff_t StringDecoder_R(const std::string &number,
const std::string::const_iterator curIt,
StringDecoderMap& cache)
{
if (curIt == number.end()) {
return 1;
}
if (*curIt == '0') {
return -1;
}
auto itNext = curIt + 1;
if (itNext == number.end()) {
return 1;
}
const std::string key(curIt, number.end());
auto itFound = cache.find(key);
if (itFound != cache.end()) {
return itFound->second;
}
ptrdiff_t decodes = -1;;
ptrdiff_t tempCount = StringDecoder_R(number, itNext, cache);
if (tempCount >= 0) {
decodes = tempCount;
}
const std::string twoChars(curIt, curIt + 2);
if (atoi(twoChars.c_str()) <= 26) {
tempCount = StringDecoder_R(number, ++itNext, cache);
if (tempCount >= 0) {
if (decodes > 0) {
decodes += tempCount;
}
else {
decodes = tempCount;
}
}
}
cache.insert(std::make_pair(key, decodes));
return decodes;
}
ptrdiff_t StringDecoder(const std::string &number)
{
if (!ValidStringNumber(number)) {
return -1;
}
StringDecoderMap cacheMap;
return StringDecoder_R(number, number.begin(), cacheMap);
}
// ********************************************************************************
// Testing
// ********************************************************************************
#include <cassert>
void TestDecoder()
{
assert(StringDecoder("134a457") < 0);
assert(StringDecoder("100") < 0);
assert(StringDecoder("12") == 2);
assert(StringDecoder("123") == 3);
assert(StringDecoder("0123456789") < 0);
assert(StringDecoder("10123") == 3);
assert(StringDecoder("345") == 1);
assert(StringDecoder("1123") == 5);
assert(StringDecoder("5123") == 3);
}
This is a Facebook interview question for software engineers from careercup. Here is the original thread,
"
You are given a string "abc" which is encoded like "123" where alphabets are mapped like a => 1 to z => 26. Now find out how many string can be formed by reverse engineering encode string "123".
For ex. given string "123" we can form 3 string "abc"(1,2,3), "lc" (i.e 12,3), "aw"(1,23).
for string "1234" we have following possible combinations, I might be missing some of them but you get the idea
{12, 3, 4}
{1, 23, 4}
{1, 2, 3, 4}
2. Data Structure and Algorithm
Some contributors mentioned on the thread that this is a dynamic problem. In fact the sub-problem is also reasonably obvious to spot. Given an input of number string, for instance "567123432234543789", assume that at position i of this string. Any single number can always be mapped into letters (a-z), ranges from [1, 26], therefore one sub-problem will be finding the decoding of the rest string from i+1 to the end. The second sub-problem may or may not exist, depending on the value at i and its subsequent value in i+1. If they are ranging from [10, 26], representing [j, z], then the second sub-problem exists - find the decoding of i+2 to the rest of string. If they are ranging out of [10, 26], then does not exist a second sub-problem.
For instance "36......", at position "3" only has one sub-problem of "6......"; "2415......" at position "2" has two sub problems "425......" and "15......".
A special number in the number string is "0", because "0" does not represent any letter, [a, z]. Any problem starting with "0" does not have any sub-problems and it can be terminated because it has not valid decoding.
For instance any input number string starting with "0......", does not have any valid decoding to represent any letter string.
As usual, cache technique is used in my dynamic-programming solution. It takes the sub-problem, the number string, as the key and take how many ways of decoding as value.
3. C++ Implementation
The return value of function "StringDecoder(" will be either greater than 0 or less than 0. A return value greater than 0 indicates how many ways of decoding. And a negative return value indicates failure to find an decoding.
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <string>
#include <unordered_map>
bool ValidStringNumber(const std::string &plainText)
{
if (plainText.empty()) {
return false;
}
{
auto itEnd = plainText.end();
for (auto it = plainText.begin(); it != itEnd; ++it) {
if (*it > '9' || *it < '0') {
return false;
}
}
}
return true;
}
using StringDecoderMap = std::unordered_map<std::string, ptrdiff_t>;
ptrdiff_t StringDecoder_R(const std::string &number,
const std::string::const_iterator curIt,
StringDecoderMap& cache)
{
if (curIt == number.end()) {
return 1;
}
if (*curIt == '0') {
return -1;
}
auto itNext = curIt + 1;
if (itNext == number.end()) {
return 1;
}
const std::string key(curIt, number.end());
auto itFound = cache.find(key);
if (itFound != cache.end()) {
return itFound->second;
}
ptrdiff_t decodes = -1;;
ptrdiff_t tempCount = StringDecoder_R(number, itNext, cache);
if (tempCount >= 0) {
decodes = tempCount;
}
const std::string twoChars(curIt, curIt + 2);
if (atoi(twoChars.c_str()) <= 26) {
tempCount = StringDecoder_R(number, ++itNext, cache);
if (tempCount >= 0) {
if (decodes > 0) {
decodes += tempCount;
}
else {
decodes = tempCount;
}
}
}
cache.insert(std::make_pair(key, decodes));
return decodes;
}
ptrdiff_t StringDecoder(const std::string &number)
{
if (!ValidStringNumber(number)) {
return -1;
}
StringDecoderMap cacheMap;
return StringDecoder_R(number, number.begin(), cacheMap);
}
// ********************************************************************************
// Testing
// ********************************************************************************
#include <cassert>
void TestDecoder()
{
assert(StringDecoder("134a457") < 0);
assert(StringDecoder("100") < 0);
assert(StringDecoder("12") == 2);
assert(StringDecoder("123") == 3);
assert(StringDecoder("0123456789") < 0);
assert(StringDecoder("10123") == 3);
assert(StringDecoder("345") == 1);
assert(StringDecoder("1123") == 5);
assert(StringDecoder("5123") == 3);
}
Thursday, 26 May 2016
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,
"
".
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);
}
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);
}
}
Thursday, 5 May 2016
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,
"
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;
};
// ********************************************************************************
// 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);
}
}
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.
".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);
}
}
Wednesday, 27 April 2016
Merge X-way Sorted List
1. Problem Description
This is a Google interview question from careercup. Here is the origin thread
'
You can look at the condition in a different way too..
L[i] >= L[i-x]
Sort the list L.
- jss_777 March 30, 2016 in United States
2. Data Structure and Algorithm
As the input array meets this condition "L[i] < L[i+x]", literally we have x-way of sorted list as,
- Arr1: L[0] < L[X] < L[2X] < ......
- Arr2: L[1] < L[X+1] < L[2X+1] < L[3X+1] < ......
- Arr3: L[2] < L[X+2] < L[2X+2] < L[3X+1] < ......
......
- ArrX: L[X-1] < L[2X-1] < L[3X-1] < L[4X-1] < ......
Merge sorted arrays into a single one. It is not unfamiliar to us, as it is the last step of merging sort. In merging sort two sorted arrays with the size of window is merged into a bigger array (literally size of two window size). Keep sorting and merging of the smaller window and eventually sort and merge into the full size.
Coming back to this problem with X-way sorted array. There are two ways of tackling this Itproblem.
The 1st approach:
It is to use the exactly same idea as merge sort.
- Merge Arr1 and Arr2 to become a bigger size of new array Arr_A
- Merge Arr3 and Arr3 to become a bigger size of new array Arr_B
......
Now we have X/2 sorted arrays if X is an even number or X/2 + 1 sorted arrays now if X is an odd number. Keep the above process (merge Arr_A and Arr_B, merge Arr_C and Arr_D, ......) until merged into a single array.
The 2nd approach:
It is to merge X-way in one row directly into a single array. Keep taking the heads (the smallest value of Arr1, Arr2, .. ArrX) and find the least value.
- Initial heads (L[0], L[1], ......, L[X-1]
- Find the least value, say it is L[i], which is the least value of L (globally)
- New heads array (L[0], L[1], ..., L[i-1], L[i+X], L[i+1], ..., L[X-1]
- Find the least value in the new heads array, say it is L[j], which is the 2rd least value of L
Head arrays will reduce its size if L[j] hit the end of Arr_J
- Now replace L[j] with L[j+X] to form the new heads
- Keep the above two steps until exhaust the whole array
Implementation wise it is to use a min-heap (priority queue in C++) to take the header array. Each time to pop the head, L[i] (which is the least value in the heads array) and push its next, L[i+X] into the queue. This technique has been used in this post as well, Find the Nth Multiple Given a Set.
3. C++ Implementation
This implementation implements the 2nd approach with two option of data structure of L. One is linked list and another is an array (std::vector).
As the interview question stated that L is very large. The best approach is to do in-place sorting/merging. And this implementation is not an in-place solution.
// ********************************************************************************
// Implementation
// ********************************************************************************
#include "../DetectCircleInLinkedList/DetectCircleInLinkedList/LinkedListElement.h"
#include "../DetectCircleInLinkedList/DetectCircleInLinkedList/LinkedList.h"
#include <queue>
#include <vector>
template <typename T>
struct LLE_Comparator
{
bool operator() (LinkedListElement<T>* &lhs, LinkedListElement<T>* &rhs) {
return lhs->data > rhs->data;
}
};
template<typename T>
LinkedListElement<T>* AdvanceByX(LinkedListElement<T>* start, unsigned int X)
{
unsigned int step = 0;
while (start && step < X) {
start = start->next;
++step;
}
return start;
}
template <typename T>
void MergeXwaySortedLL(LinkedList<T> &input, const unsigned int X, LinkedList<T> &result)
{
using MinHeap = std::priority_queue<LinkedListElement<T>*, std::vector<LinkedListElement<T>*>, LLE_Comparator<T>>;
LinkedListElement<T> **head = input.Release();
if (!head || !(*head)) {
return;
}
unsigned int count = 0;
LinkedListElement<T> *temp = *head;
MinHeap topNodesOfXways;
// get first X nodes
while (count < X && temp) {
topNodesOfXways.push(temp);
temp = temp->next;
++count;
}
while (!topNodesOfXways.empty()) {
temp = topNodesOfXways.top();
result.PushBack(temp->data);
temp = AdvanceByX(temp, X);
topNodesOfXways.pop();
if (temp) {
topNodesOfXways.push(temp);
}
}
}
template <typename T>
struct ValueIndexPair{
ValueIndexPair(const T& val, size_t idx)
: value(val), index(idx)
{}
ValueIndexPair()
{}
T value;
size_t index;
};
template <typename T>
struct ArrE_Comparator
{
bool operator() (ValueIndexPair<T> &lhs, ValueIndexPair<T> &rhs) {
return lhs.value > rhs.value;
}
};
template <typename T>
std::vector<T> MergeXwaySortedArr(const std::vector<T> &arr, const unsigned int X)
{
using MinHeap = std::priority_queue<ValueIndexPair<T>, std::vector<ValueIndexPair<T>>, ArrE_Comparator<T>>;
const size_t LEN = arr.size();
if (X > LEN) {
return std::vector<T>();
}
// push first X into heap
MinHeap minHeap;
for (unsigned int count = 0; count < X; ++count) {
minHeap.push(ValueIndexPair<T>(arr[count], count));
}
std::vector<T> result;
result.reserve(LEN);
while (!minHeap.empty()) {
ValueIndexPair<T> &temp = minHeap.top();
result.push_back(temp.value);
if ((temp.index + X) < LEN) {
minHeap.push(ValueIndexPair<T>(arr[temp.index + X], temp.index + X));
}
minHeap.pop();
}
return result;
}
// ********************************************************************************
// Test
// ********************************************************************************
#include <cassert>
#include <array>
void Test_LL()
{
{
LinkedList<int> input;
LinkedList<int> result;
input.PushBack(1);
MergeXwaySortedLL(input, 1, result);
LinkedListElement<int> *head = *(result.Release());
LinkedListElement<int> *tail = *(result.ReleaseTail());
assert(head->data == 1);
assert(tail->data == 1);
}
{
LinkedList<int> input;
LinkedList<int> result;
const std::array<int, 16> data = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 };
for (auto iter = data.begin(); iter != data.end(); ++iter) {
input.PushBack(*iter);
}
MergeXwaySortedLL(input, 4, result);
LinkedListElement<int> *curNode = *(result.Release());
unsigned int count = 0;
while (curNode) {
assert(curNode->data == count);
curNode = curNode->next;
++count;
}
assert(count == 16);
}
}
void Test_Arr()
{
{
const std::vector<int> data = { 1, 3, 2, 4 };
std::vector<int> result = MergeXwaySortedArr(data, 5);
assert(result.empty() == true);
result = MergeXwaySortedArr(data, 2);
assert(result == std::vector<int>({ 1, 2, 3, 4 }));
}
{
const std::vector<int> data = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 };
std::vector<int> result = MergeXwaySortedArr(data, 17);
assert(result.empty() == true);
result = MergeXwaySortedArr(data, 4);
assert(result == std::vector<int>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}));
}
}
This is a Google interview question from careercup. Here is the origin thread
'
A list L is too big to fit in memory. L is partially sorted. Partially sorted in a specific way: x-sorted L[i] < L[i+x]. Any element is at most x indices out of position.
You can look at the condition in a different way too..
L[i] >= L[i-x]
Sort the list L.
2. Data Structure and Algorithm
As the input array meets this condition "L[i] < L[i+x]", literally we have x-way of sorted list as,
- Arr1: L[0] < L[X] < L[2X] < ......
- Arr2: L[1] < L[X+1] < L[2X+1] < L[3X+1] < ......
- Arr3: L[2] < L[X+2] < L[2X+2] < L[3X+1] < ......
......
- ArrX: L[X-1] < L[2X-1] < L[3X-1] < L[4X-1] < ......
Merge sorted arrays into a single one. It is not unfamiliar to us, as it is the last step of merging sort. In merging sort two sorted arrays with the size of window is merged into a bigger array (literally size of two window size). Keep sorting and merging of the smaller window and eventually sort and merge into the full size.
Coming back to this problem with X-way sorted array. There are two ways of tackling this Itproblem.
The 1st approach:
It is to use the exactly same idea as merge sort.
- Merge Arr1 and Arr2 to become a bigger size of new array Arr_A
- Merge Arr3 and Arr3 to become a bigger size of new array Arr_B
......
Now we have X/2 sorted arrays if X is an even number or X/2 + 1 sorted arrays now if X is an odd number. Keep the above process (merge Arr_A and Arr_B, merge Arr_C and Arr_D, ......) until merged into a single array.
The 2nd approach:
It is to merge X-way in one row directly into a single array. Keep taking the heads (the smallest value of Arr1, Arr2, .. ArrX) and find the least value.
- Initial heads (L[0], L[1], ......, L[X-1]
- Find the least value, say it is L[i], which is the least value of L (globally)
- New heads array (L[0], L[1], ..., L[i-1], L[i+X], L[i+1], ..., L[X-1]
- Find the least value in the new heads array, say it is L[j], which is the 2rd least value of L
Head arrays will reduce its size if L[j] hit the end of Arr_J
- Now replace L[j] with L[j+X] to form the new heads
- Keep the above two steps until exhaust the whole array
Implementation wise it is to use a min-heap (priority queue in C++) to take the header array. Each time to pop the head, L[i] (which is the least value in the heads array) and push its next, L[i+X] into the queue. This technique has been used in this post as well, Find the Nth Multiple Given a Set.
3. C++ Implementation
This implementation implements the 2nd approach with two option of data structure of L. One is linked list and another is an array (std::vector).
As the interview question stated that L is very large. The best approach is to do in-place sorting/merging. And this implementation is not an in-place solution.
// ********************************************************************************
// Implementation
// ********************************************************************************
#include "../DetectCircleInLinkedList/DetectCircleInLinkedList/LinkedListElement.h"
#include "../DetectCircleInLinkedList/DetectCircleInLinkedList/LinkedList.h"
#include <queue>
#include <vector>
template <typename T>
struct LLE_Comparator
{
bool operator() (LinkedListElement<T>* &lhs, LinkedListElement<T>* &rhs) {
return lhs->data > rhs->data;
}
};
template<typename T>
LinkedListElement<T>* AdvanceByX(LinkedListElement<T>* start, unsigned int X)
{
unsigned int step = 0;
while (start && step < X) {
start = start->next;
++step;
}
return start;
}
template <typename T>
void MergeXwaySortedLL(LinkedList<T> &input, const unsigned int X, LinkedList<T> &result)
{
using MinHeap = std::priority_queue<LinkedListElement<T>*, std::vector<LinkedListElement<T>*>, LLE_Comparator<T>>;
LinkedListElement<T> **head = input.Release();
if (!head || !(*head)) {
return;
}
unsigned int count = 0;
LinkedListElement<T> *temp = *head;
MinHeap topNodesOfXways;
// get first X nodes
while (count < X && temp) {
topNodesOfXways.push(temp);
temp = temp->next;
++count;
}
while (!topNodesOfXways.empty()) {
temp = topNodesOfXways.top();
result.PushBack(temp->data);
temp = AdvanceByX(temp, X);
topNodesOfXways.pop();
if (temp) {
topNodesOfXways.push(temp);
}
}
}
template <typename T>
struct ValueIndexPair{
ValueIndexPair(const T& val, size_t idx)
: value(val), index(idx)
{}
ValueIndexPair()
{}
T value;
size_t index;
};
template <typename T>
struct ArrE_Comparator
{
bool operator() (ValueIndexPair<T> &lhs, ValueIndexPair<T> &rhs) {
return lhs.value > rhs.value;
}
};
template <typename T>
std::vector<T> MergeXwaySortedArr(const std::vector<T> &arr, const unsigned int X)
{
using MinHeap = std::priority_queue<ValueIndexPair<T>, std::vector<ValueIndexPair<T>>, ArrE_Comparator<T>>;
const size_t LEN = arr.size();
if (X > LEN) {
return std::vector<T>();
}
// push first X into heap
MinHeap minHeap;
for (unsigned int count = 0; count < X; ++count) {
minHeap.push(ValueIndexPair<T>(arr[count], count));
}
std::vector<T> result;
result.reserve(LEN);
while (!minHeap.empty()) {
ValueIndexPair<T> &temp = minHeap.top();
result.push_back(temp.value);
if ((temp.index + X) < LEN) {
minHeap.push(ValueIndexPair<T>(arr[temp.index + X], temp.index + X));
}
minHeap.pop();
}
return result;
}
// ********************************************************************************
// Test
// ********************************************************************************
#include <cassert>
#include <array>
void Test_LL()
{
{
LinkedList<int> input;
LinkedList<int> result;
input.PushBack(1);
MergeXwaySortedLL(input, 1, result);
LinkedListElement<int> *head = *(result.Release());
LinkedListElement<int> *tail = *(result.ReleaseTail());
assert(head->data == 1);
assert(tail->data == 1);
}
{
LinkedList<int> input;
LinkedList<int> result;
const std::array<int, 16> data = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 };
for (auto iter = data.begin(); iter != data.end(); ++iter) {
input.PushBack(*iter);
}
MergeXwaySortedLL(input, 4, result);
LinkedListElement<int> *curNode = *(result.Release());
unsigned int count = 0;
while (curNode) {
assert(curNode->data == count);
curNode = curNode->next;
++count;
}
assert(count == 16);
}
}
void Test_Arr()
{
{
const std::vector<int> data = { 1, 3, 2, 4 };
std::vector<int> result = MergeXwaySortedArr(data, 5);
assert(result.empty() == true);
result = MergeXwaySortedArr(data, 2);
assert(result == std::vector<int>({ 1, 2, 3, 4 }));
}
{
const std::vector<int> data = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 };
std::vector<int> result = MergeXwaySortedArr(data, 17);
assert(result.empty() == true);
result = MergeXwaySortedArr(data, 4);
assert(result == std::vector<int>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}));
}
}
Subscribe to:
Posts (Atom)