CMK

Reverse all words in a string

Posted on 2018-12-10 | In Algorithm | Comments:

I. Problem

Given a string consisted of several words, reverse all words in this string.

Note:

you need to trim starting & trailing white space
reduce multiple spaces to only on space between each word

1
2
3

"   This is a    test   string  " 
  ==> 
"string test a is This"

II. Solution

// Test
let str = "   This is a test   string"
let res = reverseString(str)
console.log(res)	   		// "string test a is This"

str = "This    "
res = reverseString(str) 
console.log(res)	   		// "This"

str = "This is  "
res = reverseString(str) 
console.log(res)	   		// "is This"

str = "This"
res = reverseString(str) 
console.log(res)	   		// "This"

str = ""
res = reverseString(str) 
console.log(res)	   		// ""

str = "  "
res = reverseString(str) 
console.log(res)	   		// ""


function reverseString  (str){
    let arr = str.trim().split(/\s+/)
    let n = arr.length
    
    reverse(arr, 0, n-1)
    let start = 0
    let end = 0
    for( let i = 1; i < n; i++ ){
        let prevChar = arr[i-1]
        let currChar = arr[i]
        if( prevChar !== ' ' && currChar === ' ' ){
            end = i-1
            reverse(arr, start, end)
        }else if( prevChar === ' ' && currChar !== ' ' ){
            start = i
        }else{
            continue
        }
    }
    if(start!==0) reverse(arr, start, n-1)
    return arr.join(' ')
}

function reverse (arr, left, right){
    while( left < right ){
        [arr[left], arr[right]] = [arr[right], arr[left]]
        left++
        right--
    }
}

III. Complexity

Time: O(N)
Space: O(N)

How to Check Data Types in JS?

Posted on 2018-12-09 | In Full stack | Comments:

I. Check `undeclared`, `undefined` or `null`

undeclared check: try-catch-finally

try{
  var;   	// must use it here (in any way)
}
catch(e) {
  if(e.name === 'ReferenceError') {
    console.log('var is undeclared')
  }
}

undefined check: typeof var

var undefinedVar

if (typeof undefinedVar === 'undefined') {
   console.log('var is undefined')
}

null check: if(var===null)

var nullVar = null

if (nullVar === null) {
   console.log('var is null')
}

II. String

Three ways to generate String
- String: let var = '1'
- String: let var = String(1)
- [object String]: let var = new String(1)

How to check - [ primitive string & String object ]

1
2
3

// primitive string
// String object
if (typeof var === 'string' || var instanceof String)

III. Number

Check a Number

// primitive string
// String object
// Must not `NaN`
if ( typeof var === 'number' || value instanceof var ) && isFinite(var) )

Check NaN

// 1. return true for all non-number
isNaN(var)

// 2. only return true for exact 'NaN'
Number.isNaN(var)

IV. Array

1	Array.isArray(var);

V. Function

// Returns if a value is a function
function isFunction (var) {
	return typeof var === 'function';
}

VI. Boolean

// Returns if a value is a boolean
function isBoolean (var) {
	return typeof var === 'boolean';
}

Trie Tree Implementation using JS

Posted on 2018-12-09 | In Algorithm | Comments:

I. What is Trie

Trie is an efficient information reTrieval data structure.

search complexities can be brought to optimal limit (key length).
If we store keys in BST, a well balanced BST will need time proportional to O(M*log N), where M is maximum string length, and N is number of keys in tree
Using Trie, we can search the key in O(M) time.

II. Use case

Prefix matching
Check if a word exists in a dictionary
Word frequency in dictionary
Sort Words in dictionary

III. Implementation

/* 			
				*
			 /  |  \
            a   c   o
          / |   |   |
         c  t   a   f
		/       | \
       e		t  b

    For a word of length K, we need (K+1) nodes to store
	- `add`: [1] *.children.a  
			 [2] a.children.c 
			 [3] c.children.d  
			 [4] e.children.isEnd = true
*/

class TrieNode{
    constructor(){
        this.isEnd = false
        this.freq = 0
        this.children = {}
    }
}

class Trie{
    constructor(){
        this.root = new TrieNode()
    }
    
    insert(word){
        if( word.length === 0 ) return 	// forbid empty string
        let letter, curNode = this.root
        for( let i = 0; i < word.length; i++ ){
            letter = word[i]
            if( !curNode.children.hasOwnProperty(letter) ){
                curNode.children[letter] = new TrieNode()
            }
            curNode = curNode.children[letter]
        }
        curNode.isEnd = true
        curNode.freq = curNode.freq + 1
    }
    
    getNodeForPrefix(str){
        let letter, curNode = this.root
        for( let i = 0; i < str.length; i++ ){
            letter = str[i]
            if( !curNode.children.hasOwnProperty(letter) ) 
                return null
            curNode = curNode.children[letter]
        }
        return curNode
    }
    
    isWord(word){
        if( this.getNodeForPrefix(word) === null ) return false
        return this.getNodeForPrefix(word).isEnd
    }
    
    getWordFreq(word){
        if( this.getNodeForPrefix(word) === null ) return false
        return this.getNodeForPrefix(word).freq
    }
}


/* -------------------- Testing --------------------*/

let ace = "ace"
let at = "at"
let cat = "cat"
let cab = "cab"
let of = "of"

let t = new Trie()
t.insert(ace)
console.log(t.isWord(ace))	  // true

t.insert(ace)	
console.log(t.isWord(ace))     // true
console.log(t.getWordFreq(ace))// 2

t.insert(at)	
console.log(t.isWord(at))      // true
console.log(t.getWordFreq(at)) // 1

t.insert(cat)
t.insert(cat)	
console.log(t.isWord(cat))     // true
console.log(t.getWordFreq(cat))// 2
t.insert(cat)	
console.log(t.getWordFreq(cat))// 3

t.insert(cab)	
console.log(t.isWord(cab))     // true
console.log(t.getWordFreq(cab))// 1

t.insert(of)	
console.log(t.isWord(of))     // true
console.log(t.getWordFreq(of))// 1

// check the internal representation of the Trie
console.log(t.root)

JS common interview problems

Posted on 2018-12-05 | In Full stack | Comments:

Exclude items array according excludes array

Implement a function to exclude matching items from all according to excludes array.

Assume there are m items in all, n items in excludes. Below are 3 versions to solve this problem

Bad version: O(m*n)
Decent version: O(m*n), but can return early in some case
Good version: O(max(m, n))

/*
	all: is the original array
	exclude: is the array specifying properties for items to be excluded
	
	The result should be :
 	[
 		{color: "blue", weight: 35, age: 1}
		{color: "green", weight: 10, age: 32}
        {color: "blue", weight: 89, age: 9}
    ]
*/

let all = [
  { color: "red", weight: 14, age: 10 },
  { color: "blue", weight: 35, age: 1 },
  { color: "green", weight: 4, age: 20 },
  { color: "green", weight: 10, age: 32 },
  { color: "red", weight: 89, age:9 },
  { color: "blue", weight: 89, age:9 },
  { color: "red", weight: 9, age:12},
]

let exclude = [ 
  {k: "color",  v: 'red' },
  {k: "weight",  v: 4 },
]


// 1. BAD Version: O(m*n)
function filterBad(all, exclude){
    exclude.forEach(function(pair){
        all = all.filter( (item)=> item[pair.k] !== pair.v )
    })
    return all;
}
console.log("filter bad result: ")
console.log(filterBad(all, exclude))


// 2. Decent Version: O(m*n), but can return early in some case
function filterDecent(all, exclude){
  return all.filter(function(itemAll){
    return !exclude.some(function(itemEx){
      return itemAll[itemEx.k] === itemEx.v
    })
  })
}
console.log("filter decent result: ")
console.log(filterDecent(all, exclude))

// 3. GOOD Version: O(max(m, n))
function filterGood(all, exclude){
  let map = new Map()
  exclude.forEach(function(item){
    let key = item.k
    let val = item.v
    if(!map.has(key))  
        map.set(key, new Set([val]))
    map.get(key).add(val)
  })

  return all.filter(function(item){
    return !Object.keys(item).some(function(key){
      return map.has(key) ? map.get(key).has(item[key]) : false
    })
  })
}
console.log("filter good result: ")
console.log(filterGood(all, exclude))

Create chaining function

Implement a function can take an executor , onSuccess, onFail callbacks, and call them in the right time. For the following example, please finish the exec function

slow is executor, defined by users
success(onSuccess): onSuccess also defined by users, to receive the successful generated result
fail(onFail) : onFail also defined by users, to receive error message


