27 Dec 2018

ARTS-Week8

ARTS weekly

[


                    ARTS


                    leadership

DP


                    backtrace

PKI


                    rsync

]

Algorithm

Problem

[22] Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Thought

This problem can be classified to the classical 0-1 package problem, and absolutely can be solved using the backtrace method.

For simplicity, assume that ‘0’ stands for left parenthesis, and ‘1’ the right parenthesis, and the dimension of this problem is written as dim(n).

Given n, the solution space constructs a not-full binary tree, content of which is eithor a ‘0’ or ‘1’.

Dynamic Planning

In this section, we try to solve this problem using DP method.

It’s obvious that a well-formed parentheses will always start with ‘(‘ and end with ‘)’.

If we want to sovle dim(n) problem, we can solve dim(n-1) problem first.

Following graph demonstrates how to construct the dim(n) solution with dim(n-1) results.

If the dim(n) parentheses starts with ‘()’, then we could append the dim(n-1) results to ‘()’. Otherwise, the dim(n) parentheses starts with ‘((‘, it will be more complex, and we will explain this situation with more detail.

Lemma 1: Substring of a well-formed parentheses, which is constructed excluding the first and last character, will also be a well-formed parentheses, and with dimension lesser by 1.

Based on Lemma 1, we can get to the point that there will definitely exist a pair of ‘))’ which composes a closed form with the beginning ‘((‘.

Thus, we can construct a special ‘(‘ with ‘((‘, the same to ‘)’. Then, the dim(n) problem reduced to a dim(n-1) problem.

So how could we recover a dim(n) solution through dim(n-1) results?

Iterate through each of the dim(n-1) results, and substitute the ‘)’ with ‘))’. Caution that if continuous ‘)’ occurred, we should only substitute the first occurrence.

Above substitution method has the possibility to get the same result, so we have to check repeatance before insert a candidate to the container.

The final solution is as follows:

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res(0);

        if(n == 1)
        {
            vector<string> res(0);
            res.push_back("()");
            return res;
        }
        else
        {
            vector<string> resn(0);
            for(auto& item : generateParenthesis(n - 1))
            {
                // start with "(("
                for (int i = 1; i < item.size(); ++i)
                {
                    if(item[i] == ')' && item[i - 1] == '(')
                    {
                        // possible candidate
                        string new_item_0_0 = item;
                        new_item_0_0.insert(i, ")");
                        new_item_0_0.insert(0, "(");

                        // avoid repeat candidate
                        auto result = find(resn.begin(), resn.end(), new_item_0_0);
                        if(result == resn.end())
                        {
                            resn.push_back(new_item_0_0);    
                        }
                    }
                }
                
                // start with "()"
                string new_item_0_1 = "()";
                new_item_0_1 += item;
                resn.push_back(new_item_0_1);
            }
            
            return resn;
        }   
    }
};

Back trace

It’s easy to understand, so donot waste our breath to explain it.

class Solution {
public:

    void backTrack(vector<string>& ans, string cur, int open, int close, int max)
    {
        if(cur.length() == max * 2)
        {
            ans.push_back(cur);
            return;
        }
        
        if(open < max)
        {
            backTrack(ans, cur+"(", open+1, close, max);
        }
        
        if(close < open)
        {
            backTrack(ans, cur+")", open, close+1, max);
        }
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> ans(0);
        backTrack(ans, "", 0, 0, n);
        
        return ans;
    }

};

Review

Nowadays, HTTPS and TLS has been the trend and a must-have on the internet, especially for financial and e-commerce companpies which want to provide service through the WEB.

Do you know how the client and server make a safe communication? It all owns to PKI, the hero behind our safe surfing on the internet.

This article(Everything you should know about certificates and PKI but are too afraid to ask) takes you through what PKI is, using plain words.

There are some technical terms to explain first:

Entity: include everything, subscriber or a replying party is also an entity.
Subscriber: an entity that has a certificate.
Certificate authority (CA): authority to issue a certificate.
Relying party: an user who want to use a certificate.

Certificates are like driver’s licenses or passports for computers and code. It let you use trust, and knowledge of an issuer’s public key, to learn another entity’s public key.

Usually when people talk about certificates without additional qualification they’re referring to X.509 v3 certificates. It’s widely used on the internet.

A PEM-encoded X.509 v3 certificate looks like:

Public key infrastructure (PKI) is the umbrella term for all of the stuff we need in order to issue, distribute, store, use, verify, revoke, and otherwise manage and interact with certificates and keys.

Tip

A little trick about syncing files with remote, through which you can specify a file pattern:

rsync -a --prune-empty-dirs --include '*/' --include '*.txt' --exclude '*' /path/to/remote /path/to/local

--prune-empty-dirs: prune empty directory chains from file-list

--include '*/' --include '*.txt' --exclude '*': example pattern, which only sync txt files, but still retain the folder tree structure.

Today, I would like to share two articles about leadership, and it may benefit you in your daily life and work.

The authors of these two have nearly same opinion on leadership.

The first one developed an idea that I can not agree any more, and I quoted it here:

Leadership is not tied to a position. Leadership is a mindset.

And the second one:

Look, being a leader has nothing to do with your job. Leadership is a character trait that we can all cultivate. In fact, I believe leadership is one of the essential skills that every person should have.

The first article listed some useful tips about how to act as a good leader. They are all based on real situations, and may do good to you. For detail explanation, please refer to the initial article.

Leading by teaching
Leading by example
Leading by setting high standards
Leading by communication
Leading by giving credit
Leading through coding reviews
Leading by going into hard conversations

The second article wrote some personal experience about being a good leader. It said that:

Only expect from others what you expect from yourself
Respect others and don’t try to change them or tell them what to do
And other tips…

These two really inspire me, and great thanks to them.

Article source: