Offer to come, dig friends take it! I am participating in the 2022 Spring Recruitment series of activities – experience review, click to view the details of the activities will be considered to participate

Hello, I’m Shanyue. This article can also be viewed on my blog interview Roadmap.

One of the most frequently asked questions is: How do I practice programming problems? Yamatsuki again summarizes an exercise route for writing code by hand.

Debug and test your code to make sure it works.

All of the following handwritten codes are posted hereMy codepen 中

All of the following handwritten codes are posted hereMy codepen 中

All of the following handwritten codes are posted hereMy codepen 中

The preparatory work

API Design Thinking

As anyone who has worked on a front-end for more than three years, one thing is clear: API design is more important than implementation.

Why?

For example, the compose function is commonly used in various middleware designs, such as Redux. The redux function is extremely simple to implement, even in one line, but being the first to think of compose is even more difficult.

Therefore, many interview questions in the front-end interview are mainly simulated implementation of ES API and LoDash API, so you need to be familiar with LoDash and ES6+ documents before writing the code.

Code specification

Looking at code during the interview is not only a way to look at a candidate’s logic skills, but also a way to look at a candidate’s coding skills, such as

  1. Are there consistent code specifications
  2. Is there a legible variable name
  3. Is there a more concise code

For the ability to cultivate elegant Code check out Clean Code Concepts For JavaScript., which has 50+ K stars on Github.

For example, naming optimization

// BAD
// What the heck is 86400000 for?
setTimeout(blastOff, 86400000);

// GOOD
// Declare them as capitalized named constants.
const MILLISECONDS_PER_DAY = 60 * 60 * 24 * 1000; / / 86400000;

setTimeout(blastOff, MILLISECONDS_PER_DAY);
Copy the code

Space complexity and time complexity

  • Space Complexity (Space Complexity) Describes the amount of storage Space temporarily occupied by the algorithm while it is running
  • Time complexity describes the running Time of the algorithm, which is often expressed with the big O symbol

How to find Time with the complexity of an algorithm?

  • O(1): Constant Complexity, such as when the final decision is reached after two calculations
  • Dsmt4 (logn): dsmt4 is new
  • O(n): Linear is the status of one for loop, but half or two for loops are also considered O(n).
  • O(n^2): typically nested for loops, such as bubble sort

Handwritten code roadmap

The following are some of the code problems I’ve summarized in a number of major workshops. I’ll break them down into sections based on difficulty and module attributes.

Note: Shanyue summary of all big factory interviews please click here

Therefore, I divided the questions into the following categories. I could prepare according to the number of stars and the order in which I listed all the code questions. I could find three questions to code every day and stick to them.

  1. ES API
  2. lodash API
  3. Programming logic problem
  4. Algorithms and Data Structures (LeetCode)

All of the following questions can be found in the Mountain Moon warehouse, and most of the code questions are available in thecodepenFind my problem solving test and execute it directly.

01 ES API

Many of the big companies are obsessed with emulating the native API, and while most of the time it doesn’t help, sometimes it helps to further understand the API.

For example, when you end promise.all by hand, it will be much easier for opponents to write Promises with concurrency control.

The bind/call/apply ⭐ ⭐ ⭐ ⭐ ⭐ ️ ️ ️ ️

  • To realize the call/apply
  • To realize the bind
  • Implement softBind

High frequency problem, intermediate frequency implementation.

Function.prototype.fakeBind = function(obj, ... args) {
  return (. rest) = > this.call(obj, ... args, ... rest) }Copy the code

Sleep/delay ⭐ ⭐ ⭐ ⭐ ⭐

  • 【Q435】 how to implement a sleep/delay function in JS
  • How to implement a sleep/delay function in JS

The sleep function is both a code question frequently asked in interviews and a tool function commonly used in daily work, especially testing.

const sleep = (seconds) = > new Promise(resolve= > setTimeout(resolve, seconds))

function delay (func, seconds, ... args) {
  return new Promise((resolve, reject) = > {
    setTimeout(() = > {
      Promise.resolve(func(... args)).then(resolve) }, seconds) }) }Copy the code

Promise. All ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • Code: Promise. All
  • Topic: Promise. All

Simple at first glance, not easy to implement.

