My last article received such attention. Thank you for your likes and comments, which gave me a lot of motivation to continue to update this series. I also hope that they can be of some help to you. Crab, crab.

portal

  • Summary of the interview (1) : HTML layout, CSS selector and JS basic comprehensive ability knowledge
  • Algorithm: array flat, deduplication and sort
  • React Vue Understanding and basics
  • Cross-domain problem solution
  • HTTP protocol status code
  • Cache and update issues
  • Webviews interact with native applications
  • Server-side knowledge

Algorithm: array flat, deduplication and sort

Let’s cut to the chase.

let arr = [
  [
    ['1-7'.'2-6'].4-6 ' 'The [['2-0'.1-4 ' '],
      ['3-9'].4-5 ' ',]]]// Q1: Complete array flat function
function flat(arr) {
  // code
  return arr
}

arr = flat(arr);
console.log(arr);

Q2: Count all the values in arR: '1-7' => 1 * 7 = 7, return an array of numbers
function calc(arr) {
  // code
  return arr;
}

arr = calc(arr);
console.log(arr);

// Q3: Sort and deduplicate this array
function sortAndReduce(arr) {
  // code
  return arr;
}

arr = sortAndReduce(arr);
console.log(arr);

Copy the code

Q1: Flat arrays

Time to go back

This is a deep array structure, and that should be the whole point of the problem. It looks like it’s going to recurse. No! There is a better way to do this: 🤔 use the array.prototype. flat function for ES 2019. And was voted down by the interviewer. In between scribbling and thinking, the interviewer ended the question by asking me about my train of thought.

Plan 1: Recursion

If you’re not familiar with recursion, take a look at my reading notes: Chapter 3 Recursion.

The heart of recursion lies in two steps: finding the baseline condition and the recursion condition.

function flat(arr) {
  const result = []; // Use closures to cache our results
  function _flat(arr) {
    arr.forEach(element= > {
      if(Array.isArray(element)) { // recursive condition
        _flat(element);
      } else { // Base conditions
        result.push(element); // Push the values that match the results into our results array
      }
    })
  }
  _flat(arr);
  arr = result;
  return arr;
}

// A more concise version
Thank you / / @ zwlafk
const flat = arr= >[].concat(... arr.map(v= > Array.isArray(v) ? flat(v) : v));
Copy the code

Option 2: iterative – breadth-first search

I borrowed this idea from the chapter on breadth-first search algorithms in Graphic Algorithms.

  1. Create an array to hold the results
  2. Create a queue
  3. Initialize the
  4. Use the while loop to iterate through each item in the list
  5. Push the first item out of the queue
    • If it’s an array, push the children into the queue one by one
    • If it is a string, push the subitem into the result
  6. When the list length is 0, the traversal is complete

But breadth-first search results are not guaranteed to be sequential.

  • Reference Book: Graphic Algorithms
  • Book Notes: Chapter 6 breadth-first Search
function flat(arr) {
  const result = []; // Save the result
  const list = []; / / the queue
  function _forEach(arr) {
    arr.forEach(el= > {
      if(Array.isArray(el)) list.push(el); // item if it is an array, push the subitems into the queue
      else result.push(el); // if item is a string, push the subitem into the result
    });
  }
  _forEach(arr); / / initialization
  while(list.length > 0) { // When the list length is 0, the traversal is complete
    const item = list.shift();
    _forEach(item);
  }
  arr = result;
  return arr;
}
Copy the code

TODO:

  • The above two methods are just my humble opinion and I hope to see better and better algorithms in the comments section

Plan 3: Opportunistic ToStrings

Thank you @iwanabethatguy for your advice.

// You need to make sure your data does not contain strings ',' oh
function flat(arr) {
  arr = arr.toString().split(', ')
  return arr;
}

// or 
// Same thing
function flat(arr) {
  arr = arr.join(', ').split(', ')
  return arr;
}
Copy the code

Scheme 4: iteration-depth-first search

Thank you @iwanabethatguy for your advice.

The principle is similar to breadth-first search, which iterates through arrays by simulating stack behavior. The advantage is that orderly output is guaranteed.

function flat(arr) {
  let result = [];
  let stack = []; // Simulate the stack behavior

  function forEachRight(arr) {
    for (let i = arr.length - 1; i >= 0; i--) { // First in, last out
      const item = arr[i];
      if(Array.isArray(item)) stack.push(item);
      elseresult.push(item); }}if (arr.length > 0) forEachRight(arr);
  while (stack.length > 0) { // When the stack is empty, the traversal is complete
    let current = s.pop();
    if(current.length > 0) {
       forEachRight(current); // Thanks for the advice from @drowned friend}}return ret;
}
Copy the code

Q2: Array calculation ‘1-7’ => 1 * 7 = 7

This question is not difficult, is to examine the use of some common methods, directly on the code.

function calc(arr) {
  // eval is not recommended
  arr = arr.map(el= > eval(el.replace(The '-'.The '*')));
  return arr;
}

// or

function calc(arr) {
  arr = arr.map(el= > {
    const [n1, n2] = el.split(The '-');
    return +n1 * +n2;
  });
  return arr;
}

Copy the code

Q3: Array sorting and de-weighting

Array de-duplication can be done with ES6’s Set. Portal: ES6 Set data structure, not described here. Array sorting can be done using array.prototype. sort. But obviously, the content of the algorithm can not be directly used by the native method, and the sorting and de-duplication are completed at the same time, the performance is certainly better.

I have previously written a general comparison and implementation of several kinds of sorting methods, selection sort, bucket sort, bubble sort and quicksort introduction, here I directly use quicksort to complete sorting and de-work.

function sortAndReduce(arr) {
  if(arr.length < 2) {
    return arr;
  } else {
    const pivot = arr[0]; / / value
    const lowArr= []; // Put the small one on the left
    const hightArr = []; // Put the big one on the right
    arr.forEach(current= > {
      if(current > pivot) hightArr.push(current);
      else if(current < pivot) lowArr.push(current);
    })
    returnsortAndReduce(lowArr).concat(pivot, sortAndReduce(hightArr)); }}Copy the code

Conclusion:

  • Book comes shallow sleep. Learning to succeed is a long way off. This interview let me know that the reason why I am nervous comes from the lack of solid foundation.
  • Anyway, let’s go swipe Leetcode.