Front end interview questions-1-10

1. How to optimize the simple selection sorting algorithm?

The basic idea of selective sorting: take out the minimum value in each cycle(maximum)Element as first element
 When the algorithm is implemented, every time the minimum element is determined, it will be continuously compared and exchanged to ensure the minimum first position;
It is not difficult to find that the exchange before determining the minimum is meaningless. We can set a variable min To record the subscript of the minimum value, and finally perform the exchange operation.
function selectSort(array) {
    let length = array.length;
    // If it is not an array or the array length is less than or equal to 1, it is returned directly without sorting 
    if (!Array.isArray(array) || length <= 1) return;
    for (let i = 0; i < length - 1; i++) {
        let minIndex = i; 
        // Sets the minimum element index of the current loop 
        for (let j = i + 1; j < length; j++) { 
            // If the current element is smaller than the minimum element index, the minimum element index is updated 
            if (array[minIndex] > array[j]) { 
                minIndex = j; 
            } 
        }
        // Swap the smallest element to the current location 
        [array[i], array[minIndex]] = [array[minIndex], array[i]];
    }
    return array;
}

2. Describe the "insert sort" algorithm

Insert sort: the basic idea is to insert an element to be sorted into the previously arranged sequence at each step until all elements are inserted.

Insert sort core--Poker thought: just think that you are playing poker. It doesn't matter where you put the first one. Then connect the second one, which is smaller than the first one. Put it on the left and continue to connect. It may be the middle number, which is inserted in the middle....In turn.
function insertSort(array) {
    // If it is not an array or the array length is less than or equal to 1, it is returned directly without sorting 
    if (!Array.isArray(array) || array.length <= 1) return; 
    let len = array.length;
    for(let i=1; i<len; i++) {
        // Select the target location from the sorted area [0,i)
        for(let j=0; j<i; j++) {
            if(array[i]<array[j]) {
                [array[j], array[i]] = [array[i], array[j]];
            }
        }
    }
    return array;
}

3. Briefly describe "Hill sort"?

 The basic idea of Hill sort is to group the arrays according to a certain increment of subscript, and use the direct insertion sort algorithm for each group; As the increment decreases, each group contains more and more elements. When the increment decreases to 1, the whole array is divided into one group, and the algorithm terminates.
 
In the picture above:

Initially, there is an unordered sequence with a size of 10.

In the first sort, we might as well set gap1 = N / 2 = 5,That is, elements with a distance of 5 form a group, which can be divided into 5 groups.

Next, each group is sorted according to the direct insertion sorting method.

In the second sort, we put the last one gap Halve, i.e gap2 = gap1 / 2 = 2 (Take integer). In this way, each element with a distance of 2 forms a group, which can be divided into 2 groups.

Sort each group by direct insertion sort.

In the third sort, put the gap Halve, i.e gap3 = gap2 / 2 = 1.  In this way, the elements with a distance of 1 form a group, that is, there is only one group.

Sort each group by direct insertion sort. At this point, the sorting is over.

It should be noted that there are two elements 5 and 5 with equal values in the figure. We can clearly see that in the sorting process, the positions of the two elements are exchanged.

Therefore, Hill sorting is an unstable algorithm.
function hillSort(data) {
    let gap = Math.floor(data.length / 2);
    // Used to store data to be inserted
    let temp;
    // Note that i starts from gap, because data[0] is the reference number, j=i-1
    while (gap >= 1) {
        for (let i = gap; i < data.length; i++) {
            // Save the ith number for later insertion into the appropriate position
            temp = data[i]; 
            // Because the first i-1 numbers are ordered from small to large, as long as the current comparison number (data[j-1]) is larger than temp, move this number one bit back
            // This j has to be declared with var, because J is also used in the scope outside the for loop
            for (var j = i - gap; j >= 0 && data[j] > temp; j = j - gap) {
                data[j + gap] = data[j];
            }
            // Insert temp into the appropriate position
            data[j + gap] = temp;
        }
        gap = Math.floor(gap / 2);
    }
    return data;
}

