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
- Are there consistent code specifications
- Is there a legible variable name
- 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.
- ES API
- lodash API
- Programming logic problem
- 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
- What is the first Index in the callback function?
- 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:
- Note the deep nesting of data
- Pay attention to
user['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
- If it occurs only once, no number is encoded, as in
aaab -> a3b
- If it occurs only twice, no encoding is performed, as in
aabbb -> aab3
- 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:
- Dynamically create
script
, the use ofscript.src
Load requests across cross-domains script.src
The 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
- Take the first k number in the array and make a small top heap, heap
- 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.