function exec(executor){
    let promise = {
        result: {
            state: "pending",
            data: null,
            error: null,
        },
        doneConsumers:[],
        failConsumers:[],
        done: function(onDone){
            this.doneConsumers.push(onDone)
            return promise
        },
        fail: function(onFail){
            this.failConsumers.push(onFail)
			return promise
        },
        runExecutor: function(){
            executor(this.resultHooks.bind(this))
        },
        resultHooks: function(error, data){
            this.result.data = data
            this.result.error = error
            this.result.state = data===null ? 'failed' : 'done'
            if(this.result.state === 'done'){
                this.doneConsumers.splice(0).forEach((fn)=>{
                    fn(this.result.data)
                })
            }
            if(this.result.state === 'failed'){
                this.failConsumers.splice(0).forEach((fn)=>{
                    fn(this.result.error)
                })
            }
        }
    }
    promise.runExecutor()
    return promise
}

// TEST
function slow(callback) {
    setTimeout(function(){
        if (Math.random() > 0.5) {
            return callback("Error 417",null)
        }
        callback(null, {id:123})
    },500);
}

let p = exec(slow)
.done(function(data){
    console.log("1st cb for DONE: ");  console.log(data);
}).done(function(data){
    console.log("2nd cb for DONE: ");  console.log(data);
}).done(function(data){
    console.log("3rd cb for DONE: ");  console.log(data);
}).fail(function(err){
    console.log("1st cb for Error: " + err);
}).fail(function(err){
    console.log("2nd cb for Error: " + err);
}).fail(function(err){
    console.log("3rd cb for Error: " + err);
})

console.log(p)

Cache expensive function execution

If a function execution is very expensive, such as encoding function. Cachify the expensive function, so that next time it will instantly return last calculated result, when the same arguments passed in.

Barely Workable Version [ can only cache one function ]

function cachify(fn){
    cache = {}
    return function(){
        let key = [].slice.call(arguments).join(',')
        if(cache[key]) 
            return cache[key]
        else{
            cache[key] = fn.apply(null, arguments)
            return cache[key]
        }
    }
}

// TEST
let timeConsumeFun = function( arg1, arg2 ){ 
    for( let i = 0; i < 100000000; i++ ){
        arg1 += 1;
        arg2 += 1
    } 
    return arg1 + arg2
}

let startTime = Date.now()
let cachedFun = cachify(timeConsumeFun)
let result1 = cachedFun(0, 0)
let timeUsedFirstTime = Date.now() - startTime
console.log("Result of first call should be 200000000: "+ result1)
console.log("Time used for first call: "+ timeUsedFirstTime)

startTime = Date.now()
let result2 = cachedFun(0, 0)
let timeUsedSecondTime = Date.now() - startTime
console.log("Result of seconde call should be 200000000: "+ result2)
console.log("Time used for second call: "+ timeUsedSecondTime)

Good Version I : [Can cache any function with different parameters]

cach all functions and its input/output in only one map

function cachify(fn) {
	try {
		cache // must use this var, in any way
		console.dir(cache)
	} catch (e) {
		if (e.name === "ReferenceError")
			cache = new Map()
	} finally {
		return function () {
			let params = [].slice.call(arguments).join(',')
			if (cache.has(fn)) {
				if (cache.get(fn).has(params))
					return cache.get(fn).get(params)
				else {
					let res = fn.apply(null, arguments)
					cache.get(fn).set(params, res)
					return res
				}
			} else {
				let res = fn.apply(null, arguments)
				cache.set(fn, new Map().set(params, res))
				return res
			}
		}
	}
}

// TEST
let test1 = function (arg1, arg2) {
	for (let i = 0; i < 10000000; i++) {
		arg1 += 1;
		arg2 += 1
	}
	return arg1 + arg2
}

let startTime = Date.now()
let cachedFun1 = cachify(test1)
let result11 = cachedFun1(0, 0)
let timeUsedFirstTime = Date.now() - startTime
console.log("Result of first call should be 20000000: " + result11)
console.log("Time used for first call: " + timeUsedFirstTime)

startTime = Date.now()
let result12 = cachedFun1(0, 0)
let timeUsedSecondTime = Date.now() - startTime
console.log("Result of seconde call should be 20000000: " + result12)
console.log("Time used for second call: " + timeUsedSecondTime)


let test2 = (a, b) => a + b
let cachedFun2 = cachify(test2)
let result21 = cachedFun2(0, 0)
console.log(result21)
let result22 = cachedFun2(1, 1)
console.log(result22)

Good Version II : [Can cache any function with different parameters]

cache each function and its input/output in separate map, using closure

function cachify( fn ){
  // <fn, <input, output> >
  let map = new Map()
  return function(...args){
    if( map.has(fn) ){
      let inOutMap = map.get(fn)
      let argsStr = args.join('/')
      if( inOutMap.has(argsStr) ){
        return inOutMap.get(argsStr)
      }
    }
    
    let res = fn(...args)
    if(!map.has(fn)) {
      let inOutMap = new Map()
      map.set(fn, inOutMap)
    }
    map.get(fn).set(args.join('/'), res)
    console.log(map)
    return res
  }
}

Polyfill `Array.prototype.forEach`

// 1. Example to use forEach()
let arr = [1, 2, 3]
arr.forEach(function(item, index){
    console.log("item: "+ item +", index: "+index)
})

if(typeof Array.prototype.forEach !== "function"){
    Array.prototype.forEach = function(cb){
        for( let i = 0; i < this.length; i++ ){
            cb(this[i], i)
        }
    }
}

Polyfill `Array.prototype.reduce`

// if(Array.prototype.reduce){
    Array.prototype.reduce = function(reducer, initial){
        if (this.length === 0) {
            if( typeof initial === 'undefined' ) 
                throw new Error("No initial value provided")
            else return initial
        }
        
        let accum = typeof initial === 'undefined' ? this[0] : initial
        let startIndex = typeof initial === 'undefined' ? 1 : 0
        for( let i = startIndex; i < this.length; i++ ){
            accum = reducer(accum, this[i])
        }
        return accum
    }
// }
   
    
// TEST    
let reducer = (accum, item)=>{ return accum+item }
let arr = [1, 2, 3]
let res = arr.reduce(reducer, 1) 
console.log(res)				 // 7

arr = []
res = arr.reduce(reducer, 1)
console.log(res)				 // 1

arr = [10]
res = arr.reduce(reducer)
console.log(res)				 // 10

arr = [10]
res = arr.reduce(reducer, 1)
console.log(res)				 // 11


arr = []
res = arr.reduce(reducer)
console.log(res)	   // Uncaught Error: No initial value provided

Closure: a comparison

ONLY variable inside a function can form into closure scope
only variable itself cannot be updated or

// Version 1: `countVal` is a function
function Counter(start) {
    var count = start;
    return {
        increment: function() { count++; },
        countVal: function() { return count; }
    }
}

var foo = Counter(4);
foo.increment();
foo.get(); // 5


// Version 2: `countVal` is a variable
function Counter(start) {
    var count = start;
    return {
        increment: function() { count++; },
        countVal: count
    }
}

var foo = Counter(4);
foo.increment();
foo.get(); // 4

Variable Hoisting

This following code snippet will parsed firstly into next code snippet

bar();
var bar = function() {};
var someValue = 42;

test();
function test(data) {
    if (false) {
        goo = 1;

    } else {
        var goo = 2;
    }
    for(var i = 0; i < 100; i++) {
        var e = data[i];
    }
}

The snippet will convert to the following: 上面代码在运行之前将会被转化。JavaScript 将会把 var 表达式和 function 声明提升到当前作用域的顶部。

// var 表达式被移动到这里
var bar, someValue; // 缺省值是 'undefined'

// 函数声明也会提升
function test(data) {
    var goo, i, e; // 没有块级作用域，这些变量被移动到函数顶部
    if (false) {
        goo = 1;

    } else {
        goo = 2;
    }
    for(i = 0; i < 100; i++) {
        e = data[i];
    }
}

bar(); // 出错：TypeError，因为 bar 依然是 'undefined'
someValue = 42; // 赋值语句不会被提升规则（hoisting）影响
bar = function() {};

test();

Type conversion: string to number

Number("10"): return a primitive number

new Number("10"): return a number object

1
2
3

new Number(10) === 10;     // False, 对象与数字的比较
Number(10) === 10;         // True, 数字与数字的比较
new Number(10) + 0 === 10; // True, 由于隐式的类型转换

LeetCode: word break

Given an array of strings and a target string, determin whether the target string can be formed using strings from the given array.

BAD version : many duplicate check for substrings

function canFormTarget( arr, target ){
    if( target.length === 0 ) return true
    
    for( let i = 0; i < target.length; i++ ){
        let prefix = target.substr(0,i+1)
        let suffix = target.substr(i+1)
        if( arr.includes(prefix) && canFormTarget(arr, suffix) )
            return true
    }
    return false
}

