Edward FANG's Blog

很久没发博客文章了，最近想重新捡起来，因为觉得自己总是输入不输出不是一个很好的学习习惯，祝大家虎年快乐。最近总算是读完了 Happy Money 这本书，这本书是之前在 Madison 短租房子的时候前租户留下的，作者是 Elizabeth Dunn 和 Michael Norton。正好当时也有些迷失，但是有开始了自己的全职工作，就想好好思考一下如何花钱让自己最开心。现在看完了这本书，也算是有所共鸣有所学习，在这里记录分享一下。

博主本人今年年底即将从 UWMadison 毕业，在此记录一下自己对这个小众的 Professional Master 的 Program 的介绍，方便后人借鉴参考。本文主要会介绍 UW-Madison 生活体验，以及该 Program 给笔者带来的收益，以及最重要的，找工作的情况。

春假相对有空，抽点时间记录下总算告一段落的夏季实习申请。这次的实习申请算是比较艰辛，但也算是上岸了以及可能是自己以后想发展的方向。在这里总结并记录下来找实习的历程，方便后人参考以及为自己找全职提供借鉴。

In this post I will mainly talk about some enrollment tips for future new Chinese students to UW-Madison. Some tips also are also applicable to students to other U.S. Universities.
本文主要介绍一些入学前准备工作给一些未来可能来麦屯的中国同学，其中一些 Tips 可能也适用于其他美国学校。

In this post I will give some algorithm problem from Google OA as well as Leetcode and my thoughts on them.
Our main problem here will be the OA problem appeared in the OA practice of Google Intern 2020 Online Assesment.

Problem Description

Problem Removed due to DMCA issue.

Thoughts

Original Problem

Patience. Deal cards $c_1, c_2, …, c_n$ into piles according to two rules:

• Can’t place a higher-valued card onto a lowered-valued card.
• Can form a new pile and put a card onto it.
  Goal. Form as few piles as possible.

Dual Problem

The dual problem for this is Longest increasing subsequence. And the Problem is defined as: Given a sequence of elements $c_1, c_2, …, c_n$ from a totally-ordered universe, find the longest increasing subsequence.

Duality Proof

• Greedy Algorithm
• Place each card on leftmost pile that fits.
• Observation. At any stage during greedy algorithm, top cards of piles increase from left to right.
• Weak duality.
• In any legal game of patience, the number of piles ≥ length of any increasing subsequence.
• Proof.
  1. Cards within a pile form a decreasing subsequence.
  2. Any increasing sequence can use at most one card from each pile.
• Strong duality
• [Hammersley 1972]Min number of piles = max length of an IS; moreover greedy algorithm finds both.
• Proof.
  Each card maintains a pointer to top card in previous pile at time of insertion.
  1. Follow pointers to obtain IS whose length equals the number of piles.
  2. By weak duality, both are optimal.

Conclusion
The length of longest increasing subsequence is equal to the smallest number of decresing subsequences.

Solution

Greedy Algorithm + Binary Search Algorithm

Time complexity: $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#!/usr/bin/env python3
from typing import List

def get_min_row_num(student_height_arr: List[int]) -> int:
    # greedy and binary search
    tail_list = [0] * len(student_height_arr)
    size = 0
    for height in student_height_arr:
        # i: start index of rows
        # j: end index of rows
        i, j = 0, size
        while i != j:
            m = int((i + j)/2)
            # note here we need <= to ensure in each row is strictly decreasing
            # according to the problem description
            if tail_list[m] <= height:
                i = m + 1
            else:
                j = m
        tail_list[i] = height
        size = max([i+1, size])
    return size


def main():
    assert get_min_row_num([5, 4, 3, 6, 1]) == 2
    assert get_min_row_num([5, 4, 4, 3, 6, 1]) == 3

if __name__ == '__main__':
    main()

DP

Time complexity: $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#!/usr/bin/env python3
# view it as a LNDS problem
from typing import List