function pAll (_promises) {
  return new Promise((resolve, reject) = > {
    // Iterable => Array
    const promises = Array.from(_promises)
    // The result is maintained with an array
    const r = []
    const len = promises.length
    let count = 0
    for (let i = 0; i < len; i++) {
      // promise. resolve ensure that all data is converted to promises
      Promise.resolve(promises[i]).then(o= > { 
        // Because promises are asynchronous, keep arrays one-to-one
        r[i] = o;

        // If all promises in the array are completed, the result array is returned
        if (++count === len) {
          resolve(r)
        }
        // When an exception occurs, reject it
      }).catch(e= > reject(e))
    }
  })
}
Copy the code

Array. The isArray ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • Topic: Array. IsArray

Interview questions are often asked, but that’s easy enough.

Array. The prototype. Flat ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • 【Q443】 Implement an array flattening function flatten
  • Code: [Q443] implement a flat array function flatten

Reduce and Concat are a perfect match

function flatten (list, depth = 1) {
  if (depth === 0) return list
  return list.reduce((a, b) = > a.concat(Array.isArray(b) ? flatten(b, depth - 1) : b), [])
}
Copy the code

Note that flatten has a second parameter, depth

Promise ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • Topic: Promise

That said, it’s not easy to implement true Promise compliance.

Array. The prototype. Reduce ⭐ ️ ⭐ ️ ⭐ ️

  • Code: Array. Prototype. Reduce
  • Topic: Array. Prototype. Reduce
const reduce = (list, fn, ... init) = > {
  let next = init.length ? init[0] : list[0]
  for (let i = init.length ? 0 : 1; i < list.length; i++) {
    next = fn(next, list[i], i)
  }
  return next
}
Copy the code

The problem looks simple, but in practice there are many boundary problems to pay attention to, such as

  1. What is the first Index in the callback function?
  2. What if the array is a sparse array?

String. The prototype. The trim ⭐ ️ ⭐ ️ ⭐ ️

  • How to remove whitespace from a string

In regular expressions, \s means matching a whitespace character, including a space, TAB, page feed, and line feed. Equivalent to [\f\n\ R \t\v\ u00A0 \u1680\u180e\ U2000 -\u200a\u2028\u2029\ u202F \u205f\u3000\ufeff].

const trim = str= > str.trim || str.replace(/^\s+|\s+$/g.' ')
Copy the code

This API is typically looked at when looking at regex

02 lodash API

Throtle/debounce ⭐ ⭐ ⭐ ⭐ ⭐ ️ ️

  • Title: What are anti-shake and throttling, and what are their application scenarios

Performance tuning is necessary to reduce rendering, and the code is easy enough to mention in interview questions.

function throttle (f, wait) {
  let timer
  return (. args) = > {
    if (timer) { return }
    timer = setTimeout(() = >{ f(... args) timer =null
    }, wait)
  }
}
Copy the code
function debounce (f, wait) {
  let timer
  return (. args) = > {
    clearTimeout(timer)
    timer = setTimeout(() = >{ f(... args) }, wait) } }Copy the code

CloneDeep ⭐ ⭐ ️ ⭐ ⭐ ⭐

  • 【Q202】 How to implement a cloneDeep

Deep copy, whether for performance optimization on the job or in an interview, is popular.

Deserialization using JSON serialization cannot solve the problem of copying some complex objects. The difficulty lies in handling different data types.

IsEqual ⭐ ⭐ ⭐ ⭐ ⭐

  • 【Q598】 How to implement a deep comparison function deepEqual

Deep comparisons, also commonly used in performance tuning, are less difficult than cloneDeep.

The get ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • How to implement a function like Lodash.get
  • Code: How do I implement functions like Lodash.get

In ES6+, using the optional chain operator? . Can further reduce the difficulty of implementation

function get (source, path, defaultValue = undefined) {
  // a[3].b -> a.3.b -> [a, 3, b]
  const paths = path.replace(/\[(\w+)\]/g.'$1').replace(/\["(\w+)"\]/g.'$1').replace(/\['(\w+)'\]/g.'$1').split('. ')
  let result = source
  for (const p ofpaths) { result = result? .[p] }return result === undefined ? defaultValue : result 
}
Copy the code

Compose (flowRight) ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • 题目: how to implement the composing function for compose
const compose = (. fns) = >
  // Pay attention to the position of f and g, if the calculation is implemented from left to right, then replace the order
  fns.reduce((f, g) = > (. args) = >f(g(... args)))Copy the code

