Merge to sorted arrays into second array, both arrays has N elements, but second array size is N * 2. So you merge both arrays in second array in a sorted way.

Question

Sigiloso · Accepted Answer

// A and B are sorted input vectors and C is merged output vector
void vectorMerge(const vector &A, const vector &B, vector &C)
{
	int i = 0;
	int j = 0;
	int k = 0;

	while ((j < B.size()) && (i < A.size()))
	{
		if (A[i] <= B[j])
		{
			C[k++] = A[i++];
		}
		else
		{
			C[k++] = B[j++];
		}
	}

	if (j < B.size())
	{
		for (; j < B.size(); ++j)
		{
			C[k++] = B[j];
		}
	}

	if (i < A.size())
	{
		for (; i < A.size(); ++i)
		{
			C[k++] = A[i];
		}
	}
}

Yulia · Answer

// Example program
#include 
#include 
#include 

int main()
{
    std::vector A = {0, 2};
    std::vector B = {3, 5, 8};
    size_t size = A.size() + B.size();
    std::vector C(size);

    size_t i = 0, j = 0, k = 0;
    
    while (k < size)
    {
        if (i < A.size() && A[i] < B[j]) {
            C[k++] = A[i++];
             std::cout << C[k-1] << " ";
             continue;
        }
        
        C[k++] = B[j++];
        std::cout << C[k-1] << " ";
    }
 
}

Seedy · Answer

# merge from backwards, so that the sorted element are copied into the larger array

def mergeLists (li1, len1, li2, len2):
    idx1 = len1 - 1 
    idx2 = len2 - 1 
    idx3= len1  + len2 -1
    for i in range (idx3,-1, -1):
        if idx1 >= 0:
            val1 = li1[idx1]
        else:
            return

        if idx2 >= 0:
            val2 = li2[idx2]
        else:
            for j in range (idx1+1):
                li2[j] = li1[j]
            return

        if val1 >= val2:
            li2[i] = val1
            idx1 -= 1 
        else:
            li2[i] =  val2
            idx2 -= 1 

li1 = [1,4,9, 15] 
li2 = [3,6,9,10,19,0,0,0,0]
print (li1, li2)
mergeLists (li1,4, li2, 5)
print (li1, li2)

Sigiloso · Answer

In a regular merge sort, the arrays are sorted from the beginning. Here, sort from the end directly to the second array.

Bloomberg

Pergunta de entrevista da empresa Bloomberg

Respostas da entrevista

Empresas seguidas

Buscas de vagas