Leo-20180909.md

Leo Lei | 雷雨

Sep 09, 2018

1. Leetcode

Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Output: "wertf"

Analysis

There are two parts involved in order to solve the problem: 1. understand the input, e.g. wrt is before wrf means t is before f for the aliens. 2. build a graph and sort the graph topologically.

Implementation

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        from collections import defaultdict, deque
        def build_G():
            G = defaultdict(set)
            for i in range(len(words) - 1):
                w1, w2 = words[i], words[i+1]
                for j in range(min(len(w1), len(w2))):
                        if w1[j] != w2[j]:
                            G[w1[j]].add(w2[j])
                            break
            return G
        
        G = build_G()
        visiting, done = set(), deque()
        def DFS(ch):
            if ch in done:
                return True
            if ch in visiting:
                return False
            visiting.add(ch)
            for child in G.get(ch, []):
                if not DFS(child):
                    return False
            done.appendleft(ch)
            return True
        
        # topological sort G  
        for ch in G:
            if ch not in visiting:
                if not DFS(ch):
                    return ""
                
        all_chs = set([ch for word in words for ch in word])
        return "".join(list(done) + [ch for ch in all_chs if ch not in done])

2. Article and comment

Google Developer: Inside look at modern web browser (part 1)

It's the 1st part of a 4-part blog that explains the details of Chrome's architecture.

Highlights:

1. Generally two architectures for browser: many threads in a big process(left) or multi-processes with a few threads(right) in each process. Chrome adopts a multi-process architecture: Browser process, Renderer process, Network process, Plugin process, etc

2. For each tab, render processes, along with many other processes, are created and assigned to each tab.

3. Pros and cons of multi-process arch a. pros: 1) one dead tab won't impact other tabs, 2) security and sandboxing b. cons: may use too much memo resource if too many processes been created. Each process often contains copies of common infrastructure. "This means more memory usage as they can't be shared the way they would be if they were threads inside the same process."

4. Servicification To save memory, Chrome is making architecture changes to run each part of the browser program as a service allowing to easily split into different processes or aggregate into one. In powerful hardware, Chrome may split each service into different processes. Otherwise, it consolidates services into one process saving memory.

5. Site isolation is enabled on desktop by default since Chrome 67. Each cross-site iframe in a tab gets a separate rendered process.

3. New skill/tool

None

4. Share an article

LinkedIn Top Startups 2018: The 50 most sought-after startups in the U.S.