debounce & throttle

Throttle

Throttle is used to limit how often a function can be called, though throttle is simpler to implement

Using a flag to record the state: within or exceed the time limit

Use case: during scrolling, resizing

1
2
3
4
5
6
7
8
9
10
11
12
13

const throttle = (fn, limit) => {
        let flag = false; //init the flag
        return (...arg) => {
          if (!flag) { //if the flag is false, exceeds the limit
            fn(arg); //run the passed in function
            flag = true; //turn the flog to ture, still inside the limit
           setTimeout(() => { //use a timer to turn flag to false after the limit
            flag = false;
          }, limit);
          }
  			//if the flag was true, do nothing.
        };
      };

Debounce

A debounced function is called only once in a given period, delay milliseconds after its last invocation (the timer is reset on every call).

use case: auto search

1
2
3
4
5
6
7
8
9

const debounce = (fn, limit) => {
   let id; 
   return (...arg) => {
     if (id) clearTimeout(id); //every time the function was called, test if the the timer is running, if so, restart the timer
     id = setTimeout(() => { 
       fn(arg);
     }, limit);
   };
 };

type conversion

Type Conversion

Primitive

JavaScript is a loosely typed or a dynamic language. Variables in JavaScript are not directly associated with any particular value type, and any variable can be assigned (and re-assigned) values of all types:

There are 6 primitive data types: string, number, bigint, boolean, undefined, and symbol. There also is null, which is seemingly primitive, but indeed is a special case for every Object: and any structured type is derived from null by the Prototype Chain.

Except for null and undefined, all primitive values have object equivalents that wrap around the primitive values:

String/ Number /BigInt /Boolean / Symbol
The wrapper’s valueOf() method returns the primitive value.

Explicit coercion


Boolean()

Primitive to Boolean

1
2
3
4
5
6
7
8

console.log(Boolean()) // false
console.log(Boolean(false)) // false
console.log(Boolean(undefined)) // false
console.log(Boolean(null)) // false
console.log(Boolean(+0)) // false
console.log(Boolean(-0)) // false
console.log(Boolean(NaN)) // false
console.log(Boolean("")) // false

Number()

When Number is called as a function rather than as a constructor, it performs a type conversion.

Returns a Number value (not a Number object) computed by ToNumber(value) if value was supplied, else returns +0.

toNumber()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

console.log(Number()) // +0

console.log(Number(undefined)) // NaN
console.log(Number(null)) // +0

console.log(Number(false)) // +0
console.log(Number(true)) // 1
console.log(Number("123")) // 123
console.log(Number("-123")) // -123
console.log(Number("1.2")) // 1.2
console.log(Number("000123")) // 123
console.log(Number("-000123")) // -123
console.log(Number("0x11")) // 17
console.log(Number("")) // 0
console.log(Number(" ")) // 0
console.log(Number("123 123")) // NaN
console.log(Number("foo")) // NaN
console.log(Number("100a")) // NaN

1
2
3
4
5
6

console.log(parseInt("3 abc")) // 3
console.log(parseFloat("3.14 abc")) // 3.14
console.log(parseInt("-12.34")) // -12
console.log(parseInt("0xFF")) // 255 hexadecimal
console.log(parseFloat(".1")) // 0.1
console.log(parseInt("0.1")) // 0

String()

When String is called as a function rather than as a constructor, it performs a type conversion.

Returns a String value (not a String object) computed by ToString(value). If value is not supplied, the empty String “” is returned.

toString()

1
2
3
4
5
6
7
8
9
10
11
12
13
14

console.log(String()) // 'empty string'

console.log(String(undefined)) // undefined
console.log(String(null)) // null

console.log(String(false)) // false
console.log(String(true)) // true

console.log(String(0)) // 0
console.log(String(-0)) // 0
console.log(String(NaN)) // NaN
console.log(String(Infinity)) // Infinity
console.log(String(-Infinity)) // -Infinity
console.log(String(1)) // 1

Primitive type to reference type

String()、Number() and Boolean() constructor with new keyword

1
2
3
4

var a = 1;
console.log(typeof a); // number
var b = new Number(a);
console.log(typeof b); // object

primitive to boolean

1

console.log(Boolean(new Boolean(false))) // true

Object to string and number

first converts to primitive using toPrimitive, then convert to sting/number using ToString/ToNumber

Object.prototype
{
toString: ƒ toString()
valueOf: ƒ valueOf()
….
}

let a ={}
a.valueOf= function(){ return ‘run this method’}

1
2
3

let a ={a:'1'}
a.valueOf() //{a: "1"}
a.toString() //"[object Object]"

1
2
3
4
5
6
7

console.log(({}).toString()) // [object Object]
console.log([].toString()) // ""
console.log([0].toString()) // 0
console.log([1, 2, 3].toString()) // 1,2,3
console.log((function(){var a = 1;}).toString()) // function (){var a = 1;}
console.log((/\d+/g).toString()) // /\d+/g
console.log((new Date(2010, 0, 1)).toString()) // Fri Jan 01 2010 00:00:00 GMT+0800 (CST)

