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芯片规格书
