Video interview uHF online programming questions. This is enough for most companies

The introduction

Now the big factory interview will almost ask the algorithm, can’t answer will let you in the interviewer’s front discount. How to advance the front-end algorithm?

This week is the third week of Aquarius advanced algorithms 🎉🎉🎉. Here, we will take you to build a complete front-end data structure and algorithm system from 0 to 1.

This week is not only a simple list operations (general list of problems can consider to use speed pointer), began to involve the five commonly used algorithm strategy, binary tree, Trie tree, queue, etc., just as a primer, behind will be described in detail, divergent thinking, you will discover that the algorithm in the interview, the development of the algorithm is really very easy.

Past wonderful series

• 10 questions and 10 answers, a quick introduction to front-end algorithms
• Front-end advanced algorithm 4: the list is so simple (+ Leetcode brush problem)
• Front-end advanced algorithm 3: learning LRU algorithm from browser cache elimination strategy and Vue keep-Alive
• Summary of the first week of the advanced algorithm camp
• Front-end advanced algorithm 2: From Chrome V8 source code to see JavaScript array
• Front-end advanced algorithm 1: How to analyze and count the efficiency and resource consumption of the algorithm?

And the title:

• Leetcode88: merge two ordered arrays
• Byte & Leetcode1: Sum of two numbers
• Tencent: Array flatten, deduplicate, sort
• Leetcode349: Given two arrays, write a function to calculate their intersection
• Leetcode146: Design and implement an LRU (least recently used) caching mechanism
• Ali algorithm problem: write a function to calculate the intersection of multiple arrays
• Leetcode21: Merges two ordered lists
• Leetcode141: Determine if a singly linked list has a loop
• Diagram LeetCode206: Reverse linked list
• Leetcode876: Find the middle node of the linked list
• Leetcode19: deletes the NTH node from the reciprocal of the linked list
• Diagram Byte & LeetCode160: Write a program to find the starting node where two single linked lists intersect
• Diagram byte & Leetcode151: Flips the words in a string
• Leetcode14: longest common prefix

This section is a summary and review of week 3, so let’s get started! 👇 👇 👇

Byte & PBT & LEetCode14: the longest common prefix

1. The subject

Write a function to find the longest common prefix in an array of strings.

Returns an empty string “” if no common prefix exists.

Example 1:

Input:"flower"."flow"."flight"] output:"fl"
Copy the code

Example 2:

Input:"dog"."racecar"."car"] output:""Explanation: Input does not have a common prefix.Copy the code

2. The answer

Solution 1: Compare one by one

Compare a string from front to back to get a common prefix

To help you understand:

Code implementation:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    let prevs = strs[0]
    for(let i = 1; i < strs.length; i++) {
        let j = 0
        for(; j < prevs.length && j < strs[i].length; j++) {
            if(prevs.charAt(j) ! == strs[i].charAt(j))break
        }
        prevs = prevs.substring(0, j)
        if(prevs === "") return ""
    }
    return prevs
};
Copy the code

Time complexity: O(s), where s is the sum of the number of characters in all strings

Space complexity: O(1)

Solution 2: only the longest common prefix of the largest and smallest strings

The longest public prefix of the smallest string and the longest public prefix of the largest string is also the public prefix of the other strings, which is the longest public prefix of the string array

For example, ABC, abcd, ab, and ac. The longest common prefix of the minimum ab and maximum AC must also be the common prefix of ABC and abcd

To help you understand:

Code implementation:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    if(strs.length === 1) return strs[0]
    let min = 0, max = 0
    for(let i = 1; i < strs.length; i++) {
        if(strs[min] > strs[i]) min = i
        if(strs[max] < strs[i]) max = i
    }
    for(let j = 0; j < strs[min].length; j++) {
        if(strs[min].charAt(j) ! == strs[max].charAt(j)) {return strs[min].substring(0, j)
        }
    }
    return strs[min]
};
Copy the code

Time complexity: O(n+m), where n is the length of the array and m is the length of the shortest character in the string array

Space complexity: O(1)

Solution 3: divide and conquer strategy merge idea