// Test
let arr = ["l", "e", "ee", "et", "co", "d", "e"]
let target = "leetcode"


console.time("test")
let result = canFormTarget(arr, target)
console.timeEnd("test")

GOOD version : use DP with memoization to speed up process

let strChecked = new Map()
function canFormTarget( arr, target ){
    if( target.length === 0 ) return true
    if( strChecked.has(target) ) return strChecked.get(target)
    for( let i = 0; i < target.length; i++ ){
        let prefix = target.substr(0,i+1)
        let suffix = target.substr(i+1)
        if( arr.includes(prefix) && canFormTarget(arr, suffix) ){
            strChecked.set(target, true)
            return true
        }
    }
    strChecked.set(target, false)
    return false
}

// Test
let arr = ["l", "e", "ee", "et", "co", "d", "e"]
let target = "leetcode"

console.time("test")
let result = canFormTarget(arr, target)
console.timeEnd("test")

Curry Function

Implement a curry function addToBase will return another function take an argument to be added on the base.

function addToBase(base){
    return function(addOn){
        return base+addOn
    }
}

// TEST
let addToTen = addToBase(10)
console.log(addToTen(1)) // 11
console.log(addToTen(3)) // 13

let addToHundred = addToBase(100)
console.log(addToHundred(1)) // 101
console.log(addToHundred(3)) // 103

Counting frequency of values in an object

var names = ['Alice', 'Bob', 'Tiff', 'Bruce', 'Alice'];
let res = names.reduce((accum, item, index, names)=>{
  if( accum[item] ){
    accum[item]++
  }else{
    accum[item] = 1
  }
  return accum
},{})
console.log(res)

Group objects by a certain property

let people = [
    {name: "a", age: 10},    
    {name: "b", age: 10},
    {name: "c", age: 12},
    {name: "d", age: 12},
    {name: "e", age: 12},
    {name: "f", age: 14},
    {name: "g", age: 15},
]

/*
	OUTPUT should be: 
 { 
   10: [
         {name: "a", age: 10},    
         {name: "b", age: 10},
       ],
   12: [
          {name: "c", age: 12},
          {name: "d", age: 12},
          {name: "e", age: 12},
       ],
   14: [
   		  {name: "f", age: 14}
       ],
   15: [
     	  {name: "g", age: 15}
       ]
 }
*/

function groupByAge(accum, item, index, arr){
    if(item.age in accum){
         accum[item.age].push(item)
    }else{
        accum[item.age] = [item]
    }
    return accum
}
let groupedPeople = people.reduce(groupByAge)
console.log(groupedPeople)

Function composition enabling piping

const double = x => x + x;
const triple = x => 3 * x;
const quadruple = x => 4 * x;

// Function composition enabling pipe functionality
const pipe = (...funcs)=>{
  return function(input){
    return funcs.reduce((accum, fun)=>{
      accum = fun(accum)
      return accum
    }, input)
  }
}


// Composed functions for multiplication of specific values
const multiply6 = pipe(double, triple);
const multiply9 = pipe(triple, triple);
const multiply16 = pipe(quadruple, quadruple);
const multiply24 = pipe(double, triple, quadruple);

// Usage
console.log(multiply6(6)); // 36
console.log(multiply9(9)); // 81
console.log(multiply16(16)); // 256
console.log(multiply24(10)); // 240

Another composition / pipe example

const compose = (...args)=>{
    return function(x){
        return args.reduce( function(accum, item){
            return item(accum)
        }, x)
    }
}

let pipe = (...args)=>{
    return function(x){
        return args.reduceRight( function(accum, item){
            return item(accum)
        }, x)
    }
}

// TEST
console.log(" TEST: compose & pipe: ")
const add = x => y => x + y
const multiply = x => y => x * y

const testCompose = compose(add(2), multiply(3), add(2), multiply(3))
console.log(testCompose(1)) // ( (2+1) * 3 + 2 )*3 = 9

const testPipe = pipe(add(2), multiply(3), add(2), multiply(3))
console.log(testPipe(1))     //( ( ( 1 * 3) + 2) * 3) + 2

Composition vs Inheritance

Here we compare 2 ways to make an Employee object, using Composition and Inheritance

make employee using Inheritance

function Person(fn, ln){
  this.firstName = fn;
  this.lastName = ln;
};
 
Person.prototype.getInfo = function(greetStr){
  //In real life this method/function will be bigger
  return `${greetStr}, I am ${this.firstName} ${this.lastName}.`
}
 
function Employee(fn, ln, empid){
  Person.call(this, fn, ln);
  this.empid = empid;
};
 
Employee.prototype = Object.create(Person.prototype);
Employee.prototype.getId = function(greetStr){
  return return `${greetStr}, my employee id is ${this.empid}.`;
}s
var e1 = new Employee("John", "Doe", 123);
console.log( e1.getInfo('Hi') ); // Hi, I am John Doe.
console.log( e1.getId('Hello') ); // Hello, my employee id is 123.

make employee using Composition [ Closure applied ]

function getInfo(firstName, lastName, greetStr){
  return `${greetStr}, I am ${firstName} ${lastName}.`
}
 
function getId(empid, greetStr){
  return `${greetStr}, my employee id is ${empid}.`;
}
 
function createEmployee(fn, ln, empid){
  return {
    empid: empid,
    getId : (greetStr) => getId(empid, greetStr),
    getInfo: (greetStr) => getInfo(fn, ln, greetStr) 
  };
}

var e1 = createEmployee("john", "doe", 123);
console.log( e1.getInfo('Hi') ); // Hi, I am John Doe.
console.log( e1.getId('Hello') ); // Hello, my employee id is 123.

CSS: `width:100%` for parent with `position:relative` & `position:absolute`

will escape from normal document flow:
- position: absolute: Note, if no top, left, right, bottom specified, it will stay at its original position
- postion:fixed
won’t escape from normal document flow:
- position: relative
- float

width:100% : the percentage means relative to its parents

If still in normal document flow: parent is its container

if not in normal document flow: parent is the element it positioned relative to

<!DOCTYPE html>
<html>
    <head>
        <style>
            #outer{
                width: 100px;            
                height: 100px;
                border: 1px red solid;
            }

            #inner1{
                position: relative;
                width:100%;
                height:100%;
                border: 1px green solid;
            }

            #inner2{
                position: absolute;
                width:100%;
                height:100%;
                border: 1px blue solid;
            }

        </style>
    </head>
    
    <body>
        <div id="outer">
            <div id="inner1">
            </div>
            <div id="inner2">
            </div>
        </div>
    </body>
</html>

Add, Remove& Toggle Classes With `classList` in JavaScript

Say we have an element like this:

1
2
3

<div class="cool new shades">
  	content
</div>

We can get all class names using 2 ways:

element.classList

let shadesEl = document.querySelector('.cool');

console.log(shadesEl.classList);
// ["cool", "new", "shades", value: "cool new shades"]

console.log(shadesEl.classList[1]); // new

element.className

let shadesEl = document.querySelector('.cool');

console.log(shadesEl.className);
// "cool new shades"

`add`

1 2	shadesEl.classList.add('make', 'me', 'look', 'rad'); // <div class="cool new shades make me look rad">content </div>

contains

1	console.log(shadesEl.classList.contains('look')); // true

item

1
2
3

console.log(shadesEl.classList.item(3));   // make
// equals way
console.log(shadesEl.classList[3]);  	   // make

remove

1 2	shadesEl.classList.remove('cool', 'make', 'me'); // <div class="new shades look rad">content </div>

toggle

// GOOD version
coolButton.addEventListener('click', () => {
  shadesEl.classList.toggle('cool');
});

// BAD toggle
if (shadesEl.classList.contains('rad')) {
  shadesEl.classList.remove('rad');
} else {
  shadesEl.classList.add('rad');
}

CSS Notes

Posted on 2018-11-15 | In Full stack | Comments:

I. Inherit `height` of outer `div`

Problem: how to make an inner div to inherit the height of its containing div ?

If containing div already specified height

use height: 100% to inherit the outer div

if containing div doesn’t specify height

cannot use height: 100% to inherit the containing div. The computed height for the inner one will become auto, which means its height depends on its content

If the height of the containing block is not specified explicitly (i.e., it depends on content height), and this element is not absolutely positioned, the value computes to auto

https://developer.mozilla.org/en-US/docs/Web/CSS/height

Right way: containing div set position:relative; inner div set position: absolute and top:0 & bottom:0

<!DOCTYPE html>
<html>
<head>
<style> 
    #container{
        border: 1px solid red;
        position: relative;
    } 
    #fullHeight{
        border: 1px solid green;
        position: absolute;
        top: 0;
        bottom: 0;
        width:100%;
        background-color: grey;
   	 	opacity: 0.5;
    }
    #noHeight{
        height: 100%;
        width: 100%;
        border: 1px solid blue;
    }
