Quora Challenges are basically a set of programming problems posted on the website, used as like a backdoor of recruiting. Rumor has it that whoever can solve one of these would guarantee an interview with Quora, skipping the resume selection process.

## Problem Statement

At Quora, we have aggregate graphs that track the number of upvotes we get each day. As we looked at patterns across windows of certain sizes, we thought about ways to track trends such as non-decreasing and non-increasing subranges as efficiently as possible.

For this problem, you are given N days of upvote count data, and a fixed window size K. For each window of K days, from left to right, find the number of non-decreasing subranges within the window minus the number of non-increasing subranges within the window.

A window of days is defined as contiguous range of days. Thus, there are exactly N−K+1 windows where this metric needs to be computed. A non-decreasing subrange is defined as a contiguous range of indices [a, b], a < b, where each element is at least as large as the previous element. A non-increasing subrange is similarly defined, except each element is at least as large as the next. There are up to K(K − 1) / 2 of these respective subranges within a window, so the metric is bounded by [−K(K−1) / 2, K(K − 1) / 2].

Quora Challenges

## Approach

• The problem is asking for the number of subranges, not the longest subranges. For example, [1, 2, 3] has 3 non-decreasing ranges [1, 2], [2, 3], [1, 3]. Therefore the common approach of iterating a pointer through the window while counting subrange length until comparison condition breaks is not valid. Instead, we need to generate a list of all the subranges in a window and count the combination of them. For example, a 10 day non-decreasing subrange has 9 + 8+ 7+ 6 + 5 + 4 + 3 + 2 + 1 = 45 non-decreasing subranges.

• We could do a Brute Force algorithm of computing the number of subranges separately for each window and loop the algorithm through every window. But the algorithm for the subranges would be O(K) within a window since it has to touch each element in the window at least once. The entire algorithm would then be O(K(N - K + 1)) = O(KN), which is way to slow.

• Instead, we can compute the number of subranges for the first window and update those subranges. The update is very efficient O(1) since we are just removing an element in the back and adding an element in the front and we just need to do a constant amount of comparisons to update the front and back subranges.

## Code

All 29 test cases passed!

## Potential Areas of Improvement

• Maybe a window can be scanned once for both non-decreasing subrange and non-increasing subrange by keeping track of more pointers. I am not certain, without giving much thought.

• Maybe the updating of both non-decreasing subrange and non-increasing subrange can be done simultaneously.