This is a Google Interview Question for Software Engineer/Developer from careercup. The following is the original description of the thread.
"given a vector of integers, v[i] represent the stock price on day i. Now you may do at most K transactions. you must sell your stock before you buy it again and that means you can NOT have two stocks at the same time. write a program to find max profit you can get."
2. Mathematical Analysis
As some of contributors on this thread have pointed out, the problem is not very clear and people have different understanding, for instance if holding stock initially, what one transaction means and so on. Here I would like to make the following assumptions and be absolutely clear about what I am discussing in this blog entry
Assumptions:
- Don't hold stack at the beginning
- Hold cash only at the beginning
- One transaction: buy-then-sell
- K transaction: do buy-then-sell K times
- Hold cash only and no stocks at the end of day
- Data V - v[i] represents the price/ticks in the timeline.
Let's give the data a time scale, for instance intra-day stock ticks. (Obviously this falls into a technical trading techniques). When the price goes down to the local bottom, this is a buying opportunity. And when the price goes up to the local top, this is a selling opportunity. Combine this local bottom and local top together is an opportunity to make some profit. Or in this question the price going from the local bottom to the local top is a candidate of transaction to make profit.
As the price fluctuates, each bottom-top rising is the candidate of transaction to make profit. Assume that the data given shows N opportunities to make profit and we are given K transactions. The problem is clearly to make the most of the profit of K transactions out of N opportunities. And this is maximal optimization problem.
The input data V represents the price/ticks in the time line. And assume along the time V presents N opportunities to make profit. Let's represent each opportunity (the candidate of transactions) with a bottom price/tick and top price/tick as (Bi, Ti), where i is within [0, N-1]. They are constrained on time, Time at B0 is earlier than Time at T0, which is earlies than B1, which is earlier than T1, .... Except this constraint B0 < T0, T0 > B1, B1 < T1, T1 > B2, ......
Analysis:
When K >= N, then it is simple because this is maximization problem and we would like to take each opportunities to take profit. So the maximal profit is Sigman(Ti-Bi), where i is from 0 to N-1.
When K < N, then it is not that simple as some contributors suggested that simply pick up the most K profitable opportunities from N and then this problem can be solved by heap sort with K top values. Why is it not simple? Because when K < N, the neighbor opportunities can be combined together to become even bigger opportunities, which makes more profit than both individually. For instance, N=2 opportunities (1, 3) and (2, 5), and K=1 transaction. Then the profit we can make is not 5-2=3, but 5-1=4. In this example we need to find global bottom and top to make the most profit. Therefore when K < N, we have to explore all the combinations of all possible merging of neighbor opportunities to get the most profit. For instance N opportunities and K=N-1 transactions, we need to check each combination of 2 neighbor opportunities.
- Merge 0 and 1 to get N-1 opportunities and N-1 transactions
- Merge 1 and 2 to get N-1 opportunities and N-1 transactions
......
- Merge N-2 and N-1 to get N-1 opportunities and N-1 transactions
- Take the maximal value above N-1 combinations.
3. Dynamic Programming Solution
Here I would like to discuss how to solve the above K<N case via dynamic programming. Assume that we have N opportunities (Bi, Ti), where i is within [0, N-1] and have K transactions where K is less than N.
- F(N, K) = T0 - B0 + F(N-1, K-1), take first opportunity as one transaction
- F(N, K) = Max(T0, T1) - Min(B0, B1) + F(N-2, K-1), take the first two opportunities combined
as one opportunity
- F(N, K) = Max(T0, T1, T2) - Min(B0, B1, B2) + F(N-3, K-1), take the fist 3 opportunities
combined as one opportunity
......
- F(N, K) = Max(Tj) - Min(Bj) + F(N-K+1, K-1), take the first (N-K+1) opportunities combined as
one opportuinity, where j is within [0, N-K]
And this is an maximization problem and the maximal value above should be returned.
- F(N, K) = Max{Max(Tj) - Min(Bj) + F(N-i, K-1)},
where i is within [0, N-K] and j is within [0, i-1]
Corner case:
When K >= N, return sum of profits of all opportunities.
4. Complexity Analysis
When K >= N, it takes linear time to compute the sum of profits of all opportunities. Let's take a look at the case of K < N.
- K = N-1; combine two opportunities next to each other, we have N-1 opportunities and K=N-1
N' = (N-1), then K = N' and it's a corner case
- K = N-2,
* Combine 2 opportunities next to each other, we have N-1 opportunities and K = N-2,
N'=(N-1) and K = N'-1
* Now combine 2 neighbor opportunities out of N' into one opportunity, we have N'-1
opportunities. N'' = (N'-1) = (N-2) = K, It's a corner case now
* There are repetitive cases. For instance combine 1,2 and 3 together have two choice, 1, 2
first then 3, or 2, 3 first and then 1.
* So all together we need to examine (N-1)(N'-1)/2 = (N-1)(N-2)/2 possible choice to find the
maximal return.
- K = N- 3,
* Combine opportunities in 3 steps, (N-1)(N-2)(N-3)
* Repetitive cases: combine 1, 2, 3, 4 together, then we have 6 choices
> 1,2 first, then 3 and then 4
> 3, 4 first then 2 and then 1
> 1, 2 first then 3, 4 second, then combine two combinations
> 3, 4 first then 1, 2 second, then combine two combinations
> 2, 3 first then 1 and then 4
> 2, 3 first then 4 and then 1
* Complexity: (N-1)(N-2)(N-3)/6 = (N-1)(N-2)(N-3)/(3*2*1)
......(use induction theory)
- K = N-X. The complexity will be (N-1)(N-2)...(N-X)/X! = N!/(N*(N-X-1)!*X!)
= N!/(N*(K-1)!*(N-K)!) = (K/N)*(N!/(K!*(N-K)!) = K/N * C(N,K), where
C(N, K) is called combination with value of N!/(K!*(N-K)!) (See combination[1][2])
The above analysis also provides good evidence to use caching technique to prevent the repetitive cases computing again.
5. C++ Implementation
- Dynamic programming solution
- Use caching technique
// ********************************************************************************
// IMPLEMENTATION
// ********************************************************************************
#include <limits>
#include <numeric>
#include <unordered_map>
#include <vector>
struct BuySellEntry
{
BuySellEntry()
{}
BuySellEntry(size_t buy, size_t sell) :
ticksToBuy(buy), ticksToSell(sell)
{}
BuySellEntry(const BuySellEntry& other) :
ticksToBuy(other.ticksToBuy),
ticksToSell(other.ticksToSell)
{}
BuySellEntry(const BuySellEntry&& other) :
ticksToBuy(std::move(other.ticksToBuy)),
ticksToSell(std::move(other.ticksToSell))
{}
size_t ticksToBuy = 0;
size_t ticksToSell = 0;
};
struct HashKeyPair
{
HashKeyPair(size_t i, size_t k) :
index(i), kAttemp(k)
{}
bool operator==(const HashKeyPair& rhs) const {
return index == rhs.index && kAttemp == rhs.kAttemp;
}
size_t index{ std::numeric_limits<size_t>::max() };
size_t kAttemp{ std::numeric_limits<size_t>::min() };
};
struct HashKeyPairHashFunc
{
size_t operator()(const HashKeyPair& hKey) const {
return std::hash<size_t>()(hKey.index) ^
std::hash<size_t>()(hKey.kAttemp);
}
bool operator()(const HashKeyPair& lhs, const HashKeyPair& rhs) const {
return lhs == rhs;
}
};
using HashMap = std::unordered_map<HashKeyPair, size_t, HashKeyPairHashFunc, HashKeyPairHashFunc>;
std::vector<BuySellEntry> DetectBuySellEntries(const std::vector<size_t> ticks,
std::vector<size_t>& profit)
{
const auto sizeOfData = ticks.size();
std::vector<BuySellEntry> BSE;
if (sizeOfData == 0) {
return BSE;
}
BSE.reserve(sizeOfData);
profit.clear();
profit.reserve(sizeOfData);
size_t buy;
for (size_t index = 1; index < sizeOfData; ++index) {
if (ticks[index] > ticks[index - 1]) {
buy = ticks[index - 1];
for (; index < sizeOfData; ++index) {
if (index == (sizeOfData - 1) || ticks[index] > ticks[index + 1]) {
BSE.push_back(BuySellEntry{ buy, ticks[index] });
profit.push_back(ticks[index] - buy);
break;
}
}
}
}
return BSE;
}
size_t BestBuySell_DP(const std::vector<BuySellEntry>& BSE,
const std::vector<size_t>& profit,
const size_t startIndex,
const size_t kAttemps,
HashMap& cache)
{
if (BSE.empty() || kAttemps == 0 || startIndex == BSE.size()) {
return 0;
}
if (kAttemps >= (BSE.size() - startIndex)) {
return std::accumulate(profit.begin() + startIndex, profit.end(), 0);
}
// cached?
const HashKeyPair key = { startIndex, kAttemps };
{
auto foundCIter = cache.find(key);
if (foundCIter != cache.end()) {
return foundCIter->second;
}
}
// DP
auto minBuyTick = std::numeric_limits<size_t>::max();
auto maxSellTick = std::numeric_limits<size_t>::min();
auto totalProfit = std::numeric_limits<size_t>::min();
size_t tempProfit;
for (auto index = startIndex; index < BSE.size(); ++index) {
if (BSE[index].ticksToBuy < minBuyTick) {
minBuyTick = BSE[index].ticksToBuy;
}
if (BSE[index].ticksToSell > maxSellTick) {
maxSellTick = BSE[index].ticksToSell;
}
tempProfit = maxSellTick - minBuyTick +
BestBuySell_DP(BSE, profit, index + 1, kAttemps - 1, cache);
if (tempProfit > totalProfit) {
totalProfit = tempProfit;
}
}
// cache it
cache.insert(HashMap::value_type(key, totalProfit));
return totalProfit;
}
size_t BestBuySell(const std::vector<size_t>& ticks, const size_t kAttemps)
{
if (ticks.empty() || kAttemps == 0) {
return 0;
}
std::vector<size_t> profit;
auto BSE = DetectBuySellEntries(ticks, profit);
HashMap cache;
return BestBuySell_DP(BSE, profit, 0, kAttemps, cache);
}
// ********************************************************************************
// TEST
// ********************************************************************************
#include <cassert>
void TestCases()
{
{
std::vector<size_t> ticks = { 1, 2, 3, 4, 5, 6, 7 };
// BuySellEntries: (1, 7)
assert(BestBuySell(ticks, 0) == 0);
assert(BestBuySell(ticks, 1) == 6);
assert(BestBuySell(ticks, 2) == 6);
}
{
std::vector<size_t> ticks = { 1, 2, 3, 4, 2, 6, 7 };
// BuySellEntries: (1, 4), (2, 7)
assert(BestBuySell(ticks, 0) == 0);
assert(BestBuySell(ticks, 1) == 6);
assert(BestBuySell(ticks, 2) == 8);
assert(BestBuySell(ticks, 3) == 8);
}
{
std::vector<size_t> ticks = { 1, 2, 3, 4, 2, 6, 7, 2, 4, 6};
// BuySellEntries: (1, 4), (2, 7), (2, 6)
assert(BestBuySell(ticks, 0) == 0);
assert(BestBuySell(ticks, 1) == 6);
assert(BestBuySell(ticks, 2) == 10);
assert(BestBuySell(ticks, 3) == 12);
assert(BestBuySell(ticks, 4) == 12);
}
{
std::vector<size_t> ticks = { 1, 2, 3, 4, 2, 6, 7, 2, 4, 6 , 1, 5, 9};
// BuySellEntries: (1, 4), (2, 7), (2, 6), (1, 9)
assert(BestBuySell(ticks, 0) == 0);
assert(BestBuySell(ticks, 1) == 8);
assert(BestBuySell(ticks, 2) == 14);
assert(BestBuySell(ticks, 3) == 18);
assert(BestBuySell(ticks, 4) == 20);
assert(BestBuySell(ticks, 5) == 20);
}
{
std::vector<size_t> ticks = { 4, 3, 2, 5, 4, 6, 7, 1, 7, 8, 5, 6 };
// BuySellEntries: (2, 5), (4, 7), (1, 8), (5, 6)
assert(BestBuySell(ticks, 0) == 0);
assert(BestBuySell(ticks, 1) == 7);
assert(BestBuySell(ticks, 2) == 12);
assert(BestBuySell(ticks, 3) == 13);
assert(BestBuySell(ticks, 4) == 14);
assert(BestBuySell(ticks, 5) == 14);
}
}
// ********************************************************************************
Bibliography:
[1] Donald E. Knuth "The Art of Computer Programming", Volume 1, Fundamental Algorithms, Third Edition
[2] Donald E. Knuth "The Art of Computer Programming", Volume 2, Seminumerical Algorithms, Third Edition
No comments:
Post a Comment