Interview oriented programming: Here’s everything you need to know about handwriting

Basic principles of handwriting

Write a call

Function.prototype.myCall = function (context) {
  if (typeof this! = ="function") {
    throw new Error("Type error");
  }

  const args = [...arguments].slice(1);

  const currentContext = context || window;

  const fn = Symbol(a); currentContext[fn] =this;

  constres = currentContext[fn](... args);Reflect.deleteProperty(currentContext, fn);
  return res;
};
Copy the code

Handwritten apply

Function.prototype.myApply = function (context) {
  if (typeof this! = ="function") {
    throw new Error("Type error");
  }

  const currentContext = context || window;

  const fn = Symbol(a); currentContext[fn] =this;

  let res = null;
  if (arguments[1]) { res = currentContext[fn](... arguments[1]);
  } else {
    res = currentContext[fn]();
  }

  Reflect.deleteProperty(currentContext, fn);

  return res;
};
Copy the code

Write a bind

Function.prototype.myBind = function (context) {
  if (typeof this! = ="function") {
    throw new Error("Type error");
  }

  const self = this;
  const args = [].slice.apply(arguments.1);

  const fBind = function () {
    const currentArgs = [].slice.apply(arguments);

    return self.apply(
      this instanceof fBind ? this : context,
      arg.concat(currentArgs)
    );
  };

  fBind.prototype = Object.create(this.prototype);

  return fBind;
};
Copy the code

Currization function implementation

function curry(fn) {
  if (fn.length <= 1) return fn;
  const generator = (. args) = > {
    if (fn.length === args.length) {
      returnfn(... args); }else {
      return (. args2) = > {
        returngenerator(... args, ... args2); }; }};return generator;
}
Copy the code

Simple version of the anti – shake function

function simpleDebounce(func, wait) {
  let timer = null;
  return function (. args) {
    if (timer) {
      clearTimeout(timer);
    }
    timer = setTimeout(() = > {
      func.apply(this, args);
    }, wait);
  };
}
Copy the code

Simplified version of the throttle function

function simpleThrottle(func, wait) {
  let canRun = true;
  return function () {
    if(! canRun)return; // Return if the flag is not true
    canRun = false; // Modify the flag
    setTimeout(() = > {
      func.apply(this.arguments);
      canRun = true; // When the execution is complete, set the flag to true, indicating that the next execution is ready. If the execution is not completed, the function will return directly
    }, wait);
  };
}
Copy the code

Event delegate implementation

function delegate(element, eventType, selector, fn) {
  element.addEventListener(
    eventType,
    (e) = > {
      let el = e.target;
      while(! el.matches(selector)) {if (element === el) {
          el = null;
          break;
        }
        el = el.parentNode;
      }
      el && fn.call(el, e, el);
    },
    true
  );

  return element;
}
Copy the code

Handwriting implementation instanceof

function myInstanceof(left, right) {
  let prototype = right.prototype;
  left = left._proto_;
  while (true) {
    if (left === null || left === undefined) {
      return false;
    }
    if (prototype === left) {
      return true; } left = left._proto_; }}Copy the code

Simple package JSONP

function jsonp(url, callback, success) {
  let script = document.createElement("script");
  script.src = url;
  script.async = true;
  script.type = "text/javascript";
  window[callback] = function(data) {
    success && success(data);
  };
  document.body.appendChild(script);
}

Copy the code

New Principle of handwriting

function myNew(fn, ... args) {
  if (typeoffn ! = ="function") {
    throw new Error("Type error");
  }
  const obj = Object.create(fn.prototype);

  const res = fn.apply(obj, args);

  return res instanceof Object ? res : obj;
}
Copy the code

Handwritten Object. The create

function create(proto){
  function Fn(){}
  Fn.prototype = proto;
  Fn.prototype.constructor = Fn;

  return new Fn();
}
Copy the code

Simple shallow copy

function shallowClone(obj) {
  function isObject() {
    return typeof o === "object";
  }
  if(! isObject(obj))return obj;
  let target = {};
  Reflect.ownKeys(obj).forEach((key) = > {
    target[key] = obj[key];
  });
}
Copy the code

Simple deep copy

function deepClone(obj) {
  function isObject(o) {
    return typeof o === "object";
  }
  if(! isObject(obj))return obj;

  let isArray = Array.isArray(obj);
  // Compatible array
  let newObj = isArray ? [] : {};
  Reflect.ownKeys(newObj).forEach((key) = > {
    newObj[key] = isObject(obj[key]) ? deepClone(obj[key]) : obj[key];
  });
  return newObj;
}
Copy the code

Implement filter method by hand

const myFilter = function(fn, context) {
  const arr = [].slice.call(this);
  const filterArray = [];
  for (let i = 0; i < arr.length; i++) {
    if(! arr.hasOwnProperty(i))continue;
    fn.call(context, arr[i], i, this) && filterArray.push(arr[i]);
  }
  return filterArray;
};
Copy the code

