Find the kth largest element collectively from 2 sorted integer arrays.

Question

Anonymous · Accepted Answer

Begin by comparing the two largest elements in the arrays. If you're looking for the largest, it will be the winner of this comparison. If you're looking for the kth largest you will decrement the index of the array containing the largest element and compare again using the largest of the 2nd array. Repeat this process in a loop while k > 1 and decrement k for every loop. Be careful to check that you're not going out of bounds in either array. If you do go out of bounds, you will simply decrement the index of the array until k = 0 (or k=1? not sure if I remember correctly). Also, do an initial check that the two arrays collectively have at least as many elements as the value k (you can't find the 11th smallest of 10 elements total). This will ensure that you don't go out of bounds when decrementing the array that has elements left over in it.

Ben · Answer

Throw every element in both arrays into a max heap, then call extractMax() k times.

LP · Answer

//Find the kth largest element collectively from 2 sorted  integer arrays.
vector findLargest(vector in1, vector in2, int k)
{
    vector sol;
    vector finalSol;
    int p1 = 0;
    int p2 = 0;
    
    //O(n1 + n2)
    while(p1  in2[p2])
        {
            sol.push_back(in1[p1]);
        }
        if(in1[p1] < in2[p2])
        {
            sol.push_back(in2[p2]);
        }
    }
    
    //actually only one of the for loop will work
    for(int i = p1 ; i < in1.size(); i++)
    {
        sol.push_back(in1[p1]);
    }
    for(int i = p2 ; i < in2.size(); i++)
    {
        sol.push_back(in2[p2]);
    }
    
    //return k largest
    for(int i = 0; i < k; i++)
    {
        finalSol.push_back(sol[i]);
    }
}

Bloomberg

Bloomberg Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches