preface

In my last article, I wrote some pen questions for the interview, not all of them (ha ha ha, basically all of them are memorized by the brain, and some of them are forgotten).

The portal is here: June 2018 front-end interview experience (I) ~ ~ ~

In this article, I will write some algorithm problems I encountered, the solution is not uniform, I hope you can provide their own ideas and code ~

Algorithm problem

1) Quicksort

Ideas: - Select A random number in the array, A, and base it on that number. - Compare other numbers to that number, and place those smaller to the left and those larger to the right. - After one loop, the left of A is less than A, Const Arr = [85, 24, 63, 45, 17, 31, 96, 50]; const Arr = [85, 24, 63, 45, 17, 31, 96, 50];function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else{ right.push(arr[i]); }} // RecursivereturnquickSort(left).concat([pivot], quickSort(right)); } console.log(quickSort(Arr)); Ps: This is a quick typeset method of Teacher Ruan. There are many debates about this on the Internet. First, teacher Ruan should not use splice to value, should use subscript, and should not open two new arrays every time. In fact, I think the algorithm is important ideas, there are many ways to achieve, do not necessarily say who is right who is wrong, the better the efficiency of the algorithm is indeed what we want, but more understanding of some different implementation ideas, I think it is also possible ~.Copy the code

Here’s a different voice: Interviewer: Nguyen yifeng’s version of quicksort is all wrong

2) Dichotomous sorting

Binary search method is mainly to solve the problem of “find the specified number in a bunch of ordered numbers”, no matter these numbers are one-dimensional array or multidimensional array, as long as the order, you can use binary search to optimize.

Binary search is a “divide and conquer” algorithm, roughly the process is as follows:

  • The middle number in the array, A, is compared to the number you are looking for
  • Because the array is ordered, a) a large number means that the number to be looked for should be in the first half b) a
  • Smaller means you should search from the second half of the search number
  • This keeps the search shrinking by orders of magnitude (throwing away half the data) until the array is gone
In a two-dimensional array, each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Complete a function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.function Find(target, array) {
    let i = 0;
    let j = array[i].length - 1;
    while (i < array.length && j >= 0) {
        if (array[i][j] < target) {
            i++;
        } else if (array[i][j] > target) {
            j--;
        } else {
            return true; }}return false; } / / test cases to the console. The log (Find (10, [[1, 2, 3, 4], [5, 9, 10, 11], [13, 20, 21, 23]]));Copy the code

3) Parses the parameters after the URL

function parseParam(url) {
  let obj = {};
  let arr = url.split("?");
  if(arr. Length == 1) {// Judge without question markreturn "No parameters"
  }
  let total = arr[1].split("&");
  for (let i = 0; i < total.length; i++) {
    let single = total[i].split("=");
    if (single[0] == ' ') {// Determine whether there is? But there are no parametersreturn 'No arguments'
    }
    if(! single[1]) { obj[single[0]] =true;
    } else {
      if (obj[single[0]]) {
        let concat
        if(! Array.isarray (obj[single[0]])) {// Concat = [obj[single[0]]]}else{ concat = obj[single[0]]; } concat.push(single[1]); concat = new Set(concat); Concat = array. from(concat) obj[single[0]] = concat}elseDecodeURI (single[1]) {obj[0]] = decodeURI(single[1])}}return obj
}

var url = 'http://www.baidu.com/?user=huixin&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled';

var params = parseParam(url)

console.log(params)
Copy the code

4) Implement a simple template engine:

Column: My name is A, age B, gender C; Let data = {name: ‘small ‘, age: 18,} undefined return undefined


let template = 'I am {name}, age {age}, gender {sex}';
    let data = {
        name: 'Ming',
        age: 18,
    }
    const  reg= /({([a-zA-Z]+)})/g;
    var r= ' ',regrounp={};
    while( r = reg.exec(template) ){
        Object.defineProperty(regrounp,r[2],{
            enumerable:true,
            value:r[2]
        })
    }

    var render = (template,regrounp)=>{
        var result=' ';
        for( key in regrounp){
            if(data[key] == undefined){
                result  = (result || template).replace(new RegExp(`{${regrounp[key]}} `,"g"),undefined);
            }else{		
                result  = (result || template).replace(new RegExp(`{${regrounp[key]}} `,"g"),data[key]); }}return result
    }
    letnewtemple = render(template, regrounp); Console. log(newtemple) // Result: I am Xiao Ming, age 18, gender undefinedCopy the code

Object. DefineProperty enumerable {}} can be used as an enumerable, Object. DefineProperty can’t use for-in enumerable unless you define Enumerable: True.

There is a good article here that recommends writing a simple JavaScript template engine

5) How to quickly turn a string into a number with 1000 precision

function exchange(num) {
    num += ' '; // To a stringif (num.length <= 3) {
        returnnum; } num = num. Replace (/ \ d {1, 3} (? =(\d{3})+$)/g, (v) => { console.log(v)return v + ', ';
    });
    return num;
}