Divide and conquer, as the name suggests, is to divide and conquer, to divide a complex problem into two or more similar subproblems, and then divide the subproblems into smaller subproblems, until the smaller subproblems can be easily solved, and by solving the subproblems, the solution of the original problem is a combination of the solutions of the subproblems.

This is a classic divide-and-conquer problem:

• Problem: Find the longest common prefix for multiple strings
• Decompose into similar subproblems: Find the longest common prefix of two strings
• The subproblem is simple to solve: the longest common prefix of two strings is simple to solve
• The solution of the original problem is the combination of the subproblem solutions: the longest public prefix of multiple strings is the longest public prefix of the longest public prefix of two strings. We can merge and compare the longest public prefix of the two longest public prefix strings, until finally merge and compare into one, then it is the longest public prefix of the string array:LCP(S1, S2, ... , Sn) = LCP(LCP(S1, Sk), LCP(Sk+1, Sn))

To help you understand:

Take ABC, ABCD, AB, and AC as examples:

Code implementation:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    return lCPrefixRec(strs)
};

// If the length of the split array is not 1, the split will continue
// Until the split array is 1 in length,
// Then compare to get the longest common prefix
function lCPrefixRec(arr) {
  let length = arr.length
  if(length === 1) {
    return arr[0]}let mid = Math.floor(length / 2),
      left = arr.slice(0, mid),
      right = arr.slice(mid, length)
  return lCPrefixTwo(lCPrefixRec(left), lCPrefixRec(right))
}

// Find the longest common prefix str1 and str2
function lCPrefixTwo(str1, str2) {
    let j = 0
    for(; j < str1.length && j < str2.length; j++) {
        if(str1.charAt(j) ! == str2.charAt(j)) {break}}return str1.substring(0, j)
}
Copy the code

Time complexity: O(s), where s is the sum of the number of characters in all strings

Space complexity: O(m*logn), where n is the length of the array and m is the length of the longest character in the string array

Solution 4: Trie tree (dictionary tree)

A Trie tree, also known as a dictionary tree or prefix tree, is, as the name suggests, a data structure used to deal with the problem of string matching, and to solve the problem of finding fixed prefix strings in a set.

Build a Trie tree where the longest common sequence of string arrays is from the root node through the tree until:

• The traversal node has more than one child node

• Or traversal nodes as the end character of a string

Until, the character passed is the longest common prefix of the string array

To help you understand:

Build a Trie tree with ABC, ABCD, AB, AC as an example:

Code implementation:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    // Initialize the Trie tree
    let trie = new Trie()
    // Build the Trie tree
    for(let i = 0; i < strs.length; i++) {
        if(! trie.insert(strs[i]))return ""
    }
    // Return the longest common prefix
    return trie.searchLongestPrefix()
};
/ / Trie tree
var Trie = function() {
    this.root = new TrieNode()
};
var TrieNode = function() {
    // next puts the children of the current node
    this.next = {};
    // Whether the node is the end node
    this.isEnd = false;
};
Trie.prototype.insert = function(word) {
    if(! word)return false
    let node = this.root
    for (let i = 0; i < word.length; i++) {
        if(! node.next[word[i]]) { node.next[word[i]] =new TrieNode()
        }
        node = node.next[word[i]]
    }
    node.isEnd = true
    return true
};
Trie.prototype.searchLongestPrefix = function() {
    let node = this.root
    let prevs = ' '
    while(node.next) {
        let keys = Object.keys(node.next)
        if(keys.length ! = =1) break
        if(node.next[keys[0]].isEnd) {
            prevs += keys[0]
            break
        }
        prevs += keys[0]
        node = node.next[keys[0]]}return prevs
}
Copy the code

Time complexity: O(s+m), s is the sum of the number of characters in all strings, m is the length of the longest character in the string array, building the Trie tree requires O(s), the complexity of the longest common prefix query operation is O(m).

Space complexity: O(s) for building the Trie tree LeetCode

3. More solutionsFigure byte & LeetCODE14: longest common prefix

Diagram byte & LeetCode151: Flips the words in the string

1. The subject

Given a string, flip each word in the string one by one.

