Take home exercise for Airbyte.

airbyte_exercise.js

/**
 * Merges two sorted lists into a single sorted list.
 * 
 * @param {Array} listOne 
 * @param {Array} listTwo 
 * @returns {Array} - listOne and listTwo sorted and combined.
 * 
 */

/**
 * I debated whether I should use linked lists or arrays in this exercise, and base on the wording of using 'input arrays',
 * I decided to go with the latter.
 * 
 * This was an interesting exercise to work on and I found quite a few edge cases! Thank you for the opportunity!
 */

const mergeLists = (listOne, listTwo) => {
  // Establish variables for the merged list to be returned and a counter for its index
  let mergedList = [];
  let currentIndex = 0;

  // Edge case: if one of the lists is empty, return the other one.
  if (listOne.length === 0) {
    return listTwo;
  } else if (listTwo.length === 0) {
    return listOne;
  }

  // Edge case: if the arrays have one element each, return right away.
  if (listOne.length === 1 && listTwo.length === 1) {
    return [listOne[0], listTwo[0]];
  }

  /**
   * Determine whether the first list is ascending or descending.
   * This is needed to make sure the merged list is sorted correctly.
   */
  const descending = listOne[0] >= listOne[listOne.length - 1];

  // Indexes to keep track of where we are in both lists.
  let index1 = 0;
  let index2 = 0;

  /**
   * Keep going through the lists until we get through both.
   */
  while (currentIndex < listOne.length + listTwo.length) {

    /**
     * Determine which list is longer and use that first to avoid having 'undefined' at the end of the merged list.
     * This can happen if the loop keeps going after the list has run out.
     */
    const firstArray = listOne.length >= listTwo.length ? listOne : listTwo;
    const secondArray = listOne.length < listTwo.length ? listOne : listTwo;

    /**
     * A condition that triggers when the current list is out of elements, but the second list still has some.
     */
    const secondArrayExceded = index2 >= secondArray.length;

    /**
     * Set the loop condition based on whether the list we chose to start with is descending or not
     * and whether it has negative integers or not.
     */
    const condition = descending
      ? firstArray[index1] >= secondArray[index2]
      : firstArray[index1] <= secondArray[index2];

    /**
     * Edge case: once we have gone through the list we initially picked, there might be some elements 
     * left in the second list. The secondArrayExceeded condition makes sure this does not result in
     * 'undefined' being added to the list.
     */
    if (condition || secondArrayExceded) {
      mergedList.push(firstArray[index1]);
      index1++;
    } else {
      mergedList.push(secondArray[index2]);
      index2++;
    }

    currentIndex++;
  }

  return mergedList;
}

/**
 * TEST CASES:
 * Below are some example arrays and test cases for them. 
 * I made sure to consider cases when the sorted lists might be ascending, descending, empty, or include negative integers.
 * 
 * JavaScript compares arrays and objects by reference and not value, so I decided to serialize the arrays 
 * and compare the serialized strings.
 */

let arr1 = [1, 3, 4, 5, 7];
let arr2 = [2, 6, 9, 10];
let arr3 = [20, 19, 18, 17];
let arr4 = [25, 24, 23, 22];
let arr5 = [];
let arr6 = [1];
let arr7 = [3];
let arr8 = [-5, -3, -2, -1];
let arr9 = [-1, -2, -3, -4];

let ascending = [1, 2, 3, 4, 5, 6, 7, 9, 10];
let descending = [25, 24, 23, 22, 20, 19, 18, 17];
let theSame = [1, 1, 3, 3, 4, 4, 5, 5, 7, 7];
let oneNegative = [-5, -3, -2, -1, 1, 3, 4, 5, 7];
let negatives = [-5, -3, -2, -1, -1, -2, -3, -4];
let singleArrays = [1, 3];
let empty = [];


const twoAscendingArrays = mergeLists(arr1, arr2);
const twoSameArrays = mergeLists(arr1, arr1);
const twoDescendingArrays = mergeLists(arr4, arr3);
const oneEmptyArray = mergeLists(arr1, arr5);
const emptyArrays = mergeLists(arr5, arr5);
const oneArray = mergeLists(arr6, arr7);
const oneNegativeArray = mergeLists(arr1, arr8);
const negativeArrays = mergeLists(arr8, arr9);

if (JSON.stringify(twoAscendingArrays) == JSON.stringify(ascending)) {
    console.log(`Merging ${arr1} and ${arr2} returns an ascending array: ${twoAscendingArrays}`)
} else {
    console.log(`This does not return the expected array, check for errors: ${twoAscendingArrays} and ${ascending}`);
}

if (JSON.stringify(twoDescendingArrays) == JSON.stringify(descending)) {
    console.log(
      `Merging ${arr4} and ${arr3} returns a descending array: ${twoDescendingArrays}`
    );
} else {
    console.log(
      `This does not return the expected array, check for errors: ${twoDescendingArrays} and ${descending}`
    );
}

if (JSON.stringify(twoSameArrays) == JSON.stringify(theSame)) {
    console.log(
      `Merging ${arr1} and ${arr1} returns a combined array with doubling: ${twoSameArrays}`
    );
} else {
    console.log(
      `This does not return the expected array, check for errors: ${twoSameArrays} and ${theSame}`
    );
}

if (JSON.stringify(oneEmptyArray) == JSON.stringify(arr1)) {
    console.log(
      `Merging ${arr1} and ${arr5} returns only one of the arrays because the other one was empty: ${oneEmptyArray}`
    );
} else {
    console.log(
      `This does not return the expected array, check for errors: ${oneEmptyArray} and ${arr1}`
    );
}

if (JSON.stringify(emptyArrays) == JSON.stringify(empty)) {
    console.log(
      `Merging ${arr5} and ${arr5} returns an empty array: ${emptyArrays}`
    );
} else {
    console.log(
      `This does not return the expected array, check for errors: ${emptyArrays} and ${empty}`
    );
}
if (JSON.stringify(oneArray) == JSON.stringify(singleArrays)) {
    console.log(
      `Merging ${arr6} and ${arr7} returns an array with only two elements: ${oneArray}`
    );
} else {
    console.log(
      `This does not return the expected array, check for errors: ${oneArray} and ${singleArrays}`
    );
}

if (JSON.stringify(oneNegativeArray) == JSON.stringify(oneNegative)) {
    console.log(
      `Merging ${arr1} and ${arr8} returns an array with negative and positive integers: ${oneNegativeArray}`
    );
} else {
    console.log(
      `This does not return the expected array, check for errors: ${oneNegativeArray} and ${oneNegative}`
    );
}

if (JSON.stringify(negativeArrays) == JSON.stringify(negatives)) {
    console.log(
      `Merging ${arr8} and ${arr9} returns an array with negative integers: ${negativeArrays}`
    );
} else {
    console.log(
      `This does not return the expected array, check for errors: ${negativeArrays} and ${negatives}`
    );
}