console.log(exchange(1234567));

Copy the code

6) Implement deep copy of JS objects

A deep copy is a copy of all reference structures of the data. To put it simply, if two data structures are identical and independent in memory, the reference type is copied instead of just the reference relationship.

How to make deep copy:

  • First, assume that the deep copy method has been completed, called deepClone
  • To copy a piece of data, we must iterate over its properties. If the properties of the object are still objects, we continue to use this method, and so on
function deepClone(o1, o2) {
    for (let k in o2) {
        if (typeof o2[k] === 'object') {
            o1[k] = {};
            deepClone(o1[k], o2[k]);
        } else{ o1[k] = o2[k]; }}} // Test caselet obj = {
    a: 1,
    b: [1, 2, 3],
    c: {}
};
let emptyObj = Object.create(null);
deepClone(emptyObj, obj);
console.log(emptyObj.a == obj.a);
console.log(emptyObj.b == obj.b);

Copy the code

Recursion is easy to cause stack explosion, tail call can solve the problem of recursion, Chrome V8 made tail call optimization, we should also pay attention to tail call writing when writing code. The recursive stack burst problem can be solved by rewriting the recursion into enumerations, using either for or while instead of recursion.

7) for the Fibonacci sequence (rabbit series) 1,1,2,3,5,8,13,21,34,55,89… The NTH term in

In the following code, count counts the number of recursions. Let's look at the value of count in the two different codes:let count = 0;
 function fn(n) {
    let cache = {};
    function _fn(n) {
        if (cache[n]) {
            return cache[n];
        }
        count++;
        if (n == 1 || n == 2) {
            return 1;
        }
        let prev = _fn(n - 1);
        cache[n - 1] = prev;
        let next = _fn(n - 2);
        cache[n - 2] = next;
        return prev + next;
    }
    return _fn(n);
}

let count2 = 0;
function fn2(n) {
    count2++;
    if (n == 1 || n == 2) {
        return 1;
    }
    returnfn2(n - 1) + fn2(n - 2); } console.log(fn(20), count); // 6765 20 console.log(fn2(20), count2); / / 6765 13529Copy the code

8) Efficiency of the algorithm

The quality of algorithm can be measured by algorithm complexity, which includes time complexity and space complexity. Due to the characteristics of easy estimation and evaluation, time complexity is the focus of the interview. Spatial complexity is not examined much in interviews.

Common time complexities are:

  • Constant of the orderO(1)
  • The logarithmic orderO(logN)
  • Linear orderO(n)
  • Linear logarithmic orderO(nlogN)
  • Square orderO(n^2)
  • Cubic orderO(n^3)
  • ! K to the power stageO(n^k)
  • The index orderO(2^n)

As the problem size n increases, the above time complexity increases, and the execution efficiency of the algorithm decreases.

Generally, the following tips are followed for algorithm complexity analysis:

  • If you look at how many cycles there are, generally one is O(n), two is O(n^2), and so on
  • If there’s two, it’s order logN.
  • Keep the highest term and get rid of the constant term

Title: Analyze the algorithmic complexity of the following code

leti =0; // Execute the statement oncewhile(I < n) {// Statement console.log(' Current I is${i}`); I++; } The algorithm complexity is 1 + n + n + n = 1 + 3n, and the constant term is removed, which is O(n).Copy the code

In fact, there are many algorithm problems, such as binary tree increase, delete, change, etc., recommend everyone to have a look at the free time at night ~ or very interesting ~

Extended resources:

Learn about data structures and algorithms in JavaScript

I have been exposed to front-end data structures and algorithms

eggs

The hr interview

1) What do you think of yourself?

2) Why did you leave?

3) What did you dislike most about your former leader?

4) What do you do on weekends?

5) What was your favorite project to work on? Why is that?

6) What kind of team do you like?

React is my technology stack, so the next topic is around react ~