Shuffle ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • 【Q447】 How to implement an array shuffle function shuffle
  • Related: [Q645] Randomly generated six-digit mobile phone captCha (duplicate/non-duplicate)
  • How to implement an array shuffle function shuffle

Implementing a simple shuffle can be extremely simple.

const shuffle = (list) = > list.sort((x, y) = > Math.random() - 0.5)
Copy the code

If you don’t use array.prototype. sort, you can do this with the following code

function shuffle (list) {
  const len = list.length
  let result = [...list]
  for (let i = len - 1; i > 0; i--) {
    const swapIndex = Math.floor(Math.random() * (i + 1));
    [result[i], result[swapIndex]] = [result[swapIndex], result[i]]
  }
  return result
}
Copy the code

Shuffle is used in many scenarios in production practices, such as randomly generating six-digit mobile phone verification codes that are not repeated

The sample ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • 【Q436】 How to implement a sample function that randomly selects an element from an array

The math.random () function returns a floating point pseudo-random number in the range 0 to less than 1, mathematically [0, 1], which you can use to implement the sample function

Array.prototype.sample = function () { return this[Math.floor(Math.random() * this.length)] }
Copy the code

SampleSize ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • 【Q677】 How to implement a sampleSize function that randomly selects N elements from an array

You can implement a simple sampleSize based on shuffle

const shuffle = (list) = > list.sort((x, y) = > Math.random() - 0.5)
const sampleSize = (list, n) = > shuffle(list).slice(0, n)
Copy the code

MaxBy ⭐ ⭐ ⭐ ⭐ ⭐

  • 【Q628】 implement a function maxBy that finds the largest array item based on the given condition

KeyBy ⭐ ⭐ ⭐ ⭐

  • 【Q678】 Implement a function keyBy

GroupeBy ⭐ ⭐ ⭐ ⭐

  • 【Q679】 implement a function groupBy

The chunk ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • 【Q643】 How to implement the chunk function, array grouping
function chunk (list, size) {
  const l = []
  for (let i = 0; i < list.length; i++ ) {
    const index = Math.floor(i / size) l[index] ?? = []; l[index].push(list[i]) }return l
}
Copy the code

The chunk ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • 【Q399】 Implement a once function that returns the result only once
const f = x= > x

const onceF = once(f)

/ / = > 3
onceF(3)

/ / = > 3
onceF(4)
Copy the code

The template ⭐ ⭐ ⭐ ⭐ ️ ️ ️ ️ ️

  • 【Q660】 Implement a render/template function, which can be used to render templates
  • Q660: implement a render/template function, which can be used to render templates

A slightly more difficult programming problem.

const template = '{{user/" name "}}, have you learned today? - user ID: {{. User ID}}';

const data = {
  user: {
    id: 10086.name: 'mountain month',}};//=> "Shan Yue, today you learn again - user ID: 10086"
render(template, data); 
Copy the code

Note:

  1. Note the deep nesting of data
  2. Pay attention touser['name']attribute

PickBy/omitBy ⭐ ⭐ ⭐ ⭐

CamelCase ⭐ ️ ⭐ ⭐ ⭐

  • Title: Naming the hump

Difference ⭐ ️ ⭐ ️ ⭐ ️

  • 【Q655】 Implement intersection, take the array intersection

03 Programming logic

In terms of programming logic problems, it refers to some data processing frequently encountered in the work

⭐️⭐️⭐ ⭐️⭐️

  • Is FizzBuzz divisible by 3 or 5

Enter an integer, and if divisible by 3, print Fizz

If divisible by 5, Buzz is printed

If it is divisible by both 3 and 5, FizzBuzz is printed

//=> 'fizz'
fizzbuzz(3)

//=> 'buzz'
fizzbuzz(5)

//=> 'fizzbuzz'
fizzbuzz(15)

/ / = > 7
fizzbuzz(7)
Copy the code

It’s a simple question, but most people still don’t get it right in an interview

Implement promise. map to control the concurrency ⭐️⭐️⭐ ⭐️⭐️

  • Topic: Promise. The map
  • Code: Promise. The map

The Promise of concurrency control is often asked in interviews, and often covered at work. Knowing the implementation of Promise.all will go a long way toward achieving concurrency control before getting started with this problem.

In addition, bluebird, the most popular Promise library, implements promise.Map, which is widely used in projects.

Asynchronous sum/add ⭐️⭐️⭐ ⭐️⭐️

