Arrays

Question 1

How are let and const different from var

Answer 1

var is function scoped
let and const have block scope also var can be redeclared

Question 2

What do these array functions do?

1. push()
2. pop()
3. concat()
4. shift()
5. unshift()
6. reverse()
7. slice()
8. splice()
9. for of

Answer 2

1. push() - add item to the end
2. pop() - remove item from end
3. concat() - concat 2 arrays and return new array
4. shift() - remove item from start O(n)
5. unshift() - add item to start O(n)
6. reverse() - reverse array O(n)
7. slice(startIndex, endIndex) - create new array with startIndex excluding endIndex
8. splice(startIndex, count, ...items) - remove + add items from array
9. for of - loop on array

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array

Question 3

Implement a function, findProduct(arr), which modifies an array so that each index has a product of all the numbers present in the array except the number stored at that index.

Sample Input
arr = [1,2,3,4]
Sample Output
arr = [24,12,8,6]

Answer 3

Traverse the array and multiply all elements. In next loop take the result and divide by current element and save it at that position

Question 4

Two numbers sum solution

Answer 4

Use hashmap or hashtable to store the complements of values encountered. For each element check if complement is present in hashmap or hashtable.
T-O(n), S-O(n)

Question 5

Merge Two Sorted Arrays

Answer 5

Add pointers pointing first element of each array. Compare and add lower to new array. At the end fill the remaining values. T,S - O(m+n)

Question 6

Find First Unique Integer in an Array

Answer 6

1. Brute force solution - look thru each element comparing with other elements in the array T - O(n^2)
2. Loop thru the array and create a hashmap with values as frequencies. Then loop thru the array again and check if that element has frequency of only 1 and return. If the array is looped completely return -1. T,S - O(n)

Question 7

Find Second Maximum Value in an Array

Answer 7

1. Traversing the array twice - We traverse the array twice. In the first traversal, we find the maximum element. In the second traversal, we find the greatest element less than the element obtained in the first traversal.
2. We initialize two variables max and secondmax to NEGATIVE_INFINITY. We then traverse the array, and if the current element in the array is greater than the maximum value, then set secondmax to max and max to the current element. If the current element is in between the max and secondmax, then update secondmax to store the value of the current variable. Finally, return the value stored in the secondmax.

function findSecondMaximum(arr) {
  let max = Number.NEGATIVE_INFINITY;
    let secondMax = Number.NEGATIVE_INFINITY;
    for (let num of arr) {
       if (num > max) {
          secondMax = max;
            max = num;
        } else if (num > secondMax && num !== max) {
           secondMax = num;
        }
    }
    return secondMax;
}

Question 8

Right Rotate an Array by n

Answer 8

1. Manual Rotation - we first create an empty array. We then iterate through the last n elements of the array and append them to the new array. Lastly, we append the first arr.length-n elements to the new array and return.
2. Using splice() and concat()

Question 9

Given an array, can you re-arrange its elements in such a way that the negative elements appear at one side and positive elements appear in the other

Answer 9

1. Use additional arrays - create 2 arrays positives, negatives. Loop thru the input array and add items to positives and negatives then concat them. T,S-O(n)
2. Rearranging in place - initialize positiveEleIndex to 0. Loop on the array and check if the element is less than 0 and the index !== positiveEleIndex then swap

function reArrange(arr) {
    let positiveElementIndex = 0;

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < 0) {
            if (i !== positiveElementIndex) {
                swap(arr, positiveElementIndex, i);
            }

            positiveElementIndex++;
        }
    }

    return arr;
}

Question 10

Rearrange Sorted Array in Max/Min Form

Answer 10

1. Take left and right pointers and loop and keep adding max and min elements to the new array. T,S - O(n)
2. Take left, right pointers min and max elements, mode='max'. Loop thru the array and create temp if mode is max update max else min, update arr element to temp then. T-O(n), S-O(1)

function maxMin(arr) {
    let right = arr.length - 1
    let mode = 'max';
    let left = 0;
    let min = arr[left];
    let max = arr[right];

    while (left < arr.length) {
        let temp;

        if (mode === 'max') {
            temp = max
            max = arr[--right];
        } else {
            temp = min;
            min = arr[left];
        }

        arr[left++] = temp;
        mode = mode === 'max' ? 'min' : 'max'
    }

    return arr;
}

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array

Question 11

Maximum Sum Subarray - find subarray with maximum sum

Answer 11

Use kadanes algorithm - This algorithm takes a dynamic programming approach to solve the maximum subarray sum problem. The basic idea of Kadane’s algorithm is to scan the entire array and at each position find the maximum sum of the subarray ending there. This is achieved by keeping a current_max for the current array index and a global_max. The algorithm is as follows:

current_max = A[0]
global_max = A[0]
for i = 1 -> size of A
    if current_max is less than 0
        then current_max = A[i]
    otherwise 
        current_max = current_max + A[i]
    if global_max is less than current_max 
        then global_max = current_max

function findMaxSumSubArray(array_) {
    if (array_.length < 1) {
        return 0;
    }

    let currMax = array_[0];
    let globalMax = array_[0];
    let lengtharray = array_.length;
    for (let i = 1; i < lengtharray; i++) {
        if (currMax < 0) {
            currMax = array_[i];
        } else {
            currMax += array_[i];
        }
        if (globalMax < currMax) {
            globalMax = currMax;
        }
    }
    return globalMax;
};

Question 12

flat function to flatten array

Answer 12

function flattenArray(arr) {
    let result = [];
    
    for (let i = 0; i < arr.length; i++) {
        if (Array.isArray(arr[i])) {
            // If the element is an array, recursively flatten it
            result = result.concat(flattenArray(arr[i]));
        } else {
            // If the element is not an array, simply add it to the result
            result.push(arr[i]);
        }
    }
    
    return result;
}

// Example usage
const nestedArray = [1, [2, 3, [4, 5]], 6, [[7, 8], 9]];
console.log(flattenArray(nestedArray));
// Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

with max level

function flattenArrayWithMaxLevel(arr, maxLevel = Infinity) {
    function flatten(currentArr, currentLevel) {
        let result = [];
        
        for (let i = 0; i < currentArr.length; i++) {
            if (Array.isArray(currentArr[i]) && currentLevel < maxLevel) {
                // If the element is an array and we haven't reached max level,
                // recursively flatten it
                result = result.concat(flatten(currentArr[i], currentLevel + 1));
            } else {
                // If the element is not an array or we've reached max level,
                // simply add it to the result
                result.push(currentArr[i]);
            }
        }
        
        return result;
    }
    
    return flatten(arr, 1);
}

// Example usage
const nestedArray = [1, [2, 3, [4, 5]], 6, [[7, 8], 9]];
console.log(flattenArrayWithMaxLevel(nestedArray)); // Flattens completely
// Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

console.log(flattenArrayWithMaxLevel(nestedArray, 1)); // Flattens only 1 level
// Output: [1, 2, 3, [4, 5], 6, [7, 8], 9]

console.log(flattenArrayWithMaxLevel(nestedArray, 2)); // Flattens 2 levels
// Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]