Implement the map method by hand

const myMap = function(fn, context) {
  const arr = [].slice.call(this);
  const resultArray = [];
  for (let i = 0; i < arr.length; i++) {
    if(! arr.hasOwnProperty(i))continue;
    resultArray.push(fn.call(context, arr[i], i, this));
  }
  return resultArray;
};
Copy the code

Handwriting to Reduce

Array.prototype._reduce = function (callback, initVal) {
  let i = 0;
  let result = initVal;
  if (typeof initVal === "undefined") {
    result = this[0];
    i++;
  }

  for (i; i < this.length; i++) {
    result = callback(result, this[i], i);
  }
  return result;
};

Copy the code

Implement filter through Reduce

const myReduceFilter = function (fn, context) {
  const arr = [].slice.call(this);
  return arr.reduce((total, cur, index) = > {
    return fn.call(context, total, cur, index, this)? [...total, cur] : [...total]; } []); };Copy the code

Flat is achieved through Reduce

const myFlat = function (deep = 1) {
  const arr = [].slice.call(this);
  if (deep === 0) return arr;
  return arr.reduce((total, cur) = > {
    if (Array.isArray(cur)) {
      return [...total, ...myFlat.call(cur, deep - 1)];
    } else {
      return[...total, cur]; }} []); };Copy the code

Flat is achieved through Reduce

const myReduceToMap = function (fn, context) {
  const arr = [].slice.call(this);
  return arr.reduce((total, cur, index) = > {
    return [...total, fn.call(context, total, cur, index, this)]; } []); };Copy the code

A simple implementation of Promise

const PENDING = "pending";
const RESOLVED = "resolved";
const REJECTED = "rejected";

// The promise body is implemented
function MyPromise(fn) {
  const that = this;
  that.state = PENDING;
  that.value = null;
  that.resolvedCallbacks = [];
  that.rejectedCallbacks = [];

  function resolve(value) {
    if (that.state === PENDING) {
      that.state = RESOLVED;
      that.value = value;
      that.resolvedCallbacks.map((cb) = >{ cb(value); }); }}function reject(value) {
    if (that.state === PENDING) {
      that.state = REJECTED;
      that.value = value;
      that.rejectedCallbacks.map((cb) = >{ cb(value); }); }}try {
    fn(resolve, reject);
  } catch(e) { reject(e); }}// Then implementation
MyPromise.prototype.then = function (onFulfilled, onRejected) {
  const that = this;
  onFulfilled = typeof onFulfilled === "function" ? onFulfilled : (v) = > v;
  onRejected =
    typeof onRejected === "function"
      ? onRejected
      : (r) = > {
          throw r;
        };
  if (that.state === PENDING) {
    that.resolvedCallbacks.push(onFulfilled);
    that.rejectedCallbacks.push(onRejected);
  }
  if (that.state === RESOLVED) {
    onFulfilled(that.value);
  }
  if(that.state === REJECTED) { onRejected(that.value); }};Copy the code

Handwriting advanced implementation

Implement a cache function

const memorize = function (fn) {
  const catchs = {};

  return function (. args) {
    const _args = JSON.stringify(args);
    return catchs[_args] || (catchs[_args] = fn.apply(null, args));
  };
};

const add = function (a, b) {
  return a + b;
};

const adder = memorize(add);

adder(2.6);
// get the cache directly
adder(2.6);
Copy the code

Design to implement a function that limits the maximum number of runs

function maxTask(tasks, n) {
  return new Promise((resolve, reject) = > {
    let start = 0;
    let index = 0;
    let finish = 0;
    const res = [];

    function processValue(index, value) {
      start -= 1;
      finish += 1;
      res[index] = value;
      runTask();
    }

    function runTask() {
      if (finish === n) {
        resolve(res);
        return;
      }

      while (start < n && index < tasks.length) {
        start += 1;
        let cur = index;
        Promise.resolve(tasks[cur]())
          .then((value) = > {
            processValue(cur, value);
          })
          .catch((err) = > {
            processValue(cur, err);
          });
      }
    }

    runTask();
  });
}
Copy the code

Implement lodash’s [get] method

// var object = { 'a': [{ 'b': { 'c': 3 } }] };

// _.get(object, 'a[0].b.c');
/ / = > 3

function myGet(targetObj, path, defaultValue) {
  if(! path ||typeofpath ! = ="string") {
    return defaultValue;
  }
  const transPath = path.replace(/\[(\d+)\]/g."$1").split(".");
  let result = targetObj;

  for (const p of transPath) {
    result = Object(result)[p];
    if (result === undefined) {
      returndefaultValue; }}return result;
}
Copy the code

