Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Time series queries challenge

Sharing is caring!

Problem statement
A time series is a series of data points indexed in time order. They are commonly used in the financial world, especially in stock markets.

In this challenge you are working with a time series of stock prices. You are given n historical records (t_i, p_i) where the stock at time t_i had a price p_i. You have to answer 2 types of q queries of the form :

  1. For type 1, given a value v, when was the first time that the price of the stock was at least v?

  2. For type 2, given a value v, what’s the maximum price of the stock at a time greater or equal to v?

If for any of these queries the answer is not defined, i.e. there are no historical records that match the query, the answer is -1.

Input Format
In the first line, there are two space-separated integers n and q denoting the number of historical records and the number of queries, respectively.

The second line contains n space-separated integers denoting the time-stamps t. The next line contains n space-separated integers denoting the price of stock p, where i^{th} value corresponds to the i^{th} time-stamp.

Next, q lines follow and each of them describes a single query. Each query is given as two space-separated integers. The first of them is either 1 or 2 and denotes the type of the query followed by a single integer v denoting the value to be queried.

Constraints
1 \le n \le 10^5
1 \le q \le 10^5
1 \le t_i \le 10^9
1 \le p_i \le 10^9
1 \le v \le 10^9
t_i \textless t_{i+1}\ for\ 0 \le i \textless n - 1

Output Format
For each of the q queries, print the answer on a new line. If the answer is not defined, print -1.

Sample Input 0

Sample Output 0

Explanation 0
In the sample, there are 5 data records and 5 queries to answer. At time 1 the price was 5, at time 2 the price was 3, at time 4 the price was 12, at time 8 the price was 1, and finally, at time 10 the price was 10.

In the first query, we are asked for the minimum time at which the price was at least 10. The answer is 4 because at this time the price was 12 and there is no earlier time with a price at least 10.

In the second query, we are asked for the minimum time at which the price was at least 4. The answer is 1 because the price at this time was 5 which is greater than 4.

In the third query, we are asked for the maximum price at time 8 or greater. The answer is 10 because there are two data records with time at least 8 and the highest price among them is 10.

In the fourth query, we are asked for the maximum price at time 3 or greater. The answer here is 12.

In the last query, we are asked for the minimum time at which the price was at least 13. Since there is no data record with price 13 or greater, the answer is -1.

Solution
For the algorithm we will use a Binary Search Tree for query type 1 and Binary Search in range for query type 2.

So lets go ahead and implement a very simple Binary Search Tree (BST) data structure:

The BST implementation will take the price of a stock as a key and the time as value. It also has a toString() method to pretty print our BST and a search(int v) method to return the first value of a node that has key >= v. This will answer any queries of type 1. We then go on to implement a helper function that constructs a BST from our given arrays t and p:

For queries of type 2 we will use a simple Binary Search with range algorithm on our time array t. That is, we will search t for first t[i] with t[i] >= v and return i:

We also construct a precomputed array, maxPriceFromIndex, with maxPriceFromIndex[i] holding the maximum price starting from index i till index n-1:

Finally, we can combine the two algorithms to get our solution to the problem:

The full source code to the problem is listed below. It also includes a brute force solution.

Full code