Example 1:

Input:"the sky is blue"Output:"blue is sky the"
Copy the code

Example 2:

Input:" hello world! "Output:"world! hello"Explanation: Input strings can contain extra Spaces before or after them, but reversed characters cannot.Copy the code

Example 3:

Input:"a good example"Output:"example good a"Explanation: If there is extra space between two words, reduce the space between the reversed words to just one.Copy the code

Description:

• No space characters make up a word.
• The input string can contain excess space before or after it, but the reversed character cannot.
• If there is extra space between two words, reduce the space between the inverted words to just one.

2. The answer

Solution 1: Regular + JS API

var reverseWords = function(s) {
    return s.trim().replace(/\s+/g.' ').split(' ').reverse().join(' ')};Copy the code

Solution 2: Dual-enqueued (no API)

Dual-end queue, the name implies that both ends of the queue can enter the queue

答 案 :

• First remove the left and right Spaces of the string
• Each word in the string is read one at a time and placed into the dual-enqueued headers in turn
• Convert the queue to string output (with Spaces as delimiters)

Drawing comprehension:

Code implementation:

var reverseWords = function(s) {
    let left = 0
    let right = s.length - 1
    let queue = []
    let word = ' '
    while (s.charAt(left) === ' ') left ++
    while (s.charAt(right) === ' ') right --
    while (left <= right) {
        let char = s.charAt(left)
        if (char === ' ' && word) {
            queue.unshift(word)
            word = ' '
        } else if(char ! = =' '){
            word += char
        }
        left++
    }
    queue.unshift(word)
    return queue.join(' ')};Copy the code

leetcode

3. More solutionsDiagram byte & Leetcode151: Flips the words in a string

Leetcode160: Write a program to find the starting node where two single linked lists intersect

1. The subject

Write a program to find the starting node where two singly linked lists intersect.

Here are two linked lists:

It intersects at node C1.

Example 1:

Enter intersectVal =8, listA = [4.1.8.4.5], listB = [5.0.1.8.4.5], skipA = 2, skipB = 3Output: the Referenceof the node with value = 8Input description: The value of the intersecting node is8(Note that if two lists intersect, not0). Starting from the header of each list, A is [4.1.8.4.5], the linked list B is [5.0.1.8.4.5]. In A, there is before the intersection node2A node; In B, there is before the intersection node3A node.Copy the code

Example 2:

Enter intersectVal =2, listA = [0.9.1.2.4], listB = [3.2.4], skipA = 3, skipB = 1Output: the Referenceof the node with value = 2Input description: The value of the intersecting node is2(Note that if two lists intersect, not0). Starting from the header of each list, A is [0.9.1.2.4], the linked list B is [3.2.4]. In A, there is before the intersection node3A node; In B, there is before the intersection node1A node.Copy the code

Example 3:

Enter intersectVal =0, listA = [2.6.4], listB = [1.5], skipA = 3, skipB = 2Output:nullInput explanation: From the respective table header, the list A is [2.6.4], the linked list B is [1.5]. Since these two linked lists do not intersect, intersectVal must be0While skipA and skipB can be any value. Explanation: The two lists do not intersect, so returnnull.Copy the code

Note:

• If two lists do not intersect, null is returned.
• After the results are returned, the two lists must retain their original structure.
• It can be assumed that there are no loops in the entire list structure.
• The program tries to meet the O(n) time complexity and only uses O(1) memory.

2. The answer

Solution 1: labeling method (simple but the space complexity is O(n), does not conform, only for reference)

Solution idea: two times traversal, first traversal a list, to each node in the list to increase a flag bit, and then traversal another list, traversal to the first node has been marked for the two list intersection of the starting node.

If no marked node is found after traversal, the two lists do not intersect and null is returned

var getIntersectionNode = function(headA, headB) {
    while(headA) {
        headA.flag = true
        headA = headA.next
    }
    while(headB) {
        if (headB.flag) return headB
        headB = headB.next
    }
    return null
};
Copy the code

Time complexity: O(n)

Space complexity: O(n)

Solution two: double pointer method

