Said in the previous

Limited to this is a self-examination manual, the answer is not so detailed, if there is a link under a knowledge point, and they have not in-depth understanding, should click the link or search in-depth understanding.

Two other parts:

Front end test questions self – check JS CSS part
Front end test questions self-test Vue web browser performance optimization part

The basic algorithm

Learning data structures and algorithms in Javascript

The sorting

Stability: elements with the same keyword are sorted in the same position before and after sorting

Selection sort

The most stable algorithm in time complexity, fixed O(n²), has stability

Find the smallest number after a bit and switch; Loop from front to back.

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // Look for the smallest number
                minIndex = j;                 // Save the index with the smallest number
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
Copy the code

Insertion sort

O(n^2) is stable

To continue to compare and exchange positions in a previously ordered sequence until a position is found; Loop back and forth

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}
Copy the code

Merge sort

Order nlog n is not stable

Merge the array, and then split the array in half. And then merge back;

function MergeSort(arr) {
  const len = arr.length
  if (len <= 1) return arr
  const middle = Math.floor(len / 2)
  const left = MergeSort(arr.slice(0, middle))
  const right = MergeSort(arr.slice(middle, len))
  return merge(left, right)
  // Core function
  function merge(left, right) {
    let l = 0 
    let r = 0
    let result = []
    while (l < left.length && r < right.length) {
      if (left[l] < right[r]) {
        result.push(left[l])
        l++
      } else {
        result.push(right[r])
        r++
      }
    }
    result = result.concat(left.slice(l, left.length))
    result = result.concat(right.slice(r, right.length))
    return result
  }
}
Copy the code

Quick sort

Order nlog n is not stable

The writing method of the function is very simple, first take out the first number, first use fliter to divide into less than the area and greater than the area, and then divide and conquer the two; And then we synthesize an array

The filter iterates twice through the array. Instead, the for loop iterates once

function QuickSort(arr) {
  if (arr.length <= 1) return arr
  const flag = arr.shift()
  const left = QuickSort(arr.filter(num= > num <= flag))
  const right = QuickSort(arr.filter(num= > num > flag))
  return [...left, flag, ...right]
}
Copy the code

The tree

The recursive traversal

Front, middle and back sequence traversal

Output on the first pass of a presequence node

Output when the sequence node passes the second time

Output on the third pass of the sequential node

// Preorder traversal
function ProOrderTraverse(biTree) {
    if (biTree == null) return;
    console.log(biTree.data);
    ProOrderTraverse(biTree.lChild);
    ProOrderTraverse(biTree.rChild);
}

// In order traversal
function InOrderTraverse(biTree) {
    if (biTree == null) return;
    InOrderTraverse(biTree.lChild);
    console.log(biTree.data);
    InOrderTraverse(biTree.rChild);
}
 
// Back-order traversal
function PostOrderTraverse(biTree) {
    if (biTree == null) return;
    PostOrderTraverse(biTree.lChild);
    PostOrderTraverse(biTree.rChild);
    console.log(biTree.data);
}


Copy the code

Non-recursive traversal (iterative traversal)

Depth first traversal

The iterative method needs to master both preorder and middle order; In general, we use preorder for traversal, and middle order for binary search trees

Leetcode 144. Preorder traversal of the binary tree

Preorder traversal is adding subtrees as you exit the stack and then looping; Notice that you push the right subtree first and then the left subtree;

In order traversal of binary tree

The sequence traversal is to push the nodes on the left side of the line successively, and push the right node after the stack; You need to use the p pointer to hold the traversal position

As shown in the figure below: First, push a-h, exit H, D, D has the right node, push I, exit I, exit B, B has the right node E, push e-n; And so on…

// Depth first is not recursive
// Preorder traversal
function DepthFirstSearch(biTree) {
    let stack = [biTree];
    while(stack.length ! =0) {
        let node = stack.pop();
        console.log(node.data);
        // Note that rChild is not allowed to access the left subtree first
        if (node.right) stack.push(node.right);
        if(node.left) stack.push(node.left); }}// In order traversal
