客观准备

首先是环境因素: 温度和光强，温度控制在72、73华氏度，光的话尽量全黑。
Bedroom Setup: 被子需要和外界温度适应，如果低于5度我会加一个薄被子在脚上。枕头，非常重要，我尝试过所谓很好的枕头，但是不适合，我发现的原因是我那一周的睡眠质量下降了很多。比较适合软硬始终，偏软一点点，蓬松那一类型的被子。
睡前准备: 90分钟法则，也即睡前九十分钟不从事会让人激动兴奋的活动。其二，保持自己的睡前routine，吃好维生素片，写日记，看书，然后一有困意就睡觉。
用睡眠app去监控我的睡眠，这样就可以用数据衡量自己的睡眠质量而非“感觉”。

主观认知

我曾经对于睡眠很不自信，然后会担心睡眠影响我的performance，这种想法造成了许多焦虑和压力反而让睡眠更差，这时候回到监测那一点，这就是工具能带来的，客观认识自己的睡眠质量。

所以，睡眠对于performance重要，但也没那么重要。

Review of Alice in Borderland

Posted on 2023-01-08 In Video Works Reviews

弥留之国的爱丽丝刷完了，最后一集四倍速看的，四倍速真是刷剧的一剂良药，能够捕捉到一切信息又能节省大量时间。

关于这个国度的悬念终于揭晓了，弥留之际的梦境真是一种偷懒取巧的做法啊。但故事铺陈堆叠到现在，也想不到更好的解法了。梦境真是万能。

但弥留之际的梦境的确讲得通，这些玩家在游戏中反反复复的询问活着的理由，人生的意义，自己的理想，而只有那些有答案的或是说有执念的活了下来。

总的来说，大团圆结局俗套，但在这部剧弥留之国很合适。

观世界

世界是以一种严格的理性运行的，其中掺杂许多不同元素：善恶，是非，情绪，感性等等等等，但本质，是一种严格的理性。

世界的底色是理性，但不代表无趣，其理性含有对真善美的支持，对智慧的推崇，对灵魂的关怀，对恶的存在的必要，善恶是非的无限变化。

我对于世界观的思维模式

是一种自适应模式，adaptive。基于过去经历，此时境遇来得出客观结论，达到与现实和自我的平衡。

主义

基于唯物主义的唯心主义。但两种融合的话怎么叫“唯”呢，一半一半，半殖民地半封建（不是。

我是个怎样的人

我是个认准一件事情后，会反复去努力的人，一直重复。喜欢的菜，餐馆，音乐，都会在一段时间反复的光顾。不过最近也在领悟给自己生活加入新元素新想法的道理。

情感比较充沛。

Database Sys Lec2 Intermediate SQL

Posted on 2021-01-21 In Computer Science

Lecture #2: Intermediate SQL

RELATIONAL LANGUAGES

User only needs to specify the answer that they want, not how to compute it.

The DBMS is responsible for efficient evaluation of the query.

→ High-end systems have a sophisticated query optimizer that can rewrite queries and search for optimal execution strategies.

Data Manipulation Language (DML)
Data Definition Language (DDL)
Data Control Language (DCL)

Also includes:

→ View definition

→ Integrity & Referential Constraints

→ Transactions

Important: SQL is based on bags (duplicates) not sets (no duplicates).

Outline

Aggregations + Group By
String / Date / Time Operations
Output Control + Redirection
Nested Queries
Common Table Expressions
Window Functions

Aggregates

Functions that return a single value from a bag of tuples:

→ AVG(col)→ Return the average col value.

→ MIN(col)→ Return minimum col value.

→ MAX(col)→ Return maximum col value.

→ SUM(col)→ Return sum of values in col.

→ COUNT(col)→ Return # of values for col.

Aggregate functions can (almost) only be used in the SELECT output list.

DISTINCT AGGREGATES: COUNT, SUM, AVG support DISTINCT

Output of other columns outside of an aggregate is undefined.

GROUP BY

Project tuples into subsets and calculate aggregates against each subset.

Non-aggregated values in SELECT output clause must appear in GROUP BY clause.

HAVING

Filters results based on aggregation computation. Like a WHERE clause for a GROUP BY

STRING OPERATIONS

LIKE is used for string matching.

String-matching operators

→‘%’ Matches any substring (including empty strings).