</style>
</head>
<body >
    <div id="container">
        <div id="noHeight" >ads </div>
        <div id="fullHeight"></div>
        <p>Dummy text. Dummy text. Dummy text. Dummy text. </p>
    </div>
</body>
</html>

II. Set mask to a `div` to disable it

Problem: set a mask layer to cover its outer div

Solution: use position: absolute & top: 0 & bottom: 0 to cover the whole height or its containing div, which set position: relative

<!DOCTYPE html>
<html>
<head>
<style> 
    #container{
        border: 1px solid red;
        position: relative;
    } 
    #inner {
        background-color: coral;
    }
    #mask{
        border: 1px solid green;
        position: absolute;
        top: 0;
        bottom: 0;
        width: 100%;
        height: 100%;
        background-color: grey;
        opacity: 0.5;
    }
</style>
</head>
<body >
    <div id="container">
        <div id="inner" >myBox</div>
        <div id="mask"></div>
        <p>Dummy text. Dummy text. Dummy text. Dummy text. </p>
    </div>
    
    <script>
        let inner = document.getElementById("inner")
        inner.addEventListener("click", function(){alert("inner")})

        let mask = document.getElementById("mask")
        mask.addEventListener("click", function(){alert("mask")})

        let container = document.getElementById("container")
        container.addEventListener("click", function(){alert("container")})
    </script>
</body>
</html>

Write A Promise

Posted on 2018-11-02 | In Full stack | Comments:

I. Why do we need `Promise` - “callback hell”

Asynchronous call is the core of JavaScript across browser and Node.js.
JavsScript runtime thread use callback to execute result of asynchronous task handled by other threads (Ajax thread, Timer thread, Rendering Thread)

Example below are callback hell , which is a headache for programmer. For

// when the nesting level exceeds 3, people will get crazy!!
getData(function(x){				// getData of x
    getMoreData(x, function(y){   	// getMoreData of y, using x
        getMoreData(y, function(z){ // getMoreData of x, using y
            ...
        });
    });
});

Is there a way to flatten the nesting callbacks, in a chainable way? => Node
- Consider the Node data structure, it contains child node in itself, similar to our requirement!!
- Promise is such a stateful utility object, which can be chained to implement nested callbacks

II. Promise Usage

executer:

execute asynchronous action, generating result

when create new Promise, need to pass in pre-defined executer

// executer: a function with parameters: `resolve` and `reject`
let p = new Promise( function(resolve, reject){
    ajaxGet( url, function(res){
        if(res.status == 200)  
            resolve(res.data)
        else     			   
            reject(res.error)
    })
})

callbacks in then:

onFulfilled & onRejected specify how to handle the result of asynchronous action

use case 1: multiple callbacks on a promise

// Assume executor will: resolve(1)
let callback1 = function(res){ console.log("This is from callback1: " + res*1) }
let callback2 = function(res){ console.log("This is from callback2: " + res*2)}
p.then(callback1)  // This is from callback1: 1
p.then(callback2)  // This is from callback1: 2

use case 2: chaining callbacks

// Assume executor will: resolve(1)
let callback1 = function(res){ return res+1 }
let callback2 = function(res){ return res+1 }
let callback3 = function(res){ console.log("The final res will be 3: " + res) }
p.then(callback1).then(callback1).then(callback3)  // The final res will be 3: 3

III. Promise: stateful utility object

“Stateful”

Promise is an object, its properties are stateful, ie. property value can change dynamially
state can only change in 2 ways: pending => fulfilled, pending => rejected

the cause of stateful is: asynchronous actions inside the executor. Once instantiated to promise object, the executor will be executed inside promise object, and will update state, value, consumers

function MyPromise( executor ){
    this.state = "pending"  // keep record of the state update
	this.value = undefined  // store the result of asynchronous action
	this.consumers = []     // place to store callbacks (actually child promises)
    
    executor(this.resolve.bind(this), this.reject.bind(this)) // run executor 
}

resolve & reject: hooks to receive asynchronous result.
- The asynchronous function executor , will pass its result to Promise using its hooks: resolve and reject
then: hooks to receive passed in callbacks onFulfilled & onRejected
- the callbacks are passed to Promise using then hook
- Promise will take care of executing callback, when asynchronous result is ready
How to it chainable
- In fact, then() method can not only receive callbacks,
- but also can return a new Promise, which can be chained by using another then, …., and so on
- then() create a new Promise, then put the callbacks inside the newly created Promise, then put into the consumers array to consume the asynchronous result when its ready

VI. Write One!

Promise state:

There are only 2 state transitions allowed: from pending to fulfilled, and from pending to rejected. No other transition should be possible, and once a transition has been performed, the promise value (or rejection reason) should not change.

function MyPromise(executor) {
    this.state = 'pending';
    this.value = undefined;
    executor(this.resolve.bind(this), this.reject.bind(this));
}

// provide only two ways to transition
MyPromise.prototype.resolve = function (value) {
    if (this.state !== 'pending') return; // cannot transition anymore
    this.state = 'fulfilled'; 		      // can transition
    this.value = value; 				  // must have a value
}

MyPromise.prototype.reject = function (reason) {
    if (this.state !== 'pending') return; // cannot transition anymore
    this.state = 'rejected'; 			  // can transition
    this.value = reason; 				  // must have a reason
}

then method: the core of chaining

[Note 1]: each then() will return a new Promise!
The then method is the core to Promise, which can be chained using then. It has two tasks:
- receive callbacks, and store them for later use when asynchorous result is ready
- create new promise, to make promise chainable
In fact, we put callbacks of the current promise, into the newly created child promises. Each callback will correspond a new Promise creation
This way, we can also easily consume the outcome of the callback(result), to resolve(outcome)for the child promises

[Note 2]:

child promise execute its parent’s callback ;
and resolve outcome of that callback, pass the outcome to promise created by next then

// For each then(), create a new Promise to embody this callback pair
MyPromise.prototype.then = function(onFulfilled, onRejected) {
    var consumer = new MyPromise(function () {});
    
    // ignore onFulfilled/onRejected if not a function
    consumer.onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : null;
    consumer.onRejected  = typeof onRejected  === 'function' ? onRejected  : null;
    
    // put the consumer with parent's callbacks onto `this.consumers`
    this.consumers.push(consumer);
    
    // It's possible that the promise was already resolved, 
    // so, try to consume the resolved result 
    this.broadcast();
    
    // must return a promise to make it chainable
    // used by next potential `then()` in the chain
    return consumer;
};

broadcast(): Consume the asynchorous result

After the asynchronous action return a result, we need to

first, update the state to fulfilled or rejected
execute the each callback of onFulfilled, onRejected (in child promise) collected by then
onFulfilled, onRejected must be called asynchronously

for example, new Promise(executor).then(callback), callback execution must happen after executor. Thus, we can correctly get result even if executor is synchorous

MyPromise.prototype.broadcast = function() {
    var promise = this;
    // only get called after promise is resolved
    if (this.state === 'pending') return;
    
    // callback must be executed by its corresponding promise
    var callbackName = this.state == 'fulfilled' ? 'onFulfilled' : 'onRejected';
    
    // when no callback specified in then(), still need to resolve/reject it
    var resolver = this.state == 'fulfilled' ? 'resolve' : 'reject';
    
    // onFulfilled/onRejected must be called asynchronously
    setTimeout(function() {
        // traverse in order & call only once, using `splice(0)` for deletion
        promise.consumers.splice(0).forEach(function(consumer) {
            try {
                var callback = consumer[callbackName];
                // if a functon, call callback as plain function
                // else, ignore callback
                if (callback) {
                    // child promise resolve outcome of callback(value)
                    consumer.resolve(callback(promise.value)); 
                } else {
                    // child promise resolve value without callback
                    consumer[resolver](promise.value);
                }
            } catch (e) {
                consumer.reject(e);
            };
        })
    }, 0 );
}

[Note 2]: the current then can only handle chainable promise when callback is pure function; Cannot handle when callback return a new Promise.

Make then can response another Promise

This time, we need to modify the resolve method to be able to receive another Promise; At the same time, the original one we call it fulfill.

