javascript面试

    科技2025-03-03  33

    javascript面试

    Array related questions and answers from brute force to better optimal way of achieving Big O

    阵列相关的问题和答案,从蛮力到实现Big O的更好的最佳方法

    查找数组的最大值 (Find the maximum value of an array)

    //method: 1 // BAD function findMaxVal(arr) { const len = arr.length; let res = arr[0]; for (let i = 0; i < len; i++) { if (arr[i] > res) { // use "<" to find minimum val res = arr[i]; } } return res; } // GOOD //method: 2 function findMaxVal2(arr) { return Math.max.apply(null, arr); // use "Math.min" to find minimum val } // TEST const numbers = [ 255, 25, 154, 26, 78]; console.time('findMaxVal'); findMaxVal(numbers);// RESULT: 255 console.timeEnd('findMaxVal'); // findMaxVal: 0.053955078125ms console.time('findMaxVal2'); findMaxVal2(numbers);// RESULT: 255 console.timeEnd('findMaxVal2'); // findMaxVal2: 0.030029296875ms /** * FOR MULTI-DIMENTIONAL ARRAY **/ // method: 1 (brute force) function findMaxValsOfMDArrs(arr) { const len = arr.length; let res = []; for (let i = 0; i < len; i++) { var innerArr = arr[i]; res[i] = arr[i][0]; for (let j = 0; j < innerArr.length; j++) { if (innerArr[j] > res[i]) { res[i] = innerArr[j]; } } } return res; } // method: 2 (built-in) function findMaxValsOfMDArrs2(arr) { return arr.map((el) => el.reduce((acc, el) => Math.max(acc, el))); } // TEST const multiNumbers = [ [2, 34, 555, 77], [33, 34, 778, 2], [5, 900, 1, 56], ]; console.time("findMaxValsOfMDArrs"); findMaxValsOfMDArrs(multiNumbers);//RESULT: [ 555, 778, 900 ] console.timeEnd("findMaxValsOfMDArrs"); // findMaxValsOfMDArrs: 0.057861328125ms (first time execution) // findMaxValsOfMDArrs: 0.027099609375ms (second time execution) console.time("findMaxValsOfMDArrs2"); findMaxValsOfMDArrs2(multiNumbers); //RESULT: [ 555, 778, 900 ] console.timeEnd("findMaxValsOfMDArrs2"); // findMaxValsOfMDArrs2: 0.069091796875ms (first time execution) // findMaxValsOfMDArrs2: 0.009033203125ms (second time execution)

    从数组/唯一数组中删除重复项 (Remove duplicate from an array/ unique array)

    // method: 1 (using indexOf) function getUniqueArr1(arr) { const len = arr.length; let res = []; for (let i = 0; i < len; i++) { if (res.indexOf(arr[i]) === -1) { res.push(arr[i]); } } return res; } // method: 2 (using hash) function getUniqueArr2(arr) { const len = arr.length; let res = []; const hash = {}; let elem; for (let i = 0; i < len; i++) { elem = arr[i]; if (!hash[elem]) { hash[elem] = true; res.push(elem); } } return res; } // method: 3 (using built-in) function getUniqueArr3(arr) { return arr.filter((el, idx, arr) => { return idx === arr.indexOf(el); }); } // TEST const numbers = [5, 900, 1, 56, 5, 4, 3, 1]; // method: 1 (using indexOf) console.time('getUniqueArr1'); getUniqueArr1(numbers);// RESULT: [ 5, 900, 1, 56, 4, 3 ] console.timeEnd('getUniqueArr1'); // method: 2 (using hash) console.time('getUniqueArr2'); getUniqueArr2(numbers);// RESULT: [ 5, 900, 1, 56, 4, 3 ] console.timeEnd('getUniqueArr2'); // method: 3 (using built-in) console.time('getUniqueArr3'); getUniqueArr3(numbers);// RESULT: [ 5, 900, 1, 56, 4, 3 ] console.timeEnd('getUniqueArr3'); // // TIME COMPLEXITY // // first time execution // // getUniqueArr1: 0.059326171875ms // getUniqueArr2: 0.051025390625ms // getUniqueArr3: 0.047119140625ms // // second time execution // // getUniqueArr1: 0.010009765625ms // getUniqueArr2: 0.02197265625ms // getUniqueArr3: 0.005859375ms (its the winner!!!)

    从数组中获取重复项 (Get duplicates from an array)

    // method: 1 (using hash) function getDupsFromAnArr1(arr) { const len = arr.length; const res = []; const hash = {}; let elem; for (let i = 0; i < len; i++) { elem = arr[i]; if (!hash[elem]) { hash[elem] = true; } else { res.push(elem); } } return res; } // method: 2 (using built-in) function getDupsFromAnArr2(arr) { return arr.filter((el, idx, arr) => { return idx !== arr.indexOf(el); }); } // TEST const numbers = [5, 900, 1, 56, 5, 4, 3, 1]; // method: 1 (using hash) console.time('getDupsFromAnArr1'); getDupsFromAnArr1(numbers); // RESULT: [ 5, 1 ] console.timeEnd('getDupsFromAnArr1'); // method: 2 (using built-in) console.time('getDupsFromAnArr2'); getDupsFromAnArr1(numbers); // RESULT: [ 5, 1 ] console.timeEnd('getDupsFromAnArr2'); // // TIME COMPLEXITY // // getDupsFromAnArr1: 0.071044921875ms // getDupsFromAnArr2: 0.012939453125ms

    展平数组 (Flatten the array)

    // method: 1 (brute force) function flattenArrs1(arr) { const len = arr.length; const res = []; for (let i = 0; i < len; i++) { let inner = arr[i]; for (let j = 0; j < inner.length; j++) { res.push(arr[i][j]); } } return res; } // method: 2 function flattenArrs2(arr) { return [].concat.apply([], arr); } // method: 3 (BEST) function flattenArrs3(arr) { return arr.reduce((acc, el) => acc.concat(el)); } // method: 4 (more level of multidimensional) function flattenArrs4(arr) { return arr.reduce((acc, el) => { el = Array.isArray(el) ? flattenArrs4(el) : el; return acc.concat(el); }, []); } // method: 5 (using spread operator) [1, 3, ...[2, 8]]; // Example const mock = { family: [ { id: "1", name: "John", children: [ { id: "2", name: "Peter", age: 15, }, { id: "3", name: "Harry", age: 11, }, ], age: 55, }, ], }; const all = mock.family; function flatArrOfObj(arr) { let res = []; return arr.reduce((acc, el) => { res.push({ id: el.id, name: el.name, age: el.age }); if (Array.isArray(el.children)) { res = res.concat(flatArrOfObj(el.children)); } return res; }, []); } // TEST // input const lettersMulti = [ ["c", "o"], ["m", "b", "i"], ["n", "e", "d"], ]; // RESULT: ["c", "o", "m", "b", "i", "n", "e", "d"] console.time('flattenArrs1'); flattenArrs1(lettersMulti); console.timeEnd('flattenArrs1'); console.time('flattenArrs2'); flattenArrs2(lettersMulti); console.timeEnd('flattenArrs2'); console.time('flattenArrs3'); flattenArrs3(lettersMulti); console.timeEnd('flattenArrs3'); console.time('flattenArrs4'); flattenArrs4(lettersMulti); console.timeEnd('flattenArrs4'); // EXECUTION TIME // 1st time // // flattenArrs1: 0.05810546875ms // flattenArrs2: 0.031982421875ms // flattenArrs3: 0.0439453125ms // flattenArrs4: 0.06884765625ms // // 2nd time // // flattenArrs1: 0.010009765625ms // flattenArrs2: 0.007080078125ms // flattenArrs3: 0.0048828125ms (Winner!!) // flattenArrs4: 0.013916015625ms JSON.stringify(flatArrOfObj(all), 0, 4); // RESULT // '[ // { // "id": "1", // "name": "John", // "age": 55 // }, // { // "id": "2", // "name": "Peter", // "age": 15 // }, // { // "id": "3", // "name": "Harry", // "age": 11 // } // ]'

    查找数组的中值 (Find the median value of an array)

    // method: 1 function findMedianValOfArr1(arr) { if (!arr || arr.length === 0) return 0; arr.sort((a, b) => a - b); const mid = Math.floor(arr.length / 2); if (mid % 2 === 0) { return arr[mid]; } else { return (arr[mid - 1] + arr[mid]) / 2.0; } } // method: 2 const findMedianValOfArr2 = (arr) => { const mid = Math.floor(arr.length / 2), nums = [...arr].sort((a, b) => a - b); return arr.length % 2 !== 0 ? nums[mid] : (nums[mid - 1] + nums[mid]) / 2; }; // TEST // console.time("findMedianValOfArr1"); console.log(findMedianValOfArr1([5, 6, 50, 1, -5])); // RESULT: 5 console.timeEnd("findMedianValOfArr1"); console.time("findMedianValOfArr2"); console.log(findMedianValOfArr2([5, 6, 50, 1, -5])); // RESULT: 5 console.timeEnd("findMedianValOfArr2"); console.log(findMedianValOfArr1([1, 2, 3, 4, 5])); // RESULT: 3 // EXECUTION TIME // 1st time // findMedianValOfArr1: 0.185791015625ms // findMedianValOfArr2: 0.251220703125ms // 2nd time // findMedianValOfArr1: 0.093994140625ms // findMedianValOfArr2: 0.0390625ms

    查找数组twoSum(arr,sum)的两个和 (Find two sum of an array twoSum(arr, sum))

    // method: 1 (brute force) function findTwoSumOfArr(arr, sum) { const len = arr.length; const res = []; for (let i = 0; i < len; i++) { for (let j = i + 1; j < len; j++) { if (arr[i] + arr[j] === sum) { res.push([arr[i], arr[j]]); } } } return res; } // TEST findTwoSumOfArr([-4, 2, 1, 9, 7, 5], 3); // RESULT: [ [ -4, 7 ], [ 2, 1 ] ]

    数组中的最大连续整数和 (Maximum consecutive sum of integers in an array)

    // method: 1 (brute force) function maxSumSubArray1(arr) { const len = arr.length; let maxSumSoFar = -Infinity; let leftIdx = 0; let rightIdx = len - 1; const maxCSum = 0; let i; let j; let k; for (i = 0; i < len; i++) { for (j = i; j < len; j++) { maxSum = 0; for (k = j; k < len; k++) { maxSum += arr[k]; if (maxSum > maxSumSoFar) { leftIdx = i; maxSumSoFar = maxSum; rightIdx = j; } } } } return maxSumSoFar; } // method: 2 (kadane’s algorithm) function maxSumSubArray2(arr) { const len = arr.length; let start = 0; let end = len - 1; let maxSum = 0; let maxSumSoFar = -Infinity; let curSum = 0; let i; let a; let b; let s; //var a = b = s = i = 0; for (i = 0; i < len; i++) { curSum += arr[i]; if (curSum > maxSumSoFar) { maxSumSoFar = curSum; a = s; b = i; } if (curSum < 0) { curSum = 0; s = i + 1; } } start = a; end = b; maxSum = maxSumSoFar; return maxSum; } // method: 3 (using built-in) function maxSumSubArray3(arr) { const len = arr.length; let currSum = 0; let maxSum = 0; let i; for (i = 0; i < len; i++) { currSum = Math.max(0, currSum + arr[i]); maxSum = Math.max(maxSum, currSum); } return maxSum; } // TEST // RESULT: 6 console.time("maxSumSubArray1"); maxSumSubArray1([-2, 1, -3, 4, -1, 2, 1, -5, 4]); console.timeEnd("maxSumSubArray1"); console.time("maxSumSubArray2"); maxSumSubArray2([-2, 1, -3, 4, -1, 2, 1, -5, 4]); console.timeEnd("maxSumSubArray2"); console.time("maxSumSubArray3"); maxSumSubArray3([-2, 1, -3, 4, -1, 2, 1, -5, 4]); console.timeEnd("maxSumSubArray3"); // EXECUTION TIME // 1st time // maxSumSubArray1: 0.10009765625ms // maxSumSubArray2: 0.05517578125ms // maxSumSubArray3: 0.046875ms // 2nd time // maxSumSubArray1: 0.177001953125ms // maxSumSubArray2: 0.0068359375ms (Winner!) // maxSumSubArray3: 0.01513671875ms

    数组的并集(合并两个没有重复的数组) (Union of arrays (merge two arrays without duplicates))

    function getUniqueArr(arr) { return arr.filter((el, idx, arr) => { return idx === arr.indexOf(el); }); } // method: 1 function unionOfArrs(arr1, arr2) { const combined = [...arr1, ...arr2]; return getUniqueArr(combined); // use the getUniqueArr method from the above } // TEST unionOfArrs(["raj", "john", "prem"], ["prem", "tom", "keerthi"]); // RESULT: (5) ["raj", "john", "prem", "tom", "keerthi"]

    数组的交集/查找数组的公共值(多维) (Intersection of arrays/ find common values of arrays (multidimensional))

    // method: 1 function intersectionOfArr1(arr) { const len = arr.length; let res = {}; let hash = {}; let i; let j; const firstArr = arr[0]; for (i = 0; i < firstArr.length; i++) { res[firstArr[i]] = true; } for (i = 1; i < len; i++) { const inner = arr[i]; for (j = 0; j < inner.length; j++) { if (res.hasOwnProperty(inner[j])) { hash[inner[j]] = true; } } res = hash; hash = {}; } return res; } // method: 2 (intersection of two arrays) function intersectionOfArr2(firstArray, secondArray) { // The logic here is to create a hashmap with the elements of the firstArray as the keys. // After that, you can use the hashmap's O(1) look up time to check if the element exists in the hash // If it does exist, add that element to the new array. const hashmap = {}; const intersectionArray = []; firstArray.forEach((element) => { hashmap[element] = 1; }); // Since we only want to push unique elements in our case... we can implement a counter to keep track of what we already added secondArray.forEach((element) => { if (hashmap[element] === 1) { intersectionArray.push(element); hashmap[element]++; } }); return intersectionArray; // Time complexity O(n), Space complexity O(n) } // TEST console.time("intersectionOfArr1"); intersectionOfArr1([ [1, 5, 8, 11, 6, 11], [1, 5, 7, 11, 63], [1, 54, 81, 12, 5], ]); // RESULT: { '1': true, '5': true } console.timeEnd("intersectionOfArr1"); const firstArray = [2, 2, 4, 1]; const secondArray = [1, 2, 0, 2]; console.time("intersectionOfArr2"); intersectionOfArr2(firstArray, secondArray); // RESULT: [ 1, 2 ] console.timeEnd("intersectionOfArr2"); // EXECUTION TIME: // 1st time // intersectionOfArr1: 0.067138671875ms // intersectionOfArr2: 0.105224609375ms // 2nd time // intersectionOfArr1: 0.029296875ms // intersectionOfArr2: 0.010009765625ms (Winner!!)

    给定一个整数数组,每个元素出现两次,除了一个。 找到那一个 (Given an array of integers, every element appears twice except for one. Find that single one)

    // method: 1 function findOddOne(arr) { const len = arr.length; let res = {}; for (let i = 0; i < len; i++) { if (!res[arr[i]]) { res[arr[i]] = 1; } else { res[arr[i]]++; } } for (key in res) { if (res[key] < 2) res = key; } return res; } // TEST findOddOne([1, 2, 3, 4, 6, 2, 3, 1, 6]); // RESULT: "4"

    给定一个整数数组,找到从三个整数中产生的最大乘积 (Given an array of integers, find the largest product yielded from three of the integers)

    const sortIntegers = (a, b) => a - b; // Greatest product is either (min1 * min2 * max1 || max1 * max2 * max3) function findLargestProductYiedl(unsorted) { const sortedArray = unsorted.sort(sortIntegers); let product1 = 1; let product2 = 1; const array_n_element = sortedArray.length - 1; // Get the product of three largest integers in sorted array for (let x = array_n_element; x > array_n_element - 3; x--) { product1 = product1 * sortedArray[x]; } product2 = sortedArray[0] * sortedArray[1] * sortedArray[array_n_element]; if (product1 > product2) return product1; return product2; } // TEST const unsortedArray = [-10, 7, 29, 30, 5, -10, -70]; findLargestProductYiedl(unsortedArray); // RESULT: 21000

    被告知未排序的数组包含n个连续的数字(其中定义了边界的n-1个),请在O(n)的时间内找到丢失的数字 (Being told that an unsorted array contains (n — 1) of n consecutive numbers (where the bounds are defined), find the missing number in O(n) time)

    function findMissingNumber1(arrayOfIntegers, upperBound, lowerBound) { // Iterate through array to find the sum of the numbers let sumOfIntegers = 0; for (let i = 0; i < arrayOfIntegers.length; i++) { sumOfIntegers += arrayOfIntegers[i]; } // Find theoretical sum of the consecutive numbers using a variation of Gauss Sum. // Formula: [(N * (N + 1)) / 2] - [(M * (M - 1)) / 2]; // N is the upper bound and M is the lower bound upperLimitSum = (upperBound * (upperBound + 1)) / 2; lowerLimitSum = (lowerBound * (lowerBound - 1)) / 2; theoreticalSum = upperLimitSum - lowerLimitSum; return theoreticalSum - sumOfIntegers; } // method: 2 (difference of sorted numbers === 1, else that num) function findMissingNumber2(arr) { arr.sort((a, b) => a - b); let num; for (let i = 1; i < arr.length; i++) { if (arr[i] - arr[i - 1] > 1) { num = arr[i] - 1; } } return num; } // The output of the function should be 8 // TEST const arrayOfIntegers = [2, 5, 1, 4, 9, 6, 3, 7]; const upperBound = 9; const lowerBound = 1; console.time('findMissingNumber1'); findMissingNumber1(arrayOfIntegers, upperBound, lowerBound); // RESULT: 8 console.timeEnd('findMissingNumber1'); console.time('findMissingNumber2'); findMissingNumber2(arrayOfIntegers); // RESULT: 8 console.timeEnd('findMissingNumber2'); // EXECUTION TIME // 1st time // findMissingNumber1: 0.06787109375ms // findMissingNumber2: 0.072021484375ms // 2nd time // findMissingNumber1: 0.010009765625ms // findMissingNumber2: 0.00927734375ms (winner!)

    给定一个整数数组,请找出两个元素之间的最大差,以便较小值的元素必须位于较大元素的前面 (Given an array of integers, find the largest difference between two elements such that the element of lesser value must come before the greater element)

    function findLargestDifference(array) { // If there is only one element, there is no difference if (array.length <= 1) return -1; // currentMin will keep track of the current lowest let currentMin = array[0]; let currentMaxDifference = 0; // We will iterate through the array and keep track of the current max difference // If we find a greater max difference, we will set the current max difference to that variable // Keep track of the current min as we iterate through the array, since we know the greatest // difference is yield from `largest value in future` - `smallest value before it` for (let i = 1; i < array.length; i++) { if (array[i] > currentMin && array[i] - currentMin > currentMaxDifference) { currentMaxDifference = array[i] - currentMin; } else if (array[i] <= currentMin) { currentMin = array[i]; } } // If negative or 0, there is no largest difference if (currentMaxDifference <= 0) return -1; return currentMaxDifference; } // TEST const array = [7, 8, 4, 9, 9, 15, 3, 1, 10]; // [7, 8, 4, 9, 9, 15, 3, 1, 10] would return `11` based on the difference between `4` and `15` // Notice: It is not `14` from the difference between `15` and `1` because 15 comes before 1. findLargestDifference(array); // RESULT: 11

    给定一个整数数组,返回一个输出数组,使output [i]等于该数组中除自身以外的所有元素的乘积。 (在O(n)中解决这个问题,不做除法) (Given an array of integers, return an output array such that output[i] is equal to the product of all the elements in the array other than itself. (Solve this in O(n) without division))

    function productExceptSelf(numArray) { var product = 1; const size = numArray.length; const output = []; // From first array: [1, 2, 4, 16] // The last number in this case is already in the right spot (allows for us) // to just multiply by 1 in the next step. // This step essentially gets the product to the left of the index at index + 1 for (let x = 0; x < size; x++) { output.push(product); product = product * numArray[x]; } // From the back, we multiply the current output element (which represents the product // on the left of the index, and multiplies it by the product on the right of the element) var product = 1; for (let i = size - 1; i > -1; i--) { output[i] = output[i] * product; product = product * numArray[i]; } return output; } // TEST const firstArray = [2, 2, 4, 1]; const secondArray = [0, 0, 0, 2]; const thirdArray = [-2, -2, -3, 2]; productExceptSelf(firstArray); // RESULT: [8, 8, 4, 16] // EXPLANATION: firstArray of first element is 2, so when make product except the number it self (2 * 4 * 1 = 8) productExceptSelf(secondArray); // RESULT: [0, 0, 0, 0] productExceptSelf(thirdArray); // RESULT: [12, 12, 8, -12]

    DNF问题(数组仅包含1s,2s和3s。对数组进行排序) (DNF problem (An array just contains 1s, 2s, and 3s. Sort the array))

    // Method: 1 (using swap) function swap(arr, i1, i2) { const temp = arr[i1]; arr[i1] = arr[i2]; arr[i2] = temp; } function dutchNatFlag1(arr) { let low = 0; let mid = 0; let high = arr.length - 1; // one pass through the array swapping // the necessary elements in place while (mid <= high) { if (arr[mid] === 0) { swap(arr, low++, mid++); } else if (arr[mid] === 2) { swap(arr, mid, high--); } else if (arr[mid] === 1) { mid++; } } return arr; } //Method: 2 (without swap) function dutchNatFlag2(arr) { let i, j, k, n = arr.length, hash = { 0: 0, 1: 0, 2: 0 }; for (i = 0; i < n; i++) { if (arr[i] === 0) { hash[arr[i]]++; } else if (arr[i] === 1) { hash[arr[i]]++; } else if (arr[i] === 2) { hash[arr[i]]++; } } for (i = 0; i < hash[0]; i++) { arr[i] = 0; } for (j = i; j < i + hash[1]; j++) { arr[j] = 1; } for (k = j; k < j + hash[2]; k++) {} return arr; } // TEST console.time('dutchNatFlag1') dutchNatFlag1([2, 2, 2, 0, 0, 0, 1, 1]); console.timeEnd('dutchNatFlag1') // RESULT // [ // 0, 0, 0, 0, // 1, 1, 2, 0 // ] console.time('dutchNatFlag2') dutchNatFlag2([0, 2, 1, 0, 0, 1, 2, 0]); console.timeEnd('dutchNatFlag2') // RESULT // [ // 0, 0, 0, 0, // 1, 1, 2, 0 // ] // EXECUTION TIME // 1st time // dutchNatFlag1: 0.21826171875ms // dutchNatFlag2: 0.08984375ms (winner!! reason is after multiple execution this has slightly better numbers) // 2nd time // dutchNatFlag1: 0.01318359375ms // dutchNatFlag2: 0.03466796875ms

    翻译自: https://medium.com/@sathishiva/javascript-coding-interview-array-part-3-806906d4d908

    javascript面试

    相关资源:镁光8+8eMCP芯片规格书
    Processed: 0.012, SQL: 8