function DepthFirstInorderSearch(biTree){
    let stack = [biTree]
    let p = biTree
    while(stack.length ! =0) {// The left side of a node is pushed first
        while(p.left){
            stack.push(p.left)
            p = p.left
		}
		p = stack.pop()
		console.log(p.data)
		if(p.right){
            stack.push(p)
            p = p.right
        }
    }
}

// The sequential traversal is https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/
var postorderTraversal = function(root) {
    let res = [];
    if(! root) {return res;
    }
    let stack = [];
    let cur = root;
    do {
        if(cur) {
            stack.push([cur, true]);
            cur = cur.left;
        } else {
            cur = stack[stack.length-1] [0];
            if(! cur.right || ! stack[stack.length-1] [1]) {
                res.push(stack.pop()[0].val);
                cur = null;
            } else {
                stack[stack.length-1] [1] = false;
                cur = stack[stack.length-1] [0].right; }}}while(stack.length);

    return res;
};
Copy the code

Breadth-first traversal (sequential traversal)

// The breadth-first non-recursion is the same as the previous order iteration traversal structure
function BreadthFirstSearch(biTree) {
    let queue = [];
    queue.push(biTree);
    while(queue.length ! =0) {
        let node = queue.shift();
        console.log(node.data);
        if (node.left) {
            queue.push(node.left);
        }
        if(node.right) { queue.push(node.right); }}}Copy the code

Two priority traversal analyses

Both non-recursive traversal constructs are identical, with one major difference

Depth-first is stack (first in, first out) and breadth-first is queue (first in, first out)
Since depth-first is stack, when pushing left and right subtrees, the right subtree should be pushed first and then the left subtree should be pushed to ensure left-to-right order

generate

Sequence spanning tree

class Node { // Define the node
    constructor(data){
        this.data = data
        this.left = null
        this.right = null}}// Sequence traversal of the resulting array, generating sequence traversal tree
/ / input cases [' a ', 'b', 'd', null, null, 'e', null, null, 'c', null, null] # is null
// a
/ / / /
// b d
// / \ / \
// # # e #
/ / / /
// # c
/ / / /
/ / # #
function CreateTree(arr) {
  let i = 0
  const head = new Node(arr[i++])
  let queue = [head]
  let next
  while (queue.length) {
    let node = queue.shift()
    next = arr[i++]
    if(! (next ==null)) queue.push((node.left = new Node(next)))
    next = arr[i++]
    if(! (next ==null)) queue.push((node.right = new Node(next)))
  }
  return head
}
// Or for of can simulate queues
function CreateTree(arr) {
  let i = 0
  const head = new Node(arr[i++])
  let queue = [head]
  let next
  for (let node of queue) {
    next = arr[i++]
    if(! (next ==null)) queue.push((node.left = new Node(next)))
    next = arr[i++]
    if(! (next ==null)) queue.push((node.right = new Node(next)))
  }
  return head
}
Copy the code

Binary Search Tree (BST)

A thorough grasp of binary search tree, (multi-group GIFs) history of the most complete summary

define

When the left subtree is not empty, all nodes in the left subtree are less than the root node
When the right subtree is not empty, all nodes in the right subtree are greater than the root node
Left and right subtrees are also binary search trees
There are no duplicate nodes

Other features

In order traversal output is ordered sequence

Can be used to output the KTH largest/smallest node
The leftmost node has the smallest value and the rightmost node has the largest value

search

If the tree is empty, the search is missed and null is returned.

If the searched key is equal to that of the root node, the value of the root node is returned.

If the searched key is small, the search continues in the left subtree, and if the searched key is large, the search continues in the right subtree.

Performance: best O(logn) a balanced binary tree worst O(n) degradation to a linked list