Implicit coercion

(👆The tricky part)

Abstract Equality Comparison (==)

To primitive:

ToPrimitive(A) attempts to convert its object argument to a primitive value, by attempting to invoke varying sequences of A.toString and A.valueOf methods on A.

• the piority of comparison type is Number > String >Boolean>Obj

• if one side is number, then convert to number; else if one side is boolean, convert to number

• true=='2'//false
  true->Number ->1
  '2'->Number ->2
  false=='a'//false
  true='a'//false
  'a'->Number->NaN
  <!--8-->
  

1
2
3
4
5

[] == ![] //true
left:ToPrimitive(![]) >> ToPrimitive(!ToBoolean([])) >>
ToPrimitive(!true) >> ToPrimitive(false) >> 0
ToPrimitive([]) >> ""
"" == 0 >> ToNumber("") == 0 >> 0 == 0 >> return true

‘+’ operartor

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var a = 21;
var b = 4;
var c = '21';
var d = '4';
a + b; // 25
c + d; // "214"

var arr0 = [1, 2];
var arr1 = [3, 4];
arr0 + arr1; // '1，23，4'

console.log(+['1']); // 1
console.log(+['1', '2', '3']); // NaN
console.log(+{}); // NaN

|| && !

The value produced by a && or || operator is not necessarily of type Boolean. The value produced will always be the value of one of the two operand expressions.

1
2
3
4
5
6
7
8

let A = '';
let B = 1
A ||B //1
A && B //''
!B //flase
!A //true
A->Boolean->false ->OR run A 
				  ->AND run B

Ref:

ES5

Article

Binary tree part 1

Since the root and node share similar structure, it’s natural to use recursion to solve relative problem.

Also, iteration can also be applied. The key would be which kind of data structure to store the data of a tree. Normally, a queue(FIFO) or a stack(FILO) depeding on the traversal order.

Binary Tree in javascript：

1
2
3
4
5
6
7
8

function BinaryTree() {
  let Node = function (val) {
    this.val = val;
    this.left = null;
    this.right = null;
  };
  let root = null;
}

Or using an array to store the elements of the tree where the root node is stored at index 1 not 0.

For complete binary tree, if the index of an element (eg, D, i = 4). Its left child node will be stored in 2*i (H,at 8), and its right childe node will be stored in2 * i-1, its root node will be stored at Math.floor( i/2)

Traversal of tree

