Geek Answers Handbook

Given the array and series of queries for the `ij` indexes, how do you know which index was most frequently requested?

Given an array A indexed from 0 to n-1 , where n is the size of the array, and a series of queries of the form ij , where i and j indicate the indices ( i and j inclusive), how do you know which index was the largest number of queries more efficient?

For example, consider an array [3,4,5,6,7,9]

And requests

 0 3 3 5 1 2 2 4 Output Index 0 has been queried 1 time. Index 1 has been queried 2 times. Index 2 has been queried 3 times. Index 3 has been queried 3 times. Index 4 has been queried 2 times. Index 5 has been queried 1 time.

How to do it as quickly as possible?

+6
source share
4 answers

You can do this in O (n + q), where n is the size of the array and q is the number of queries:

  • Make an empty array A with n elements
  • For each request i, j, increase A [i] by 1 and decrease A [j + 1] by 1
  • Loop over an array calculating the total amount and tracking the index with the highest total total value

The total amount will contain +1 for each interval where we saw the beginning, and -1 for each interval where we saw the end. This means that the total will count the current open intervals or, in other words, the number of requests that have been requested.

+9
source

You can use the interval tree to store all your queries (building a tree takes O(nlogn) time), and then check each array and enter the number of intervals ( O(log n) ).

A more naive, but still effective approach would be to use an auxiliary array A size n (all entries initialized to 0) for each request:

 for (int k = i; k <= j; k++) A[k]++;

And then just print the array.

+1
source 
  1) Sort all the times in the given queries. O(q log q) 2) num_times_queried[times[i]]=num_queries_started_till[times[i]]-num_queries_ended_till[times[i]-1] num_queries_started/ended_till(x) can be found in log q using binary search.

O (q log q + n log q)

0
source

There are several possible measures: access execution and any processing performed while it is “free”; you want to receive an invoice when everything is done efficiently; or you need to consider processing during access and the final search.

In the first case, configure the priority queue and delete each of them as they become available. The final step in getting the most affordable value is constant.

In the second case, you cannot do better than counting each access for each index (linear in the number of hits), and in the end go through the calculations to select the largest (linear in the number of indices, presumably less than the number of hits).

0
source

More articles:


All Articles