// The Promise Resolution Procedure: will treat values that are thenables/promises
// and will eventually call either fulfill or reject/throw.
MyPromise.prototype.resolve = function(x) {
    var wasCalled, then;
    // 2.3.1
    if (this === x) {
        throw new TypeError('Circular reference: promise value is promise itself');
    }
    // 2.3.2
    if (x instanceof MyPromise) {
        // 2.3.2.1, 2.3.2.2, 2.3.2.3
        x.then(this.resolve.bind(this), this.reject.bind(this));
    } else if (x === Object(x)) { // 2.3.3
        try {
            // 2.3.3.1
            then = x.then;
            if (typeof then === 'function') {
                // 2.3.3.3
                then.call(x, function resolve(y) {
                    // 2.3.3.3.3 don't allow multiple calls
                    if (wasCalled) return;
                    wasCalled = true;
                    // 2.3.3.3.1 recurse
                    this.resolve(y);
                }.bind(this), function reject(reasonY) {
                    // 2.3.3.3.3 don't allow multiple calls
                    if (wasCalled) return;
                    wasCalled = true;
                    // 2.3.3.3.2
                    this.reject(reasonY);
                }.bind(this));
            } else {
                // 2.3.3.4
                this.fulfill(x);
            }
        } catch(e) {
            // 2.3.3.3.4.1 ignore if call was made
            if (wasCalled) return;
            // 2.3.3.2 or 2.3.3.3.4.2
            this.reject(e);
        }
    } else {
        // 2.3.4
        this.fulfill(x);
    }
}

// 2.1.1.1: provide only two ways to transition
MyPromise.prototype.fulfill = function (value) {
    if (this.state !== 'pending') return; // 2.1.2.1, 2.1.3.1: cannot transition anymore
    this.state = 'fulfilled'; // 2.1.1.1: can transition
    this.value = value; // 2.1.2.2: must have a value
    this.broadcast();
}

V. Test Our Own Promise (stack overflow)

function MyPromise(executor) {
    this.state = 'pending';
    this.value = undefined;
    // A list of "clients" that need to be notified when a state
    //   change event occurs. These event-consumers are the promises
    //   that are returned by the calls to the `then` method.
    this.consumers = [];
    executor(this.resolve.bind(this), this.reject.bind(this));
}

// 2.1.1.1: provide only two ways to transition
MyPromise.prototype.fulfill = function (value) {
    if (this.state !== 'pending') return; // 2.1.2.1, 2.1.3.1: cannot transition anymore
    this.state = 'fulfilled'; // 2.1.1.1: can transition
    this.value = value; // 2.1.2.2: must have a value
    this.broadcast();
}    

MyPromise.prototype.reject = function (reason) {
    if (this.state !== 'pending') return; // 2.1.2.1, 2.1.3.1: cannot transition anymore
    this.state = 'rejected'; // 2.1.1.1: can transition
    this.value = reason; // 2.1.3.2: must have a reason
    this.broadcast();
}    

// A promise’s then method accepts two arguments:
MyPromise.prototype.then = function(onFulfilled, onRejected) {
    var consumer = new MyPromise(function () {});
    // 2.2.1.1 ignore onFulfilled if not a function
    consumer.onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : null;
    // 2.2.1.2 ignore onRejected if not a function
    consumer.onRejected = typeof onRejected === 'function' ? onRejected : null;
    // 2.2.6.1, 2.2.6.2: .then() may be called multiple times on the same promise
    this.consumers.push(consumer);
    // It might be that the promise was already resolved... 
    this.broadcast();
    // 2.2.7: .then() must return a promise
    return consumer;
};

MyPromise.prototype.broadcast = function() {
    var promise = this;
    // 2.2.2.1, 2.2.2.2, 2.2.3.1, 2.2.3.2 called after promise is resolved
    if (this.state === 'pending') return;
    // 2.2.6.1, 2.2.6.2 all respective callbacks must execute
    var callbackName = this.state == 'fulfilled' ? 'onFulfilled' : 'onRejected';
    var resolver = this.state == 'fulfilled' ? 'resolve' : 'reject';
    // 2.2.4 onFulfilled/onRejected must be called asynchronously
    setTimeout(function() {
        // 2.2.6.1, 2.2.6.2 traverse in order, 2.2.2.3, 2.2.3.3 called only once
        promise.consumers.splice(0).forEach(function(consumer) {
            try {
                var callback = consumer[callbackName];
                // 2.2.1.1, 2.2.1.2 ignore callback if not a function, else
                // 2.2.5 call callback as plain function without context
                if (callback) {
                    // 2.2.7.1. execute the Promise Resolution Procedure:
                    consumer.resolve(callback(promise.value)); 
                } else {
                    // 2.2.7.3 resolve in same way as current promise
                    consumer[resolver](promise.value);
                }
            } catch (e) {
                // 2.2.7.2
                consumer.reject(e);
            };
        })
    });
};

// The Promise Resolution Procedure: will treat values that are thenables/promises
// and will eventually call either fulfill or reject/throw.
MyPromise.prototype.resolve = function(x) {
    var wasCalled, then;
    // 2.3.1
    if (this === x) {
        throw new TypeError('Circular reference: promise value is promise itself');
    }
    // 2.3.2
    if (x instanceof MyPromise) {
        // 2.3.2.1, 2.3.2.2, 2.3.2.3
        x.then(this.resolve.bind(this), this.reject.bind(this));
    } else if (x === Object(x)) { // 2.3.3
        try {
            // 2.3.3.1
            then = x.then;
            if (typeof then === 'function') {
                // 2.3.3.3
                then.call(x, function resolve(y) {
                    // 2.3.3.3.3 don't allow multiple calls
                    if (wasCalled) return;
                    wasCalled = true;
                    // 2.3.3.3.1 recurse
                    this.resolve(y);
                }.bind(this), function reject(reasonY) {
                    // 2.3.3.3.3 don't allow multiple calls
                    if (wasCalled) return;
                    wasCalled = true;
                    // 2.3.3.3.2
                    this.reject(reasonY);
                }.bind(this));
            } else {
                // 2.3.3.4
                this.fulfill(x);
            }
        } catch(e) {
            // 2.3.3.3.4.1 ignore if call was made
            if (wasCalled) return;
            // 2.3.3.2 or 2.3.3.3.4.2
            this.reject(e);
        }
    } else {
        // 2.3.4
        this.fulfill(x);
    }
}



// ------------------ TEST ------------------ 
let p0 = new MyPromise((resolve, reject)=>{
    setTimeout(()=>{ resolve(0) },1000)
})

let p1 = p0.then((res)=>{ 
    console.log("p1 get result from p0, value should be 0: " + res)
    return res+1
})

let p2 = p0.then((res)=>{ 
    console.log("p2 get result from p0, value should be 0: " + res)
    return res+2
})

let p3 = p0.then((res)=>{ 
    console.log("p3 get result from p0, value should be 0: " + res)
    return res+3
})

console.log("This should be an array of 3 Promises: " + p0.consumers)

let p4 = p1.then(res=>{ console.log("p4 get result from p1, value should be 1: " + res)})
let p5 = p2.then(res=>{ console.log("p5 get result from p2, value should be 2: " + res)})
let p6 = p3.then(res=>{ console.log("p6 get result from p3, value should be 3: " + res)})

Credits to:

Sorting Algorithms in JS

Posted on 2018-11-01 | In Algorithm | Comments:

I. Selection Sort

totally unsorted: O(n^2)
partially sorted: O(n^2)

/*
  select min element from rest of unsorted elements, put into front
    - totally unsorted: O(n^2)
    - partially sorted: O(n^2)
*/

function slectionSort( list ){
  if( list === null || list.length <= 1 ) return 

  for( let i = 0; i < list.length; i++ ){
    let curMinId = i
    for( let j = i+1; j < list.length; j++ ){
      list[curMinId] > list[j] && (curMinId = j)
    }
    [ list[i], list[curMinId] ] = [ list[curMinId], list[i] ]
  }
}

// Test
let list = [ 2, 1, 3, 4, 5, 6, 3, 5, 1 ]
console.log("Original list: " + list)
slectionSort(list)
console.log("Selection sort: " + list)

II. Insertion Sort

totally unsorted: O(n^2)

partially sorted: O(n)

/*
  for each element, insert it into the sorted part exactly before its position
    - totally unsorted: O(n^2)
    - partially sorted: O(n)
*/

function insertionSort(list){
  if( list === null || list.length <= 1 ) return 
  
  for( let i = 1; i < list.length; i++ ){
    let idToBe = i
    while( idToBe-1 >= 0 && list[idToBe] < list[idToBe-1] ){
      [ list[idToBe-1], list[idToBe] ] = [ list[idToBe], list[idToBe-1] ] 
      idToBe -= 1
    }
  }
}

// Test
let list = [ 2, 1, 3, 4, 5, 6, 3, 5, 1 ]
console.log("Original list: " + list)
insertionSort(list)
console.log("Insertion sort: " + list)

III. Bubble Sort

BAD version:

totally unsorted: O(n^2)
partially sorted: O(n^2)

/*
  for each element, compare with its right element, swap if it's larger;
  keep doing util (n-1)th, (n-2)th,, (n-3)th ... 1st position
    - totally unsorted: O(n^2)
    - partially sorted: O(n^2)
*/