The summation of the coding problem, from the headline, promise serial, parallel, dichotomy, concurrent control, cascading.

  • Title: [Q644] Implement an asynchronous sum/add

How to use JS to implement a publish and subscribe mode ⭐ ⭐️⭐ ⭐️⭐️

  • 【Q613】 How to use JS to implement a publish/subscribe model
  • Q613: How to use JS to implement a publish subscribe model

How to implement infinite sum function ⭐️⭐ ⭐ ⭐️⭐️

  • Title: [Q421] How to implement a function of infinite accumulation
  • Code: Q421 how to implement infinite accumulation of a function

Implement a sum function as follows:

sum(1.2.3).valueOf() / / 6
sum(2.3) (2).valueOf() / / 7
sum(1) (2) (3) (4).valueOf() / / 10
sum(2) (4.1) (2).valueOf() / / 9
sum(1) (2) (3) (4) (5) (6).valueOf() / / 21
Copy the code

This is byte, Kuaishou, Ali a number of big factory most preferred topic, in fact, there is a bit of skill problem.

This is byte, Kuaishou, Ali a number of big factory most preferred topic, in fact, there is a bit of skill problem.

This is byte, Kuaishou, Ali a number of big factory most preferred topic, in fact, there is a bit of skill problem.

This is a lazy calculation function that uses sum to collect all the sums and valueOf to do the calculation

  • Sum returns a function that collects all the cumulative terms, implemented recursively
  • The return function has a valueOf attribute for unified calculation
function sum (. args) {
  const f = (. rest) = >sum(... args, ... rest) f.valueOf =() = > args.reduce((x, y) = > x + y, 0)
  return f
}
Copy the code

Statistics the largest number/second largest number in the array ⭐️⭐ ⭐ ⭐️⭐️

  • Title: Count the largest number/second largest number in the array
  • Code: count the largest number/second largest number in the array

Find the largest value:

function max (list) {
  if(! list.length) {return 0 }
  return list.reduce((x, y) = > x > y ? x : y)
}
Copy the code

Find the two largest values:

Find the two largest values in the array – codepen

function maxTwo (list) {
  let max = -Infinity, secondMax = -Infinity
  for (const x of list) {
    if (x > max) {
      secondMax = max
      max = x
    } else if (x > secondMax) {
      secondMax = x
    }
  }
  return [max, secondMax]
}
Copy the code

If you want TopN, you can use big top heap, small top heap implementation, see another problem

The most frequent characters in a character string ⭐️⭐️⭐ ⭐️ ️

  • 【Q644】 Count the number of characters that occur the most times in a string
  • Code: [Q644] Count the number of characters that occur the most times in a string
function getFrequentChar (str) {
  const dict = {}
  for (const char of str) {
    dict[char] = (dict[char] || 0) + 1
  }
  const maxBy = (list, keyBy) = > list.reduce((x, y) = > keyBy(x) > keyBy(y) ? x : y)
  return maxBy(Object.entries(dict), x= > x[1])}Copy the code

In the following scheme, the algorithm complexity of O(n) is only needed once for counting statistics and size comparison

function getFrequentChar2 (str) {
  const dict = {}
  let maxChar = [' '.0]
  for (const char of str) {
    dict[char] = (dict[char] || 0) + 1
    if (dict[char] > maxChar[1]) {
      maxChar = [char, dict[char]]
    }
  }
  return maxChar
}
Copy the code

Compress the following digits ⭐️⭐ ⭐ ⭐ ⭐️⭐️

  • Title: [Q412] Compress and encode the following strings
  • Code: [Q412] to compress the following strings

This is a big factory often test code problem

  • Input: ‘aaaabbbccd’
  • Output: ‘a4b3C2D1’, representing four consecutive occurrences of A, three consecutive occurrences of B, two consecutive occurrences of C, and one consecutive occurrence of D

There are the following test cases

//=> a4b3c2
encode('aaaabbbcc')

//=> a4b3a4
encode('aaaabbbaaaa')

//=> a2b2c2
encode('aabbcc')
Copy the code

If the code is written correctly, you can go further:

  • If it occurs only once, no number is encoded, such as AAAB -> a3b
  • If it occurs only twice, it is not encoded, as in aABbb -> aAB3
  • How to resolve digital conflicts if decoding is carried out

Write the function encode to do this

Code see [Q412] to compress the following character encoding – codepen

