Category: Sorting Problem

Sorting Problem

Merge One Sorted Array Into Another

Tech CornerLeave a comment

Problem

First array has n positive numbers, and they are sorted in the non-descending order.

Second array has 2n numbers: first n are also positive and sorted in the same way but the last n are all zeroes.

Merge the first array into the second and return the latter. You should get 2n positive integers sorted in the non-descending order.

Example

{
"first": [1, 3, 5],
"second": [2, 4, 6, 0, 0, 0]
}

Output:

[1, 2, 3, 4, 5, 6]

Solution

function merge_one_into_another(first, second) {
    // Write your code here.
    var n = first.length;
    var top = n-1;
    var bottom = n-1;
    var k = second.length -1;
    
    while(top >= 0 && bottom >=0){
        if(first[top] >= second[bottom]) {
            second[k] = first[top];
            top-=1;
            k-=1;
        } else {
            second[k] = second[bottom];
            bottom-=1;
            k-=1;
        }
    }
    
    while(top >=0){
        second[k] = first[top];
        top-=1;
        k-=1;
    }
    
    return second;
}
Sorting Problem

3 Sum Smaller

Tech CornerLeave a comment

Problem

Given a list of numbers, count the number of triplets having a sum less than a given target.

Example One

{
"target": 4,
"numbers": [5, 0, -1, 3, 2]
}

Output:

2

{numbers[1], numbers[2], numbers[3]} and {numbers[1], numbers[2], numbers[4]} are the triplets having sum less than 4.

Example Two

{
"target": 7,
"numbers": [2, 2, 2, 1]
}

Output:

4

{numbers[0], numbers[1], numbers[2]}, {numbers[0], numbers[1], numbers[3]}, {numbers[0], numbers[2], numbers[3]} and {numbers[1], numbers[2], numbers[3]} are the triplets having sum less than 7.

Solution

function count_triplets(target, numbers) {
    // Write your code here.
    // Initialize result
    let n = numbers.length;
    let result = 0;
        
        // Fix the first element as A[i]
        for (let i = 0; i < n-2; i++)
        {
           // Fix the second element as A[j]
           for (let j = i + 1; j < n-1; j++)
           {
               // Now look for the third number
               for (let k = j + 1; k < n; k++)
                   if (numbers[i] + numbers[j] + numbers[k] < target)
                       result++;
           }
        }
    return result;
}
Sorting Problem

Intersection Of Three Sorted Arrays

Tech CornerLeave a comment

Problem

Given three arrays sorted in the ascending order, return their intersection sorted array in the ascending order.

Example


{
"arr1": [2, 5, 10],
"arr2": [2, 3, 4, 10],
"arr3": [2, 4, 10]
}

and 

{
"arr1": [1, 2, 3],
"arr2": [],
"arr3": [2, 2]
}

Output:

[2,10] and [-1]

Solution


function find_intersection(arr1, arr2, arr3) {
    let n1 = arr1.length;

    // stores size of arr2
    let n2 = arr2.length;

    // stores size of arr3
    let n3 = arr3.length;

    // stores starting index of arr1
    let i = 0;

    // stores starting index of arr2
    let j = 0;

    // stores starting index of arr3
    let k = 0;
    
    let result = [];

    /*
     * traverses the arrays until 
     * we reach the end of
     * one of the arrays
    */
    while (i < n1 && j < n2 && k < n3) {
        // if the integers appointed by i, j and k are equal
        if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
            // prints the common integer
            result.push(arr1[i]);

            // increases i, j and k by 1
            i++; j++; k++;
        }

        /*
         * otherwise, if arr1[i] < arr2[j]
         * we have already found one smaller integer
         * which is arr1[i]
         */
        else if (arr1[i] < arr2[j]) {
            i++; // increases i by 1
        }

        /*
         * otherwise, if arr2[j] < arr3[k]
         * we have got a smaller integer
         * which is arr2[j]
         */
        else if (arr2[j] < arr3[k]) {
            j++; // increases j by 1
        }

        /*
         * otherwise, we consider arr3[k] to be smaller
         */
        else {
            k++; // increases k by 1
        }
    }
    
    return result.length > 0 ? result : [-1];
}
Sorting Problem

Online Median (Part I)

Tech CornerLeave a comment

Problem

Given an array of integers, find the median number in it.

Example


{
"stream": [3, 8, 5, 2]
}

Output:

4

Solution


function median(arr) {
    // 1: sort array in ascending order
    const sortedArr = arr.sort();
    const middleIndex = arr.length / 2;
    // 2.1: if odd, return middle element
    if (arr.length % 2 !== 0) {
        return arr[Math.floor(middleIndex)];
    }
    // 2.2: if even, return average of two middle elements
    return (arr[middleIndex - 1] + arr[middleIndex]) / 2;
}

console.log(median([1, 2])); // 1.5
console.log(median([4, 1, 7])); // 4
console.log(median([3, 7, 5, 1, 8, 9])); // 6
console.log(median([39, 3, 14, 29, 23, 13, 23, 23, 40, 23, 21, 5, 7, 12, 56])); // 23