Streaming quality

See the original problem on HackerRank.

Solutions

The naive solution involves storing each number into the buffer and calculating the product when requested:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class NaiveStreamingQualityAnalyzer 
{
public:
    void add(int num) 
    {
        stream.push_back(num);
    }

    int get(int k) 
    {
        int product = 1;
        for (auto i = ssize(stream)-k; i < ssize(stream); ++i) 
        {
            product *= stream[i];
        }
        return product;
    }
private:
    std::vector<int> stream;
};

int main() 
{
    int n, i, j; 
    cin >> n;
    NaiveStreamingQualityAnalyzer stream;
    while (n--)
    {
        cin >> i >> j;
        if (i == 1)
        {
            stream.add(j);
        }
        else
        {
            cout << stream.get(j) << "\n";
        }
    }
}

NaiveStreamingQualityAnalyzer::get might be rewritten in terms on standard algorithms:

1
2
3
4

int get(int k) 
{    
    return std::accumulate(prev(end(stream), k), end(stream), 1, multiplies<>{});
}

However, this solution proves to be excessively slow, resulting in a timeout for one test case. The issue lies in the fact that whenever a product operation is requested, the algorithm iterates through all the last K elements to compute the product. The complexity of this approach is in the order of \(O(N \cdot K) \). We need to find a solution that does not involve calculating this product every time.

A more effective approach leverages the problem’s constraints and employs a classical pattern.

As per the problem statement, the product of any contiguous sequence of numbers can fit into a single 32-bit integer without overflowing. Hence, it’s safe to compute the product during every add operation. A pattern comes to the rescue: prefix sum. Indeed, we can maintain the running product of the elements rather than storing the elements themselves. This way, we can calculate the product of any subarray in constant time. In particular, the product of the last K numbers is simply (pseudo-code):

1

prod_last_k = buffer[last] / buffer[last - k];

For example, suppose we have these numbers in the buffer:

1

1 2 4 2 3

Here is the running product:

1

1 2 8 16 48

The product of the last 2 elements (2 * 3 = 6) is:

1

prod_last_2 = 48 / 8 = 6

The product of the last 4 elements (2 * 4 * 2 * 3 = 48) is:

1

prod_last_4 = 48 / 1 = 48

The only problem with this approach is the presence of zeros: indeed, when the first 0 is added to the buffer, it perpetually sets the running product to zero. Instead, we can do the following trick: when a 0 is added, we empty and reset the buffer to the initial state. In this case, if a get operation is requested, the algorithm will yield 0 as expected (because the last value added was 0). It will do it by checking the size of the current buffer against K. In this regard, it’s practical to initialize the buffer as {1}, this way both the running product and the check of the size would be simplified.

Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class StreamingQualityAnalyser 
{
public:
    StreamingQualityAnalyser() 
        : m_data{ 1 }
    {
    }

    void add(int num)
    {
        if (num != 0)
        {
            m_data.push_back(num * m_data.back());
        }
        else
        {
            m_data = { 1 };
        }
    }

    int get(int k)
    {
        if (k < ssize(m_data))
	        return m_data.back() / m_data[m_data.size() - k - 1];
        return 0;
    }
private:
    vector<int> m_data;
};

Finally, get is constant time and add is “amortized constant” (if push_back reallocates, it’s linear in the entire size, but chances decrease as the size increases).

In case HackerRank does not support ssize yet, replace it with static_cast<int>(m_data.size()).