If A and B intersect, then A and B are consistent from the point of intersection.

We can try to eliminate the length difference between A and B linked lists, and synchronously traverse the nodes in the box in the figure above to determine whether there are the same nodes. If there are the same nodes, it is the intersection of the two linked lists and return the first same node. Otherwise null is returned, and the two lists do not intersect.

Problem solving steps:

• Synchronously traversing lists A and BpA 、 pB, until one of the lists (short lists) has been traversed, as shown in the figure above. Let A be the long list
• So the difference between the lengths of A and B is 0pATo the end of the chainpBRefers to the head of a long listheadAAnd continue the synchronous traversal until the long list has been traversed
• At this point,headA 到 pBIs the difference between the lengths of the two lists,pBTo the length of the listheadBAll the way to the end of the chain
• At this point, can bepAPoint to theheadB, and then synchronous traversalpB 及 pA, until there is an intersection node, return the intersection node, otherwise returnnull

Drawing helps to understand:

var getIntersectionNode = function(headA, headB) {
    // Clear the height difference
    let pA = headA, pB = headB
    while(pA || pB) {
        if(pA === pB) return pA
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return null
};
Copy the code

Time complexity: O(n)

Space complexity: O(1)

leetcode

3. More solutionsDiagram Byte & LeetCode160: Write a program to find the starting node where two single linked lists intersect

Leetcode19: Delete the NTH node from the bottom of the linked list

1. The subject

Given a linked list, remove the NTH reciprocal node of the list and return the head node of the list.

Example:

Given a linked list:1->2->3->4->5, and n =2.When the penultimate node is deleted, the list becomes1->2->3->5.
Copy the code

Description:

The given n guarantee is valid.

Advanced:

Can you try using a scan?

2. Solution: fast and slow pointer

To delete the NTH node from the list, we need to know the NTH +1 node, and then delete the NTH +1 node’s successor

Steps:

Use two Pointers:

• fastThe fast hand goes earlyn+1 步
• slowThe pointer points to the current distancefastFrom the firstnThe initial value ishead

Then, fast and slow move forward in sync until fast.next is null

At this point, fast is the last node and slow is the reciprocal n+1 node. At this point, the problem is to delete the successor node of Slow in the linked list

But there is a problem, when the length of the list is n, FAST is forward less than N +1 node position, so there are two solutions:

• Create a header nodepreHeadTo set uppreHead.next = headIn this way, the above problem can be solved by deleting the penultimatenIs returned after one nodepreHead.nextCan be
• The other way is,fastThe fast hand goes earlynStep after, judgefast.nextWhether it isnull, i.e.,fastIs the last node? If yes, thenheadFor the bottom firstnIn this case, the problem can be simplified as deleting the head node; If not,fast = fast.next ，fastOne more step forward,slowFor the bottom firstn+1, which also solves the above problems.

Solution 1: AddpreHeadnode

var removeNthFromEnd = function(head, n) {
    let preHead = new ListNode(0)
    preHead.next = head
    let fast = preHead, slow = preHead
    // Take n+1 steps first
    while(n--) {
        fast = fast.next
    }
    // Go fast and slow together
    while(fast && fast.next) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return preHead.next
};
Copy the code

Solution 2: Deal with the penultimate separatelynnode

var removeNthFromEnd = function(head, n) {
    let fast = head, slow = head
    // Take n steps first
    while(--n) {
        fast = fast.next
    }
    if(! fast.next)return head.next
    fast = fast.next
    // Go fast and slow together
    while(fast && fast.next) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return head
};
Copy the code

Time complexity: O(n)

Space complexity: O(1)

leetcode

3. More solutionsLeetcode19: deletes the NTH node from the reciprocal of the linked list

Leetcode876: Find the middle node of the linked list

1. The subject

Given a non-empty single linked list with head, return the middle node of the list.

If there are two intermediate nodes, the second intermediate node is returned.

Example 1:

Input:1.2.3.4.5] Output: the nodes in this list3(Serialized form: [3.4.5]) returns the value of3. (The evaluation system describes the node serialization as [3.4.5]). Note that we return an object of type ListNode, ans, as follows: ans.val =3, ans.next.val = 4, ans.next.next.val = 5, and ans.next. Next = NULL.Copy the code

