There are ‘N’ horses running in ‘N’ different lanes numbered from 1 to ‘N’. You are given an array “FINISHTIME” containing ‘N’ integers where “FINISHTIME[i]” represents the time taken by the ith horse to complete the race.
You are now given ‘Q’ queries, each containing two integers each, ‘L’ and ‘R’. For each query, return the time taken by the fastest horse amongst the horses with numbers {L, L + 1, L + 2, …., R - 1, R} to complete the race.
Note:
The fastest horse is the one that takes the minimum time to finish the race.
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains two space-separated integers ‘N’ and ‘Q’ that denote the number of horses and number of queries respectively.
The second line of each test case contains ‘N’ space-separated integers, denoting the time taken by each horse to complete the race.
The next ‘Q’ lines contain two space-separated integers ‘L’ and ‘R’ denoting the range of the query.
Output Format :
For each test case, return the list of integers, where the ith of them denotes the answer of the ith query.
Output for each test case will be printed in a new line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10000
1 <= Q <= 10000
1 <= FINISHTIME[i] < 10 ^ 9
0 <= L <= R < N
Time Limit: 1 sec.
For each query, we can simply loop between ‘L’ and ‘R’ and store the minimum time taken by a horse to complete the race in a variable, and return the value stored in that variable.
Algorith...read more
A segment Tree is a data structure that allows us to perform range queries efficiently. In a minimum segment tree, at any node, we store the minimum value of all the leaf nodes present in the subtree rooted at that node. Similarly, for maximum segment trees, we store the maximum, for sum segment trees we store the sum, etc.
To learn more about segment trees, wiki is a good source to get started.
The first step in this approach is to build the minimum segment tree using ‘FINISHTIME’. Once we have built a segment tree, for each query calculate the range minimum for the given range i.e. for elements between ‘Lth’ and ‘Rth’ index.
Store the result of each query in an array and return the array.
Algorithm:
- Build the minimum segment tree using ‘FINISHTIME’, the given array, and store the segment tree in a variable named ‘RANGEQUERY’.
- Initialize the answer array ‘ANS’ with size ‘Q’, that is the number of queries.
- For the ith query, store the range minimum between ‘L’ and ‘R’ in ‘ANS[ i ]’.
- Return “ANS”.
O(N + Q), where ‘N’ denotes the number of horses and ‘Q’ denotes the number of queries.
Since we are using an array to store our result -> O(Q).
Since we are storing the time taken by each horse to complete the race -> O(N).
Since we are using an array of size 4 * N to store the segment tree -> O(N).
Overall Space Complexity -> O(N + Q).
Time Complexity: OtherExplanation:O(N + Q * log(N)), where ‘N’ denotes the number of horses and ‘Q’ denotes the number of queries.
The time complexity for building the segment tree is O(N).
Note that for each of the ‘Q’ queries, in the worst case we iterate through each level of the segment tree which has a depth of log(N). Therefore the time complexity for each query is O(log(N)), which leads to the overall time complexity of O(Q * log(N)) for each query.
Total Time Complexity is therefore: O(N + Q * log(N)).
Python (3.5)
'''
Time Complexity : O(N + Q * log(N))
Space Complexity : O(N + Q)
where 'N' is number of horses and
'Q' is number of queries.
'''
# Class Segment Tree.
class SegmentTree:
def __init__(self, data, default=10**9, func=lambda a, b: min(a,b)):
# Initialize the segment tree with data.
self._default = default
self._func = func
self._len = len(data)
self._size = _size = 1 << (self._len - 1).bit_length()
# Create the array.
self.data = [default] * (2 * _size)
self.data[_size:_size + self._len] = data
for i in reversed(range(_size)):
self.data[i] = func(self.data[i + i], self.data[i + i + 1])
def __getitem__(self, idx):
return self.data[idx + self._size]
def __len__(self):
return self._len
# Function to give range minimum.
def query(self, start, stop):
if start == stop:
return self.__getitem__(start)
stop += 1
start += self._size
stop += self._size
res = self._default
while start < stop:
if start & 1:
res = self._func(res, self.data[start])
start += 1
if stop & 1:
stop -= 1
res = self._func(res, self.data[stop])
start >>= 1
stop >>= 1
return res
def fastestHorse(finishTime, queries):
ans = []
# Make a segment tree.
s = SegmentTree(finishTime)
# We go through each query.
for l, r in queries:
res = s.query(l - 1, r - 1)
ans.append(res)
return ans
C++ (g++ 5.4)
/*
Time Complexity : O(N + Q * log(N))
Space Complexity : O(N + Q)
where 'N' is number of horses and
'Q' is number of queries.
*/
vector fastestHorse(vector &finishTime, vector> &queries)
{
// Declare the min segment tree as a struct.
struct segtree
{
vector tree, arr;
const int INF = 1e9;
// Constructor to build the segment tree with an array.
segtree(vector a)
{
arr = a;
tree.resize(arr.size() * 4);
build(1, 0, arr.size() - 1);
}
// Build function for segment tree.
void build(int root, int tl, int tr)
{
// Condition for leaf node.
if (tl == tr)
{
// Assign current value to leaf node.
tree[root] = arr[tl];
return;
}
build(root * 2, tl, (tl + tr) / 2);
build(root * 2 + 1, (tl + tr) / 2 + 1, tr);
tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
}
// Query function that returns minimum in the range [al, ar].
int query(int root, int tl, int tr, int al, int ar)
{
// If the range doesn't contain any element return default value.
if (tl > ar || al > tr)
{
return INF;
}
if (al <= tl && tr <= ar)
{
return tree[root];
}
// Return minimum by querying left and right child for their minimum.
return min(query(root * 2, tl, (tl + tr) / 2, al, ar), query(root * 2 + 1, (tl + tr) / 2 + 1, tr, al, ar));
}
// Function that calls query declared above with fewer parameters.
int query(int l, int r)
{
return query(1, 0, (int)arr.size() - 1, l, r);
}
};
// Store the size of finishTime and queries in N and Q respectively.
int N = finishTime.size(), Q = queries.size();
// Initialize and build the min segment tree using finishTime.
segtree rangeQuery(finishTime);
// Initialize our answer array with size Q.
vector ans(Q);
// Iterate through each query.
for (int q = 0; q < Q; q++)
{
// Store the minumum by querying rangeQuery in O(log(N)).
ans[q] = rangeQuery.query(queries[q][0] - 1, queries[q][1] - 1);
}
// Return ans.
return ans;
} Java (SE 1.8)
/*
Time Complexity : O(N + Q * log(N))
Space Complexity : O(N + Q)
where 'N' is number of horses and
'Q' is number of queries.
*/
public class Solution {
public static class segtree{
int[] tree, arr;
// Default value to return.
final int INF = Integer.MAX_VALUE;
// Constructor to build the segment tree with an array.
public segtree(int[] a){
arr = a;
tree = new int[(arr.length) *4];
build(1, 0, arr.length - 1);
}
// Build function for segment tree.
public void build(int root, int tl, int tr){
// Condition for leaf node.
if (tl == tr){
// Assign current value to leaf node.
tree[root] = arr[tl];
return;
}
build(root * 2, tl, (tl + tr) / 2);
build(root * 2 + 1, (tl + tr) / 2 + 1, tr);
tree[root] = Math.min(tree[root * 2], tree[root * 2 + 1]);
}
// Query function that returns minimum in the range [al, ar].
public int query(int root, int tl, int tr, int al, int ar){
// If the range doesn't contain any element return default value.
if (tl > ar || al > tr){
return Integer.MAX_VALUE;
}
if (al <= tl && tr <= ar){
return tree[root];
}
// Return minimum by querying left and right child for their minimum.
return Math.min(query(root * 2, tl, (tl + tr) / 2, al, ar), query(root * 2 + 1, (tl + tr) / 2 + 1, tr, al, ar));
}
// Function that calls query declared above with fewer parameters.
public int query(int l, int r){
return query(1, 0, (int)arr.length - 1, l, r);
}
}
public static int[] fastestHorse(int[] finishTime, int[][] queries){
// Store the size of finishTime and queries in N and Q respectively.
int n = finishTime.length;
int q = queries.length;
// Initialize and build the min segment tree using finishTime.
segtree rangeQuery = new segtree(finishTime);
// Initialize our answer array with size Q.
int[] ans = new int[q];
// Iterate through each query.
for (int i = 0; i < q; i++){
// Store the minumum by querying rangeQuery in O(log(N)).
ans[i] = rangeQuery.query(queries[i][0] - 1, queries[i][1] - 1);
}
// Return ans.
return ans;
}
}Top JPMorgan Chase & Co. Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Top HR questions asked in JPMorgan Chase & Co. Software Developer Intern
Reviews
Interviews
Salaries
Users/Month
Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.