function encode (str) {
  const l = []
  let i = 0
  for (const s of str) {
    const len = l.length
    const lastChar = len > 0 ? l[len - 1] [0] : undefined
    if (lastChar === s) {
      l[len - 1] [1] + +}else {
      l.push([s, 1])}}return l.map(x= > x.join(' ')).join(' ')}Copy the code

The test pass

> encode('aaab')
< "a3b1"
Copy the code

But interviewers tend to move on

  1. If it occurs only once, no number is encoded, as inaaab -> a3b
  2. If it occurs only twice, no encoding is performed, as inaabbb -> aab3
  3. If the decoding, encounter a number how to deal with?

The following are further encodings in addition to numbers

function encode (str) {
  const l = []
  let i = -1;
  let lastChar
  for (const char of str) {
    if(char ! == lastChar) { lastChar = char i++ l[i] = [char,1];
    } else {
      l[i][1]++
    }
  }
  return l.map(([x, y]) = > {
    if (y === 1) {
      return x
    }
    if (y === 2) {
      return x + x
    }
    return x + y
  }).join(' ')}Copy the code

LRU Cache ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️

  • Code: [Q249] use JS to implement an LRU cache

Implement a function to encode and decode the QUERyString URL ⭐ ⭐️⭐ ⭐️ ️

  • Implement a function to encode the QueryString of the URL

What is the principle of JSONP and how to implement ⭐️⭐️ disk ⭐

  • 【Q439】 What is the principle of JSONP and how to implement it

JSONP, which stands for JSON with Padding, was developed to solve cross-domain problems. Although it can only handle GET cross-domain, and although CORS cross-domain is basically used these days, it’s still important to know about it because the interview will ask.

JSONP is based on two principles:

  1. Dynamically createscript, the use ofscript.srcLoad requests across cross-domains
  2. script.srcThe loaded script content is JSONP: that isPADDING(JSON)format
function jsonp ({ url, onData, params }) {
  const script = document.createElement('script')

  // To avoid global contamination, use a random function name
  const cbFnName = `JSONP_PADDING_The ${Math.random().toString().slice(2)}`

  // The default callback function is cbFnName
  script.src = `${url}?${stringify({ callback: cbFnName, ... params })}`

  // use onData as cbFnName callback to receive data
  window[cbFnName] = onData;

  document.body.appendChild(script)
}

// Send the JSONP request
jsonp({
  url: 'http://localhost:10010'.params: { id: 10000 },
  onData (data) {
    console.log('Data:', data)
  }
})
Copy the code

How do I generate a random string ⭐️⭐️⭐ ⭐️⭐️

  • Q619: How to generate a random string using JS
const random = (n) = > Math.random().toString(36).slice(2.2 + n)
Copy the code

Add thousands to a number ⭐️⭐️ port ️

  • Code: How to add thousands to an array

The thousands substitution can be made by the regular /(\d)(? =(\d\d\d)+(? ! \d))/ match

function numberThousands (number, thousandsSeperator = ', ') {
  return String(number).replace(/(\d)(? =(\d\d\d)+(? ! \d))/g.'$1' + thousandsSeperator)
}
Copy the code

04 Algorithms and Data Structures (LeetCode)

Leetcode 200/100 simple and intermediate level questions, mainly simple questions. Just brush it.

In my question bank, I also collected multiple algorithm questions summarized in many dachang surface classics, which are summarized as follows

Output the Fibonacci sequence up to 100

  • Output the Fibonacci sequence up to 100

TopK problem

  • 【Q288】 How to find TOP K in array

Typical binary heap problem

  1. Take the first k number in the array and make a small top heap, heap
  2. The rest of the array is compared to the heaptop element one by one, and if it is greater than the heaptop element, it is inserted

Time complexity O(NLG (k))

Find two numbers in an array of positive-growing integers whose sum is N

  • 【Q681】 Find two numbers in an array of positive integers whose sum is N

Find all possible sets of N numbers in a given array whose sum is sum

  • 【Q673】 Find all possible sets of N numbers in a given array whose sum is sum

Find all possible sets of N numbers in a given array whose sum is sum

function fn(arr, n, sum) {}
Copy the code

How do I determine if two linked lists intersect

  • 【Q061】 How to determine whether two linked lists intersect

A classic problem

In the end

Code programming questions appear frequently in the interview process, and can largely judge the candidate’s code ability and code style.