→‘_’ Match any one character

SQL-92 defines string functions.

→ Many DBMSs also have their own unique functions

Can be used in either output and predicates

SQL standard says to use || operator to concatenate two or more strings together.

DATE/TIME OPERATIONS

Operations to manipulate and modify DATE/TIME attributes.

Can be used in either output and predicates.

Support/syntax varies wildly…

OUTPUT REDIRECTION

Store query results in another table:

→ Table must not already be defined.

→ Table will have the same # of columns with the same types as the input.

Insert tuples from query into another table:

→ Inner SELECT must generate the same columns as the target table.

→ DBMSs have different options/syntax on what to do with integrity violations (e.g., invalid duplicates).

OUTPUT CONTROL

ORDER BY [ASC|DESC]

→ Order the output tuples by the values in one or more of their columns.

LIMIT [offset]

→ Limit the # of tuples returned in output.

→ Can set an offset to return a “range”

NESTED QUERIES

Queries containing other queries.

They are often difficult to optimize.

Inner queries can appear (almost) anywhere in query.

ALL→ Must satisfy expression for all rows in the sub-query.

ANY→ Must satisfy expression for at least one row in the sub-query.

IN→ Equivalent to ‘=ANY()’ .

EXISTS→ At least one row is returned.

WINDOW FUNCTIONS

Performs a “sliding” calculation across a set of tuples that are related.

Like an aggregation but tuples are not grouped into a single output tuples.

The OVER keyword specifies how to group together tuples when computing the window function.

Use PARTITION BY to specify group.

You can also include an ORDER BY in the window grouping to sort entries in each group.

COMMON TABLE EXPRESSIONS

Provides a way to write auxiliary statements for use in a larger query.

→ Think of it like a temp table just for one query.

Alternative to nested queries and views.

Database Sys Lec1: Course Overview and Relational Model

Posted on 2021-01-21 Edited on 2021-01-20 In Computer Science

Lecture #1: Course Intro & Relational Model

Course Outline

Relational Databases
Storage
Execution
Concurrency Control
Recovery
Distributed Databases
Potpourri

Databases

DATABASE

Organized collection of inter-related data that models some aspect of the real-world.

Databases are core the component of most computer applications.

DATABASE MANAGEMENT SYSTEM

A DBMS is software that allows applications to store and analyze information in a database.

A general-purpose DBMS is designed to allow the definition, creation, querying, update, and administration of databases.

DATA MODELS

A data model is collection of concepts for describing the data in a database.

A schema is a description of a particular collection of data, using a given data model.

DATA MODEL

Relational
Key/Value
Graph
Document
Column-family
Array / Matrix
Hierarchical
Network
Multi-Value

RELATIONAL MODEL

Structure: The definition of the database’s relations and their contents. 数据库关系及其内容的定义。

Integrity: Ensure the database’s contents satisfy constraints.

Manipulation: Programming interface on how to access and modify a database’s contents.

A relation is unordered set that contain the relationship of attributes that represent entities.

A tuple is a set of attribute values (also known as its domain) in the relation.

→ Values are (normally) atomic/scalar.

→ The special value NULL is a member of every domain.

RELATIONAL MODEL: PRIMARY KEYS

A relation’s primary key uniquely identifies a single tuple.

Some DBMSs automatically create an internal primary key if a table does not define one.

Auto-generation of unique integer primary keys:

→ SEQUENCE (SQL:2003)

→ AUTO_INCREMENT (MySQL)

RELATIONAL MODEL: FOREIGN KEYS

A foreign key specifies that an attribute from one relation has to map to a tuple in another relation.

DATA MANIPULATION LANGUAGES (DML)

Methods to store and retrieve information from a database.

Procedural:

→ The query specifies the (high-level) strategy the DBMS should use to find the desired result.

Non-Procedural:

→ The query specifies only what data is wanted and not how to find it.

.png)

RELATIONAL ALGEBRA

Fundamental operations to retrieve and manipulate tuples in a relation. → Based on set algebra.

Each operator takes one or more relations as its inputs and outputs a new relation.

→ We can “chain” operators together to create more complex operations.

SELECT

Choose a subset of the tuples from a relation that satisfies a selection predicate.

PROJECTION

Generate a relation with tuples that contains only the specified attributes.

