Front-end Thinking Series (” Front-end Thinking Record “) mainly includes Thinking about each stage of front-end learning

preface

Recently, when I saw the morning sun’s article in nuggets, I suddenly wanted to write an article about LeetCode.

I started to brush the questions regularly in October 2019, and now I have finished the questions of 464/1715. I have carefully studied all possible solutions for most of the questions, so you can see that my submission amount has reached 1285/1871. First of all, I wrote 99% of the questions in JavaScript, and the rest in Python or Java if I was a little lazy.

Easy/Medium/Hard is about 30%/55%/15% :

In addition, the results of my recent LeetCode competition are as follows:

With this in mind, I felt compelled to share my experience of competing in LeetCode with JavaScript.

Right now, basic algorithms or other computer science knowledge has been left out of the front end for a lot of reasons, but there is no immediate reward for the fact that I spend so much time learning the basics. But I think that’s something you have to catch up on sooner or later, just like the front end is always catching up on the old lessons.

Back to the theme, I learned about Chenxi from the article of Waterfall Liu. At that time, I thought he was very thoughtful and efficient in learning algorithm (the combination of theory and practice can be regarded as the application of Feynman learning method). A lot of people learn algorithms to the point where they’re too theoretical, where you get frustrated, and then you go into a phase of resignation and self-doubt. Because of that article, I added Chenxi’s wechat and LeetCode as friends, and had a brief chat about LeetCode. In my opinion, the LeetCode timeline shows that Dawn is a very persistent person.

At the beginning, everyone in accordance with the outline of the morning brush study. So what is the purpose of this article? The main purpose is to provide some experiences to help you deepen your learning of LeetCode (similar to beginner to Intermediate).

The body of the

First of all, at present, domestic large factories have begun to tend to foreign large factories, in the interview algorithm proportion is more and more large. Although historically these computer science foundation in the front of the investigation will be less (school recruitment and social recruitment are relatively less, but because the school recruitment of the actual project experience is generally not rich, so the school recruitment of these foundations will be more than social recruitment).

For most are interested in entering the domestic factory (foreign factory algorithm both before and after the end are required), the algorithm will become your board.

First of all, I have to be clear.

What does the above formula mean? Most of the problems in LeetCode can be solved after training, and the difficulty is not very great. Although there is a tendency of the original ACM problems in several competitions during this period, the data scale of the problems is much smaller than the original problems, which means that we can use more inefficient and simple solutions to solve them. That means you don’t have to be afraid to think differently, you don’t have to invent an algorithm, you just have to use someone else’s algorithm to solve the problem. In my opinion, most people can achieve a decent level of training in a regular 3-6 month period (1-2 hours per day).

Brush algorithm benefits

  1. Personally, I think algorithms are the cornerstone of programs, something that all developers have to master, because whether you are a front-end engineer or a back-end engineer, you have to be an engineer first.

  2. Of course, it can get benefits immediately, that is, the interview to, like small factory want to go to domestic big factory, domestic big factory want to go to foreign big factory. The algorithm is the first step.

  3. This is my personal favorite, exercise our thinking ability. During the 1 and a half hours of each weekly game, your brain is working at high speed, and you need to come up with solutions and be able to consider all the boundary cases and write bug-free code (facebook problems require your code to be bug-free directly). Every time I was in a state of high concentration, I felt especially cool after the race.

  4. It makes you more humble. Slap you in the face when you’re cocky and keep learning. Every time I see the top 10 finish times after a race, I know there is still a long way to go.

Here are my general steps to solve the problem, which are generally applicable to interviews and competitions.

Do the first step: read the question

The first step in doing a LeetCode problem is to read the content of the problem and the data size, which is somewhat similar to the preconditions in a math problem. In general, the data size of the problem will give you a pretty good idea of the time complexity of the algorithm, and that means what kind of solution you can use.

