Google phone screening round L3/SDE-2
Anonymous User
1559
GoogleInterview

question :
The problem is to find the longest interval over which the value has decreased, but the interval doesn't have to be consecutive
{50,52,58,54,57,51,55,60,62,65,68,72,62,61,59,63,72}
Ans : 7 (index 14 - index 7)

Solution i gave

for (int i = 0; i < arr.size(); i++) {
    for (int j = i + 1; j < arr.size(); j++) {
        if (arr[j] < arr[i]) {
            maxInterval = std::max(maxInterval, j - i);
        }
    }
}

}

not able to optimize during the interview , but tried after interview

int longestDecreasingInterval(const vector& arr) {
vector<pair<int, int>> pairs;
for (int i = 0; i < arr.size(); i++) {
pairs.push_back({arr[i], i});
}
int it=0;
sort(pairs.begin(), pairs.end());
//for(auto i : pairs)cout<<"{["<<it++<<"],"<<i.first<<","<<i.second<<"}";
cout<<endl;
int maxInterval = 0;
int minIndex = pairs[0].second;
int n =pairs.size();

for (int i = 1; i < pairs.size(); i++) {
    pair<int,int> p = pairs[i];
    
    auto low1 = lower_bound(pairs.begin(), pairs.end(), p, [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
        return a.first < b.first && a.second > b.second;
    });
    auto low2 = lower_bound(pairs.begin(), pairs.end(), p , [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
        return a.first < b.first && a.second < b.second;
    });
    //cout<<"{["<<i<<"],"<<p.first<<","<<low2->first<<","<<low1->first<<"#"<<abs(low2->second-low1->second)<<"}";
    
    if(p.first > low1->first && p.second < low1->second)
        maxInterval = max(maxInterval , abs(p.second - low1->second));
    
    if(p.first > low2->first && p.second < low2->second)
        maxInterval = max(maxInterval , abs(p.second - low2->second));
}

return maxInterval;

}

Comments (11)