Longest common subsequence

This is a typical recursive problem. The pseudocode is:

If S1[i] == S2[j], lcs(S1[i:],S2[j:]) = 1 + lcs(S1[i+1:],S2[j+1:])
else lcs(S1[i:],S2[j:]) = max(lcs(S1[i:],S2[j+1:]), lcs(S1[i+1s:],S2[j:]))

Recursive solution:

int longestCommonSubsequence(string text1, string text2) {
    if(text1.size() == 0 || text2.size() == 0 ){
        return 0;
    }

    if(text1[0] == text2[0]){
        return 1 + longestCommonSubsequence(text1.substr(1, text1.size()-1), text2.substr(1, text1.size()-1));
    }

    return max(longestCommonSubsequence(text1, text2.substr(1, text1.size()-1)),
            longestCommonSubsequence(text1.substr(1, text1.size()-1), text2));
}

Time complexity: O(2^n) Using dp could store the state that already calculate before.

What is dp problem

DP problem is a programming strategy which use extra space to save time. These problems need to store some state instead of calculate again. For most situation, DP is a strategy to reduce the time consuming for recursive problem.

1. Memorization
2. Tabulation

fibonacci example

The classic recursive problem:

const fib = (n) => {
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
};

How to memorize :

Download

Go to this link

workspace

Run go env in terminal. The variable GOPATH is the default workspace path. Project should under this folder.

In this workspace, file should structured as how you route your project:

.
├── bin
├── pkg
└── src
    └── <The home web page of version control>
        └── <User name>
            └── <Project name>

Example:

Here have some good pictures that is helpful for understanding git and contain the record for git commend

Concept Map

Here is a concept map given by Udacity.com. This picture shows the relationship between these basic git concept.

Git Data Transport Map

Git have four working zones. This map shows that using which commend to shift your code from one zone to another.

Vuex Document: English 中文

Concept

• State - App-level state/data
• Getters - Get pieces of state or computed values from state
• Actions - Called from components to commit mutation (async)
• Mutations - Mutate the state (sync)
• Modules - Each module can have its own state, getters, actions and mutations

Work flow

Vuex work flow is similar with Redux => More Detail about Redux

Basic structure

In store/index.js

Vue Document: English 中文

life cycle

Basic structure

<template>
    <div></div>
</template>
<script>
    export default {
        name: '',
        props: [...],
        data() {
            return {};
        },
        computed:{
            ...
        }
        methods: {
            ...
        }
    };
</script>
<style lang="css"></style>

Basic vue function

v-bind

<option
    v-for="(user, idx) in Users"
    :key="idx"
    :value="user.id"
    @mousedown.prevent="multiSelectEvent"
    >{{ user.name }}</option
>

v-bind:value is equal to :value

You can read this Article to know What new feature brings in since ES6

Conversion

Any => Boolean

!!false; // false
!!undefined; // false
!!null; // false
!!NaN; // false
!!0; // false
!!''; // false

!!variable == Boolean(variable);

String => Integer

Number('100'); //100
+'100'; // 100

+'abc'; // NAN

Object <=> Array

Array => Object

let arr = [1, 2, 3, 4, 5];

let objFromArr1 = Object.assign({}, arr);

let objFromArr2 = { ...arr };

console.log(objFromArr1); // { '0': 1, '1': 2, '2': 3, '3': 4, '4': 5 }

console.log(objFromArr2); // { '0': 1, '1': 2, '2': 3, '3': 4, '4': 5 }

let pair = [
  ['key1', 'val1'],
  ['key2', 'val2'],
]; // Map works as well

let objFromPair = Object.fromEntries(arr); // ES10

console.log(objFromPair); //{ key1: 'val1', key2: 'val2' }

Object.fromEntries(arr) included in ES10 (ES2019). Before ES10 or convert a complex array, arr.reduce(()=>{}, {}) is a good method

This posts only use as a remainder

Variable

Multiple assignment

x, y, name, is_cool = (1, 2.5, 'a name', True)

Casting

x = str(x)
# x will be string
y = int(y)
# y will be an integer

String

name = 'Brad'
age = 37

print('name is' + name + ' and age is ' + str(age))
print('name is {name} and age is {age}'.format(name = name, age = age))
print(f'name is {name} and age is {age}')

Methods

# Capitalize string
print(s.capitalize())

# Make all uppercase
print(s.upper())

# Make all lower
print(s.lower())

# Swap case
print(s.swapcase())

# Get length
print(len(s))

# Replace
print(s.replace('world', 'everyone'))

# Count
sub = 'h'
print(s.count(sub))

# Starts with
print(s.startswith('hello'))

# Ends with
print(s.endswith('d'))

# Split into a list
print(s.split())

# Find position
print(s.find('r'))

# Is all alphanumeric
print(s.isalnum())

# Is all alphabetic
print(s.isalpha())

# Is all numeric
print(s.isnumeric())

List

A List is a collection which is ordered and changeable. Allows duplicate members.

chmod is linux command to control file permission

usage

chmod [u|g|o|a][=|+|-] [r|w|x]

u => user

g => group

o => other

a => all

r => read

w => write

x => execute

example

chmod +wr test.txt give write and read permission for user

chmod -r test.txt remove read permission for user

chmod g=wrx test.txt give write, read and execute permission for group

use number

specific the bits 011101110111 => -rwx-rwx-rwx

socket.io enable realtime, bidirectional communication for Nodejs

Backend

We use Express as backend framework.

const express = require('express');
const path = require('path');
const http = require('http');
const socket_io = require('socket.io');

const app = express();
const server = http.createServer(app);
const io = socket_io(server);

io.on('connection', (server_socket) => {
    // ...
}

Frontend

1. bring client side socket.io in your html file

<script src="/socket.io/socket.io.js"></script>

2. connect in your frontend script file

const clientSocket = io();

Function

Receive -> on()

socket.on('<head>', (data) => {
    // deal with data
});

Send -> emit()

socket.emit('<head>', data);

Send to all client socket except itself -> socket.broadcast.emit()

socket.broadcast.emit('<head>', data);

Sent to all client socket include itself -> io.emit()

io.emit('<head>', data);

Group socket together

socket.join('<name>');

Send to a group

socket.to('<name>').emit();
socket.broadcast.to('<name>').emit();
io.to('<name>').emit();