Preorder (root -> left node ->right node

Recursion:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var preorderTraversal = function (root) {
  const res = [];
  function traversal(root) {
    if (root !== null) {
      //exit point
      //the sequences matters!
      res.push(root.val); // access the root
      traversal(root.left); // left
      traversal(root.right); // right
    }
  }
  traversal(root);
  return res;
};

*Iteration: *

version 1:

1
2
3
4
5
6
7
8
9
10
11
12

const preorderTraversal = (root) => {
  const res = []; //store the values of nodes
  const stack = [root]; //FILO
  if (!root) return res; //exit point
  while (stack.length > 0) {
    let cur = stack.pop(); //pop out the current element
    res.push(cur.val); //push to the result array
    cur.right && stack.push(cur.right); //if has right node, first push it
    cur.left && stack.push(cur.left); //if has left node, then push it
  }
  return res;
};

version 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var preorderTraversal = function (root) {
  var result = [];
  var stack = [];
  var p = root;
  while (stack.length != 0 || p != null) {
    if (p != null) {
      stack.push(p);
      result.push(p.val); // Add before going to children
      p = p.left;
    } else {
      var node = stack.pop();
      p = node.right;
    }
  }
  return result;
};

Inorder left node -> root -> right node

• 

  Recursion:

1
2
3
4
5
6
7
8
9
10
11
12
13

var inorderTraversal = function (root) {
  const res = [];
  function traversal(root) {
    if (root !== null) {
      //exit point
      traversal(root.left); //left node first
      res.push(root.val); //store the root
      traversal(root.right); //right node last
    }
  }
  traversal(root);
  return res;
};

A visual way to understand inheritance & prototype

A visual way to understand inheritance & prototype

In JavaScript, there is actually no concept of real Class (in es6, class is purely syntax sugar 🍬)

The inheritance was made by inheriting along the prototype chain. And it’s a real OOP language since you can create a new object directly from an object bypassing the class.

The keyword new <Constructor> and Object.create(<Prototype object>) method can both manuiplate the prototype chain (__proto__):

the orange line refers to the prototype chain.

1
2
3
4
5
6
7
8

function A(argu){
	this.con = argu;
}
A.prototype.proto = ()=>{console.log(this)}
let a1 = Object.create(A.prototype)
let a2 = new A('a2')
a2.con // 'a2'
a1.con // undefined

the new keyword and the .create method both combine the returned object to the prototype of the constructor function. However, the new object a2 will inheritage the this.con property constructor (a function) while the a1 will not.

Both a1 and a2 have access to the .proto method by searching along the prototype chain.

A common mistakes when I first bump into the idea of inheritance I have made was accidentally create an object from a constructor function rather than the prototype of the constructor.

As the figure shown, the incorrectly created object a1now is an instance of function. And have no access to method of A.prototype.proto:

1
2
3

a1 instanceof Function //true
a1.proto() //a1.proto is not a function
a1.prototype.proto() //this works

The prototype object can be only found on a function. An object other than function have no pointer referencing to prototype.

Leetcode Linked List

Linked List

Comparing with Array, linked list dosen’t support accessing by index. So for searching a certain element, the complexcity is O(n).

The linked list doesn’t took up continuous space in memory, so for inserting/deleting element, the complexcity is O(1)

Using two pointer can help to reduce the complexity.

For loop in the list, using fast and slow pointers.

206. Reverse Linked List

Reverse a singly linked list.

Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

• iterative

  1 2 3 4 5 6 7 8 9 10 11 12 13

  var reverseList = function (head) { if (!head || !head.next) return head; let pre = null, cur = head; while (cur) { let next = cur.next; cur.next = pre; pre = cur; cur = next; } head = pre; return head; };

• recursive

  1 2 3 4 5 6 7 8

  var reverseList = function (head) { if (!head || !head.next) return head; let next = head.next; let reversedHead = reverseList(next); head.next = null; next.next = head; return reversedHead; };

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

• iterative (two pointer)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var mergeTwoLists = function (l1, l2) {
  let p = new ListNode(-1);//dummy head
  let preHead = p;  //store the dummy head!
  while (l1 && l2) {
    if (l1.val >= l2.val) {
      p.next = l2;
      l2 = l2.next;
    } else {
      p.next = l1;
      l1 = l1.next;
    }
      p=p.next
  }
  if (l1) { //add the remaining list
    p.next = l1;
    l1 = l1.next;
  }
  if (l2) {
    p.next = l2;
    l2 = l2.next;
  }
  return preHead.next; //dummy head's next is the first head
};

• Recursive

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  function mergeTwoLists(l1, l2) { //always compare two node if(l1 === null) { //if it reaches the end return the other node return l2 } if(l2 === null) { return l1 } if(l1.val <= l2.val) { l1.next = mergeTwoLists(l1.next, l2) //let the next head point to the next result //pass the new head l1.next return l1 //return the smaller one } else { l2.next = mergeTwoLists(l2.next, l1) //pass the new head l2.next return l2 } }

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

Input: intersectVal = 8,
listA = [4,1,8,4,5],
listB = [5,0,1,8,4,5],
skipA = 2, skipB = 3

Output: Reference of the node with value = 8
Input Explanation: The intersected node’s value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

Output: Reference of the node with value = 2
Input Explanation: The intersected node’s value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

1
2
3
4
5
6
7
8
9
10

var getIntersectionNode = function (headA, headB) {
  let pA = headA,
    pB = headB;
  while (pA || pB) {
    if (pA === pB) return pA;
    pA === null ? (pA = headB) : (pA = pA.next);
    pB === null ? (pB = headA) : (pB = pB.next);
  }
  return null;
};

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Use slow & fast pointers:

Space complexity :O(1) Time complexcity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12

var hasCycle = function(head) {
    if(!head || !head.next) {
        return false
    }
    let fast = head.next.next, slow = head
    while(fast !== slow) {
        if(!fast || !fast.next) return false
        fast = fast.next.next
        slow = slow.next
    }
    return true
};

Using the list to store a marker/flag to indicate if this node was traversed.

Space&Time complexcity: O(N)

1
2
3
4
5
6
7
8

var hasCycle = function(head) {
    while(head) {
        if(head.flag) return true //this list was marked
        head.flag = true
        head = head.next
    }
    return false
};

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up: Could you do it in O(n) time and O(1) space?

Two pointer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

var isPalindrome = function (head) {
  if (!head || !head.next) return false;
  if (!head.next.next) {
    if (head.val === head.next.val) return true;
    return false;
  }
  let slow = head,
    fast = head.next.next;
  while (fast.next) {
    slow = slow.next;
    fast = fast.next;
  }
  let reversed = slow.next; //find the mid point 
  pre = null; //reverse the last half
  while (reversed) {
    let next = reversed.next;
    reversed.next = pre;
    pre = reversed;
    reversed = next;
  }
  reversed = pre; //the reversed head
  while (reversed && head) { //compare the two halfs
    if (reversed.val != head.val) return false;
    reversed = reversed.next;
    head = head.next;
  }
  return true

Using stack:

1
2
3
4
5
6
7
8
9
10
11

var isPalindrome = function (head) {
  let arr = [];
  while (head) {
    arr.push(head.val);
    head = head.next;
  }
  while (arr.length > 1) {
    if (arr.pop() != arr.shift()) return false;
  }
  return true;
};

148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Merge sorting:

It’s easy to just apply the Divided Conqure algorithm template 😁