UNION

Generate a relation that contains all tuples that appear in either only one or both input relations.

INTERSECTION

Generate a relation that contains only the tuples that appear in both of the input relations.

DIFFERENCE

Generate a relation that contains only the tuples that appear in the first and not the second of the input relations.

PRODUCT

Generate a relation that contains all possible combinations of tuples from the input relations.

JOIN

Generate a relation that contains all tuples that are a combination of two tuples (one from each input relation) with a common value(s) for one or more

attributes.

OBSERVATION

Relational algebra still defines the high-level steps of how to compute a query.

A better approach is to state the high-level answer that you want the DBMS to compute.

→ Retrieve the joined tuples from R and S where b_id equals 102.

因为relational algebra还是对于人类来说太抽象，所以有了query语言

RELATIONAL MODEL: QUERIES

The relational model is independent of any query language implementation.

SQL is the de facto standard (many dialects).

CONCLUSION

Databases are ubiquitous.

Relational algebra defines the primitives for processing queries on a relational database.

We will see relational algebra again when we talk about query optimization + execution.

Leetcode Weekly Contest 204

Posted on 2020-08-30 Edited on 2020-08-29 In Competitive Programming , Algorithm

Overview

Rank: 599/13949

Score: 13(Q1~3)

Finish Time: 0:51:39

This contest is interesting. Q3 is tricky and Q4 is worth trying.

Q2 Maximum Length of Subarray With Positive Product

https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/

This is a typical dp problem. When it’s about max/min length of subarray, you can try to use dynamic programming and define dp array like the max/min length ending with index i.

My solution is below. O(n) for time complexity and O(n) for space complexity.

But we can easily improve it into O(1) space complexity.

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0, 0] for _ in range(n)]
        
        if nums[0] > 0: dp[0][0] = 1
        elif nums[0] < 0: dp[0][1] = 1
        
        for i in range(1, n):
            if nums[i] == 0:
                continue
            elif nums[i] > 0:
                dp[i][0] = dp[i - 1][0] + 1
                dp[i][1] = dp[i - 1][1] + 1 if dp[i - 1][1] > 0 else 0
            else:
                dp[i][0] = dp[i - 1][1] + 1 if dp[i - 1][1] > 0 else 0
                dp[i][1] = dp[i - 1][0] + 1
        
        return max([x[0] for x in dp])

Q3 Minimum Number of Days to Disconnect Island

https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/

This one is really tricky.

At first it feel like we need to find the bridge and use algorithm like Tarjan. But then I find that the result of days will not be greater than 2! Just think about corner of connected component.

Thus we just need to enumerate 0, 1, 2 this three condition.

0 means there are multiple island. 1 means we can delete one ‘1’ and it’s not fully connected. Use bfs to check that. If it’s not 0 nor 1, then it must be 2!

Below is my solution. O(m^2*n^2) for time and space complexity.

from collections import deque
class Solution:
    def minDays(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        cnt_ones = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    cnt_ones += 1
        
        if cnt_ones == 0: return 0
        elif cnt_ones == 1: return 1
        
        bfs_cnt = self.bfs(grid)
        if bfs_cnt != cnt_ones: return 0
        
        # whether only use 1 day
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    grid[i][j] = 0
                    bfs_cnt = self.bfs(grid)
                    if bfs_cnt != cnt_ones - 1: return 1
                    grid[i][j] = 1
        return 2
                    
    def bfs(self, grid):# return cnt of ones
        m, n = len(grid), len(grid[0])
        start = None
        move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    start = (i, j)
                    break
            if grid[i][j]: break
        
        queue = deque([start])
        visited = set()
        visited.add(start)
        
        while queue:
            x, y = queue.popleft()
            for dx, dy in move:
                nx, ny = x + dx, y + dy
                if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny]): continue
                np = (nx, ny)
                if np in visited: continue
                queue.append(np)
                visited.add(np)
        
        return len(visited)

Q4 Number of Ways to Reorder Array to Get Same BST

https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/

This one is interesting and not that hard. Actually I got the right approach and feelings but messed up some parts.

“When it comes to BST, this about root and its left and right child’s relationship.”

This problem is also following that thinking.

It’s about how many reorder of left and right and how many ways to combine left and right’s order nums!

Below is the implementation. Not sure about time and space complexity.