Example 2:

Input:1.2.3.4.5.6] Output: the nodes in this list4(Serialized form: [4.5.6]) since the list has two intermediate nodes, the value is3 和 4We return the second node.Copy the code

Tip:

The number of nodes in a given list is between 1 and 100.

2. Solution: fast and slow pointer

The fast pointer takes two steps at a time, while the slow pointer takes one step at a time. When the fast pointer comes to the end, the slow pointer just goes to the middle

var middleNode = function(head) {
    let fast = head, slow = head
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};
Copy the code

Time complexity: O(n)

Space complexity: O(1)

leetcode

3. More solutionsLeetcode876: Find the middle node of the linked list

Leetcode206: reverse linked list

1. The subject

Example:

Input:1->2->3->4->5- > NULL output:5->4->3->2->1->NULL
Copy the code

Advanced: You can iterate or recursively reverse a linked list. Can you solve this problem in two ways?

2. The answer

Solution 1: iterative method

The following pointer of each node in a single linked list can be pointed to its precursor node

Drawing realization: drawing to help understand

Determine boundary conditions: When the list is NULL or there is only one node in the list, inversion is not required

Code implementation:

var reverseList = function(head) {
    if(! head || ! head.next)return head
    var prev = null, curr = head
    while(curr) {
        // For temporary storage of curr successor nodes
        var next = curr.next
        // Reverse the pointer to curr
        curr.next = prev
        // Change prev, curr
        // The node to be reversed points to the next node
        prev = curr
        curr = next
    }
    head = prev
    return head
};
Copy the code

Time complexity: O(n)

Space complexity: O(1)

Solution two: tail recursive method

Start at the beginning of the node and recursively reverse each node until null

Code implementation:

var reverseList = function(head) {
    if(! head || ! head.next)return head
    head = reverse(null, head)
    return head
};

var reverse = function(prev, curr) {
    if(! curr)return prev
    var next = curr.next
    curr.next = prev
    return reverse(curr, next)
};
Copy the code

Time complexity: O(n)

Space complexity: O(n)

Solution 3: recursive method

The next node of the current node head is recursively reversed

Drawing realization: drawing to help understand

Code implementation:

var reverseList = function(head) {
    if(! head || ! head.next)return head
    var next = head.next
    // Reverse recursively
    var reverseHead = reverseList(next)
    // Change the pointer
    next.next = head
    head.next = null
    return reverseHead
};
Copy the code

Time complexity: O(n)

Space complexity: O(n)

leetcode

3. More solutionsLeetcode206: Reverse the linked list

Seven, front-end algorithm training camp first free to join

The introduction

Stack structure is very simple, we can simulate a stack structure through an array, but just the stack structure is not the front end, this section from the stack structure began to extend to the browser JavaScript operation mechanism, as well as the storage mechanism used in the stack structure and related data structure, this article thoroughly understand all the front end of the stack knowledge.

When we talk about stacks later, we won’t be limited to LIFos, but a deep stack.

This is a prerequisite for advanced front end applications, and it’s also important to know if you want to build high-performance front end applications. It’s also a common interview spot.

Understanding the stack is crucial to our understanding of the JavaScript language. This article mainly introduces the stack from the following aspects:

• First, introduce the stack and code implementation
• Introduce JavaScript mechanism and the application of stack in it
• How to use the call stack in our development
• JS memory mechanism: stack (base type, reference type address) and heap (reference type data)
• Finally, a summary and byte & Leetcode brush problem, to achieve the minimum stack

This section thoroughly stack principle, after a few days will be a daily question, brush through the stack topic, enter the body 👍 below

A stack,

A stack is an ordered collection that follows the LIFO/Last In First Out principle. Its structure is similar to the following:

Stack operations include: push(e) (into the stack), pop() (out of the stack), isEmpty() (to determine whether the stack isEmpty), size() (the size of the stack), and clear() to clear the stack.

Two, code implementation

