code.js

// Best algo, minimiz memory usage.
// Q 1:
// 1. Fib
// 1st:  1,
// 2nd:  1
//       2, 3, 5, 8, ..
// What is 100th Fib?

function fib(n) {
    if (n < 0) throw new Error('Input shall be a non-negative int')
    if (n === 0) return BigInt(0).toString()
    if (n === 1) return BigInt(1).toString()

    let a = BigInt(0)
    let b = BigInt(1)

    for (let i = 2; i <= n; i++) {
        const tmp = a + b
        a = b
        b = tmp
    }
    return b.toString()
}

// const res = fib(100)
// console.log(res)
// 354224848179262000000

function runTestForQ1() {
    const testCase = [
        { input: 0, expected: `0` },
        { input: 1, expected: `1` },
        { input: 2, expected: `1` },
        { input: 3, expected: `2` },
        { input: 4, expected: `3` },
        { input: 5, expected: `5` },
        { input: 6, expected: `8` },
        { input: 40, expected: `102334155` },
        { input: 50, expected: `12586269025` },
        { input: 100, expected: `354224848179261915075` }
    ]

    testCase.forEach(({ input, expected }) => {
        let result = fib(input)
        console.assert(result === expected)
    })
}

runTestForQ1()

////////  Hi Liu, Question here ^^ ///////////////
// For Q1, Integer can not hold 100th fib, so I return String type, is it okay?

// Q 2:
// [1, 2, 2, 3, 4] sorted
// [2, 2, 3, 3] sorted
// Want: [1, 2, 3, 4] sorted, no-duplication

function mergeAndRemoveDuplicates(arr1, arr2) {
    let merged = []
    let i = 0 // Pointer for arr1
    let j = 0 // Pointer for arr2

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            // Only add if it's not a duplicate
            if (merged.length === 0 || merged[merged.length - 1] !== arr1[i]) {
                merged.push(arr1[i])
            }
            i++
        } else if (arr1[i] > arr2[j]) {
            // Only add if it's not a duplicate
            if (merged.length === 0 || merged[merged.length - 1] !== arr2[j]) {
                merged.push(arr2[j])
            }
            j++
        } else {
            // If they are equal, add one and move both pointers
            if (merged.length === 0 || merged[merged.length - 1] !== arr1[i]) {
                merged.push(arr1[i])
            }
            i++
            j++
        }
    }

    // Add remaining elements from arr1
    while (i < arr1.length) {
        if (merged.length === 0 || merged[merged.length - 1] !== arr1[i]) {
            merged.push(arr1[i])
        }
        i++
    }

    // Add remaining elements from arr2
    while (j < arr2.length) {
        if (merged.length === 0 || merged[merged.length - 1] !== arr2[j]) {
            merged.push(arr2[j])
        }
        j++
    }

    return merged
}

// Example usage
const input1 = [1, 2, 2, 3, 4]
const input2 = [2, 2, 3, 3]
const result = mergeAndRemoveDuplicates(input1, input2)
// console.log(result) // Output: [1, 2, 3, 4]

function testForCombinedAndDeDupTest1() {
    let a1 = [1, 2, 2, 3, 4]
    let a2 = [2, 2, 3, 3]
    const expected = [1, 2, 3, 4]
    const result = mergeAndRemoveDuplicates(a1, a2)
    console.assert(checkArrayEqual(result, expected))
}

function testForCombinedAndDeDupTest2() {
    let a1 = [1, 2, 2, 3, 4, 5, 5, 5, 6, 7, 9, 9, 22]
    let a2 = [0, 0, 0, 2, 2, 3, 3, 9, 9, 22, 42]
    const expected = [0, 1, 2, 3, 4, 5, 6, 7, 9, 22, 42]
    const result = mergeAndRemoveDuplicates(a1, a2)
    console.assert(checkArrayEqual(result, expected))
}

testForCombinedAndDeDupTest1()
testForCombinedAndDeDupTest2()

function checkArrayEqual(a1, a2) {
    if (a1.length !== a2.length) return false

    for (let i = 0; i < a1.length; i++) {
        if (a1[i] !== a2[i]) return false
    }

    return true
}