from math import comb
class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        mod = 10 ** 9 + 7
        def cnt(nums):
            n = len(nums)
            if n <= 1: return n
            left = [x for x in nums if x < nums[0] ]
            right = [x for x in nums if x > nums[0]]
            
            left_cnt, right_cnt = cnt(left), cnt(right)
            # in case there are 0 for cnt
            if not left_cnt: return right_cnt
            if not right_cnt: return left_cnt
            
            return (comb(len(left) + len(right), len(right)) * left_cnt * right_cnt) % mod
            
        return cnt(nums) - 1

80 Percent of Cpp

Posted on 2020-08-23 Edited on 2020-08-25 In Programming language

Updating

Binary Tree Traversal

Posted on 2020-08-22 Edited on 2020-08-23 In Algorithm

In this article we will discuss two approaches to do binary tree traversal: recursion based and stack based.

In general, these two approach have their own strengths and weaknesses. The recursion ones are easy to understand and implement however might cause stack overflow. The stack based are more efficient in terms of memory but hard to understand and more complex to implement compared to recursion based approach. Normally on a coding interview, the interviewer prefers stack based binary tree traversal.

We will discuss four types of binary tree traversal:

Preorder Traversal https://leetcode.com/problems/binary-tree-preorder-traversal/
Inorder Traversal https://leetcode.com/problems/binary-tree-inorder-traversal/
Postorder Traversal https://leetcode.com/problems/binary-tree-postorder-traversal/
Level Order Traversal https://leetcode.com/problems/binary-tree-level-order-traversal/

Binary Tree Preorder Traversal

Recursion based

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.helper(root, res)
        return res
    
    def helper(self, root, res):
        if not root: return
        
        res.append(root.val)
        self.helper(root.left, res)
        self.helper(root.right, res)
        return

Stack based:

How to derive a stack-based solution?

For preorder traversal, it’s root->left->right. So for any node, we first get its value and then check if it has left child. If so, we goes into left child. Until it’s none. If it’s none, we want to check it’s right child.

Remember after visited left child we want to visit its right child. That why we need stack.

“For each node, it is root to itself.”

For any node the detailed steps are:

1) Get its value, store the node into stack and goes to its left child

2) If left child is none then pop the stack and goes into its right child. If left child is valid then continue step 1

Universal one:

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stk = []
        res = []
        tmp = root
        while tmp or stk:
            if tmp:
                res.append(tmp.val)
                stk.append(tmp)
                tmp = tmp.left
            else:
                tmp = stk.pop()
                tmp = tmp.right
        return res

Special yet simple one:

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        res = []
        stk = [root]
        while stk:
            tmp = stk.pop()
            res.append(tmp.val)
            if tmp.right:
                stk.append(tmp.right)
            if tmp.left:
                stk.append(tmp.left)
        return res

Binary Tree Inorder Traversal

Recursion based:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.helper(root, res)
        return res
    
    def helper(self, root, res):
        if not root: return
        self.helper(root.left, res)
        res.append(root.val)
        self.helper(root.right, res)
        return

Stack based:

How to derive a stack-based solution?

For inorder traversal, it’s left->root->right. So for any node, we check if it has left child. If so, we goes into left child. Until it’s none. If it’s none, we want to get back to node gets its value and check it’s right child.

Remember after visited left child we want to visit itself.

“For each node, it is root to itself.”

For any node the detailed steps are:

1) Store the node into stack and goes to its left child

2) If left child is none then pop the stack, gets the node’s value and goes into its right child. If left child is valid then continue step 1

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res, stk = [], []
        tmp = root
        while tmp or stk:
            if tmp:
                stk.append(tmp)
                tmp = tmp.left
            else:
                tmp = stk.pop()
                res.append(tmp.val)
                tmp = tmp.right
        
        return res

Binary Tree Postorder Traversal

Recursion based:

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.helper(root, res)
        return res
    
    def helper(self, root, res):
        if not root: return
        self.helper(root.left, res)
        self.helper(root.right, res)
        res.append(root.val)
        return

Stack based:

How to derive a stack-based solution?

Can’t use the universal template for preorder and inorder. Because it’s left->right->root, the root is the last one to visit. It’s useless to use stack. Because when we pop a node from stack, it’s root to itself.