function bubbleSort(list){
  if( list === null || list.length <= 1 ) return 
  for( let i = list.length-1; i > 0; i-- ){
    for( let k = 0; k < i; k++ ){
      if( list[k] > list[k+1] ){
         [ list[k], list[k+1] ] = [ list[k+1], list[k] ]
      }
    }
  }
}


// Test
let list = [ 2, 1, 3, 4, 5, 6, 3, 5, 1 ]
console.log("Original list: " + list)
bubbleSort(list)
console.log("Bubble sort: " + list)

Good Version
- totally unsorted: O(n^2)
- partially sorted: O(n) if no swap for a iteration, then every element is in its place, terminate

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
28
/*
  for each element, compare with its right element, swap if it's larger;
  keep doing util (n-1)th, (n-2)th,, (n-3)th ... 1st position
    - totally unsorted: O(n^2)
    - partially sorted: O(n)
    - if no swap for a iteration, then every element is in its place, terminate
*/

function bubbleSort(list){
  if( list === null || list.length <= 1 ) return 
  let swapped = true
  for( let i = list.length-1; i > 0; i-- ){
  	if(swapped === false) return 
  	swapped = false
    for( let k = 0; k < i; k++ ){
      if( list[k] > list[k+1] ){
         [ list[k], list[k+1] ] = [ list[k+1], list[k] ]
         swapped = true
      }
    }
  }
}

// Test
let list = [ 2, 1, 3, 4, 5, 6, 3, 5, 1 ]
console.log("Original list: " + list)
bubbleSort(list)
console.log("Bubble sort: " + list)

VI. Merge Sort

Time Complexity
- totally unsorted: O(n^2)
- partially sorted: O(n)
Space Complexity: cannot sort in-place
- O(n^2)

/*
  recursively divide list into two half, till each half have one or two elements
  recursively merge two half into one, till achieve original size
  
  Time Complexity
  	- totally unsorted: O(n^2)
    - partially sorted: O(n^2)
  Space Complexity:
  	- O(n^2)
*/

function mergeSort(list){
  if( list === null || list.length <= 1 ) return 
  return divideAndMerge(list)
}

function divideAndMerge(list){
  let l1 = list.slice(0, list.length/2)  
  if( l1.length > 1 )  l1 = divideAndMerge(l1)
  
  let l2 = list.slice(list.length/2, list.length)
  if( l2.length > 1 )  l2 = divideAndMerge(l2)
  
  return merge(l1, l2)
}

function merge(l1, l2){
  let list = []
  let i = 0, j = 0, k = 0
  while(i < l1.length && j < l2.length){
    if( l1[i] > l2[j] ) 
      list[k++] = l2[j++]
    else
      list[k++] = l1[i++]
  }
  while( i < l1.length ) list[k++] = l1[i++]
  while( j < l2.length ) list[k++] = l2[j++]
  
  return list
}

// Test
let list = [ 2, 1, 3, 4, 5, 6, 3, 5, 1 ]
console.log("Original list: " + list)
mergeSort(list)
console.log("Merge sort: " + mergeSort(list))

V. Quick Sort

Time Complexity:
- totally unsorted: O(n^2)
- partially sorted: O(n)
Space Complexity: O(n) in-place
Approach:
- randomly choose a pivot, here we use the first element in the question list
- loop from both ends, compare value with pivot, and swap their value
- how to swap: front & back two pointers
  - “LeetCode: sort color”: https://leetcode.com/problems/sort-colors/description/

/*
  1. randomly choose a pivot, here we use the first element in the question list
  2. loop from both ends, compare value with pivot, and swap their value
  3. how to swap: "LeetCode: sort color" ==> "front & back two ponters"
     https://leetcode.com/problems/sort-colors/description/
     
     
       0......0   1......1  x1  x2 .... xm   2.....2
                  ^         ^            ^
                 zero       i           two
              smallerToBe			 largerToBe
              
        区间一：0  | 区间二：1 | 区间三：未知 |  区间四：2
*/

function quickSort(list, left, right){
    if( list === null || left >= right ) return 

    let pivot = list[left],
    	smallerToBe = left, 
        largerToBe = right, 
        i = left
    	
    while( i <= largerToBe ){
        if( list[i] === pivot ){
            i++
        }else if( list[i] < pivot ){
            swap(list, i++, smallerToBe++)
        }else{
            swap(list, i, largerToBe--)
        }
    }
    quickSort(list, left, smallerToBe-1)  
    quickSort(list, largerToBe+1, right)
}

function swap(list, p1, p2){ [ list[p1], list[p2] ] = [ list[p2], list[p1] ] }

// Test
let list = [ 3, 1, 3, 4, 5, 1, 3, 2, 5, 1 ]
console.log("Original list: " + list)
quickSort(list, 0, list.length-1)
console.log("Quick sort: " + list)

setTimeout vs setInterval

Posted on 2018-10-31 | In Full stack | Comments:

0. Credits to:

http://www.laruence.com/2009/09/23/1089.html

https://www.jeffjade.com/2015/08/03/2015-08-03-javascript-this/

https://www.youtube.com/watch?v=8aGhZQkoFbQ

https://www.zhihu.com/question/55050034

https://codepen.io/discountry/pen/XRXdVX?editors=1011

I. `setTimeout`

After delay period, put cb to taskQueue of main thread, rather than executing cb right away!
- only guarantees after exactdelay, cb is scheduled,
- cannot guarantee cb being executed after exact delay, because maybe at that time, the main thread is still dealing a time-consuming task, which will postpone the execution of cb
Good use case: recursively schedule delayed task, like a node data structure
- deal with CPU intensive task, set aside period for UI update to be executed to avoid freezing
- eg. break down large task into smaller ones, schedule smaller task execution every delay period
  - the bigger delay period is, the longer time left for UI
  - the time left for UI is exactly delay period
  - NOTE: don’t use setInterval, since the execution time for cb can be longer thandelay , resulting in there’s no time left for UI update. When cb finishes execution, the UI update and next cb will race to be executed in next event loop

setTimeout(cb, 0):

1. 等到Call Stack为空，即下一轮 Event Loop的时候执行 cb
1. Render Queue 比 Callback Queue 在browser中的优先级高，他们共用一个JS V8 Engine。因此，callback中的cb会等到DOM被render之后在调用，这就是为什么使用 setTimeout(cb, 0)
1. 这样，即便有很多setTimeout(cb, 0)短时间大量被调用，也会因为render queue的高优先级，使得它能够在两个cb 调用之间，插入到 JS V8 thread中update DOM，从而使页面不会freeze
Waiting for elements mounted to DOM by GUI thread, then switch to JS thread, do the manipulation by cb
Every function put inside setTimeout with 0 delay, will respect all the DOM task, and will scheduled after all DOM tasck
will execute right after all synchronous task is finished on stack by main thread
i.e. has to wait for next event loop come

Great Use Case:

set the order of event handler:

// 1. parent event_handler will be executed first, 
// 2. then the target element 
let input = document.getElementById('myButton');

input.onclick = function A() {
  setTimeout(function B() {
    input.value +=' input';
  }, 0)
};

document.body.onclick = function C() {
  input.value += ' body'
};

tackle the race problem of keypress

/*
	keypress has two results:
	1. give input the value of pressed key [asynchronous - hardware]
	2. call the keypress event handler [asynchronous - event]
	
	BAD version: 
		- cannot get the current key value when callback is called
		- can only get the value of previous pressed key value
	GOOD version:
		- use setTimeout(fn, 0)
		- callback will be executed after the key value is updated in DOM
*/

<input type="text" id="input-box">

// 1. BAD Version
document.getElementById('input-box').onkeypress = function (event) {
  	this.value = this.value.toUpperCase();
}

// 2. GOOD Version
document.getElementById('input-box').onkeypress = function() {
  let self = this;
  setTimeout(function() {
    self.value = self.value.toUpperCase();
  }, 0);
}

II. `setInterval`

Every delay period, put cb to taskQueue of main thread if there is no cb waiting to be executed on the taskQueue; Otherwise, won’t schedule cb even delay period is achieved
Note:
1. when delay is up, even there exists an CPU-intensive task , setInterval won’t wait for the finish of the current task, instead put the cb directly to taskQueue at the exact time spot;
2. But if the main thread is still executing task, the cb has to waits to be executed
3. There is NO accumulated cb scheduled on event queue, even if there is a CPU intensive task blocking the periodic cb scheduling.
4. setInterval timer has a check mechnism to ensure, there will be only one cb on event queue

Common use case: CSS animation

Note1:
- it only focus scheduling cb after delay, don’t care how long vacant time left
- it’s possible that execution of cb is longer than delay, then next cb will be executed right after first cb finishes

Note2:

mustn’t use time variable as terminating condition to clear interval,
because some time it cost longer to execute cb, making some scheduled task won’t be executed
use other variable as terminating condition to clear interval