Generally speaking, we use 1GHZ CPU 1s as the base value, which generally means that the CPU can perform 10 ^ 9 floating-point operations per second, and your algorithm should theoretically take no more than 1 second per test. If your estimate more than 1 second, this often means that the timeout (but it is important to note that this method is still in the interview we need to show the interviewer, because although not optimal solution, but at least I am the answer out of him, 10 points to give me at least five points, another advantage is that you say first low efficiency of writing, Step by step to give the best ones, which will give the interviewer your ability to think in a logical way, but will also shorten the length of the algorithm.

For example, if you can scale your data up toSo it’s obviousIs not so suitable in this case.

Here is a rough approximation of the size of the data and the time complexity acceptable to the algorithm (remember, this is a rough approximation, as a rule of thumb) :

The data size Algorithm time complexity
–

Step 2: Identify the problem type

At the beginning of our training, we need to be familiar with various problem solving templates. After mastering the template of the question, we can go back from the content of the question to the type of question.

This is why many people recommend that you brush the questions according to tag for the first time. It means that you can strengthen this type of questions in many aspects, which can help you think, summarize, and abstract to the following point.

After scanning the tags, you will generally summarize common data structures, ideas, and algorithms, such as the following:

  1. Data structures you must master: arrays, linked lists, stacks, queues, heaps, trees, hash tables, graphs, and look-up sets
  2. Algorithms to master: recursion, DFS and BFS, sorting, dichotomy, double Pointers, sliding Windows
  3. Common ideas: divide and conquer, greed, backtracking, dynamic programming, and branch boundaries
  4. Common skills: bit operation, double pointer, sliding window

By the time you’ve figured out these common abstractions, you’ve probably already gone through at least 100 problems in LeetCode. This means that you have entered the stage where you can draw inferences and make associations.

But many people still don’t know what to think of the specific solution when they see a new problem, which usually means two things:

  1. You don’t understand the real solution well enough, the association is not strong enough
  2. You are not good at abstracting questions, that is, how do you get rid of irrelevant information and extract the key things

So, what to do. One is in the usual training, try to think of their own solution first. If you can’t think of anything (for example, you’ve been stuck for an hour), look at the answer, record the problem, and do it again in half a month.

There is also a trick to reading the answer, what do you think of the answer? When you look at the answer, you must not directly copy the code, but first try to understand the algorithm of the answer, and then draw the logical flow with a pen on paper, if you do not understand, according to the answer sample code head walk again. Finally close your answers and write your own questions.

In addition, we can help solve the problem by the topic keywords, we can guess by these keywords when we solve the template in association with the question.

  1. If they haveContinuous substring.Continuous subarrayThese kinds of words and then require time complexity, then you can try to use the sliding window idea.

To give a few examples, for example, leetcode’s 3. Maximum string without repeating characters

This problem is to find the longest continuous substring without repeating characters, classic sliding window problem.

76. Minimum coverage substring

Also can extract the keyword minimum continuous substring, and covering all characters in T is just one of the constraints, classic sliding window title.

Step 3: write algorithm ideas on the draft

The most taboo to do algorithm problems is to see the problem, not clear thinking and boundary conditions, directly start to write code.

There are several situations where you can write code directly:

  1. You’re a big shot, like Lord Lou
  2. Close to the original problem, or you are already familiar with this kind of problem
  3. It’s too easy

However, as a general developer, I recommend writing out the algorithm idea first.

For example, 55. Jump games

I’d rather you did this on paper (of course you don’t have to write this many words) :

We iterate through the array starting at the beginning and maintain a maximum distance value Max. As we iterate, we need to keep updating the farthest we can currently jump to, which is Max. During traversal, we need to determine whether the current position is less than or equal to Max: - If so, proceed to the next position - if greater than Max, it means that the last position cannot be reached.Copy the code

With this in mind, we are moving closer to bug free when we write code

Step 4: Consider the boundary case

Once you have an idea, you need to think about all the boundary cases and the initial cases in advance. As in the 55. Jump game above, the boundary case is when the array is empty: if(! nums.length) return true;

Let Max = nums[0] + 0;

Finally the code comes out:

/** * @param {number[]} nums * @return {boolean} */
var canJump = function(nums) {
  if(! nums.length)return true;

  let max = nums[0];

  for(let i = 1; i < nums.length; i++) {
    if(max >= nums.length - 1) return true;
    if(i > max) return false;

    max = Math.max(max, i+nums[i]);
  }
  return true;
}
Copy the code

If the whole problem solving process is fast, it will not take more than 5 minutes. Later, we can constantly optimize our solution, such as:

var canJump = function(nums) {
    if(! nums.length)return true;

    let len = nums[0];
    for(let i = 0; i <= len; i++) {
        len = Math.max(len, nums[i] + i);
        if(len >= nums.length- 1) return true; 
    }

    return false;
};
Copy the code

Disadvantages of JavaScript brush algorithm problems

There are many disadvantages to doing leetcode arithmetic problems or contests in JavaScript, which are basically at the bottom of all languages. It’s not as efficient as a static language like Java or c++ (meaning the same set of tests might pass c++ but not JavaScript), and it’s not as rich in library functions as a dynamic language like Python (meaning we have to write a lot of functionality ourselves). Here are some disadvantages of JavaScript:

1. Apply for large-capacity arrays

In JavaScript, arrays tend to be more expensive than static languages because they can store any type of data. If you request too much capacity, it’s easy to exceed v8’s maximum available space, and we can’t hack node at this point.

At this point I recommend various Types of typedArray, such as Uint32Array, to keep the overhead of arrays as low as possible.

2. Lack of library functions

A lot of times the solution requires a lot of encapsulated data structures, such as red-black trees and heaps. We have to pre-wrap JavaScript ourselves. See Python in tears, how powerful import Heapq is.

Here I would recommend two ways to write it:

  1. When encountering such problems, write directly in a language like Python. I prefer Python because the library functions are very rich, easy to learn and simple to code.

  2. Write all library functions in advance, using manual copy

3. Multi-dimensional array application

Writing multidimensional arrays in JavaScript requires a bit more code, which brings a race time disadvantage:

let dp = new Array(n);

for(let i = 0; i < n; i++) dp[i] = new Array(n).fill(0);
Copy the code

However, this is not a problem. So far, I have used only a 4-dimensional array, and this 4-dimensional array can be reduced to a 3-dimensional array by optimization.

Other skills

Before the contest, you should prepare your local debug environment in advance. Just use the Debug of Node or Browser.

Recommended data

  1. Algorithm 4 and a related Coursera course in Standford (see video on site B).

Algorithms 4 is a bit more engineering than Introduction to Algorithms (which I only read a little bit), without much derivation, and is more suitable for non-algorithmic developers.

  1. Tsinghua university deng junhui “data structure and algorithm”, C++ version, comparison recommended. Be able to take steps

  2. Geek Time’s The Beauty of Data Structures and Algorithms, a combination of algorithms and engineering practice

conclusion

Here, due to length reasons and personal level, only a little bit of very simple things, I hope you can give me more advice. Also hope that the front circle can be less impetuous.

In addition, I also set up a front-end LeetCode solution on Github page

In it, I also wrote many JavaScript versions of the problem solutions according to tag, and regularly updated the weekly contest problem solutions.

I’m BY, an interesting person who will bring more original articles in the future.

This article is subject to MIT protocol. Please contact the author for republication.

Interested can follow the public account (Baixue Principle) or Star GitHub repo.