This is an Amazon interview question for software develop engineer at the 2nd round face-to-face from careercup. Here is the original thread,
Q1) Given an array 'A' of size 'n' and a number 'm' such that 'm <= n'. For all subsets of 'A' of size 'm', return the difference between the number of non-increasing and non-decreasing sub-sequences.
He asked me to write the program on paper in any language.
This is how i approached it.
1) First i gave the brute force solution and explained it to him. He liked it.
2) Then he asked for the complexity of the solution. I gave right ans.
3) Then i told him that it can be optimized by 'xyz' approach.
4) Then he asked me if i can write the solution. I said i will first explain him how it can be solved. Then if he wants me to write the code, he will have to leave me alone for some time. He agreed. I explained.
5) There was a bug in my solution. He gave a test case that exposed it. Then i rectified the bug. He accepted.
6) He said that it. He does not need the full code.
2. Data Structure And Algorithm
There is not really much to talk about the data structure. Simply use array to represent the input sequence. The key point here is the algorithm - namely the complexity. This is a combination problem for given m and n. The total number of possible sequences is C(n, m) - pick up m from n, where C(n, m) = n!/(m! * (n-m)!). Therefore theoretically it has computation complexity of O(N!) - factorial complexity. It should absolutely avoided in implementation.
It is an combination problem and likely dynamic programming is a good candidate to solve it. Here we are only caring about ascending and descending sequences. In order to form a sequence m must be greater than 1 and not greater than n. m's range is [2, n]. In order to know if this sequence is ascending or descending the starting two digits are to decide its ascending/descending order. Suppose that we know the first two digits of the sequence x, y and the index, i, of next available digit in the array. Then the sub-problem can be described as,
- F(N, x, y, i) , where N = m -2, i <= (n-m+2)
* F(N-1, y, arr[i], i+1) if x < y and y < arr[i] (ascending order sequence candidate)
* F(N-1, y, arr[i], i+1) if x > y and y > arr[i] (descending order)
* 0, neither an ascending sequence nor a descending sequence
- F(0, r, s, t) = 1
Again dynamic programming help us to solve the problem but does not help us to reduce the complexity. In this case the caching technique is employed to cache the result to avoid the repeated computation. See the examples in Dynamic Programming - Stock Best Buy and Sell Problem: Google Interview Question and Dynamic programming - Sum K of N dices with S sides. Two caching repositories are needed - one for ascending order sequence and another for descending order sequence. The hash key is pair of (i, N) - the index of the current available number in the array and the length of the remaining of sequence. The cache technique requires O(n*m) space. In the best case it can achieve O((n-m)^2) computation complexity.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <exception>
#include <unordered_map>
#include <vector>
class InvalidParamException : public std::exception
{
public:
InvalidParamException(const std::string & msg)
: m_msg(msg)
{}
const char* what() const {
return m_msg.c_str();
}
private:
const std::string m_msg;
};
struct HashKey
{
size_t idx;
size_t remainingSeqLen;
bool operator==(const HashKey& rhs) const {
return idx == rhs.idx && remainingSeqLen == rhs.remainingSeqLen;
}
};
struct HashKeyHashFunc
{
size_t operator()(const HashKey &key) const {
return std::hash<size_t>()(key.idx) ^
std::hash<size_t>()(key.remainingSeqLen);
}
bool operator()(const HashKey &lhs, const HashKey &rhs) const {
return lhs == rhs;
}
};
using HashMap = std::unordered_map<HashKey, int, HashKeyHashFunc, HashKeyHashFunc>;
template <typename T>
int DetectAscendingOrDescendingSequence(const std::vector<T> &input,
const size_t input_size,
const size_t idx,
const bool isAscending,
size_t m,
HashMap &cacheAscending,
HashMap &cacheDescending)
{
if (!m) {
// F(0, r, s, t) return 1
return 1;
}
// Return the cached value if it's a repeated computation
if (isAscending) {
auto foundIter = cacheAscending.find(HashKey{ idx, m });
if (foundIter != cacheAscending.end()) {
return foundIter->second;
}
}
else {
auto foundIter = cacheDescending.find(HashKey{ idx, m });
if (foundIter != cacheDescending.end()) {
return foundIter->second;
}
}
int numSeq = 0;
for (size_t i = idx; i <= (input_size - m); ++i) {
// Continue the sub-problem if sequence's order is maintained
// Check next available digits if the order is broken
if ( (isAscending && input[idx - 1] < input[i]) ||
(!isAscending && input[idx - 1] > input[i])) {
numSeq += DetectAscendingOrDescendingSequence(input,
input_size,
i + 1,
isAscending,
m - 1,
cacheAscending,
cacheDescending);
}
}
// cache the result
if (isAscending) {
cacheAscending.insert(std::make_pair(HashKey{ idx, m }, numSeq));
}
else {
cacheDescending.insert(std::make_pair(HashKey{ idx, m }, numSeq));
}
return numSeq;
}
template <typename T>
int GetDiffOfAscendingAndDescedningSequence(const std::vector<T> &input, size_t m)
{
if (m < 2) {
throw InvalidParamException("The length of sequence MUST be >= 2.");
}
if (input.empty()) {
throw InvalidParamException("The input array is empty.");
}
const size_t INPUT_LEN = input.size();
if (INPUT_LEN < m) {
throw InvalidParamException("The length of sequence must be <= the length of input array.");
}
int numOfAscending = 0;
int numOfDescening = 0;
bool isAscending;
int temp;
HashMap CacheAscendingSeq;
HashMap CacheDescedningSeq;
for (size_t idx1 = 0; idx1 <= INPUT_LEN - m; ++idx1) {
for (size_t idx2 = idx1 + 1; idx2 <= (INPUT_LEN - m + 1); ++idx2) {
// First two digits in the sequence to decide ascending/descending
isAscending = input[idx1] < input[idx2];
temp = DetectAscendingOrDescendingSequence(input,
INPUT_LEN,
idx2 + 1,
isAscending,
m - 2,
CacheAscendingSeq,
CacheDescedningSeq);
if (isAscending) {
numOfAscending += temp;
}
else {
numOfDescening += temp;
}
}
}
return numOfAscending - numOfDescening;
}
// ********************************************************************************
// Test
// ********************************************************************************
#include <cassert>
void TestFindDiffOfAscAndDescSeq()
{
{
bool exceptionCaught = false;
try {
const std::vector<int> input;
GetDiffOfAscendingAndDescedningSequence(input, 2);
}
catch (const InvalidParamException &e) {
exceptionCaught = true;
}
catch (...)
{
}
assert(exceptionCaught == true);
exceptionCaught = false;
try {
const std::vector<int> input = { 1, 2, 3 };
GetDiffOfAscendingAndDescedningSequence(input, 1);
}
catch (const InvalidParamException &e) {
exceptionCaught = true;
}
catch (...)
{
}
assert(exceptionCaught == true);
exceptionCaught = false;
try {
const std::vector<int> input = { 1, 2, 3 };
GetDiffOfAscendingAndDescedningSequence(input, 4);
}
catch (const InvalidParamException &e) {
exceptionCaught = true;
}
catch (...)
{
}
assert(exceptionCaught == true);
exceptionCaught = false;
try {
const std::vector<int> input = { 1, 2, 3 };
GetDiffOfAscendingAndDescedningSequence(input, 1);
}
catch (const InvalidParamException &e) {
exceptionCaught = true;
}
catch (...)
{
}
assert(exceptionCaught == true);
}
{
const std::vector<int> input = { 1, 2, 3, 4, 5, 6, 7, 8 };
assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == 28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == 56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == 70);
assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == 56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == 28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == 8);
assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == 1);
}
{
const std::vector<int> input = { 8, 7, 6, 5, 4, 3, 2, 1 };
assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == -28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == -56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == -70);
assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == -56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == -28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == -8);
assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == -1);
}
{
const std::vector<int> input = { 8, 7, 6, 5, 4, 3, 2, 1, 11, 12, 13, 14, 15, 16, 17, 18 };
assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == 8*8);
assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == 8*28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == 8*56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == 8*70);
assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == 8*56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == 8*28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == 8*8);
assert(GetDiffOfAscendingAndDescedningSequence(input, 9) == 8);
assert(GetDiffOfAscendingAndDescedningSequence(input, 10) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 11) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 12) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 13) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 14) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 15) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 16) == 0);
}
}
