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