Nan Chen

Brushes & Keys

Coding-Baking Photos-Paints

Template for Divided Conquer Algorithm

2020-05-21

Disclaimer

This article is originally based on my understanding of this concept. No guarantee on the accuracy.😅

Template:

1.base case
2.split to smaller sacle

(directly slice from the array otherwise maintain the index, and dynamically updated every call)
3.recursion
4.combination

(define the combination function and pass the returned value from recursion as parameter)

Let’s see the examples from easy to moderate

🌟 Search the max&min value

  function searchMaxMin(arr) {
      //the base case
        if (arr.length <= 2) {
          return [Math.max(...arr), Math.min(...arr)];
        }
      //split
        var mid = arr.length / 2 - 1;
        let left = arr.slice(0, mid + 1);
        let right = arr.slice(mid + 1, arr.length);
      //recursion
        var sortedLeft = searchMaxMin(left);
        var sortedRight = searchMaxMin(right);
//combination function
         const combine = (left, right) => {
          var result = [];
          result[0] = left[0] > right[0] ? left[0] : right[0];
          result[1] = left[1] > right[1] ? right[1] : left[1];
          return result;
        };
//combine the returned value
        return combine(sortedLeft, sortedRight);
      }
searchMaxMin([11,2,34,0,55,11])

🌟🌟 Merge Sorting

const mergeSort=arr=>{
    //the edge case
    if(arr.length<2) return arr;
     //split into smaller pieces
    let mid=Math.floor(arr.length/2);
    let left=arr.slice(0,mid),right=arr.slice(mid);
   //recursion
    let sortedLeft = mergeSort(left),sortedRight=(mergeSort(right));
    //combination function
    const merge=(left,right)=>{
    let res=[];
    while(left.length&&right.length){
        if(left[0]<=right[0]){
            res.push(left.shift());
        }else{
            res.push(right.shift());
        }
    }
    while(left.length){
        res.push(left.shift());
    }
    while(right.length){
        res.push(right.shift());
    }
    return res;
};
    //combine the returned value
    return merge(sortedLeft,sortedRight);
};
mergeSort([3, 1, 5, 0, 2]);

The call-stack would run in this sequence:

merge(mergesort(3,1),mergersort(5,0,2))
merge(mergesort(3),mergersort(1))
merge(left-3,right-1)
merge(mergesort(5),mergersort(0,2))
merge(mergesort(0),mergersort(2))
merge(left-0,right-2)
merge(left-5,right-0,2)
merge(left-1,3,right-0,2,5)

🌟🌟 Quick Sorting

function quick(nums) {
    //the base case
        if (nums.length <= 1) return nums;
    
        let mid = Math.floor(nums.length / 2);
        let pivot = nums.splice(mid, 1);
        let left = [],
          right = [];
    //break into two smaller array;
        for (num of nums) {
          if (num < pivot) left.push(num);
          if (num >= pivot) right.push(num);
        }
    //recursively pass the smaller sacle
    let sortedLeft =quick(left); 
    let sortedRight = quick(right);
    //combine the returned result
   return [...sortedLeft, ...pivot, ...sortedRight]; 
      }

Understanding Promise part 2

2020-05-16

Disclaimer

This article is originally based on my understanding of this concept. No guarantee on the accuracy.😅

‘The Promise object represents the eventual completion (or failure) of an asynchronous operation, and its resulting value.’

It was introduced to handle asynchronous operation like synchronous opeartion and avoid the callback hell.

doSomething(function(result) {
  doSomethingElse(result, function(newResult) {
    doThirdThing(newResult, function(finalResult) {
      console.log('Got the final result: ' + finalResult);
    }, failureCallback);
  }, failureCallback);
}, failureCallback);

Common asynchronous-operation

setTimeOut, setInterval
XHR request (fetch api)
Event Listening

Thansk to promise’s .then() chaining, we can put the callback outside：

doSomething()
.then(result => doSomethingElse(result))
.then(newResult => doThirdThing(newResult))
.then(finalResult => {
  console.log(`Got the final result: ${finalResult}`);
})
.catch(failureCallback);//error handler for all above!

*This all based on modern API that returning a promise. That is to say, the promise chains starts with an API function which returns a promise. *

We can create our own promise as well. Although it’s not typical practice but it can be helpful to ‘promisify’ some old callback-style API then chain the handler.

Let’s look at how a promise is created.

var promise = new Promise(
  //executor which runs immediately/sync:
  console.log('sync!')
  (res, rej)=>{
    // asynchronous operation. they will be put into the task queue
    //instead of returning something, it calls the callback as sideeffect to pass the result of asyn operation to res()/rej()
    if(somecodition) res(result); //once the promise is settled the state won't be changed
    rej(error)
    //then the res()/rej() can pass the result to the ousdie by chaining a .then()/.catch()
} 
  //the construcor return the new promise obj (of course)
);

An example of wrapping a callback-style function with Promise:

const wait = ms => new Promise(resolve => setTimeout(resolve, ms));
wait(10000).then(() => saySomething("10 seconds")).catch(failureCallback);
//template
new Promise(function (resolve, reject) {
            resolve(someSynchronousValue); 
}).then( /* ... */ );
//more simple and clear way
Promise.resolve(someSynchronousValue).then(
            /* recieve someSynchronousValue return value*/
);

Understanding Promise part 1

2020-05-16

Disclaimer

This article is originally based on my understanding of this concept. No guarantee on the accuracy.😅

Starting from a puzzle from this article:

doSomething().then(function () {
  return doSomethingElse();
});

