Let’s start with a problem (src: leetcode#53)

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Constraints:
・ 1 <= nums.length <= 1e5
・ -1e4 <= nums[i] <= 1e4

Since subarray means to a contiguous non-empty sequence of elements within an array. It’s easy to find the trivial solution where we try to calculate all possible subarray.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN;
        for (int l = 0; l < nums.size(); ++l) {
            for (int r = l; r < nums.size(); ++r) {
                int sum = 0;
                for (int i = l; i <= r; i++) sum += nums[i];
                ans = max(ans, sum);
            }
        }
        return ans;
    }
};

The time complexity for this solution is $O(n^{3})$ which clearly impossible to be an AC solution. Then how to update that?

Start with the problem (src: leetcode#714)

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

How do we know it’s a Dynamic Programming (DP) problem? 💭

It’s based on your sense ;) But there are some signs that you can follow

Today I got a really nice chess puzzle that makes me review all of my knowledge, or even more important - the way I should think strategically. 🤔

via chess.com

The puzzle starts with black makes Na5, white to move.

To this day, what I have learned about chess strategies could be shortened into: seek to prevail. There are many shapes of prevail, that is:

• checkmate the opposite king
• gain the advantage in trading pieces (sacrifice)
• take the advantage of space (suppress, narrow the opponent’s scope of activity)
• promotion

Apply to the current situation, white wins one piece (a pawn which means 1 point but it’s just a gambit), a little bit advantage of space (a pawn in d5 followed by Bishop at c4), a bad move of black pawn f7. And on top of that, white has a strong Bishop - Bc4 which makes a threat to Kg8 indirectly.

Process and Thread

Process

Tiến trình có thể hiểu đơn giản là một chương trình đang chạy trong máy tính. Khi chúng ta mở một trang web trình duyệt thì đây được xem là một tiến trình. Khi chúng ta viết 1 chương trình máy tính bằng ngôn ngữ lập trình như C, Java, hay Go, sau khi tiến hành biên dịch và chạy chương trình thì hệ điều hành sẽ cấp cho chương trình một không gian bộ nhớ nhất định, PID (process ID),… Mỗi tiến trình có ít nhất một luồng chính (main thread) để chạy chương trình, nó như là xương sống của chương trình vậy. Khi luồng chính này ngừng hoạt động tương ứng với việc chương trình bị tắt.

The following list contains common time complexities of algorithms:

• O(1) The running time of a constant-time algorithm does not depend on the input size. A typical constant-time algorithm is a direct formula that calculates the answer.

• O($\log n$) A logarithmic algorithm often halves the input size at each step. The running time of such an algorithm is logarithmic, because $\log n$ equals the number of times n must be divided by 2 to get 1.

  Read more...

Bữa tối của các triết gia (dining philosophers problem) là một ví dụ nổi tiếng khi nhắc đến các vấn đề trong bài toán xử lý concurrent.

Vấn đề được phát biểu như sau: Cho 5 triết gia ngồi chung một bàn tròn với 5 chiếc đũa xếp xem kẽ giữa 2 người ngồi cạnh nhau như hình

img: sphof.readthedocs.io

Mỗi triết gia tìm cách để ăn được thức ăn từ đĩa của mình với điều kiện: “chỉ ai có 2 chiếc đũa cạnh mình mới được phép ăn”, do đó họ lần lượt đổi trạng thái giữa ăn (eating) và đợi (thinking) :)) Mỗi người sau khi giữa đôi đũa để ăn sau 1 khoảng thời gian phải bỏ lại 2 chiếc đũa về vị trí cũ để tiếp tục quá trình này. Yêu cầu: tìm một phương pháp đảm bảo để các triết gia đều có thể đk ăn / đợi đổi lượt để không ai bị chết đói (chỉ đợi chứ không được ăn).

Every Go programmer knows about the receiver in go, which be declared as:

type X struct {}

func (receiver X) doThing() {...}

We have two types of receiver in Golang, which is Value receiver and Pointer receiver. Basically, the receiver in Golang could be map to self in other programming languages and the function which uses the receiver will be pointed from struct type of the receiver.

So, what does this means, anyway?

Difference between Imperative languages and Functional languages:

• Imperative languages are based on assignment sequences whereas functional languages are based on nested function calls.

• In imperative languages, the same name may be associated with several values, whereas in functional languages a name is only associated with one value.

• Imperative languages have fixed evaluation orders whereas functional languages need not.(1)

• In imperative languages, new values may be associated with the same name through command repetition whereas in functional languages new names are associated with new values through recursive function call nesting.

  Read more...

Some boundaries you should know to approximate time and space complexity of your algorithm.

• $2^{10} = 1,024 \approx 10^{3}, 2^{20} = 1,048,576 \approx 10^{6}$
• 32-bit signed integers (int) and 64-bit signed integers (long long) have upper limits of $2^{31} − 1 \approx 2 \times 10^{9}$ (safe for up to $\approx 9$ decimal digits) and $2^{63} − 1 \approx 9 \times 10^{18}$ (safe for up to $\approx 18$ decimal digits) respectively.
• Unsigned integers can be used if only non-negative numbers are required. 32-bit unsigned integers (unsigned int) and 64-bit unsigned integers (unsigned long long) have upper limits of $2^{32} − 1 \approx 4 \times 10^{9}$ and $2^{64} − 1 \approx 1.8 \times 10^{19}$ respectively.
• There are $n!$ permutations and $2^{n}$ subsets (or combinations) of n elements.
• The best time complexity of a comparison-based sorting algorithm is $Ω(n\log_{2}{n})$.

Notes:

Một điều được nhắc đến rất nhiệu khi chuyển từ sql sang nosql là cách để lưu trữ quan hệ giữa các đối tượng trong database. Một đối tượng thường rất ít khi tồn tại độc lâp trong một hệ thống mà nắm giữ 1 phần thông tin được sử dụng để tạo ra một đối tượng khác.

Các dạng quan hệ chính giữa các đối tượng có thể lưu được trong cơ sở dữ liệu quan hệ bao gồm