introduce
The traditional interview process typically starts with a basic question about how to write a mobile screen, followed by a full day of on-site work to test coding skills and cultural fit. Almost invariably, the determining factor is coding ability. After all, engineers get paid to produce usable software at the end of the day. Typically, we use whiteboards to test this coding ability. More important than getting the right answer is a clear thought process. In coding, as in life, the right answer is not always obvious, but good arguments are usually good enough. Effective reasoning ability marks the potential for learning, adaptation and development. The best engineers are always growing and the best companies are always innovating.
Algorithmic challenges are effective ways to exercise your abilities because there is always more than one way to solve them. This opens up possibilities for decision-making and algorithmic decisions. When solving algorithmic problems, we should challenge ourselves to define the problem from multiple perspectives and weigh the benefits and drawbacks of each approach. With enough connections, we can even glimpse the truth of the universe; There is no “perfect” solution.
To really understand algorithms is to understand the relationship between data and structure. The relationship between data structures and algorithms is like Yin to Yang, glass to water. Without a glass, water cannot be carried. Without data structures, we have no objects to use for logic. Without water, the glass will become empty for lack of substance. Without algorithms, objects cannot be transformed or “consumed.”
For further analysis of Data Structures, see: Data Structures in JavaScript:
The introduction
When applied to code, an algorithm is simply a function that converts the input of a defined data structure into the output of a defined data structure. The logic inherent in the algorithm determines how to transform. First, inputs and outputs should be explicitly defined as unit tests. This requires a complete understanding of the problem at hand, which is not trivial, as thorough analysis allows the problem to be solved naturally without writing any code.
Once you have a thorough grasp of the problem area, you can start brainstorming solutions. What variables are needed? How many loops and what types of loops are needed? Is there a clever built-in way to help? What are the edge cases to consider? Complex and repetitive logic only increases the difficulty of reading and understanding. Can helper functions be abstracted or pulled away? Algorithms usually need to be extensible. How will the function perform as the input size increases? Should there be some kind of caching mechanism? Performance optimization (time) usually requires sacrificing memory space (increased memory consumption).
To make the problem more concrete, let’s draw a diagram!
When the high-level structure in the solution starts to appear, we can start writing pseudocode. To make a real impression, prioritize refactoring and reuse of code. Sometimes functions that behave similarly can be combined into a more general function that can accept additional arguments. Other times, it’s better to de-parameterize. It also makes sense to keep functions pure for testing and maintenance. In other words, take architecture and design patterns into account when designing algorithms.
If anything is unclear, please ask questions to clarify!
Big O (Algorithm complexity)
To estimate the run-time complexity of an algorithm, we usually estimate the scalability of an algorithm by extrapolating the input size to infinity before calculating the number of operations the algorithm requires. In this worst-case run-time upper bound, we can ignore the coefficients and add-ons, leaving only the factors of the dominant function. Therefore, only a few types are needed to describe almost all extensible algorithms.
The optimal optimal algorithm is one that changes in time and space at a constant rate. That is, it doesn’t care about the size of the input at all. Suboptimal algorithms change over time or space at a logarithmic rate, again linear, linear logarithmic, quadratic and exponential respectively. The worst is to change in time or space at a factorial rate. In big-O notation:
- Constant: O (1)
- Log: ORDER (log n)
- Linear: O (n)
- Linear logarithm: O(n log n)
- Second: O (n squared)
- Index: O (2 ^ n)
- Factorial: O (n!
Graph: bigocheatsheet.com
Big-o asymptotic analysis is an indispensable tool when we consider the tradeoff between the temporal and spatial complexity of algorithms. However, Big O ignores constants that may have an impact in practice. In addition, the temporal and spatial complexity of optimization algorithms may increase realistic development time or negatively impact code readability. Intuition for what is truly negligible is equally important when designing the structure and logic of an algorithm.
Arrays
The cleanest algorithms usually make use of standard objects that are inherent in the language. Arguably the most important thing in computer science is Arrays. No other object in JavaScript has more utility methods than arrays. The array methods worth remembering are sort, reverse, slice, and splice. The array inserts elements from the 0th index. This means that the position of the last array element is array.length -1. Arrays are great for indexing (push), but terrible for inserting, deleting (not popping), and searching. In JavaScript, arrays can grow dynamically.
Corresponding Big O:
- Index: O (1)
- Insert: O (n)
- Delete: O (n)
- Violent Search: O(n)
- Optimized search: O(log n)
It’s also worth reading the full MDN documentation on Arrays.
Sets and Maps are similar to arrays. In a set, the elements must be unique. In a Map, elements consist of keys and values in a lexicographical relationship. Of course, Objects (and their literals) can also store key-value pairs, but the keys must be strings.
The Object constructor creates an Object wrapper developer.mozilla.org
The iteration
Closely related to Arrays is looping through them. In JavaScript, we can iterate with five different control structures. The most customizable is the for loop, which we can use to iterate over a set of indexes in almost any order. If the number of iterations cannot be determined, we can use while and do while loops until a certain condition is met. For any object, we can use for in and for of loops to iterate over its “key” and “value,” respectively. To get both “keys” and “values,” we can use its entries() method. We can break the loop at any time with a break statement, or skip to it with a continue statement. In most cases, controlling iteration through generator functions is the best option.
The native methods for traversing all array items are indexOf, lastIndexOf, includes, Fill, and Join. In addition, we can provide callbacks for the following methods: findIndex, find, filter, forEach, map, some, every, and reduce.
recursive
In a groundbreaking Church-Turing Thesis, it was shown that any iterative function can be rewritten as a recursive function, and vice versa. Sometimes, recursion is more concise, more clear, more elegant. Take the factorial iteration function:
const **factorial** = number => {
let product = 1;
for (let i = 2; i <= number; i++) {
product *= i;
}
return product;
};
Copy the codeUsing recursive functions, it only takes one line of code!
const **factorial** = number => {
return number < 2 ? 1 : number * factorial(number - 1);
};
Copy the codeAll recursive functions have a general pattern. They always consist of a recursive part that calls itself and a base case that does not call itself. When a function calls itself, it pushes a new execution context onto the execution stack. This continues until the base case is reached, and then the stack pops up and unfolds into individual contexts one by one. Therefore, sloppy dependency recursion can lead to terrible run-time stack overflow errors.
Examples of code for the factorial function:
Finally, we’re ready for any algorithmic challenge! 😉
Hot algorithm problem
In this section, we’ll go through 22 frequently asked algorithmic questions, in order of difficulty. We will discuss the different approaches and their pros and cons as well as the time complexities at work. The most elegant solutions often use special “tricks” or sharp insights. With that in mind, let’s get started!
1. Reverse the string
Taking a given string of characters as input, write a function that reverses the character order of the incoming string and returns it.
describe("String Reversal", () => {
it("**Should reverse string**", () =\> {
assert.equal(reverse("Hello World!"), ! "" dlroW olleH");
});
});
Copy the codeAnalysis:
If we know the “trick,” then the solution doesn’t matter. The trick is to realize that we can use the built-in reverse method for arrays. First, we use the split method on the string to generate an array of characters, then we can use the reverse method, and finally we can use the join method to recombine the array of characters back into a string. This solution can be done in one line of code! It’s not as elegant, but you can solve problems with the latest syntax and helper functions. Using the new for of loop to iterate over each character in the string demonstrates our familiarity with the latest syntax. Alternatively, we can use the reduce method of arrays, which eliminates the need to keep temporary primitives.
Each character for a given string is “accessed” once. Although the access may occur multiple times, the time can be normalized to linear time. And because there is no separate internal state to be kept, the space is constant.
2. The palindrome
Palindrome is when a word or phrase is read the same forward and backward. Write a function to verify that a given input value is a palindrome.
describe("Palindrome", () => {
it("**Should return true**", () =\> {
assert.equal(isPalindrome("Cigar? Toss it in a can. It is so tragic"), true);
});
it("**Should return false**", () =\> {
assert.equal(isPalindrome("sit ad est love"), false);
});
});
Copy the codeAnalysis:
The key here is to realize that we’re building on what we learned in the previous problem. In addition, we need to return a Boolean value. This is as simple as returning a triple equality check on the original string. We can also use the new every method on arrays to check that the first and last characters match in order with a center point of symmetry. However, this can make more than twice as many checks as necessary. Similar to the previous problem, the time and space runtime complexity of this problem is the same.
What if we want to extend our functionality to test the entire phrase? We can create a helper function that uses regular expressions and the replace method on strings to weed out non-alphabetic characters. If regular expressions are not allowed, we create an array of acceptable characters to use as filters.
3. Integer inversion
Given an integer, reverse the order of the numbers.
describe("Integer Reversal", () => {
it("**Should reverse integer**", () =\> {
assert.equal(reverse(1234), 4321);
assert.equal(reverse(-1200), -21);
});
});
Copy the codeAnalysis:
The trick here is to first convert the number to a string using the built-in toString method. We can then simply reuse the algorithmic logic of the reversed string. After the number inversion, we can use the global parseInt function to convert the string back to an integer and use math.sign to handle the sign of the number. This approach can be simplified to one line of code!
Because we reused the logic of the inversion string algorithm, the time and space runtime complexity of this algorithm is the same as before.
4. Fizz Buzz
Given a number as an input value, prints all integers from 1 to the given number. However, if the integer is divisible by 2, “Fizz” is printed; When it is divisible by 3, print “Buzz”; When it is divisible by both 2 and 3, “Fizz Buzz” is printed.
Analysis:
The challenge of this classical algorithm becomes very simple when we realize that modular operators can be used to check separability (whether it is divisible). Modular operators mod two numbers and return the remainder of their division. So we can simply iterate over each integer and check to see if the remainder of each integer divisible by 2 and 3 is 0. And that shows us our mathematical skills, because we know that when a number is divisible by both a and B, it’s also divisible by their least common multiple.
Also, the time and space runtime complexity of this algorithm is the same as before, because every integer is accessed and checked once but no internal state needs to be saved.
5. Most common characters
Given a string of characters, returns the most frequently occurring character in the string.
describe("Max Character", () => {
it("**Should return max character**", () =\> {
assert.equal(max("Hello World!"), "l");
});
});
Copy the codeAnalysis:
The trick here is to create a table that records the number of occurrences of each character as the string is traversed. This table can be created with object literals, with characters as the key of object literals, and the number of occurrences of characters as values. We then iterate through the table to find the most frequent character with a temporary variable that holds each key-value pair.
Although we used two separate loops to iterate over two different input values (string and character map), the time complexity was still linear. Although the loop is for strings, ultimately, there is a limit to the size of the character map because any language has a finite number of characters. By the same token, although internal state is preserved, spatial complexity is constant no matter how the input string grows. Temporary primitives are also negligible on a large scale.
6. Anagrams
Anagrams are words or phrases that contain the same characters. Write a function that checks this functionality.
describe("Anagrams", () => {
it("**Should implement anagrams**", () =\> {
assert.equal(anagrams("hello world"."world hello"), true);
assert.equal(anagrams("hellow world"."hello there"), false);
assert.equal(anagrams("hellow world"."hello there!"), false);
});
});
Copy the codeAnalysis:
One obvious way to do this is to create a character map that counts the number of characters per input string. Later, we can compare the mappings to see if they are the same. The logic for creating a character map can be separated into a helper function for easy reuse. To be more careful, we should first delete all non-characters from the string, and then lower case the remaining characters.
As we have seen, character maps have linear time complexity and constant space complexity. More specifically, this method is O(n + m) complexity for time because two different strings are checked.
A more elegant alternative is to simply sort the input values and check if they are equal! However, the disadvantage is that sorting usually takes linear time.
7. A vowel
Given a word or phrase of type string, count the number of vowels.
describe("Vowels", () => {
it("**Should count vowels**", () =\> {
assert.equal(vowels("hello world"), 3);
});
});
Copy the codeAnalysis:
The easiest way is to use a regular expression to take all the vowels and count them. If regular expressions are not allowed, we can simply iterate over each character to see if it is a cause letter. But first you need to convert the string to lowercase.
Both methods are linear time complexity and constant space complexity, because every character needs to be checked once, and temporary primitives can be ignored.
8. The array
For an array of a given size, split the array elements into a list of array types of a given size.
describe("Array Chunking", () => {
it("**Should implement array chunking**", () =\> {
assert.deepEqual(chunk(\[1, 2, 3, 4\], 2), \[\[1, 2\], \[3, 4\]\]);
assert.deepEqual(chunk(\[1, 2, 3, 4\], 3), \[\[1, 2, 3\], \[4\]\]);
assert.deepEqual(chunk(\[1, 2, 3, 4\], 5), \[\[1, 2, 3, 4\]\]);
});
});
Copy the codeAnalysis:
An obvious way to do this is to keep a reference to the last “block” and check its size as you iterate over the array of elements to see if you should put an element in the last block. A more elegant solution is to use the built-in Slice method. This eliminates the need for “references” and makes the code clearer. This can be done through a while loop or a for loop, which increments by step of a given size.
These algorithms have linear time complexity because each array item needs to be accessed once. They also have linear spatial complexity because of the need to hold an intrinsic “block” type array that changes in size as input values change.
9. Reverse the array
Given an array of any type, reverse the order of the array.
describe("Reverse Arrays", () => {
it("**Should reverse arrays**", () =\> {
assert.deepEqual(reverseArray(\[1, 2, 3, 4\]), \[4, 3, 2, 1\]);
assert.deepEqual(reverseArray(\[1, 2, 3, 4, 5\]), \[5, 4, 3, 2, 1\]);
});
});
Copy the codeAnalysis:
The simplest solution, of course, is to use the built-in Reverse method. But that’s so lame! If this method is not allowed, we can simply loop through the array and swap the beginning and end elements of the array. This means we’re going to hold an array element in memory. To avoid this need for staging, we can use structural assignment for elements that are symmetrically located in the array.
Although only half of the input array is traversed, the time complexity is still linear because Big O approximately ignores the coefficients.
10. Reverse words
Given a phrase, reverse the character order of each word in the phrase.
describe("Reverse Words", () => {
it("**Should reverse words**", () =\> {
assert.equal(reverseWords("I love JavaScript!"), "I evol ! tpircSavaJ");
});
});
Copy the codeAnalysis:
We can use the split method to create an array of single words. Then for each word, we use the logic of reversing strings to reverse its characters. Another approach is to iterate over each word in reverse and store the results in temporary variables. Either way, we need to temporarily store all the inverted words and finally splice them together.
Because every character is iterated over, and the size of the temporary variable required is proportional to the input string, the time and space complexity is linear.
11. Uppercase conversion
Given a phrase, capitalize each word.
describe("Capitalization", () => {
it("**Should capitalize phrase**", () =\> {
assert.equal(capitalize("hello world"), "Hello World");
});
});
Copy the codeAnalysis:
One solution is to iterate over each character, using the toUpperCase method toUpperCase the current character when the preceding character is a space. Since string literals are immutable in JavaScript, we need to reconstruct the input string using the appropriate uppercase conversion method. This approach requires that we always capitalize the first character. A more concise approach is to split the input string into an array of words. You then iterate through the array, capitalizing the first character of each element, and reconcatenating the words. For the same immutable reason, we need to keep a temporary array in memory to hold the correctly capitalized words.
Both have linear time complexity because each string is iterated once. They also have linear spatial complexity because they hold a temporary variable that grows in proportion to the input string.
12. The Caesar Code
Given a phrase, a new character that moves a given integer forward or backward by replacing each character with the alphabet. If necessary, the shift should loop back to the beginning or end of the alphabet.
describe("Caesar Cipher", () => {
it("**Should shift to the right**", () =\> {
assert.equal(caesarCipher("I love JavaScript!", 100), "E hkra FwrwOynelp!");
});
it("**Should shift to the left**", () =\> {
assert.equal(caesarCipher("I love JavaScript!", - 100),"M pszi NezeWgvmtx!");
});
});
Copy the codeAnalysis:
First, we need to create an array of alphabet characters to calculate the result of moving characters. This means that we need to convert the input string to lowercase before iterating through the characters. It’s easy to keep track of the current index with a regular for loop. We need to build a new string that contains the characters shifted after each iteration. Note that when we encounter a non-alphabetic character, we should immediately append it to the end of our result string and skip to the next iteration using the continue statement. One key thing to realize is that we can use modular operators to simulate the behavior of looping to the beginning or end of an alphabetic array when the shift exceeds 26. Finally, we need to check the case in the original string before appending the result to the result string.
The time and space complexity of this algorithm is linear because the characters of each input string need to be accessed and a new result string needs to be created based on the input string.
13. Ransom Note
Given a magazine paragraph and a Ransom paragraph, determine whether the magazine paragraph contains the words in each Ransom paragraph.
const magazine =
“Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum“;
describe("Ransom Note", () => {
it("**Should return true**", () =\> {
assert.equal(ransomNote("sit ad est sint", magazine), true);
});
it("**Should return false**", () =\> {
assert.equal(ransomNote("sit ad est love", magazine), false);
});
it("**Should return true**", () =\> {
assert.equal(ransomNote("sit ad est sint in in", magazine), true);
});
it("**Should return false**", () =\> {
assert.equal(ransomNote("sit ad est sint in in in in", magazine), false);
});
});
Copy the codeAnalysis:
The obvious thing to do is to break up the Magazine and Ransom paragraphs into arrays of single words, and then check if each Ransom word is present in the magazine paragraph. However, the time complexity of this method is quadratic, or O(n * m), which indicates poor performance of this method. We can achieve linear time complexity if we first create a list of words for the Magazine paragraph and then check if each word in the Ansom paragraph exists in the table. This is because lookups in mapped objects can always be done in constant time. But we will sacrifice spatial complexity because we need to keep the mapped objects in memory.
In code, this means we need to create a count of words in each magazine paragraph, and then check that the “hash table” contains the right number of Ransom words.
14. Average, median, and Mode(most frequent numbers)
Given an array of numbers, calculate the average, median, and Mode of those numbers.
const **stat1** = new Stats(\[1, 2, 3, 4, 4, 5, 5\]);
const **stat2** = new Stats(\[1, 1, 2, 2, 3, 3, 4, 4\]);
describe("Mean", () => {
it("**Should implement mean**", () =\> {
assert.equal(Stats.round(stat1. The mean ()), 3.43); assert.equal(Stats.round(stat2. The mean ()), 2.5); }); }); describe("Median", () => {
it("**Should implement median**", () =\> {
assert.equal(stat1.median(), 4);
assert.equal(stat2. The median (), 2.5); }); }); describe("Mode", () => {
it("**Should implement mode**", () =\> {
assert.deepEqual(stat1.mode(), \[4, 5\]);
assert.deepEqual(stat2.mode(), \[\]);
});
});
Copy the codeAnalysis:
In terms of difficulty, the algorithm to find the average of the set of numbers is the easiest. In statistics, average is defined as the sum of sets of numbers divided by the number of sets of numbers. Therefore, we can simply sum the array using the reduce method and divide by its length. The runtime complexity of this algorithm is linear with respect to time and constant with respect to space. Because each number has to be summed up as it goes through without having to store variables in memory.
The algorithmic difficulty of finding the median of a set is moderate. First, we need to sort the array, but if the length of the set is cardinality, we need extra logic to handle the two numbers in the middle. In this case, we need to return the average of these two numbers. This algorithm has linear logarithmic time complexity because it requires sorting, and linear space complexity because it requires memory to hold sorted arrays.
The algorithm for finding mode is the most complex. Since mode is defined as one or more digits that occur most frequently, we need to maintain a frequency table in memory. To complicate matters further, if each value occurs the same number of times, there is no mode. This means that in the code, we need to create a hash map to calculate the frequency of each “number”; The map is then traversed to find one or more digits with the highest frequency, possibly without mode. Because each number needs to be retained and counted in memory, this algorithm has linear time and space complexity.
15. Multiple summation
Given a set of numbers, return all combinations such that the sum of two numbers equals the given sum. Each number can be used more than once.
describe("Two Sum", () => {
it("**Should implement two sum**", () =\> {
assert.deepEqual(twoSum(\[1, 2, 2, 3, 4\], 4), \[\[2, 2\], \[3, 1\]\]);
});
});
Copy the codeAnalysis:
The obvious solution is to create nested loops that check each number against the rest of the group. Combinations that satisfy the summation and satisfy the given sum can be pushed into a result array. However, this nesting can lead to exponential time complexity, which is very inappropriate for large input values.
A neat trick is to maintain an array of “counterparts” for each number as we iterate through the input array, checking to see if the counterpart for each number already exists. By maintaining such arrays, we sacrifice spatial efficiency for linear time complexity.
Maximize profits
Given a set of stock prices in chronological order, find the lowest bid price and the highest offer price to maximize profit.
describe("Max Profit", () => {
it("**Should return minimum buy price and maximum sell price**", () =\> {
assert.deepEqual(maxProfit([1, 2, 3, 4, 5]), [1, 5]);
assert.deepEqual(maxProfit([2, 1, 5, 3, 4]), [1, 5]);
assert.deepEqual(maxProfit([2, 10, 1, 3]), [2, 10]);
assert.deepEqual(maxProfit([2, 1, 2, 11]), [1, 11]);
});
Copy the codeAnalysis:
Similarly, we can build nested loops that examine every possible combination of bid and ask prices to see which pair produces the most profit. In practice we can’t sell before we buy, so not every combination needs to be checked. Specifically, for a given buying price, we can ignore all prices up to the selling price. Therefore, the time complexity of the algorithm is better than that of the quadratic type.
But for a second, we can solve the problem with just one loop through the price array. The key is to realize that the selling price should never be lower than the buying price; If so, we should buy shares at lower prices. This means that in code we can simply maintain a temporary Boolean value to indicate that we should change the purchase price for the next iteration. This elegant approach requires only one loop and thus has linear time complexity and constant space complexity.
17. Sieve of Eratosthenes
For a given number, find all primes between zero and that number.
describe("Sieve of Eratosthenes", () => {
it("**Should return all prime numbers**", () =\> {
assert.deepEqual(primes(10), \[2, 3, 5, 7\]);
});
});
Copy the codeAnalysis:
At first glance, we might want to iterate over each number by simply using the modular operator to check for all possible separability. However, it is easy to think that this approach is very inefficient, with less time complexity than the quadratic. Fortunately, Eratosthenes of Cyrene, the inventor of geography, also found an effective way to identify prime numbers.
In the code, the first step is to create an array as large as the given number and initialize each of its elements to true. In other words, the index of the array represents all possible prime numbers, and each number is assumed to be true. We then set up a for loop to iterate over the number from 2 to the square root of the given number, using the array’s key interpolation to set the value of the element for each iterated number to false for a multiple less than the given number. By definition, no product of integers can be prime, and 0 and 1 are ignored here because they do not affect separability. Finally, we can simply filter out all the false values to get all the primes.
By sacrificing spatial efficiency to maintain an internal “hash table,” the Eratosthenes sieve would be better in time complexity than the quadratic, or O(n * log (log n)).
18. Fibonacci term formula
Implements a function that returns the Fibonacci number at a given index.
describe("Fibonacci", () => {
it("**Should implement fibonacci**", () =\> {
assert.equal(fibonacci(1), 1);
assert.equal(fibonacci(2), 1);
assert.equal(fibonacci(3), 2);
assert.equal(fibonacci(6), 8);
assert.equal(fibonacci(10), 55);
});
});
Copy the codeAnalysis:
Since Fibonacci numbers are the sum of the first two, the easiest way is to use recursion. The Fibonacci sequence assumes that the first two terms are 1 and 1; So we can build our base case based on that fact. For indexes greater than 2, we can call the first two terms of our own function. While elegant, this recursive approach is extremely inefficient, with exponential time complexity and linear spatial complexity. Because each function call requires a call stack, memory usage grows exponentially, so it can quickly crash.
The iterative approach is less elegant, but more time intensive. Through a loop, a complete Fibonacci sequence of the first N items (N for a given index value) can achieve linear time and space complexity.
19. Memoized Fibonacci
Implement an efficient recursive function for Fibonacci sequence.
describe("Memoized Fibonacci", () => {
it("**Should implement memoized fibonacci**", () =\> {
assert.equal(fibonacci(6), 8);
assert.equal(fibonacci(10), 55);
});
});
Copy the codeAnalysis:
Because the Fibonacci sequence makes redundant calls to itself, it can dramatically benefit from a strategy known as memorization. In other words, if we cache all input and output values when calling a function, the number of calls is reduced to linear time. Of course, this means we sacrifice extra memory.
In code, we can implement the mnemonization technique inside the function itself, or we can abstract it as a higher-order utility function that decorates any mnemonization function.
20. Draw the stairs
For a given stride length, print a “staircase” using # and “.
describe("Steps", () => {
it("**Should print steps**", () =\> {
assert.equal(steps(3), "# \\n## \\n###\\n");
assert.equal(_steps(3), "# \\n## \\n###\\n");
});
});
Copy the codeAnalysis:
The key insight is to realize that as we move down the stride, the number of #’s increases and the number of ”s decreases accordingly. If we have n steps to move, the global range is n rows and n columns. This means that runtime complexity is quadratic in both time and space.
Again, we found that this could be done recursively. In addition, we need to pass additional parameters in place of necessary temporary variables.
Draw the pyramids
For a given number of levels, print the “pyramid” using # and “.
describe("Pyramid", () => {
it("**Should print pyramid**", () =\> {
assert.equal(pyramid(3), " # \\n ### \\n#####\\n");
assert.equal(_pyramid(3), " # \\n ### \\n#####\\n");
});
});
Copy the codeAnalysis:
The key here is to realize that when the height of the pyramid is N, the width is 2 times N minus 1. And then as we go down to the bottom, we just keep increasing the number of #’s with central symmetry, and decreasing the number of double’s. Since the algorithm builds a pyramid with 2 * n-1 * n traversal, its runtime time complexity and space complexity are quadratic.
Again, we can see that the recursive call here can use the previous method: an additional variable needs to be passed in place of the necessary temporary variable.
22. Spiral matrix
Creates a square array of a given size so that the elements of the square are arranged in spiral order.
describe("Matrix Spiral", () => {
it("**Should implement matrix spiral**", () =\> {
assert.deepEqual(spiral(3), \[\[1, 2, 3\], \[8, 9, 4\], \[7, 6, 5\]\]);
});
});
Copy the codeAnalysis:
While this is a complicated problem, the trick is to create a temporary variable at the beginning and end of the current row and column, respectively. In this way, we can spiral through the beginning row and the beginning column and decrement the end row and the end column to the center of the square matrix.
Because the algorithm iteratively builds a square matrix of a given size, its runtime complexity is quadratic in both time and space.
Data structure algorithm
Since data structures are the building blocks of algorithms, it’s well worth exploring common data structures in depth.
Again, for a quick high-level analysis, see:
Data Structures in JavaScript
For Frontend Software Engineers medium.com
The queue
Given two queues as input, create a new queue by “weaving” them together.
describe("Weaving with Queues", () => {
it("**Should weave two queues together**", () =\> {
const one = new Queue();
one.enqueue(1);
one.enqueue(2);
one.enqueue(3);
const two = new Queue();
two.enqueue("one");
two.enqueue("two");
two.enqueue("three");
const result = weave(one, two);
assert.equal(result.dequeue(), 1);
assert.equal(result.dequeue(), "one");
assert.equal(result.dequeue(), 2);
assert.equal(result.dequeue(), "two");
assert.equal(result.dequeue(), 3);
assert.equal(result.dequeue(), "three");
assert.equal(result.dequeue(), undefined);
});
Copy the codeAnalysis:
A queue class must have at least one enqueue method, one dequeue method, and one PEEK method. Then, we use the while loop, which determines if peek exists, and if so, we let it perform an exit, which is then enqueued to our new queue.
This algorithm is order n plus m in time and space because we need to iterate over two different sets and store them.
The stack
The Queue class is implemented using two stacks.
describe("Queue from Stacks", () => {
it("**Should implement queue using two stacks**", () =\> {
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
assert.equal(queue.peek(), 1);
assert.equal(queue.dequeue(), 1);
assert.equal(queue.dequeue(), 2);
assert.equal(queue.dequeue(), 3);
assert.equal(queue.dequeue(), undefined);
});
});
Copy the codeAnalysis:
We can start with a class constructor that initializes both stacks. Since the last inserted record is fetched first on the stack, we need to loop to the last record to perform a “dequeue” or “peek” to mimic the behavior of the queue: the first inserted record is fetched first. We can temporarily save all the elements in the first stack until the end by using the second stack. After “peek” or “out of the column,” we simply move everything back onto the first stack. To “column” a record, we can simply push it onto the first stack.
Although we use two stacks and loop twice, the algorithm is asymptotically linear in time and space complexity. Though we use two stacks and need to loop twice, this algorithm is still asymptotically linear in time and space.
The list
Unidirectional linked lists usually have the following functions:
describe("Linked List", () => {
it("**Should implement insertHead**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
assert.equal(chain.head.data, 1);
});
it("**Should implement size**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
assert.equal(chain.size(), 1);
});
it("**Should implement getHead**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
assert.equal(chain.getHead().data, 1);
});
it("**Should implement getTail**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
assert.equal(chain.getTail().data, 1);
});
it("**Should implement clear**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
chain.clear();
assert.equal(chain.size(), 0);
});
it("**Should implement removeHead**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
chain.removeHead();
assert.equal(chain.size(), 0);
});
it("**Should implement removeTail**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
chain.removeTail();
assert.equal(chain.size(), 0);
});
it("**Should implement insertTail**", () =\> {
const chain = new LinkedList();
chain.insertTail(1);
assert.equal(chain.getTail().data, 1);
});
it("**Should implement getAt**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
assert.equal(chain.getAt(0).data, 1);
});
it("**Should implement removeAt**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
chain.removeAt(0);
assert.equal(chain.size(), 0);
});
it("**Should implement insertAt**", () =\> {
const chain = new LinkedList();
chain.insertAt(0, 1);
assert.equal(chain.getAt(0).data, 1);
});
it("**Should implement forEach**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
chain.insertHead(2);
chain.forEach((node, index) => (node.data = node.data + index));
assert.equal(chain.getTail().data, 2);
});
it("**Should implement iterator**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
chain.insertHead(2);
for (let node of chain) node.data = node.data + 1;
assert.equal(chain.getTail().data, 2);
});
});
Copy the codeChallenge #1: The midpoint
Returns the intermediate value of the linked list without using a counter
describe("Midpoint of Linked List", () => {
it("**Should return midpoint of linked list**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
chain.insertHead(2);
chain.insertHead(3);
chain.insertHead(4);
chain.insertHead(5);
assert.equal(midpoint(chain).data, 3);
});
});
Copy the codeAnalysis:
The trick here is to do two linked list traversals at the same time, one of which is twice as fast as the other. When fast traversal reaches the end, slow traversal reaches the midpoint!
The time complexity of this algorithm is linear and the space complexity is constant.
Challenge # 2: cycle
Check if the list is circular without preserving node references.
describe("Circular Linked List", () => {
it("**Should check for circular linked list**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
chain.insertHead(2);
chain.insertHead(3);
chain.head.next.next.next = chain.head;
assert.equal(circular(chain), true);
});
});
Copy the codeAnalysis:
Much of the list functionality is based on the assertion that a list has an explicit end node. Therefore, it is important to ensure that linked lists are not circular. The trick here is to do two traversals at the same time, one of which is twice as fast as the other. If the list is circular, then eventually the faster loop will overlap with the slower one. So we can return true. Otherwise, the traversal will hit an end point, and we can return false.
This algorithm also has linear time complexity and constant space complexity.
Challenge #3: From Tail
Without a counter, returns the value of the node that is a given number of steps away from the end of the list.
describe("From Tail of Linked List", () => {
it("**Should step from tail of linked list**", () =\> {
const chain = new LinkedList();
chain.insertHead(1);
chain.insertHead(2);
chain.insertHead(3);
chain.insertHead(4);
chain.insertHead(5);
assert.equal(fromTail(chain, 2).data, 3);
});
});
Copy the codeAnalysis:
The trick here is the same as before, we’re going to go through the list twice. However, in this case, a “fast” traversal starts a given number of steps before a “slow” traversal. Then, we go down the list at the same speed until the faster one reaches the end. At this point, the slow traversal is just the right distance from the end.
This algorithm also has linear time complexity and constant space complexity.
The tree
Tree structures typically have the following functions:
describe("Trees", () => {
it("**Should add and remove nodes**", () =\> {
const root = new Node(1);
root.add(2);
assert.equal(root.data, 1);
assert.equal(root.children\[0\].data, 2);
root.remove(2);
assert.equal(root.children.length, 0);
});
it("**Should traverse by breadth**", () =\> {
const tree = new Tree();
tree.root = new Node(1);
tree.root.add(2);
tree.root.add(3);
tree.root.children\[0\].add(4);
const numbers = \[\];
tree.traverseBF(node => numbers.push(node.data));
assert.deepEqual(numbers, \[1, 2, 3, 4\]);
});
it("**Should traverse by depth**", () =\> {
const tree = new Tree();
tree.root = new Node(1);
tree.root.add(2);
tree.root.add(3);
tree.root.children\[0\].add(4);
const numbers = \[\];
tree.traverseDF(node => numbers.push(node.data));
assert.deepEqual(numbers, \[1, 2, 4, 3\]);
});
});
Copy the codeChallenge #1: Tree breadth
For a given tree, return the breadth of each level.
describe("Width of Tree Levels", () => {
it("**Should return width of each tree level**", () =\> {
const root = new Node(1);
root.add(2);
root.add(3);
root.children\[1\].add(4);
assert.deepEqual(treeWidths(root), \[1, 2, 1\]);
});
});
Copy the codeAnalysis:
A tree can have depth-first traversal of all its slices through the stack, and breadth-first traversal of all its levels with the help of queues. Since we want to count the number of multiple nodes per level, we need to do breadth-first traversal with queues in a depth-first manner. The trick here is to insert a special flag into the queue to let us know that the current level has been traversed, so we can reset the counter for the next level.
This approach has linear time and space complexity. Even though our counter is an array, it will never be larger than a linear one.
Challenge #2: Height of the tree
For a given tree, return its height (the maximum level of the tree).
describe("Height of Tree", () => {
it("**Should return max number of levels**", () =\> {
const root = new Node(1);
root.add(2);
root.add(3);
root.children\[1\].add(4);
assert.deepEqual(treeHeight(root), 2);
});
});
Copy the codeAnalysis:
We can directly reuse the logic of the first challenge problem. However, in this case, we need to increase our counter when we encounter a “reset”. The two logics are almost identical, so the algorithm also has linear time and space complexity. Here, our counter is just an integer, so its size is even more negligible.
The chart
Please wait for the follow-up! (thank you)
Sorting algorithm
We can use a number of algorithms to sort data sets. Fortunately, we are only required to know the basics and first principles. For example, optimal algorithms can achieve both constant space complexity and linear time complexity. In that spirit, we’ll analyze the most popular algorithms in order of difficulty to efficiency.
Bubble sort
This algorithm is the easiest to understand, but the least efficient. It compares each element to all the others, switching order until the larger element “bubbles” to the top. This algorithm requires quadratic time and constant space.
Insertion sort
As with bubble sort, each element is compared to all the others. The difference here is that instead of swapping, the operation “splices” into the correct order. In fact, it will keep the original order of repeating items. This “greedy” algorithm still requires quadratic time and constant space.
Selection sort
As it loops through the collection, the algorithm looks for and “selects” the index with the smallest value and swaps the starting element with the element at the index position. Algorithms also require quadratic time and constant space.
Quick sort
The algorithm recursively selects one element as the axis, iterates through the rest of the set, pushing all the smaller elements to the left and all the larger elements to the right until all the elements are sorted correctly. This algorithm has quadratic time complexity and logarithmic space complexity, so it is usually the fastest in practice. As a result, most programming languages have this algorithm built into them for sorting.
Merge sort
Although this is one of the most efficient algorithms, the algorithm is difficult to understand. It requires a recursive part that breaks up a set into individual units; And you need an iteration section, which puts the individual units back together in the correct order. This algorithm requires linear logarithmic time and linear space.
Count sorting
If we somehow know the maximum, we can use this algorithm to sort sets in linear space and time! Maximum let’s create an array of that size to count the number of occurrences of each index value. You then simply extract all the elements with non-zero count index positions into the result array. This hashing – like algorithm is the most efficient by performing a constant time lookup on the array.
Other sorting algorithms
Graph: bigocheatsheet.com
Search algorithm
The worst algorithm requires searching every item in the set and takes O(n) time. If a collection is already sorted, each iteration takes only half as many checks and O(log n) time, which is a huge performance improvement for very large data sets.
Binary search
When a collection is sorted, we can traverse or recursively examine our retrieved values and intermediate items, discarding half of the parts where the desired value is not present. In fact, our goal can be found in logarithmic time and constant space cases.
Binary search tree
Another way to sort a collection is to generate a binary search tree (BST) from it. A BST search is just as efficient as a binary search. In a similar way, we can discard half of what we know does not contain the expected value in each iteration. In fact, another way to sort collections is to do depth-first traversal of the tree in order!
The creation of a BST occurs in linear time and space, but searching for it requires logarithmic time and constant space.
To verify that a binary tree is BST, we can recursively check that each left subterm is always less than the root (most likely) and each right subterm is always greater than the root on each root (least likely). This song method requires linear time and constant space.
conclusion
In modern Web development, functions are central to the Web experience. The data structure is accepted and returned by the function, and the algorithm determines the internal mechanism. The order of magnitude of the data structure of the algorithm is described by the spatial complexity, and the order of magnitude of the calculation times is described by the time complexity. In practice, runtime complexity is represented as a big-O notation that helps engineers compare all possible solutions. The most efficient runtime is constant time, independent of the size of the input and output values; The least efficient method involves computing exponential time and space. True mastery of algorithms and data structures means being able to reason both linearly and systematically.
In theory, every problem has an iterative and recursive solution. Iterative algorithms approach the solution dynamically from the bottom up. Recursive algorithms decompose repeating subproblems from the top. In general, the recursive scheme is more intuitive and easier to implement, but the iterative scheme is easier to understand and requires less memory. JavaScript naturally supports both of these scenarios with its first-class functions and control-flow structure. Usually, some space efficiency is sacrificed for better performance, or performance is sacrificed to reduce memory consumption. The right balance between the two depends on the actual situation and the environment. Fortunately, most libraries are more concerned with computational reasoning than results.
To impress your interviewers, look for opportunities to leverage architectural design and design patterns to improve reusability and maintainability. If you’re looking for a senior position, a knowledge of the basics and first principles is just as important as system-level design experience. But the best companies also evaluate cultural fit. Since no one is perfect, the right team is essential. More importantly, there are some things in this world that cannot be achieved alone. What people create together is often the most satisfying and meaningful.