doSomething().then(function () {
  doSomethingElse();
});

doSomething().then(doSomethingElse());

doSomething().then(doSomethingElse);
//note doSomething() and doSomethingElse() return a resolved promise

How would this code run?

To answer this puzzle, a few key points should be understood:

.then(callback) would ounly be put into the task queue when the chained promise was settled (fullfulled/resolved or rejected).

.then(callback) would pass the value returned from the callback to following .then/.catch

If there is no explicit return of the callback, returns undefined
If the callback returns a promise as well, the following .then()/.catch() would be thrown into the task queue, when it’s settled. After the current stack is cleaned, they would be pushed to the stack (run the callback). Even a promise has already settled, the .then() still runs asynchronously.
- ```
let p = Promise.resolve('resolved already')
p.then(v=>{console.loe('async result: '=v)})
console.log('cleaning stack')
//print 'cleaning stack' 'async result: resolved already'

```

if the callback returns a normal variable, the variable would be passed, and the state will be set to resolved.

a corner-case: if the callback returns obj which has a ‘then’ method, the following then() would run as the code in ‘then’ method.

 Promise.resolve({value: 1,
                  then: function (resolve) { //the following then call this function
                      console.log(this.value) //print 1.
                      resolve('then method in object') 
                    //resolve (or reject) function is a must，otherwise the following then would not be called, pending
                  })
           .then(value => {
              console.log('the result from pre .then:' + value); //print 'the result form pre .then: then method in object'
              }
          })
<!--2-->

But actually this is against the design of Promise whose aim is to avoid callback style but to chain the async exceutor outside the previous one. So it’d better update to this:

Class-based local storage

Sometimes when I was trying to build some small app, it’s really not neccessary to connect the app to the cloud database like mongoDB.

A local json file would be enough.

It provide basic CURD api. And it also allows customed repo by extending a new class from it.

//using node modules
const fs = require('fs');
const crypto = require('crypto');

module.exports = class Repository {
  constructor(filename) {
    if (!filename) { //filename validator
      throw new Error('Creating a repository requires a filename');
    }

    this.filename = filename;
    try { //if the repo exists, access it
      fs.accessSync(this.filename);
    } catch (err) { //if the repo doesn't exist, create one
      fs.writeFileSync(this.filename, '[]');
    }
  }

  async create(attrs) { //cerate new data entry
    attrs.id = this.randomId();
    const records = await this.getAll();
    records.push(attrs);
    await this.writeAll(records);
    return attrs;
  }

  async getAll() { //get all data
    return JSON.parse(
      await fs.promises.readFile(this.filename, {
        encoding: 'utf8'
      })
    );
  }
  async writeAll(records) {  //write file
    await fs.promises.writeFile(
      this.filename,
      JSON.stringify(records, null, 2)
    );
  }
  randomId() { //create an uniq id for each entry
    return crypto.randomBytes(4).toString('hex');
  }

  async getOne(id) { //get single data
    const records = await this.getAll();
    return records.find(record => record.id === id);
  }

  async delete(id) { //delete
    const records = await this.getAll();
    const filteredRecords = records.filter(record => record.id !== id);
    await this.writeAll(filteredRecords);
  }

  async update(id, attrs) { //update data
    const records = await this.getAll();
    const record = records.find(record => record.id === id);

    if (!record) {
      throw new Error(`Record with id ${id} not found`);
    }
    Object.assign(record, attrs);
    await this.writeAll(records);
  }

  async getOneBy(filters) { //filter data
    const records = await this.getAll();
    for (let record of records) {
      let found = true;
      for (let key in filters) {
        if (record[key] !== filters[key]) {
          found = false;
        }
      }
      if (found) {
        return record;
      }
    }
  }
};

A user repo:

A visual way to learn Closure

2020-04-29

Disclaimer

This article is originally based on my understanding of this concept. No guarantee on the accuracy.😅

The closure is a kind of intimidating concept for people new to javascript.
I think it’s necessary to clarify some concept of execution context (EC) and scope before approaching ‘closure’ itself.

Javascript has 3 types of scope (after ES6)
- block scope
  1
  2
  3
  4
  {
  let a = 0;
  }
  console.log(a) // ReferenceError: a is not defined
- Function scope
- Global scope

whenever you’re trying to call/use a variable, the engine would find it along the scope chain.

If the engine detects that a variable would not be called after the function execution context was removed from the call stack, it would junk the variable (garbage collecting) and free the memory.

The [[scope]] is determined during function declarartion.

All code is executed in their execution context: global EC or function EC.

EC can be abstracted as an object which includes variable object, scope chain, and this value.
Whenever a function is called, its EC would be pushed to the top of the call stack. And all the VO are activated as activation objects. When all the code inside the function is executed or returned, the EC was destroyed. Next time if the same function is called again, a new EC would be created.
The function EC has two phases: creation phase and execution phase.
The creation phase is when the VO and ‘this’ are created, and the scope chain is initialed by [[scope]]
The execution phase is when the value of each object/variable is assigned and determined.

closure

A classic interview question:

1 234

Brushes & Keys

Template for Divided Conquer Algorithm

Disclaimer

🌟 Search the max&min value

🌟🌟 Merge Sorting

🌟🌟 Quick Sorting

🌟🌟 169. Majority Element

Understanding Promise part 2

Disclaimer

Understanding Promise part 1

Disclaimer

To answer this puzzle, a few key points should be understood:

Class-based local storage

Class-based local storage

A visual way to learn Closure

Disclaimer

A classic interview question: