Although a lot of times we don’t have much access to algorithms on the front end. Most of them are interactive, but from the perspective of corporate interviews, algorithms are still a consideration. In fact, learning data structures and algorithms is helpful for engineers to understand and analyze problems. If we are faced with complex problems in the future, the accumulation of these basic knowledge can help us better optimize our solutions. Here are some of the most common questions you may encounter in a front-end interview.
Q1 Is a word palindrome?
Palindrome refers to the same words or sentences, in the following transposition or upside down, to produce the interest of a loop, called palindrome, also called a loop. Like the Mamam Redivider.
A lot of people get this problem and it’s very easy to think of using “for” to reverse the alphabetical order of the string and just match it. The important thing to look at is the implementation of reverse. We can actually convert strings into arrays using existing functions, and that’s an important idea, because we have more freedom to manipulate strings.
function checkPalindrom(str) {
return str == str.split('').reverse().join('');
}
Q2 removes duplicate values from an array of integers
For example, input: [1,13,24,11,11,14,1,2] Output: [1,13,24,11,14,2] the duplicate elements 11 and 1 need to be removed.
This question appears in many front end questions. It mainly inspects the use of Object by individuals and uses key to screen.
/** * unique an array **/let unique = function(arr) { let hashTable = {}; let data = []; for(let i=0,l=arr.length; i<l; i++) { if(! hashTable[arr[i]]) { hashTable[arr[i]] = true; data.push(arr[i]); } } return data }module.exports = unique;
Q3 Counts the most letters in a string
Give a sequence of English characters and find the most repeated letters
Input: AFjGHdFRAAAASdenAs Output: a
The previous algorithm appeared in the past, where we need to count the number of repetitions.
function findMaxDuplicateChar(str) { if(str.length == 1) { return str; } let charObj = {}; for(let i=0; i<str.length; i++) { if(! charObj[str.charAt(i)]) { charObj[str.charAt(i)] = 1; }else{ charObj[str.charAt(i)] += 1; } } let maxChar = '', maxValue = 1; for(var k in charObj) { if(charObj[k] >= maxValue) { maxChar = k; maxValue = charObj[k]; } } return maxChar; }module.exports = findMaxDuplicateChar;
Q4 sorting algorithm
If the algorithm topic, should be mostly more open topics, do not limit the implementation of the algorithm, but must be required to master several of them, so bubble sort, this more basic and easy to understand the memory of the algorithm must need to memorize in mind. The bubble sort algorithm is to compare the size, the small and the big in order to swap positions.
function bubbleSort(arr) { for(let i = 0,l=arr.length; i<l-1; i++) { for(let j = i+1; j<l; j++) { if(arr[i]>arr[j]) { let tem = arr[i]; arr[i] = arr[j]; arr[j] = tem; } } } return arr; }module.exports = bubbleSort;
In addition to bubble sort, there are many such as insert sort, quick sort, hill sort and so on. Each sorting algorithm has its own characteristics. You don’t need to know all of them, but you should be familiar with several algorithms. Quicksort, for example, is very efficient, and the basic principle is shown here (wiki) :
The algorithm takes an element value, puts anything less than it in the left array, puts anything greater than it in the right array, and then does a recursive left and right array operation, and returns the merged array as the sorted array.
function quickSort(arr) { if(arr.length<=1) { return arr;
} let leftArr = []; let rightArr = []; let q = arr[0]; for(let i = 1,l=arr.length; i<l; i++) { if(arr[i]>q) {
rightArr.push(arr[i]);
}else{
leftArr.push(arr[i]);
}
} return [].concat(quickSort(leftArr),[q],quickSort(rightArr));
}module.exports = quickSort;
Amway everyone a learning address, through the animation of the implementation of the algorithm.
HTML5 Canvas Demo: Sorting Algorithms
Q5 swaps two integers without the aid of temporary variables
Input a =2, b = 4 output a = 4, b =2
This kind of problem is very clever, we need to jump out of the conventional thinking, using a, B substitution.
It’s basically using + – to do the operation, like a = a + (b – a) is actually the same thing as a = b at the end;
function swap(a , b) {
b = b - a;
a = a + b;
b = a - b; return [a,b];
}module.exports = swap;
Q6 Using canvas to draw a limited Fibonacci sequence?
The length of the sequence is limited to 9.
Fibonacci sequence, also known as the Golden section sequence, refers to the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34… In mathematics, the Fibonacci sequence mainly deals with recursion calls. We generally know the definition
fibo[i] = fibo[i-1]+fibo[i-2];
Method to generate a Fibonacci array
function getFibonacci(n) {
var fibarr = []; var i = 0; while(i<n) { if(i<=1) {
fibarr.push(i);
}else{
fibarr.push(fibarr[i-1] + fibarr[i-2])
}
i++;
} return fibarr;
}
All that remains is to draw the curve using the Canvas Arc method
DEMO
Q7 Find the maximum difference of the following positive arrays such as:
Input [10,5,11,7,8,9] output 6
This is a question to test the search for the maximum value of a basic array, and obviously we know that the maximum difference must be the difference between the maximum and minimum value of an array.
function getMaxProfit(arr) { var minPrice = arr[0]; var maxProfit = 0; for (var i = 0; i < arr.length; i++) { var currentPrice = arr[i];
minPrice = Math.min(minPrice, currentPrice); var potentialProfit = currentPrice - minPrice;
maxProfit = Math.max(maxProfit, potentialProfit);
} return maxProfit;
}
Q8 randomly generates a string of the specified length
Implement an algorithm that randomly generates characters of specified length.
For example, for a given length of 8
function randomString(n) {
let str = 'abcdefghijklmnopqrstuvwxyz9876543210'; let tmp = '',
i = 0,
l = str.length; for (i = 0; i < n; i++) {
tmp += str.charAt(Math.floor(Math.random() * l));
} return tmp;
}module.exports = randomString;
Q9 implements functionality similar to getElementsByClassName
Implement a function of your own to find all DOM nodes containing a class under a DOM node? Native-provided DOM lookup functions such as getElementsByClassName querySelectorAll are not allowed.
function queryClassName(node, name) {
var starts = '(^|[ \n\r\t\f])',
ends = '([ \n\r\t\f]|$)'; var array = [],
regex = new RegExp(starts + name + ends),
elements = node.getElementsByTagName("*"),
length = elements.length,
i = 0,
element; while (i < length) {
element = elements[i]; if (regex.test(element.className)) {
array.push(element);
}
i += 1;
} return array;
}
Q10 implement Binary Search Tree with JS
Generally called the probability of writing all is relatively small, but focus on your understanding of it and the implementation of some basic features. Ordered binary tree (ordered binary tree) is an empty tree or a binary tree with the following properties:
-
If the left subtree of any node is not empty, the value of all nodes in the left subtree is less than the value of its root node.
-
If the right subtree of any node is not empty, the value of all nodes in the right subtree is greater than the value of its root node.
-
The left and right subtrees of any node are binary search trees respectively.
-
There are no nodes with equal keys. Compared with other data structures, binary search tree has the advantage of low time complexity of search and insert. Is O (log n). Binary search trees are basic data structures used to construct more abstract data structures, such as sets, multisets, associative arrays, etc.
When writing, you need to fully understand the characteristics of binary search tree, and you need to set the data structure of each node
class Node { constructor(data, left, right) { this.data = data; this.left = left; this.right = right; }}
A tree is composed of nodes, which gradually grow from the root node to each child node, so it has the basic structure of a root node, with the method of adding, finding and deleting nodes.
class BinarySearchTree { constructor() { this.root = null; } insert(data) { let n = new Node(data, null, null); if (! this.root) { return this.root = n; } let currentNode = this.root; let parent = null; while (1) { parent = currentNode; if (data < currentNode.data) { currentNode = currentNode.left; if (currentNode === null) { parent.left = n; break; } } else { currentNode = currentNode.right; if (currentNode === null) { parent.right = n; break; } } } } remove(data) { this.root = this.removeNode(this.root, data) } removeNode(node, data) { if (node == null) { return null; } if (data == node.data) { // no children node if (node.left == null && node.right == null) { return null; } if (node.left == null) { return node.right; } if (node.right == null) { return node.left; } let getSmallest = function(node) { if(node.left === null && node.right == null) { return node; } if(node.left ! = null) { return node.left; } if(node.right ! == null) { return getSmallest(node.right); } } let temNode = getSmallest(node.right); node.data = temNode.data; node.right = this.removeNode(temNode.right,temNode.data); return node; } else if (data < node.data) { node.left = this.removeNode(node.left,data); return node; } else { node.right = this.removeNode(node.right,data); return node; } } find(data) { var current = this.root; while (current ! = null) { if (data == current.data) { break; } if (data < current.data) { current = current.left; } else { current = current.right } } return current.data; } }module.exports = BinarySearchTree;