Best solutions for Microsoft interview tasks. Largest K such that both K and -K exist in array.

Description:

Solution:

This task is very easy. It is a bit more difficult than finding of a maximum value in given array. The only thing we have to add is check if this array contains the same value on the opposite side of zero. In other words we have to check all positive values in the array and check if there are values with the same absolute value but negative sign. There is the only data structure which has constant complexity for access to unsorted items, this is a hash table.

So at first we add all given values to a hash table.

Then pass through all items of the table and check if positive item has the same absolute value but with negative sigh.

Each time if we meet an absolute value bigger than already found maximum value keep it as a new maximum value.

C++ code:

int solution(const vector<int>& input){
    unordered_set<int> s(input.begin(),input.end());
    int max_value = 0;
    for(auto n : s){
        if((abs(n) > max_value) && (s.count(-n) != 0)) {
            max_value = n;
        }
    }
    return max_value;
}        

Repository with the full project you can find here: https://github.com/jolly-fellow/microsoft/tree/master/largest_integer

Return to the table of contents.