let div = document.getElementById('someDiv');
let opacity = 1;
let fader = setInterval(function() {
	opacity -= 0.1;
		if (opacity >= 0) {
			div.style.opacity = opacity;
		} else {
			clearInterval(fader);   // use `opacity` as terminating condition
		}
}, 100);

III. Common Problems

this problem => because of window.setTimeout or window.setInterval

setTimeout( function(){ this.value=50 }, 1000 )
Problem:
- example above, exist this in the callback function, if not bind actual object, this will refer window
- setTimeout setInterval will change the reference of this to window
Why?
- this always refers to the object who calls the function where this resides
- when cb executed, it is executed like cb(), which omits the prefix object: window

How to solve?

use bind() to produce a new cb function carrying this reference to right object
use apply or call

a = "string belongs to window"    // note: not " let a = ... ";
obj = {
    a: "string belongs to obj",
    printA: function(){ console.log(this.a) }
}

// 1. "string belongs to window", after 1s
setTimeout(obj.printA, 1000)  

// 2. "string belongs to window", after 1s
let temp = obj.printA
setTimeout(temp, 1000)  	  

// 3. "string belongs to obj"
setTimeout(function(){ obj.printA.apply(obj) }, 2000) 

// 4. "string belongs to obj" 
setTimeout(function(){ obj.printA() }, 3000)

Implement a setInterval using setTimeout

NOTE:

Approach 1: the time_handle should be an object if declared inside the function, rather than an number, because the timeId is updated every delay period
Approach 2: the time_handle should be a global var outside the function , because the timeId is updated every delay period

// ----------------Approach 1----------------
function customSetInterval( cb, delay ){
    let time_handle = {id: null}
    function wrapper(){
        cb.apply(null)
        time_handle.id= setTimeout(wrapper, delay)
    }
    time_handle.id= setTimeout(wrapper, delay)
    return time_handle
}
// Test
let i = 0
function cb(){ i+=1; console.log(i) }
let interval_handle = customSetInterval(cb, 1000)  // print  1 , 2 , 3 , 4 , ...
// clearTimeout(interval_handle.id)   // use to clear interval


// ----------------Approach 2----------------
let time_handle = null
function customSetInterval( cb, delay ){
    function wrapper(){
        cb.apply(null)
        time_handle= setTimeout(wrapper, delay)
    }
    time_handle= setTimeout(wrapper, delay)
}
// Test
let i = 0
function cb(){ i+=1; console.log(i) }
customSetInterval(cb, 1000)  // print  1 , 2 , 3 , 4 , ...
// clearTimeout(time_handle)   // use to clear interval

how to handle encoding task for a file (CPU intensive)?

Problem: it might freeze the UI when encode the whole file

Solution:

Divide the file into several part, using a symbol, or using size
for each small part, just take over CPU, since it’s small task
between each encoding, leave time for UI interaction
Note: use setTimeout instead of setInterval
Since the execution time for cb can be longer thandelay , resulting in there’s no time left for UI update. When cb finishes execution, the UI update and next cb will race to be executed in next event loop

/*
	input: the file to be encoded
	output: the encoded goal file 
	totalSize: the size of the input file
	encode: the function used to encode
*/

function encodeWrapper( input, output, totalSize, encode ){
    let output = ""
    let accumSize = 0
    let i = 0
    let timeoutHandle = null
    /* delayed recursion
       i: ith step    
       stepSize: how big to encod for a step
    */
    function encodeHelper(i, stepSize ){
        output += encode( input.substring(i*stepSize,stepSize) )
        if( i*stepSize > totalSize ) {
            clearTimeout(timeoutHandle)
            return output
        }
        timeoutHandle = setTimeout(encodeHelper(i+1, stepSize), 100)
    }
    return encodeHelper(0, 1024) 
}

How to write a delayed recursion ?
- Problem: Calculate the sum from 0 to n
- Solution: f(n) = f(n-1) + n; f(0) = 0

/*
	f(n) = f(n-1) + n
	f(0) = 0
*/

function wrapper(n){
    let timeHandle = 0
    let accum = 0

    // recursive call itself every 1000ms
    function sum(n){
        timeHandle=setTimeout(function(){
            if (n === 0) {
                clearTimeout(timeHandle)
                alert(accum) // output the result
                return 
            }
            accum += n
            sum(n-1)
        },1000)
    }
    sum(n)
}

Debouncify a function

Problem: Some Ajax functions can be frequently called using events, which will cause severe performance problem on backend
Solution:
- we want to call Ajax function only after a period delay time (so that we can make sure the user is really waiting to for to make Ajax call, rather than in the middle of typing)
- when there is another intention to call the Ajax function in the middle of last delay, we want to reschedule the ajax call after another delay

function callAjaxRightAway(){ 
    console.log("Ajax call starting, with arguments: " + [...arguments] ) 
}


function Debouncify( fn, delay ){
    let time_handle = null
    return function(){
        clearTimeout(time_handle)
        let args = arguments
        time_handle = setTimeout( function(){ fn.apply(null,args) }, delay)
    }
}

let delayedFun = Debouncify(callAjaxRightAway, 2000) 

delayedFun({arr:[1, 2, 3], heigh: 10 }) // will be ignored
delayedFun(1,2)							// will be ignored
delayedFun("a", "b", "c")    // "Ajax call starting, with arguments: a,b,c"

Negative Margin in Layout

Posted on 2018-10-30 | In Full stack | Comments:

Credits to:

Document flow

All block elements like boxes (block/inline) flowing on water; The water push them to left, and to top

inline elements are only push to left; When there is no space in a row, it will automatically switch to next line without new line generated
float will make element escape from normal document flow
inline element float will make it to be block element
position: absolute & position: fixed will also make escape

Margin Used in Domcument FLow

margin determine the hidden outer border (not border) for all elements.
All elements have a hidden outer border used by browser to arrange elements.

Positive Margin

block element: will make margins on 4 directions have a gap between its parents or its siblings
inline element: will only respect left-margin and right-margin

Negative Margin

normal document flow
- positive: margin will separate boxes by a gap
- negative:
  - margin-left 和 margin-top：affect itself, move to its left/top by value
  - margin-right 和 margin-bottom：affect adjacent elements, pull them to its right/bottom by value
escape document flow: absolute position
- margin-left 和 margin-top：can affect itself, move to its left/top by value
- margin-right 和 margin-bottom：won’t affect adjacent, since it out of normal document flow

escape document flow: float

determined by float direction (like normal doc flow)

when float: left:
- margin-left: -5px will move itself to left by 5px
- margin-right: -5px will move adjacent element to its right by 5px
- margin-top：can affect itself, move to its top by value
- margin-bottom：will move adjacent element to its bottom by value
when float: right:
- margin-right: -5px will move adjacent element to its right by 5px
- margin-left: -5px will move itself to left by 5px
- margin-top：can affect itself, move to its top by value
- margin-bottom：will move adjacent element to its bottom by value

[NOTE]： margin-left:-100% in float document flow

since float flow is like inline elements, no new line between lines, even though they are in different lines
For example below: even though at first left is on bottom of main, does not mean it break off from main, it still adjacent to main
margin-left: -100%; moves itself to its left by 100% width of its parent

Example

<div class="main" >  main </div>
<div class="left" >  left </div>
<div class="right"> right </div>

<style>
    .main{
        float: left;
        width: 100%;   // occupy whole width
    }
    .left{
        float: left;
        width: 50px;   // its own width
        margin-left: -100%; 
        // even though at first it is on bottom of
        // main, does not mean break off from main
        // when '-100%' negative margin,
        // it move itself to its left by 
        // 100% width of parent
    }
    .right{
        float: left;
        width: 50px;
        margin-left: -50px;
    }
</style>

Use case of negative margin

Layout Difference: Holy Grail vs Double wings
- Holy Grail: background won’t affect two sides, even it’s higher than two sides
- Double wings: background affects parts below two sides, when it’s higher than two sides

Layout of Holy Grail (圣杯布局)

https://blog.csdn.net/zhoulei1995/article/details/80161240
container set aside left/right padding padding for left/right section
move left/right section onto main using negative margin

move left/right section to padding place using position:relative

<html>
    <head>
        <style>
        	.container {
                padding: 0 300px 0 200px;
            }
            .content {
                float: left;
                width: 100%;
                background: #f00;
            }
            .left {
                position: relative;
                left: -200px;
                float: left;
                width: 200px;
                margin-left: -100%;
                background: #0f0;
            }
            .right {
                position: relative;
                right: -300px;
                float: left;
                width: 300px;
                margin-left: -300px;
                background: #00f;
            }
        </style>
    </head>
    
    <body>
        <div class="container">
            <div class="content">
                中间内容区域 中间内容区域 中间内容区域 
                中间内容区域 中间内容区域 中间内容区域 
                中间内容区域 中间内容区域 中间内容区域 
            </div>
            <div class="left">左侧边栏区域</div>
            <div class="right">右侧边栏区域</div>
        </div>
    </body>