/ / the recursive method
function search(head, data){
    // Select * from subtree where root is x; // Select * from subtree where root is x
    // If not, return null
    if(head == null) return null;
    if(data < head.data) return search(head.left, data);
    else if(data > head.data) return search(head.right, data);
    else return head;
}
/ / iteration method
function search(head, data) {
  while (head) {
    if (data < head.data) head = head.left
    else if (data > head.data) head = head.right
    else return head
  }
  return null
}
Copy the code

insert

Inserts are inserted as leaf nodes
You need to look before you insert

function insert(head, data) {
  if (head === null) return new Node(data)
  while (true) {
    if (data < head.data) {
      if (head.left) head = head.left
      else return (head.left = new Node(data))
    } else if (data > head.data) {
      if (head.right) head = head.rightleft
      else return (head.right = new Node(data))
    } else return false}}Copy the code

Is this insertion algorithm for binary search trees guaranteed to be correct? Yes, it must be by definition inserted like this; But a set of unordered data, it can have n kinds of binary search tree forms, among which there is a binary search tree, its left subtree and the right subtree height difference is not more than 1, can bring the best performance to search, this is the balanced binary tree, balanced binary tree can be adjusted by ordinary binary search tree.

The heap

Perfect binary tree

Complete binary trees have the following properties:

The number pair of the node should be at the index of the array
If the subscript of the parent node is I, the subscript of the left child node is 2i + 1, and the subscript of the right child node is 2I + 2

Depending on the location of the root node, when the root node number is 0, the subscript of the left child node is 2I + 1, and the subscript of the right child node is 2I + 2

When the root node number is 1, the subscript of the left child node is 2i, and the subscript of the right child node is 2i + 1

Because of this property, complete binary trees are generally stored as arrays.

A heap is a complete binary tree.

define

Take the small top heap for example (the large top heap replaces less than with greater than)

The root node is less than or equal to all nodes in the left and right subtrees
If the subtree exists, it is also a heap

Function:

Heap sort

On the original array, the large top heap can be converted to an ascending sequence; The small top heap can be converted to a descending sequence;

You can get the KTH largest/smallest element

Heap sort:

There are three steps to heap sorting

1. Build the heap

2. Remove the top element of the heap and place the bottom element on the top

Because the element at the top of the heap is the largest/smallest of all the current elements, fetching in order is an ordered sequence

3. Filter (i.e. rebuild the heap)

Repeat steps 2 and 3

screening

Filtering: The process of rebuilding the heap when the root element of the heap has changed

Or the following conditions can be met to filter

The left and right subtrees are heaps, and the height difference is not greater than 1

Heap building also needs filtering, filtering steps throughout the heap sorting, so it is the most important heap;

The specific steps are as follows

Find the node with the largest value of the left and right child nodes and compare it with the root node. If the value is greater than the root node, then exchange their values, and then move the pointer down to the swapped child node; And so on and so forth
If a node is not larger than the root node or a leaf node, it indicates that the current tree conforms to the specification of the heap, and directly returns;

Analysis: Since the subtree must be the heap, the root element of the heap changes, and the heap is rebuilt until there is no interchange or leaf

As shown in the figure below, the root node changes to 6 and exchanges with the left child node, and then the pointer moves to the left child node

// The parent node switches
function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}
/ / filter
function shiftDown(A, i, length) {
  let temp = A[i] // The current parent node
  // select * from 'I' where 'I' = 'I'
  for (let j = 2 * i + 1; j < length; j = 2 * i + 1) {
    temp = A[i] // Remove A[I], the whole process is equivalent to finding the position where A[I] should be
    if (j + 1 < length && A[j] < A[j + 1]) {
      j++ // Find the older of the two children and compare it with the parent
    }
    if (temp < A[j]) {
      swap(A, i, j) // If the parent node is smaller than the child node: switch; Or jump out
      i = j // After switching, the subscript of temp is changed to j
    } else {
      break}}}Copy the code

To establish

We put in an unordered array, how do we pile it up? You just need to start from the last node, to the first node, each filter, can form a heap; In fact, the heap is built from the last non-leaf node, because the leaf node is already a heap and there is no need to filter.

