Optimize: Hackerearth Postman Software engineer intern question

Question

You want to buy a laptop. Each laptop has two parameters: Rating & Price. Your task is to buy a laptop with the highest rating within a given price range. Given Q tasks, each query consisting of price range required, you have to print the highest-rated laptop that can be bought within that price range.

Input format:

The first line contains N denoting the number of inputs.

The following N lines contain P & R denoting price and range of a laptop.

Next line contains Q denoting the number of queries.

The following Q lines contain two integers X & Y denoting the price range (inclusive).

Output format:

For each task Q, print the highest rating that can be bought within the range.

If you cannot get any laptop within the range, print -1.

Constraints:

1 <= N, Q <= 10^6

0 <= R,P <= 10^9

1 <= X <= Y <= 10^9

Time Limit: 6 Seconds for each input

Sample Input:

5
1000 300
1100 400
1300 200
1700 500
2000 600
3
1000 1400
1700 1900
0 2000

Sample Output:

400
500
600

My Approach

1. Build a (Key, value) map

2. while Y-- > X do,

   iterator = map.find(Y)

   if iterator, then, max_rating = max(max_rating, iterator.value)

3. return max_rating

Here is my solution

int solve(vector<int> P, vector<int> R, int X, int Y)
{
      int max_value=-1;
      map<int,int> price_rating;
      for(int i=0;i<N;i++)
      {
            price_rating.insert(pair<int, int>(P[i],R[i]));
      }

      while(y>x)
      {
            auto iterator = price_rating.find(y);
            if(iterator!=price_rating.end())
            {
                   max_rating = max(max_rating,iterator->second);
            }
            y-=1;
      }
      return max_rating;
}

Only a few test cases pass using the above solution while other test cases failed due to TLE (time limit exceeded). It would be great to know a better solution.

Answer 1

See the code below, for the above problem. I struggled to solve it in my exam.

Tasks of the program:

1. Sort the price and rating vector according to price.
2. Make a segment tree based on 'Maximum Rating between sl, sr index'
3. When getting MaxRating between queryLowPrice and queryHighPrice, just check if the current node contains that price or not and according to that return the answer.

#include <iostream>

#include<bits/stdc++.h>

using namespace std;

struct mydtype
{
    int price;
    int rating;
};

bool comp( mydtype a, mydtype b ){
    if( a.price != b.price ) return a.price<b.price;
    else return a.rating<b.rating;
}

int getMid( int a , int b ){
    return a+(b-a)/2;
}

void build( int st[], vector<mydtype> v, int si, int sl, int sr ){
    if(sl==sr) st[si]=v[sl].rating;
    else{
        int mid=getMid(sl,sr);
        build(st,v,2*si+1,sl,mid);
        build(st,v,2*si+2,mid+1,sr);
        st[si]=max( st[2*si+1], st[2*si+2] );
    }
}
int getMaxRating(int st[], vector<mydtype> v , int si, int sl, int sr, int queryLowPrice, int queryHighPrice ){
     if( queryLowPrice > queryHighPrice ) return -1;
     int stLowPrice = v[sl].price;
     int stHighPrice = v[sr].price;
     if( queryLowPrice > stHighPrice || queryHighPrice < stLowPrice ) return INT_MIN;
     if( stLowPrice>= queryLowPrice && stHighPrice <= queryHighPrice ) return st[si];
     else{
         int mid = getMid(sl,sr);
         return max( getMaxRating( st, v, 2*si+1, sl, mid, queryLowPrice, queryHighPrice ),
                    getMaxRating( st, v, 2*si+2, mid+1, sr, queryLowPrice, queryHighPrice ) );
    }
}

int main ()
{
    int n = 5;
    vector < mydtype > v(n);
    v={{10,2}, {20,3}, {20,4}, {30,4}, {40,2}};
    sort(v.begin(),v.end(), comp);
    int max_size = 15;
    int st[max_size];
    build (st, v, 0, 0, n-1 ); 
    cout<< getMaxRating(st, v, 0, 0, n-1, 19, 21);
    return 0;
}

Answer 2

Look into Segment tree.

The idea is to first construct a segment tree where each node represents a price range and stores the highest rating for that range.

For example, if your data has 7 prices, {10, 20, 30, 40, 50, 60, 70}, you would create a tree with these nodes:

                 [10-70]
                /        \
           [10-30]        [40-70]
          /      \         /      \
       [10-20]   [30]  [40-50]    [60-70]
       /   \            /   \      /   \
     [10]  [20]      [40]  [50]  [60]  [70]

The leaves are "ranges" with just one price. You can bubble up the maximum rating up this tree, so every node will have the maximum rating for that particular range.

Then, for an actual query you can walk down the tree (depth first search), and:

• exclude paths that go through a node whose range does not overlap with the queried range
• continue further on drilling down (extending path) when there is a partial overlap
• stop and backtrack at nodes that have ranges completely within the queried range

Eventually you will end up at nodes that together add up to the queried range. Get the maximum rating from those nodes while backtracking from recursion.

This will make a query run in O(logn).