Implement a restart function, (the request is restarted if the request fails, and an error is thrown when the maximum number of times is reached)

// Simulate an API request
function getMyData() {
  return new Promise((resolve, reject) = > {
    setTimeout(() = > {
      const num = Math.ceil(Math.random() * 20);
      if (num <= 5) {
        console.log("Meet the conditions", num);
        resolve(num);
      }
      reject(`${num}Does not meet the condition ');
    }, 2000);
  });
}

// Restart the function
function myGetData(fn, times = 5, delay = 1000) {
  return new Promise((resolve, reject) = > {
    function attempt() {
      fn().then(resolve).catch((err) = > {
        console.log(` and${times}A restart opportunity ');
        if (times === 0) {
          reject(err);
        } else {
          times -= 1;
          setTimeout(attempt, delay); }}); } attempt(); }); }Copy the code

Implements the summation function with the given prefix

// Enter: getUniqId('my')
// Output: my_1
// Enter: getUniqId('my')
// Output: my_2
// Input: getUniqId('he')
// Output: he_1
const getUniqId = (() = > {
  const keyMap = new Map(a);return function (currentStr) {
    if (typeofcurrentStr ! = ="string") {
      return "";
    }
    if (keyMap.get(currentStr)) {
      const value = keyMap.get(currentStr);
      keyMap.set(currentStr, value + 1);
      return `${currentStr}_${value + 1}`;
    } else {
      keyMap.set(currentStr, 1);
      return `${currentStr}_1 `;
    }
  };
})();
Copy the code

Implement a function that checks whether an object is a circular reference

const isCyclic = (obj) = > {
  try {
    JSON.stringify(obj);
    return false;
  } catch {
    return true; }};Copy the code

Implement an array that takes a given array and prints from large to small

const nums = [7.8.3.5.1.2.4.3.1];
/ / sorting
const sortNums = nums.sort((a, b) = > a - b);
/ / to heavy
const targetNums = [...new Set(sortNums)];
// Convert the string
const targetStr = targetNums.join("");
// Convert methods
const dealNumber = (money) = > {
  if(! money) {return "";
  }
  const temp = money.match({1, 3})/(\ d/g);
  return temp.join(",").split("").reverse().join("");
};
Copy the code

Implement a function that loads img in sequence

// const imgs = ['url1', 'url2', 'url3', ...] ;
// Load images in the image array order.

// load the img asynchronous function
const loadImg = (url) = > {
  return new Promise((resolve, reject) = > {
    let img = new Image();
    img.src = url;
    img.onload = () = > {
      resolve(img);
    };
    img.onerror = () = > {
      reject("error");
    };
  });
};

// Image processing function
const dealWithImgs = (imgs) = > {
  const imgQueue = [];
  for (let i = 0; i < imgs.length; i += 1) {
    imgQueue.push(loadImg(imgs[i]));
  }
  Promise.all(imgQueue)
    .then((item) = > {})
    .catch((err) = > {});
};

dealWithImgs(imgs);
Copy the code

Subscription-publish pattern implementation

// Subscription-publish mode
class EvevtEmitter {
  constructor() {
    // map, which stores the relationship between events and callbacks
    this.handlers = {};
  }

  // Install event listener, accept event name and callback function as parameters
  on(eventName, cb) {
    if (!this.handlers[eventName]) {
      // Initialize a listener queue
      this.handlers[eventName] = [];
    }
    this.handlers[eventName].push(cb);
  }

  // emit is used to fire the target event, taking the event name and the arguments of the listener function as arguments
  emit(eventName, ... args) {
    if (this.handlers[eventName]) {
      this.handlers[eventName].forEach((cb) = > {
        cb(...args);
      });
    }
  }

  // Remove a callback function from an event callback queue
  off(eventName, cb) {
    const callbacks = this.handlers[eventName];
    const index = callbacks.indexOf(cb);
    if(index ! = = -1) {
      this.handlers[eventName].splice(index, 1); }}// Register a single listener for the event
  once(eventName, cb) {
    const wrapper = (. args) = > {
      cb.apply(null, args);
      this.off(eventName, wrapper);
    };
    this.on(eventName, wrapper); }}Copy the code

High frequency algorithm problem

Realize the LRU

// The standard implementation is usually linked list, but for the front end, can use map write, also no problem