function Stack() {
  let items = []
  this.push = function(e) { 
    items.push(e) 
  }
  this.pop = function() { 
    return items.pop() 
  }
  this.isEmpty = function() { 
    return items.length === 0 
  }
  this.size = function() { 
    return items.length 
  }
  this.clear = function() { 
    items = [] 
  }
}
Copy the code

Search: search from the stack head, time complexity of O(n)

Insert or Delete: The time complexity between the stack and the stack is O(1)

Third, the JS operating mechanism in the browser

We know that JavaScript is single-threaded, which means that the thread responsible for interpreting and executing JavaScript code in the JavaScript engine is unique and can only perform one task at a time.

Why single-threaded? This is because JavaScript can modify the STRUCTURE of the DOM, and if the JavaScript engine thread is not single-threaded, then multiple pieces of JavaScript can be executed simultaneously, and if these pieces of JavaScript all modify the DOM, then DOM conflicts will occur.

To avoid DOM rendering conflicts, you can use single threading or deadlocks. JavaScript uses a single threaded scheme.

But there is a problem with single threading: if there is a task in the task queue that takes a long time, and the tasks that follow that task stay in the queue, the page will get stuck and the user experience will be severely affected.

To solve this problem, JavaScript divides tasks into two modes of execution: synchronous and asynchronous.

synchronous

// Synchronize tasks
let a = 1
console.log(a) / / 1
Copy the code

asynchronous

// Asynchronous task
setTimeout((a)= > {
    console.log('Time up')},1000)
Copy the code

Synchronization tasks are executed on the main thread (in this case, the JavaScript engine thread), forming a call stack called ** execution stack **;

In addition to the main thread, there is a task queue (also called message queue) that manages the event callbacks for asynchronous tasks. After the tasks in the call stack are finished, the system checks the task queue to see if any asynchronous tasks are ready to be executed.

Note: The task queue holds event callbacks for asynchronous tasks

For example:

setTimeout((a)= > {
    console.log('Time up')},1000)
Copy the code

When this code is executed, it is not printed immediately, but only after the expiration of the timer (1s). The setTimeout itself is executed synchronously, with its callback function placed in the task queue.

Let’s focus on the call stack on the main thread.

Iv. Call stack

We will introduce the call stack from the following two aspects:

• What does the call stack do
• How do you leverage the call stack in development

1. Responsibilities of the call stack

As we know, there are many functions in JavaScript, and it is often the case that one function calls another function. The call stack is a stack structure used to manage the relationship between function calls.

So how does it manage function call relationships? Here’s an example:

var a = 1
function add(a) {
  var b = 2
  let c = 3
  return a + b + c
}

// Call the function
add(a)
Copy the code

This code simply creates an add function and then calls it.

Let’s take a step by step look at the process of executing a function call.

Before executing this code, the JavaScript engine creates a global execution context that contains all declared functions and variables:

As you can see from the figure, the global variable A and the function add in the code are stored in the variable environment.

When the execution context is ready, the global code is executed by first performing an assignment of a = 1,

After the assignment, the value of a changes from undefined to 1, and then the add function is executed. JavaScript determines that this is a function call, and then does the following:

• First, pull out the add function code from the global execution context
• Next, compile this code for the add function, create the execution context and executable code for the function, and push the execution context onto the stack

• The code then executes, returns the result, and the execution context for add pops off the top of the stack, leaving only the global context on the call stack.

At this point, the entire function call execution is complete.

So, the call stack is a data structure that JavaScript uses to manage the execution context of a function. It records where a function is currently executing and which function is being executed. If we execute a function, the execution context for the function is created and put on the top of the stack. If we return from a function, we pop its execution context off the top of the stack. It can also be said that the call stack is the stack used to manage this execution context, or execution context stack (execution stack).

2. The advantages of a developer who understands the call stack

Stack overflow

When executing JavaScript code, we sometimes have a stack overflow:

The figure above is a typical stack overflow, so why does this error occur?

We know that the call stack is a data structure used to manage the execution context. It has a size. When too much context is pushed into the stack, it will overflow the stack.

function add() {
  return 1 + add()
}

add()
Copy the code