def get_min_row_num(student_height_arr: List[int]) -> int:
    # DP, convert to Longest Non-decreasing Subsequence Problem (LNDS)
    # memo[i] LNDS including ending with arr[i]
    n = len(student_height_arr)
    if n == 0:
        return 0
    memo = [1]*n
    for i in range(1, n):
        for j in range(i):
            if student_height_arr[i] >= student_height_arr[j]:
                memo[i] = max([memo[i], memo[j]+1])
    return max(memo)


def main():
    assert get_min_row_num([5, 4, 3, 6, 1]) == 2
    assert get_min_row_num([5, 4, 4, 3, 6, 1]) == 3

if __name__ == '__main__':
    main()

Related Problems

• 300. Longest Increasing Subsequence
• Google | Summer Intern OA 2019 | Decreasing Subsequences
• 72. Edit Distance (in sense of DP for Leetcode 300)
  • $x = c_{1}c_{2}\cdots c_{n}$.
  • $y = $ sorted sequence of $c_k$, removing any duplicates.
  • Mismatch penalty = $\infty$; gap penalty = $1$.
• 674. Longest Continuous Increasing Subsequence

Interesting Related Algorithm

• Patience sorting
  • Deal all cards using greedy algorithm; repeatedly remove smallest card.
  • For uniformly random deck, time complexity: $O(n^{3/2})$
  • ([Persi Diaconis]Patience sorting is the fastest wayto sort a pile of cards by hand.)

Reference

• DP slides from Princeton CS 423 (Patience solitaire)

之前一段时间 P2P 理财还没有大面积暴雷的时候，斐讯这个臭名昭著的公司弄了个白手套联壁金融以投资送斐讯产品这样的巨大羊毛吸引了大量用户，本人也入了一波，之后还好几乎平稳下车。斐讯的大部分电子产品由于恩山论坛的存在有大量高手愿意去不断研究如何“刷机”甚至改硬件“硬改”的方式增强其产品的可玩性，因此本人也屯了两个斐讯 T1 的电视盒子在家里。其中一个就打算当作 Linux 小服务器来运行一些网络方面的应用。由于网上更多的教程是关于 N1 盒子的，本文不跟风，而是介绍自己折腾在 T1 上安装 Linux 的全过程。

In this post, I will introduce the essential steps to install MATLAB on a server with only Command Line Interface.

Keywords: MATLAB, CLI, installation, activation

最近整理网盘文件以及家里自己部署的 NAS 时发现自己以前收藏了一些 offline 的字典文件，处于强迫症/数据洁癖打算清理一波没有用的。只留下最好的字典用于以后查阅使用，因此萌生了调查词典软件以及他们支持的格式的念头。本文主要调查中文社区使用的最流行的跨平台离线词典软件，包括 GoldenDict，灵格斯(Lingoes)词典，Mdict 以及欧陆词典，并进行对比提出自己的看法。

关键词： 词典, 应用, GoldenDict, Mdict, 欧陆词典, 灵格斯词典

There are many public face datasets available on the Internet for reseach purposes at present. In this post, I collect most of them and give each of them a small desciption so that people can select the proper one quickly. Selecting and preprocessing the datasets properly can be critical to the performance and reliability of the results.

Keywords: face-recognition, dataset, VGG-Face, VGG-Face2, CASIA-WebFace, UMDFaces, MS-Celeb-1M, MegaFace

工欲善其事必先利其器，对于把代码，环境搭得好不好，方不方便，会很大程度上影响到后续效率。由于有些不得已的情况必须在 Windows 下做开发以及嫌弃虚拟机性能问题以及方便性，经过摸爬滚打，本文总结了一套可以在 Windows 下开发 C/C++ 的轻巧（练习）开发环境。

关键词： Cmder, Visual Studio Code, MSYS2, MinGW, GIT, WSL, Cygwin, GDB, Clang, LLVM