I recently had a telephonic round with Google and faced the following question :
Given a 1 Dimentional array having co-ordinates: x_1 < x_2 ....x_n , which has corresponding values : v_1 , v_2 ... v_n . Find the indexes of the co-ordinates that maximizes the equation : val_x + val_y + dist(x_y - x_x) ,where x_x and x_y are coordinates and val_x and val_y are their corresponding values respectively .
My code :
class solution {
public:
pair<int, int> solve(vector<pair<double,double>> data) {
double max_val = INT_MIN ;
pair<int,int> res ;
int n = data.size() ;
vector<pair<double ,int > > right_max(n );
right_max[n-1] = { data[n-1].first + data[n-1].second , n-1} ;
for(int i =n-2 ; i>=0 ; i--) {
if(data[i].first + data[i].second < right_max[i+1].first ){
right_max[i]= right_max[i+1] ;
}
else{
right_max[i] = {data[i].first + data[i].second , i } ;
}
}
for(int i = 0 ; i < n ; i++){
pair<double , double > p = data[i] ;
double cord = p.first , value = p.second ;
int val = value + right_max[i].first + cord;
if(max_val < val ){
max_val = val ;
res.first = i ;
res.second = right_max[i].second ;
}
}
return res;
}
};TC : O(n)
SC : O(n)
Then he added a constrain that, while calculating the maximum , the co-ordinates difference should not exceed k . I could't solve the constrained problem and the time was up .
any clue , how can we solve the constrined version of problem ?
Comments (7)