class LRU {
  constructor(max) {
    this.max = max;
    this.map = new Map(a); }get(key) {
    const value = this.map.get(key);
    if (value === undefined) {
      return -1;
    }
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  set(key, value) {
    if (this.map.get(key)) {
      this.map.delete(key);
    }
    this.map.set(key, value);
    const keys = this.map.keys();
    while (this.map.size > this.max) {
      this.map.delete(keys.next().value); }}}Copy the code

Frog jumps step

/** * A frog can jump up one step or two steps at a time. Find out how many ways the frog can jump up n steps. * The answer needs to be mod 1E9 +7 (1000000007). If the initial calculation result is 1000000008, please return 1. * /

const numWays = (n) = > {
  if (n === 1) {
    return 1;
  }
  const dp = [];
  dp[0] = 1;
  dp[1] = 1;

  const max = 1e9 + 7;
  for (let i = 2; i <= n; i += 1) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % max;
  }

  return dp[n];
};
Copy the code

Binary matrix search

/* Write a valid algorithm to search a matrix with the following characteristics: 1) Each row of the matrix is sorted, increasing from left to right. 2) The first digit of each line is greater than the last digit of the previous line e.g. [[2, 4, 8, 9], [10, 13, 15, 21], [23, 31, 33, 51]] Implements a function that searches the array. Enter: 4, returns: true, enter: 3, returns: false */

// matrix search function
const searchFunc = (matrix, target) = > {
  if (matrix.length === 0 || matrix[0].length === 0 || matrix[0] [0] > target) {
    return false;
  }
  let i = matrix.length - 1;
  let j = 0;
  while (i >= 0 && j < matrix[0].length) {
    if (matrix[i][j] === target) {
      return true;
    }
    if (matrix[i][j] < target) {
      j += 1;
    } else {
      i -= 1; }}return false;
};
Copy the code

Reverse a linked list

const reverseList = (head) = > {
  // The precursor node
  let pre = null;
  // The current node
  let cur = head;

  while (cur.next) {
    // Record the next node first
    let next = cur.next;
    // Reverse the current node
    cur.next = pre;
    // Pre node forward
    pre = cur;
    // cur node forward
    cur = next;
  }
  return pre;
};
Copy the code

Three Numbers

const threeSum = function (sendSums, target = 0) {
  // Result array
  const res = [];
  if (Array.isArray(sendSums)) {
    const nums = sendSums.sort((a, b) = > {
      return a - b;
    });
    // The pointer will point to the last two numbers and calculate
    for (let i = 0; i < nums.length - 2; i += 1) {
      / / pointer to the left
      let left = i + 1;
      / / right pointer
      let right = nums.length - 1;
      // If the same number is encountered, skip it
      if (i > 0 && nums[i] === nums[i - 1]) {
        continue;
      }

      // The left pointer must be smaller than the right pointer to be three numbers
      while (left < right) {
        // Add less than the target value, the left pointer moves
        if (nums[i] + nums[left] + nums[right] < target) {
          left += 1;
          // If the left pointer is the same, move forward to avoid duplicate array elements
          while (left < right && nums[left] === nums[left - 1]) {
            left += 1; }}else if (nums[i] + nums[left] + nums[right] > target) {
          right -= 1;
          while (left < right && nums[right] === nums[right + 1]) {
            right -= 1; }}else {
          res.push([nums[i], nums[left], nums[right]]);

          // The left and right Pointers move forward simultaneously
          left += 1;
          right -= 1;

          while (left < right && nums[left] === nums[left - 1]) {
            left += 1;
          }
          while (left < right && nums[right] === nums[right + 1]) {
            right -= 1;
          }
        }
      }
    }
  }
  return res;
};
Copy the code

Simulation stack algorithm implementation

/** Simulates the stack operation push(x) -- pushes the element x onto the stack. Pop () -- Removes the top element of the stack. Top () -- Gets the top element on the stack. GetMin () -- Retrieves the smallest element in the stack. * /

class Mystack {
  constructor() {
    // Main function stack
    this.stack = [];
    // Secondary stack, used to record the smallest element in the stack
    this.minStack = []
  }

  push(x) {
    this.stack.push(x);
    if (!this.minStack.length || this.minStack[this.minStack.length - 1] >= x) {
      this.minStack.push(x); }}pop() {
    const popValue = this.stack.pop();
    if (popValue === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop(); }}top() {
    return this.stack[this.stack.length - 1];
  }

  getMin() {
    return this.minStack[this.minStack.length - 1]; }}Copy the code

Array to tree structure

const listToTree = (arr) = > {
  const map = {};
  let node;
  const tree = [];
  for (let i = 0; i < arr.length; i += 1) {
    map[arr[i].id] = arr[i];
    arr[i].children = [];
  }

  for (let i = 0; i < arr.length; i += 1) {
    node = arr[i];
    if(node.pid ! = ="0") {
      map[node.pid].children.push(node);
    } else{ tree.push(node); }}return tree;
};
Copy the code

Tree flattens the array

const treeToList = (tree) = > {
  let queen = [].concat(tree);
  const out = [];
  while (queen.length) {
    let first = queen.shift();
    if (first.children) {
      queen = queen.concat(first.children);
      Reflect.deleteProperty(first, "children");
    }
    out.push(first);
  }
  return out;
};
Copy the code