Leo-20180902.md

Leo Lei | 雷雨

Sep 02, 2018

1. Leetcode

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Analysis

The problem is equivalent to the problem of checking the existence of a cycle in a graph, i.e. check if a directed graph is a Directed Acyclic Graph (DAG). The algorithm is a modified version of DFS. Basically, there are three states for the nodes/vertices in the graph:

1. never been touched
2. in call stack, but not done visiting
3. done visiting (pop out of the stack) If the vertex is in call stack and has been visited twice, we know for sure there is a cycle starting and ending with the vertex.

For implementation, there can be different way to represent the states, e.g. coloring the vertex or use data containers to store vertices in different states.

Implementation

class Solution:
    # http://www.cs.princeton.edu/courses/archive/spring07/cos226/lectures/20DirectedGraphs.pdf
    # https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        from collections import defaultdict
        
        def build_graph(prerequisites):
            # map vertices to adjacency lists
            G = defaultdict(list)  
            for dst, src in prerequisites:
                G[src].append(dst)
            return G

        def DFS(u):
            """
            input: vertex in G
            return: no cycle exists in sub_G
            """
            if done[u]:
                return True
            
            # visit a node second time: find a cycle
            if checking[u]:
                return False
            
            checking[u] = True
            for v in G.get(u, []):
                if not DFS(v):
                    return False
            done[u] = True
            
            return True

        G = build_graph(prerequisites)
        checking = [False for _ in range(numCourses)]
        done = [False for _ in range(numCourses)]
        for src in G:
            if not DFS(src):
                return False
        return True

The slightly modified version of above algorithm can sort a DAG topologically. The order we mark the vertices as done is corresponding to the finish order of the vertices when visiting the graph. Such feature can be used to solve Course Schedule II.

2. Article and comment

Auth0 Architecture: Running In Multiple Cloud Providers And Regions

Highlights(excepted from the original article):

1. We went from processing a couple of million logins per month to 1.5+ billion logins per month, serving thousands of customers, including FuboTV, Mozilla, JetPrivilege, and more.
2. We implemented new features like custom domains, scaled bcrypt operations, vastly improved user search, and much more.
3. The number of services that compose our product in order to scale our organization and handle the increases in traffic went from under 10 to over 30 services.
4. The number of cloud resources grew immensely as well; we used to have a couple dozen nodes in one environment (US), now we have more than a thousand over four environments (US, US-2, EU, AU).
5. We doubled-down decided to use a single cloud provider for each of our environments and moved all our public cloud infrastructure to AWS.

3. New skill/tool

None

4. Share an article

Silicon Valley is changing, and its lead over other tech hubs narrowing, Economist, Sep 01, 2018

The reasons:

1. SV is too expensive for start-ups: rent, employee costs, etc.
2. new tech makes non-SV start-ups possible: remote working, etc.
3. Trump's anti-immigrate policy