Analysis: If there is a non-leaf node N, and the left and right child nodes 2n + 1, 2, n + 2, because 2n + 1 and 2n + 2 have been previously filtered, they are already heap, the problem becomes: when the root element of the heap changes, the process of rebuilding the heap; All the way down to the root node and then the whole array is a heap

function createHeap(A) {
  // Start with the last non-leaf node which is math.floor (a.length / 2-1)
  for (let i = Math.floor(A.length / 2 - 1); i >= 0; i--) {
    shiftDown(A, i, A.length)
  }
}
Copy the code

The sorting

We already know the sorting principle: build the heap, take the maximum, rebuild the heap

/ / heap sort
function heapSort(A) {
  // Initialize the large top heap, starting with the first non-leaf node
  createHeap(A)
  // Sort, each for loop to find a current maximum, the array length minus one
  for(let i = Math.floor(A.length-1); i>0; i--) {
    swap(A, 0, i); // The root node switches with the last node
    shiftDown(A, 0, i); // Start from the root node}}Copy the code

other

Binary search

The logic is simple. After determining the size of the array [middle index] compared to the search value, the left or right index moves to the middle index. Note that the point is the boundary handling problem

// The logic is simple. The main problem is boundary handling
function binarySearch(arr, num) {
  let left = 0
  let right = arr.length - 1
  let middle
  while (right - left > 1) {
    middle = Math.floor((left + right) / 2)
    const now = arr[middle]
    if (num === now) return middle
    if (num > now) left = middle
    else right = middle
  }
  if (arr[right] === num) return right
  if (arr[left] === num) return left
  return -1
}

// return the absolute value of the difference between the root square and num is less than this precision
function sqrtInt(num, precision) {
  precision = 1 / 10 ** precision // Convert to end like 0.1
  let left = 1
  let right = (1 + num) / 2
  while (true) {
    const middle = (left + right) / 2
    const middleSquare = middle ** 2
    const diff = middleSquare - num
    if (Math.abs(diff) < precision) return middle
    if (diff > 0) right = middle
    else left = middle
  }
}
Copy the code

Design patterns

9 Design Patterns to know about the front end

I. Structural Patterns

Simplify system design by identifying simple relationships among the components of the system.

Adapter mode

An adapter solves a mismatch between two existing interfaces without considering how the interface is implemented or how it should be modified in the future. Adapters allow them to work together without modifying existing interfaces;

The appearance model

The look and feel pattern is one of the most common design patterns that provides a unified, high-level interface for a set of interfaces in a subsystem, making the subsystem easier to use. In short, the design pattern abstracts complex logic from multiple subsystems to provide a more unified, concise, and easy-to-use API. Many commonly used frameworks and libraries follow the design pattern, such as JQuery, which abstracts and encapsulates complex native DOM operations and eliminates interoperability issues between browsers, thus providing a more advanced and easier to use version. In fact, in our daily work, we often use the appearance mode for development, but we do not know it.

For example, we can apply the appearance pattern to encapsulate a unified DOM element event binding/cancellation method that is compatible with different browser versions and easier to call:

// Bind the event
function addEvent(element, event, handler) {
  if (element.addEventListener) {
    element.addEventListener(event, handler, false);
  } else if (element.attachEvent) {
    element.attachEvent('on' + event, handler);
  } else {
    element['on'+ event] = fn; }}// Cancel the binding
function removeEvent(element, event, handler) {
  if (element.removeEventListener) {
    element.removeEventListener(event, handler, false);
  } else if (element.detachEvent) {
    element.detachEvent('on' + event, handler);
  } else {
    element['on' + event] = null; }}Copy the code

The proxy pattern

The proxy mode can solve the following problems:

Adds access control to an object
Additional logic is required when accessing an object

There are three parts to implementing the proxy pattern:

Real Subject: Real object
Proxy: Proxy object
SubjectInterface: The interface that both the Real Subject and Proxy need to implement so that the Proxy can be used as a “surrogate” of the Real Subject

Creational Patterns

Handle the creation of objects, using the appropriate way to create objects according to the actual situation. Conventional methods of object creation can cause design problems or add complexity to the design. The creation pattern solves the problem by controlling the creation of objects in some way.

The factory pattern

Encapsulate the constructor twice

The singleton pattern

As the name implies, the number of instances of a Class in a singleton pattern is at most 1. The singleton pattern comes in handy when an object is needed to perform some task across the system. In other scenarios, try to avoid using singletons because singletons introduce global state, and a healthy system should avoid introducing too much global state.

Behavioral Patterns

Used to identify common interaction patterns between objects and implement them, thus increasing the flexibility of these interactions.

Observer mode

The observer Pattern, also known as the Publish/Subscribe Pattern, is a design Pattern that we are often exposed to. It is also widely used in daily life. For example, if you Subscribe to a blogger’s channel, you will receive push updates when there is content. Another example is the event subscription response mechanism in JavaScript. The idea of the observer pattern is described in one sentence: a subject maintains a set of observers, and when the observed object’s state changes, the observer is notified of the changes by calling one of the observer’s methods.

The strategy pattern

The simple description of the policy pattern is that the object has a certain behavior, but in different scenarios, the behavior has different implementation algorithms. For example, everyone has to “pay personal income tax”, but “pay personal income tax in America” and “pay personal income tax in China” have different methods. In the most common login authentication scenarios, the authentication algorithm depends on the login mode of the user, such as mobile phone, email, or Third-Party wechat login, and the login mode can be obtained only during the running time. After the login mode is obtained, the authentication policy can be dynamically configured. All of these policies should implement a uniform interface, or have a uniform pattern of behavior. The well-known authentication library Passport. Js API in the Node ecosystem is designed to apply the policy pattern.

Using the login authentication example again, let’s use code to understand the policy pattern in the same way as passport. Js:

Separate the logic from the if-else into different methods, paying more attention to the logic within different methods and making switching easier.

/** * Log in to the controller */
function LoginController() {
  this.strategy = undefined;
  this.setStrategy = function (strategy) {
    this.strategy = strategy;
    this.login = this.strategy.login; }}/** * User name and password login policy */
function LocalStragegy() {
  this.login = ({ username, password }) = > {
    console.log(username, password);
    // authenticating with username and password... }}/** * Mobile phone number and verification code Login policy */
function PhoneStragety() {
  this.login = ({ phone, verifyCode }) = > {
    console.log(phone, verifyCode);
    // authenticating with hone and verifyCode... }}/** * Third party social login policies */
function SocialStragety() {
  this.login = ({ id, secret }) = > {
    console.log(id, secret);
    // authenticating with id and secret... }}const loginController = new LoginController();

// Call the user name and password login interface, using LocalStrategy
app.use('/login/local'.function (req, res) {
  loginController.setStrategy(new LocalStragegy());
  loginController.login(req.body);
});

// Call the phone/captcha login interface, using PhoneStrategy
app.use('/login/phone'.function (req, res) {
  loginController.setStrategy(new PhoneStragety());
  loginController.login(req.body);
});

// Call the social login interface, using SocialStrategy
app.use('/login/social'.function (req, res) {
  loginController.setStrategy(new SocialStragety());
  loginController.login(req.body);
});
Copy the code

From the above examples, you can see that using the policy pattern has the following advantages:

Easy to switch algorithms and policies at run time
The code is more concise and avoids using a lot of conditional judgment
Separation of concerns, each Strategy class controls its own algorithm logic, strategy and its users are also independent of each other

The operating system

“Wang Dao operating system” study notes total directory + mind map

Process related

What’s the difference between processes and threads?

A process is the smallest unit of resource allocation, and a thread is the smallest unit of CPU scheduling
Threads travel under processes, and a process can contain more than one thread
It is difficult to share data between different processes, but it is easy to share data between different threads in the same process
Thread context switches are much faster than process context switches
Processes consume more computer resources than threads
Processes do not interact with each other, and a thread failure causes the entire process to die

Interprocess communication IPC

Five ways of interprocess communication

IPC includes pipe, system IPC (semaphore, message queue, and shared memory), and socket.

A deadlock

Deadlock refers to a deadlock caused by multiple processes competing for resources in the process of running. When a process is in this deadlock state, it will not be able to move forward without external force.

Processes occupy resources required by each other and wait for each other to release resources.

Avoid deadlocks – Banker algorithm

Prevent the system from entering an unsafe state

Total amount of each resource in the system
Total amount of each resource allocated to the system
Total unallocated amount of each resource in the system

First, there is a list of process requirements that request allocation, some of which have already been allocated some resources;

Select a remaining resources of the resources needed to meet the process, process release resources before the system will allocate the resources and the just distribution of resources recycling together (so the remaining resources increases, can satisfy more process), continue to select a process, can satisfy so repeatedly, until all processes are satisfied

This satisfying sequence of processes is called the secure queue, and finding the secure queue prevents the system from entering an insecure state

First you need to define the concepts of state and security state. The system status is the current resources allocated to processes. Thus, the state consists of two vectors Resource (the total amount of each Resource in the system) and Available (the total amount of each Resource not allocated to the process) and two matrices Claim (representing the process’s demand for the Resource) and Allocation (representing the resources currently allocated to the process). A safe state means that at least one resource allocation sequence does not cause a deadlock. When a process requests a set of resources, it assumes that the request is granted, thus changing the state of the system, and then determines whether the result is still in a safe state. If so, grant the request; If not, block the process until the request is granted and the system state remains safe.

Job scheduling algorithm

First Come First service

Service the jobs in order of arrival. The disadvantage is disadvantageous to short assignments

Short First Server

The shortest jobs are served first. Disadvantages are disadvantageous to long work and may produce hunger

Minimum remaining time is preferred

A preemptive version of short job first.

The scheduler always chooses the process with the shortest remaining run time to run. When a new job arrives, its entire time is compared to the remaining time of the current process. If the new process takes less time than the current running process, the current process is suspended and the new process is run.

Time slice rotation method

Assign services to each process in turn so that each service can be responded to. It’s a preemptive algorithm

Each process in turn executes a time slice (say 100ms) in the order in which it arrives on the ready queue. If the process does not complete within a time slice, the processor is stripped and the process is requeued by putting it back at the end of the ready queue.

Front end test question self – check algorithm design mode operating system part

Said in the previous

The basic algorithm

The sorting

Selection sort

Insertion sort

Merge sort

Quick sort

The tree

The recursive traversal

Front, middle and back sequence traversal

Non-recursive traversal (iterative traversal)

Depth first traversal

Breadth-first traversal (sequential traversal)

Two priority traversal analyses

generate

Sequence spanning tree

Binary Search Tree (BST)

define

search

insert

The heap

Perfect binary tree

define

screening

To establish

The sorting

other

Binary search

Design patterns

I. Structural Patterns

Adapter mode

The appearance model

The proxy pattern

Creational Patterns

The factory pattern

The singleton pattern

Behavioral Patterns

Observer mode

The strategy pattern

The operating system

Process related

What’s the difference between processes and threads?

Interprocess communication IPC

A deadlock

Avoid deadlocks – Banker algorithm

Job scheduling algorithm

First Come First service

Short First Server

Minimum remaining time is preferred

Time slice rotation method

Memory replacement algorithm

Optimal permutation algorithm

First in first out

Most Recently Unused permutation algorithm (LRU)

Disk arm scheduling algorithm

First come, first served

Shortest search time first algorithm

The elevator algorithm

Related Posts

Call, apply, bind

CSS Revealed – Structure and Layout (1)

Using qrcodeJs2 plug-in, the URL automatically generates two-dimensional code