How to answer a question that impresses an interviewer with multiple answers?

Why write this article?

1. Array duplication should be one of the interview questions.
2. Although it is not a complicated question, it also shows the breadth and depth of the interviewer and the comprehensiveness of the question.
3. In the actual development we should choose which way the array to duplicate, this article tells you.
4. You may not think that the interviewer is just asking you to redo an array, he wants to know a bit more, including your thoughts.

Koala is dedicated to sharing the complete Node.js technology stack, from JavaScript to Node.js, to back-end database. Wish you become an excellent senior Node.js engineer. [Programmer growth refers to north] Author, Github blog open source project github.com/koala-codin…

What do you say when asked?

First of all: I know how many ways to de-weight

Double-layer for loop

function distinct(arr) {
    for (let i=0, len=arr.length; i<len; i++) {
        for (let j=i+1; j<len; j++) {
            if (arr[i] == arr[j]) {
                arr.splice(j, 1);
                // Splice changes the array length, so subtract len and j by onelen--; j--; }}}return arr;
}
Copy the code

Thought: double for loop is a clumsy way, its implementation principle is simple: first define an array containing the first element on the original array, and then traverse the original array, each element from the original array and compare the new each element of the array, if you don’t repeat is added to the new array, finally return to the new array; Because it’s O(n^2) in time, if the array is large, it’s inefficient.

Add indexOf Array. The filter ()

function distinct(a, b) {
    let arr = a.concat(b);
    return arr.filter((item, index) = > {
        return arr.indexOf(item) === index
    })
}
Copy the code

Idea: Use indexOf to check whether the first occurrence of an element in an array is the same as the current position of the element. If not, the element is a duplicate element

Array.sort() adds a line to traverse the bubble (adjacent elements are de-duplicated)

function distinct(array) {
    var res = [];
    var sortedArray = array.concat().sort();
    var seen;
    for (var i = 0, len = sortedArray.length; i < len; i++) {
        // If the first element or adjacent elements are different
        if(! i || seen ! == sortedArray[i]) { res.push(sortedArray[i]) } seen = sortedArray[i]; }return res;
}
Copy the code

Idea: call sort(), V8’s sort() will use insertion sort if the array length is less than or equal to 10, and use quicksort if the array length is greater than 10. It then traverses and aligns adjacent elements based on the sorted result (essentially a row of bubble sort comparisons), and if the result is equal, the element is skipped until the traversal is complete.

Set deduplication in ES6

function distinct(array) {
   return Array.from(new Set(array));
}
Copy the code

You can even simplify it a little bit:

function unique(array) {
    return [...new Set(array)];
}
Copy the code

We can simplify it a little bit more:

let unique = (a) => [...new Set(a)]
Copy the code

Idea: ES6 provides a new data structure called Set. One feature of the Set structure is that its member values are unique and there are no duplicate values. (Please also note this simplification.)

The Object of key-value pairs

function distinct(array) {
    var obj = {};
    return array.filter(function(item, index, array){
        return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)})}Copy the code

This method uses an empty Object. We store the value of the array as the key value of Object, such as Object[value1] = true. If Object[value2] exists, we can evaluate another value. Obj [typeof item + item] = true; obj[item] = true; obj[item] = true; obj[item] = true; obj[item] = true; Since the key of an object can only be a string, we can avoid this problem by using typeof item + item as a string for the key.

Reduce implements object array duplication

var resources = [
            { name: "Zhang".age: "18" },
            { name: "Zhang".age: "19" },
            { name: "Zhang".age: "20" },
            { name: "Bill".age: "19" },
            { name: "Fifty".age: "20" },
            { name: "Daisy".age: "21"}]var temp = {};
     resources = resources.reduce((prev, curv) = > {
         // If the temporary object has this name, do nothing
         if (temp[curv.name]) {
         }
         // If the temporary object does not have this name, add the current object to the prev
         else {
             temp[curv.name] = true;
             prev.push(curv);
         }
         return prev
     }, []);
     console.log("The results", resources);
Copy the code

In this method, the high-order function reduce is used for weight removal. Here, only an empty array [] is required for initialValue, otherwise it cannot be pushed. The detailed explanation of the high-order function reduce can be seen in my previous article [JS must know must know] detailed explanation and practice of the high-order function.

Then: Ask the interviewer about the situation

(If the interviewer doesn’t like what you’re thinking about or what you’re asking, he or she may not even think about it and ask you to redo the list.)

Performance considerations (do you want the fastest data retrieval?)

To test the performance of these solutions, I wrote a test template to calculate the amount of time it takes to undo an array. The template code is as follows:

// distinct.js

let arr1 = Array.from(new Array(100000), (x, index) = >{
    return index
})

let arr2 = Array.from(new Array(50000), (x, index) = >{
    return index+index
})

let start = new Date().getTime()
console.log('Start array de-duplication')

let arr = a.concat(b);

function distinct(arr) {
    // Array decrement
}

console.log('Weight removed length', distinct(arr).length)

let end = new Date().getTime()
console.log('takes', end - start)
Copy the code

After the above multiple arrays are gone, the calculation takes time

Double for loop > array.filter () add indexOf > array.sort () add a line traversal bubbling > Object key/value pairs to repeat > Set in ES6 to duplicate

Note: this is only the result of my test, the specific situation may be different from the scenario, for example, the sorted array is directly de-duplicated, and the performance may be better by using the bubble neighbor comparison directly. You can also try it yourself, if you have any questions, welcome to discuss and point out.

Compatibility and scenario considerations (do arrays contain objects, nans, etc.?)

We need to consider whether the array contains null, undefined, NaN, and object. If both are present, all the above array de-duplicate methods will not be applicable.

Let’s talk about the difference between == and ===

=== strict equality, will compare the two values of the type and value == abstract equality, the comparison, the first type conversion, and then compare the value of the conversion process can see this article js == and === difference

Let me talk about some of the types of equality problems THAT I talked about

let str1 = '123';
let str2 = new String('123');

console.log(str1 == str2); // true
console.log(str1 === str2); // false

console.log(null= =null); // true
console.log(null= = =null); // true

console.log(undefined= =undefined); // true
console.log(undefined= = =undefined); // true

console.log(NaN= =NaN); // false
console.log(NaN= = =NaN); // false

console.log(/a/= =/a/); // false
console.log(/a/= = =/a/); // false

console.log({} == {}); // false
console.log({} === {}); // false
Copy the code

Several deduplication functions are designed for comparison with a particular type

IndexOf and Set

Console. log(NaN === NaN) in the code above; // false. NaN elements cannot be found in indexOf because the underlying indexOf uses ===

// demo1
var arr = [1.2.NaN];
arr.indexOf(NaN); // -1
Copy the code

A Set can override NaN types. Inside a Set, the two elements are thought to be identical even though NaN === NaN is false.

// demo2
function distinct(array) {
   return Array.from(new Set(array));
}
console.log(unique([NaN.NaN])) // [NaN]
Copy the code

Specific to re-compare

Compare such an array as above:

var array = [1.1.'1'.'1'.null.null.undefined.undefined.new String('1'), new String('1'), /a/./a/.NaN.NaN];
Copy the code

Memory considerations (to repeat the process, do you want the lowest space complexity?)

With V8 engines, though, memory considerations are less important, and when there is really a lot of data, it is generally done in the background. However, we can not let go of any one can prove their excellent, or consider, hey hey.

The time complexity is O(1), which is similar to hash table. You can also use Map in ES6 to try to implement this method.

But the object to repeat the space complexity is the highest, because opened up an object, the other several ways have not opened up a new space, from the appearance of it, more in-depth source code to be explored, here is just to show that you can also take time complexity and space complexity into account when answering.

The time complexity of array.filter () + indexOf is O(n). This is not the case. Because indexOf, the source code is actually doing for loop traversal. The concrete implementation is as follows

String.prototype.indexOf = function(s) {
    for (var i = 0; i < this.length - s.length; i++) {
        if (this.charAt(i) === s.charAt(0) &&
            this.substring(i, s.length) === s) {
            returni; }}return -1;
};
Copy the code

Add description of third-party library LoDash

How does LoDash implement de-weighting

Simply say loDash uniQ method source code implementation.

The behavior of this method is the same as the result of deduplicating using Set.

When the array length is greater than or equal to 200, a Set is created and converted to an array for de-duplication (the implementation of a nonexistent Set is not analyzed). When the array length is less than 200, a double loop de-duplication scheme like the one mentioned above is used, plus NaN de-duplication.

conclusion

In addition to being able to code and run the right results, being right also involves being insightful about the question. Consider the following questions:

• To optimize the
• Code specification
• Fault tolerance

In fact, if it is a very difficult problem, for your competitors, it is also difficult, the key lies in the way you express the idea of solving the problem, even by expressing the direction of the idea of solving the problem, and you consider the comprehensiveness of the problem, in fact, not only this simple interview question, algorithm question is so. I’m Koala. That’s all FOR today’s post. Let’s go!

Refer to the article

MDN in some functions explained

Delve into array deduplication

JavaScript topics for array de-duplication

Sorting algorithm learning summary

Pay attention to my

• Welcome to add my wechat [COder_QI], pull you into the technology group, long-term exchange learning…
• Welcome to “programmer growth refers to the north”, a heart to help you grow the public number…

Node series original articles

Learn more about processes and threads in Node.js

To learn node. js, it is necessary to know stream first

Exports: module. Exports: module

Understand the Events module thoroughly

Node.js advanced fs file module learning