This one is harder than others. But we have a tricky solution. We just traverse tree in root-right-left order. And return the reversed result is the correct answer!

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res, stk = [], []
        tmp = root
        while tmp or stk:
            if tmp:
                res.append(tmp.val)
                stk.append(tmp)
                tmp = tmp.right
            else:
                tmp = stk.pop()
                tmp = tmp.left
        
        return res[::-1]

Binary Tree Level Order Traversal

This one we use queue and breadth first search instead.

Recommend you look https://lavidal.github.io/2020/08/06/Breadth-First-Search/ for the idea and solution!

80 Percent of Go

Posted on 2020-08-19 Edited on 2020-08-22 In Programming language

Go is expressive, concise, clean, and efficient. Its concurrency mechanisms make it easy to write programs that get the most out of multicore and networked machines, while its novel type system enables flexible and modular program construction. Go compiles quickly to machine code yet has the convenience of garbage collection and the power of run-time reflection. It’s a fast, statically typed, compiled language that feels like a dynamically typed, interpreted language.

—https://golang.google.cn/doc/

Updating

89感

Posted on 2020-08-09 In 随感

假期以来，学习上的进步不大，倒是做饭和弹琴越来越熟练。

这个假期感触最大的一点是，一切问题都源于身体，而我的一切身体问题其实就是睡得好不好的问题。上学期天天熬夜的习惯延续到了六月和七月，整天状态不好。而我状态不好的时候喜欢自己兜着，于是造成沉默的假象hh。但七月末调整睡眠之后，其实整个人的状态就会好很多。

想来自己也是悟得慢，毛主席说过的身体是革命的本钱，竟然现在才切身体会到。不过自己二十岁才学会洗头这件事儿，也符合我的特点了。洗头洗的是头皮而非头发，知道了才明白之前为何总洗不干净。吐槽完毕。

前几天完整看了人生中的第二部恐怖片：咒怨。老司机觉得平淡无奇，但是作为这块的新手，还是觉得恐怖的。看完后已是凌晨五点，熬夜的感觉就是很后悔，身体很难受。那天晚上是开着灯睡的，因为自己总会想到刚刚看到的电影，真是。依然是个大男孩，和第一次看完恐怖片一样，整个人紧张的不行。以后也别逞强看恐怖片了，真不合适。

这一周追乐队的夏天，有个人给我的印象很深，重塑的华东老师。不知道是节目组剪辑的问题还是人本身就这样，华东给我的第一感觉很不好。觉得这人特别装，高人一等的感觉。但是看到后面，觉得他确实有实力，装可能只是给我们的感觉，他真实的一面就是很严谨的。他说他不相信灵感，他认为创作音乐应该是想搭积木一样按照一个规律先做框架然后加其他东西。作为理工男倒是能理解这种思维。这只乐队是真的很独特。

乐夏另一个impressive的乐队是白皮书，子健评价说他们的歌段落与段落之间不是平滑过渡的，而是尖锐的直角。我没听出来，音乐乐理还得学。

吉他最近在尝试认识指板fretboard，想把上边所有的音记住。之前学的la指型，mi指型全忘了，真是无总结便无记忆。看了很多John Mayer的live视频，我最喜欢的美国歌手之一，最喜欢的吉他手。live演奏太帅了，solo两分钟，才华横溢。有些歌曲，你不看歌词，会觉得这首歌曲无感，但看了歌词就越听越好听。Slow dancing in a burning room就是这样一首歌，编曲好听，歌词更是romantic。歌名slow dancing in a burning room，这个意象真是妙，太浪漫了的一首slow rock了。

看张一鸣说他的大学收获，说的是耐心，读书，修电脑。真是搞技术的榜样，前两点还是很有借鉴意义的。耐心这点，我突然想到心流这个词，我总觉得其实没有所谓的耐心这一说，之所以能够专心的持续做一件事，是因为做事的过程中，已经沉浸在了心流之中。正所谓物我两忘。黑镜：潘达斯奈基这部里男二号也对男主说了心流这个词。“How do you get into flow?” 你怎么进入心流？很可惜电影并没能给出建设性意见。

马上要开始全职申请季了，陈绮贞说过人们总是对未发生的事情充满各种想象的恐惧，这或许是焦虑的来源。接下来好好学习，好好看书，好好练琴罢。