Add function recursion, constantly push the stack, the capacity of the call stack is limited, it will overflow, so, in our daily development, we must pay attention to the emergence of such code.

Get the call stack information in the browser

Two ways, one is breakpoint debugging, this is very simple, we use in daily development.

One is the console. The trace ()

function sum(){
  return add()
}
function add() {
  console.trace()
  return 1
}

// Call the function
sum()
Copy the code

Five, JS memory mechanism: stack (basic type, introduction type address) and heap (reference type data)

In the day-to-day life of JavaScript development, front end people rarely have the opportunity to learn about memory, but if you want to become a front end expert and build high-performance front-end applications, you need to know about this area, and it’s a common interview spot.

There are three main types of memory Spaces in JavaScript:

• Code space: Mainly used to store executable code
• Stack space: The storage space of the call stack is the stack space.
• Heap space

Code space is mainly used to store executable code. The stack space and the heap space are mainly used to store data. Next we will focus on stack space and heap space.

There are eight variable types in JavaScript, which can be divided into two types: basic types and reference types

Basic types:

• undefined
• null
• boolean
• number
• string
• bigint
• symbol

Reference type:

• object

Base types are simple data segments stored in stack memory, while reference types are stored in heap memory.

1. The stack space

Basic types take up a fixed amount of space in memory, so their values are stored in stack space, which we access by value.

Generally, the stack space is not very large.

2. The heap space

Reference types, the value size is not fixed, but the pointer to the value size (memory address) is fixed, so put objects in the heap, the address of the object to be included in the stack, so that context switching in the call stack, just need to pointer down to the last execution context address is ok, at the same time guarantee the stack space will not be huge.

When querying variables of reference types, the memory address is read from the stack and then the value in the heap is found from the address. For this, we call it access by reference.

The heap is usually large and can hold a lot of data, but it takes time to allocate and reclaim memory.

Here’s an example to help you understand:

var a = 1
function foo() {
  var b = 2
  var c = { name: 'an'}}// Call the function
foo()
Copy the code

The way that basic (stack space) and reference (heap space) types are stored determines that basic type assignments are value assignments and reference type assignments are address assignments.

/ / value assignment
var a = 1
var b = a
a = 2
console.log(b) 
/ / 1
/ / b the same

// Address assignment
var a1 = {name: 'an'}
var b1 = a1
a1.name = 'bottle'
console.log(b1)
// {name: "bottle"}
// B1 value changed
Copy the code

3. Garbage collection

Garbage data in JavaScript is automatically collected by the garbage collector and does not need to be manually freed. So most developers don’t know much about garbage collection, but it’s part of the front end of the progression for seniors!

Reclaim stack space

When JavaScript executes code, there is an ESP pointer on the main thread to point to the context in the call stack that is currently executing.

After foo is executed, ESP points down to the global execution context, at which point foo needs to be destroyed.

How to destroy nan?

When the ESP pointer points to the global execution context, the foo execution context is invalid. When a new execution context comes in, the memory space can be directly overwritten.

That is, the JavaScript engine destroys the execution context in the stack space by moving the ESP pointer down.

Reclaim heap space

In V8, the heap is divided into two areas: Cenozoic and old:

• New Generation: Stores small objects with a short lifetime. The storage capacity ranges from 1 to 8 MB
• Old generation: Used to store long-lived objects or large objects

V8 uses different recyclers for these two:

• The new generation uses a secondary garbage collector
• Older generations use the main garbage collector

In fact, no matter what kind of garbage collector, the same process is used (three steps) :

• Marking: Marking live (in use) and inactive (recyclable) objects in the heap space
• Garbage cleanup: Reclaim memory space occupied by inactive objects
• Memory defragmentation: During frequent garbage collection, there may be a large number of discontinuous memory fragments in the memory. When an object that needs to occupy a large continuous memory space needs to be allocated, there may be insufficient memory. Therefore, it is necessary to defragment the memory.

The secondary garbage collector and the primary garbage collector both use the same process, but the collection strategy and algorithm are different.

Secondary garbage collector

It uses Scavenge algorithm and object promotion strategy to collect garbage