</html>

Double Wings layout (双飞翼布局)

https://blog.csdn.net/zhoulei1995/article/details/80161240
move left/right section onto wrapper using negative margin

set margin left/right to main, to make it won’t hidden by two sides

<html>
    <head>
        <style>
        	.wrapper {
                float: left;
                width: 100%;
                background: #f00;
            }
            .content {
                margin-left: 200px;
                margin-right: 300px;
            }
            .left {
                float: left;
                width: 200px;
                margin-left: -100%;
                background: #0f0;
            }
            .right {
                float: left;
                width: 300px;
                margin-left: -300px;
                background: #00f;
            }
        </style>
    </head>
    
    <body>
        <div class="wrapper">
            <div class="content">
                中间内容区域 中间内容区域 中间内容区域 
                中间内容区域 中间内容区域 中间内容区域 
                中间内容区域 中间内容区域 中间内容区域			</div>
        </div>
        <div class="left">左侧边栏区域</div>
        <div class="right">右侧边栏区域</div>
    </body>
</html>

Horizontal & Vertical Center

For position: absolute, even thought it out of the normal document flow, the negative left/top still affect itself, moving to its left/top by value

<!DOCTYPE HTML>
<html>
<head>
    <meta charset="UTF-8">
    <title> Center </title>
    <style>
     body{ margin:0;padding:0;}
     #test{
        width:200px;
        height:200px;
        background:#F60;
        position:absolute;
        left:50%;
        top:50%;
        margin-left: -100px;
        margin-top: -100px;
    }
    </style>
</head>
<body>
 <div id="test"></div>
</body>
</html>

Create a Calculator - [React]

Posted on 2018-10-16 | In Full stack | Comments:

Problem

Build a web calculator, that supports the basic operations of add, remove, multiply and divide.

In addition, support resetting the current state, as well as a decimal point button.

Implementation

HTML

1
2
3

<div class="center-child">
  <div id="app" ></div>
 </div>

CSS

.wrapper{
          width: 400px;
          height: 400px;
          margin: 15px auto;
          border: 1px solid black;
        }
        .display-panel{
          margin: 10px auto;
          width: 95%;
          height: 60px;
          line-height: 60px;
          font-size: 30px;
          border: 1px solid black;
          text-align: right;
          overflow-y: hidden;
          overflow-x: scroll;
          white-space: nowrap;
        }

        .ctl-panel{
          margin: 5px auto;
          width: 95%;
          height: 300px;
          border: 1px solid black;
          font-size: 30px;
          display: flex;
          flex-flow: row wrap;
          justify-content: space-around;
        }

        .left-part{
          border: 1px solid red;
          flex: 1 1 70%;
          display: grid;
          justify-content: space-around;
          align-content: space-around;
          grid-template-columns: auto auto auto;
          grid-template-rows: auto auto auto auto;
        }


        .right-part{
          flex: 1 1 20%;
          border: 1px solid red;
          display: grid;
          justify-content: space-around;
          align-content: space-around;
          grid-template-columns: auto;
          grid-template-rows: 30% 60%;
        }

        #equal{
          height: 100%;
        }

        button{
          width: 50px;
          height: 50px;
        }



class Calc extends React.Component{
  constructor(){
    super()
    this.state = {
      display: ""
    }
  }
  
  handleClick(e){
    let val = e.target.textContent
    let display = this.state.display
    if(this.isNum(val)){
      this.handleNum(val, display);
    }else if(this.isDot(val)){
      this.handleDot(val, display);      
    }else if(this.isOperator(val)){
      this.handleOperator(val, display)
    }else if(this.isEqual(val)){
      this.handleCalc(display)
    }else if(this.isClear(val)){
      this.handleClear(display)
    }else{
      return 
    }
  }
  
  
        handleClear(display){ 
            this.setState({display: ""})
        }
        
        handleNum(v, display){
           this.setState({display: this.state.display+v})
        }

        handleOperator(v, display){
          let oldText = display
          if( oldText === "" ) return 
          if( this.isOperator(oldText[oldText.length-1]) )
              oldText=oldText.substr(0,oldText.length-1)
          this.setState({display: oldText+v})
        }

        handleDot(v, display){
          let oldText = display
          if( this.isDot(oldText[oldText.length-1]) ) return
          display.textContent += v
          this.setState({display: this.state.display+v})
        }

        
        handleCalc(display){
          let oldText = display
          if( !this.isNum(oldText[oldText.length-1]) ) {
            this.setState({display:0})
            return
          }
          this.setState({display: this.calc(oldText)})
        }
		
      calc( text ){
          let stack = []
          let numbers = text.split(/\+|\-|\×|\÷/)
          let operators =  text.replace(/[0-9]|\./g, "").split("")
          console.log(numbers)
          console.log(operators)

          stack.push(new Number(numbers[0]) )
          for( let i = 0; i < operators.length; i++ ){
            let num = new Number( numbers[i+1] )
            if(operators[i] === "+"){
              stack.push(num)
            }else if(operators[i] === "-"){
              stack.push(-num)
            }else if(operators[i] === "×"){
              let top = stack.pop()
              stack.push(top*num)
            }else if(operators[i] === "÷"){
              let top = stack.pop()
              stack.push(top/num)
            }
          }
          console.log(stack)
          return stack.reduce((item,accum)=>{
               return accum + item
          },0)
     }
        
    isNum(v){  return v >= "0" && v <= "9" }
    isClear(v){ return v === 'C' }
    isEqual(v){ return v === '=' }
    isDot(v){ return v === '.' }
	isOperator(v){ return v === '+' ||  v === '-' ||  v === '÷' ||  v === '×' }
  
  
  render(){
    return (
      <div className="wrapper"> 
      <div className="display-panel" id="display">{this.state.display}
      </div>
      <div className="ctl-panel" id="panel" onClick={(e)=>{this.handleClick(e)}}>
        <div className='left-part'>
            <div><button>+</button></div>
            <div><button>-</button></div>
            <div><button>&times;</button></div>
            <div><button>7</button></div>
            <div><button>8</button></div>
            <div><button>9</button></div>
            <div><button>4</button></div>
            <div><button>5</button></div>
            <div><button>6</button></div>
            <div><button>1</button></div>
            <div><button>2</button></div>
            <div><button>3</button></div>
            <div><button>0</button></div>
            <div><button>.</button></div>
            <div><button>C</button></div>
        </div>
        <div className='right-part'>
          <div><button>&divide;</button></div>
          <div><button id="equal">=</button></div>
        </div>
      </div>
    </div>
    )
  }
  
}


ReactDOM.render(<Calc />, document.getElementById('app'));

Mingkai Cao

All-trade Jack, loves full-stack

GitHub E-Mail

I. Problem

II. Solution

III. Complexity

I. Check undeclared, undefined or null

II. String

III. Number

IV. Array

V. Function

VI. Boolean

I. What is Trie

II. Use case

III. Implementation

Exclude items array according excludes array

Create chaining function

Cache expensive function execution

Polyfill Array.prototype.forEach

Polyfill Array.prototype.reduce

Closure: a comparison

Variable Hoisting

Type conversion: string to number

LeetCode: word break

Curry Function

Counting frequency of values in an object

Group objects by a certain property

Function composition enabling piping

Another composition / pipe example

Composition vs Inheritance

CSS: width:100% for parent with position:relative & position:absolute

Add, Remove& Toggle Classes With classList in JavaScript

add

contains

item

remove

toggle

I. Inherit height of outer div

II. Set mask to a div to disable it

I. Why do we need Promise - “callback hell”

II. Promise Usage

III. Promise: stateful utility object

VI. Write One!

V. Test Our Own Promise (stack overflow)

Credits to:

I. Selection Sort

II. Insertion Sort

III. Bubble Sort

VI. Merge Sort

V. Quick Sort

0. Credits to:

I. setTimeout

II. setInterval

III. Common Problems

Credits to:

Document flow

Margin Used in Domcument FLow

Positive Margin

Negative Margin

Use case of negative margin

Problem

Implementation

I. Check `undeclared`, `undefined` or `null`

Polyfill `Array.prototype.forEach`

Polyfill `Array.prototype.reduce`

CSS: `width:100%` for parent with `position:relative` & `position:absolute`

Add, Remove& Toggle Classes With `classList` in JavaScript

`add`

I. Inherit `height` of outer `div`

II. Set mask to a `div` to disable it

I. Why do we need `Promise` - “callback hell”

I. `setTimeout`

II. `setInterval`