4.

5. Briefly describe the principle of reverse proxy to solve cross domain problems?

5.1 cross domain

Cross domain is browser behavior, not server behavior.
In fact, the request has arrived at the server, but it is limited by the browser when it comes back. Like Python He can grab data, just as he can get data by sending a request without going through the browser.

5.2 agency

  1. The so-called proxy means that there is a proxy server between us and the real server, through which all our requests are transferred.

  2. Forward agent: we can't access Google, but I have a vps abroad that can access Google. I visit it and ask it to access Google and pass the data to me.

  3. Reverse proxy: reverse proxy hides the real server when we request www.baidu.com COM, just like dialing 10086, there may be thousands of servers behind us,
    But you don't know or need to know which one. You just need to know who the reverse proxy server is, www.baidu.com COM is our reverse proxy server,
    The reverse proxy server will help us forward the request to the real server.

    Summary:
    The forward proxy hides the real client.
    Reverse proxy hides the real server.

6.

7. How to understand the stability of sorting algorithm?

1,Stability means that the relative order cannot be changed for the same value.
 Generally speaking, there are two identical numbers A and B,Before sorting A stay B In front of the,
 And after sorting, B Run to A In front of, for the occurrence of this situation, we call it sequencing instability.
2.What does stability mean?
  Personal understanding for the front end, for example, we are familiar with the virtual in the framework DOM We compare one<ul>The list is used for rendering. When the data changes and needs to be compared,
   Unstable sorting or operation will change things that do not need to be changed, resulting in re rendering and performance loss.

8.js implements a function to complete the addition of two large integers beyond the range?

 The main idea is to convert numbers into strings, and then add each string in bits.
function add(a,b){
    // Save final results
    var res='';

    // Save the result of adding two digits of [this cycle] and the carry value of [last cycle]
    var c=0;

    // String to array b
    a = a.split('');
    b = b.split('');

    while (a.length || b.length || c){
        // ~~Used to convert String type to Number type
        // Add the result of adding two bits to the carry value
        c += ~~a.pop() + ~~b.pop();

        // Take the remainder and splice the remainder into the final result
        res = c % 10 + res;

        // Save carry, true or false
        // During implicit type conversion, true will be changed to 1 and false will be changed to 0
        c = c>9; // This carry value is added to the next calculation result
    }
    return res;
}

calculation:

1.add('11111111111111137','22222222222222288')
2.//   33333333333333425

9.js how to realize array flattening?

  • ES6 adds an extension operator to take out all the traversable attributes of the parameter object and copy them to the current object:
var arr = [1, [2, [3, 4]]];
console.log([].concat(...arr)); 
// [1, 2, [3, 4]]
  • The above method can only flatten one layer, but keep thinking along this method, we can write this method:
var arr = [1, [2, [3, 4]]];
function flatten(arr) {
    while (arr.some(item => Array.isArray(item))) {
        arr = [].concat(...arr);
    }
    return arr;
}
console.log(flatten(arr));
// [1, 2, 3, 4]

10.ES6 how to gracefully implement array de duplication?

  along with ES6 With the advent of, the method of weight removal has made progress again. For example, we can use it Set and Map Data structure to Set For example, ES6 Provides a new data structure Set. It is similar to an array, but the values of members are unique and there are no duplicate values.
var array = [1, 2, 1, 1, '1'];

function unique(array) {
   return Array.from(new Set(array));
}

console.log(unique(array)); // [1, 2, "1"]
It can even be simplified as follows:
function unique(array) {
    return [...new Set(array)];
}
It can also be simplified as follows:
var unique = (a) => [...new Set(a)]

In addition, if Map is used:

function unique (arr) {
    const seen = new Map()
    return arr.filter((a) => !seen.has(a) && seen.set(a, 1))
}

Added by mickfitz on Sun, 20 Feb 2022 01:49:54 +0200