The so-called Scavenge algorithm divides the Cenozoic space into two regions, one is the object region, the other is the free region, as shown in the following figure:

The newly added objects are added to the object area. When the object area is full, garbage collection is performed once. The execution process is as follows:

• Mark: First mark the objects in the region (live objects, inactive objects)
• Garbage cleaning: then garbage cleaning: the active objects in the object area are copied to the free area and arranged in an orderly manner. When the replication is complete, the object area and the free area are flipped, and the free area is promoted to the object area, and the object area is the free area

After the rolloff, the object area is defragmented. there is no need for step 3.

However, the new generation area is very small, usually 1 ~ 8M in capacity, so it is easy to fill up, so the JavaScript engine uses the object promotion strategy to handle this, that is, as long as the object is still alive after two garbage collection, it will be promoted to the old generation area.

Main garbage collector

In the region of the old generation, in addition to the long-lived objects promoted from the new generation, large objects will be directly allocated to the old generation when they encounter large objects.

Be insane. Therefore, the main garbage collector mainly stores long-lived or space-occupying objects. It is inappropriate to use the Scavenge algorithm at this time. In V8, the main garbage collector mainly adopts the mark-clearance method for garbage collection.

The main process is as follows:

• Marking: The call stack is traversed to see if the objects in the old region heap are referenced. The referenced objects are marked as active objects, and the unreferenced objects (to be cleaned up) are marked as garbage data.
• Garbage cleanup: Clean up all junk data
• Memory collation: a mark-collation strategy that aggregates live objects together

Incremental tag

V8 will automatically perform garbage collection, but since JavaScript is also running on the main thread, once garbage collection is performed, JavaScript will be interrupted, which may cause more or less page delays and affect the user experience, so V8 has decided to use the incremental markup algorithm to collect:

That is, break garbage collection down into small tasks, interspersed in JavaScript.

Six, summarized

This section starts with the stack structure, an ordered collection that satisfies the last in, first out (LIFO) principle, and then implements a stack through an array.

Then it introduces the asynchronous execution mechanism of JavaScript in the browser environment, that is, the event loop mechanism. The main thread of JavaScript repeats cyclic reading tasks from the task queue (asynchronous event callback) and puts them into the call stack for execution. Call stack, also known as execution context stack (execution stack), is a stack structure used to manage the execution context of a function.

Storage mechanism is divided into JavaScript code space, stack space and heap space, code space to hold executable code, stack space to hold basic data types and reference types address, heap space used to store a reference type data, when completing an execution context in the call stack, the need for recycling the context and the related data space, The data stored in the stack space is collected through the ESP pointer, and the data stored in the heap space is collected through the secondary garbage collector (new generation) and the main garbage collector (old generation).

Chat ran far 🤦♀️, but are the front step will be advanced, then we began to brush the stack topic!! Daily brush, advanced front end and algorithm ⛽️⛽️⛽.

Byte & LeetCode155: minimum stack (including getMin function stack)

Design a stack that supports push, pop, and top operations and can retrieve the smallest element in constant time.

• push(x)— Push element x onto the stack.
• pop()Delete the top element of the stack.
• top()Get the top element on the stack.
• getMin()Retrieve the smallest element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(2 -);
minStack.push(0);
minStack.push(- 3); minStack.getMin(); - > to return- 3.minStack.pop(); minStack.top(); - > to return0.minStack.getMin(); - > to return- 2.
Copy the code

You are welcome to submit your answers to github.com/sisterAn/Ja…

8. References

How Browsers Work and Practice (Geek Time)

Nine, know more front-end friends, advance front-end development together

The first phase of the front-end algorithm training camp is free 🎉🎉🎉, free yo!

Here, you can advance the front-end algorithm with like-minded front-end friends (1000+), from 0 to 1 to build a complete data structure and algorithm system.

Here, you can learn a dafang algorithm (Ali, Tencent, Baidu, byte, etc.) or Leetcode every day, and you will answer it the next day!

Scan the code to join the group. If the group number has reached the online limit, follow the public account “Front-end Bottle Gentleman” and reply to the “algorithm” to automatically join the group