2018-02-22

Algorithm - Interview

WAP

WAP 校招面试算法题。

Round 0

ZigZag Conversion

Round 1

Word Pattern

Round 2

Strobogrammatic Number I, II, III

Round 3

勾股定理
grep, find

Round 4

Small Chat

2018-01-31

Algorithm - Interview

Tencent IEG

腾讯互娱校招面试算法题。

这个也是 LeetCode 原题：Integer Break

给定 $m\in N$,
$\max x_1\cdot x_2\dots x_{n-1}\cdot x_n$

s.t. $x_1+x_2+…+x_n = m$ and $x_i \in N $.

（面试官给的题目里 $m = 25$）

下面我们介绍两种解法，一种是使用动态规划的编程解，另一种是直接手算出答案的数学解。

动态规划

我们使用 dp(m) 表示将整数 m 进行如上拆分后所能得到的最大乘积。那么我们要的结果就是 dp(25).

如何计算 dp(m) 呢？对于一般的情况，我们直接根据所拆分出来的第一个整数进行动态规划：

dp(m)= max{i * dp(m-i)} 其中，i \in {1,...,m}

这里为了便于计算我们将边界条件设为 dp(0) = 1

上面这个算法的复杂度是 O(m^2) ：首先我们需要计算 dp(1),...,dp(m) 这 m 个值，然后在计算每个值dp(m_0)的时候我们需要进行一个 O(m_0) 层的循环。

数学解法

首先我们假设分成的份数 n 是固定的，那么根据均值不等式我们有

$\prod_{i=1}^n x_i \le (\frac{\sum_{i=1}^n x_i}{n}) ^ n = (\frac{m}{n}) ^ n$

（几何平均值小于等于算术平均值）

上式取等的条件为各 $x_i$ 均相等。

也就是说，对于给定的 n ，我们要使得各份尽量均匀的情况下乘积最大。

下面我们考虑最优的 n 的取值。我们令 $g(n) = (\frac{m}{n})^n$, 于是只需要求 $g(n)$ 的最大值。

求导，$g’(n)=((\frac{m}{n})^n)’=(e^{n\ln(m/n)})’=e^{n\ln(m/n)}\cdot (n\ln(\frac{m}{n}))’$

因为 $(n\ln(\frac{m}{n}))’=ln(\frac{m}{n}) + n\cdot(ln(\frac{m}{n})’)=ln(\frac{m}{n}) + n \cdot \frac{n}{m} \cdot (-\frac{m}{n^2}) = ln(\frac{m}{n}) - 1$

从而 $g’(n) > 0\Leftrightarrow ln(\frac{m}{n})-1 > 0 \Leftrightarrow ln(\frac{m}{n}) > 1\Leftrightarrow \frac{m}{n} > e \Leftrightarrow n < \frac{m}{e}$

也就是说，$g(n)$ 在 $(1, \frac{m}{e})$ 递增，在 $(\frac{m}{e}, +\infty)$ 递减。

所以 $g(n)$ 在 $n=\frac{m}{e}$ 时取最大值，也就是说对于给定的数 $m$, 我们希望分成 $\frac{m}{e}$ 份，也就是说我们希望每份分成的数值是 $e$. 这里的 $e=2.71828$.

由于要求分成整数，所以我们应该分成尽量多的 3 和最多两个 2（因为我们可以把3个2变成2个3）

具体来讲，如果 m % 3 == 0，那就是 m / 3 个 3; m % 3 == 2 就是 m / 3 个 3 和 1 个 2；m % 3 == 1, 我们把多出来的 1 和它前面的那个 3 放一起拆成两个 2（2 * 2 > 1 * 3）, 就是 (m / 3 - 1) 个 3 和 2 个 2.

具体到 25，就是 25 = 3 * 7 + 2 * 2，最大的积为 $3^7\times 2^2$.

$\cdot$

其他问题

面试中遇到的其他问题包括：

说说 word2vec 的不同方法：CBOW v.s. skip-gram
说说梯度弥散 v.s. 梯度爆炸
说说线性回归 v.s 逻辑回归
说说逻辑回归中为什么使用 Sigmoid 函数
说说 SGD v.s. BGD
说说除了 SGD 之外其他的 Optimizer: Adagrad, Adam

2017-06-23

Linux

Ubuntu Package Management

Package management on Ubuntu using apt/dpkg

lsb_release

Linux Standard Base.

1 2	lsb_release -a cat /etc/issue

apt

E: Could not get lock /var/lib/dpkg/lock - open (11: Resource temporarily unavailable)
E: Unable to lock the administration directory (/var/lib/dpkg/), is another process using it?

sudo rm /var/cache/apt/archives/lock
sudo rm /var/lib/dpkg/lock

Reading package lists... Error!
E: Encountered a section with no Package: header
E: Problem with MergeList /var/lib/apt/lists/cn.archive.ubuntu.com_ubuntu_dists_xenial-backports_main_binary-amd64_Packages
E: The package lists or status file could not be parsed or opened.

sudo rm -vf /var/lib/apt/lists/*
sudo apt-get update

upgrade

1 2	sudo apt-get update sudo apt upgrade

1 2	2 upgraded, 0 newly installed, 0 to remove and 0 not upgraded. 29 not fully installed or removed.

autoclean, clean, autoremove

clean: clean clears out the local repository of retrieved package files. It removes everything but the lock file from /var/cache/apt/archives/ and /var/cache/apt/archives/partial/. When APT is used as a dselect(1) method, clean is run automatically. Those who do not use dselect will likely want to run apt-get clean from time to time to free up disk space.
autoclean: Like clean, autoclean clears out the local repository of retrieved package files. The difference is that it only removes package files that can no longer be downloaded, and are largely useless. This allows a cache to be maintained over a long period without it growing out of control. The configuration option APT::Clean-Installed will prevent installed packages from being erased if it is set to off.
autoremove: is used to remove packages that were automatically installed to satisfy dependencies for some package and that are no more needed.

dpkg

1	29 not fully installed or removed.

1	sudo apt install -f

Searches for packages that have been installed only partially on your system. dpkg will suggest what to do with them to get them working.

1	sudo dpkg -C

1	The following packages have been unpacked but not yet configured.

1	sudo dpkg --configure -a

1	dpkg-query: package 'ibus-table' is not installed

1	sudo apt install ibus-table

2017-03-22

Algorithm

Random Variable Expectation

一枚硬币, 扔出 H 的概率为 $p$, T 的概率为 $q$, 计算首次扔出 $T\underbrace{H\dots H}_{k}$ 所需投掷次数的数学期望。

我们先来考虑 $\underbrace{H\dots H}_{k}$ 这样简单后的情形，然后试图将其推广到任意模式的一般情况。

记随机变量 $X_k$ 为首次投掷出 $\underbrace{H\dots H}_{k}$ 所需的次数。

Solution 1

设我们要求的数学期望为 $e$, 则有

$$
e = q (1+e) + p q (2+e) + p p q (3+e) + p^{k-1} q (k+e) + p^k k
$$

这是对前 $k$ 位可能出现的模式进行分类讨论得到的。

记 $S=1+2p+3p^2+\dots+kp^{k-1}$, 可得 $S=1/q((1-p^k)/q-kp^k)$.

  e 
= q(1+2p+3p^2+\dots+kp^{k-1})+kp^k+q(1+p+\dots+p^{k-1})e
= q\cdot 1/q ((1-p^k)/q-kp^k) + kp^k + q 1/q(1-p^k) e
= (1-p^k)/q + (1-p^k) e

从而

$$e = 1/q (1/p ^k - 1)$$

这与我们上面的结果是吻合的。

推广：首次投掷出 HTHHT

$$e = q(1+e) + pp(2+e) + pqq(3+e) + pqpq(4+e) + pqppp(5+e) + pqppq 5$$

Solution 2

1 2	X_k = (X_{k-1} + 1)\cdot p + (X_{k-1} + 1 + X_k)\cdot q X_0 = 0

1	X_k = 1/p X_{k-1} + 1/p

1	X_k = 1/q (1/p ^k - 1)

而递推式的由来在于

1
2
3

  Pr(X_k = n) 
= Pr(X_{k-1} = n-1) p + \sum_m [ Pr(X_{k-1}=m) q Pr(X_{k}=n-m-1) ]
= p Pr(X_{k-1}+1 = n) + q \sum_m [ Pr(X_{k-1}=m) Pr(X_{k}+1=n-m) ]

也就是

1	X_k = p (X_{k-1}+1) + q (X_{k-1}+X_{k}+1)

这是由于对于随机变量 X, Y, Z, 若 Z=X+Y，则

1	Pr(Z=n) = \sum_m [Pr(X=m) Pr(Y=n-m)]

递推法可以使得我们顺便求出所有的 X_k

推广：首次投掷出 HTHHT

Solution 3

If f(x) is the generating function of the probability p_n of the ending after n tosses

1	f(x) = \sum_n p_n x^n

Consider the following toss strings, probabilities, and terms

T								q			qx
HT								pq			pqx^2
HHT								p^2q		p^2qx^3
\underbrace{H\dots H}_{k-1}T	p^{k-1}q	p^{k-1}qx^k
\underbrace{H\dots H}_k			p^{k}		p^kx^k

We get the generating function of the probability of ending after n tosses to be

1
2
3

f(x) 
= \sum_m (\sum_{t=1}^k p^{t-1}qx^t)^m p^kx^k
= p^kx^k / (1-\sum_{t=1}^k p^{t-1}qx^t)

1	f'(1) = \sum p_n n =

推广：首次投掷出 HTHHT

T		qx
HH		p^2x^2
HTT		pq^2x^3
HTHT	p^2q^2x^4
HTHHH	p^4qx^5
HTHHT	p^3q^2x^5

1
2
3

f(x) 
=\sum (qx+p^2x^2+pq^2x^3+p^2q^2x^4+p^4qx^5)^m p^3q^2x^5
=

2017-03-04

Algorithm

Poison and Prisoner

10000桶酒，其中1桶是毒酒；48小时后要举行酒会；毒酒喝下去会在之后的第23-24小时内毒死人。

国王决定用囚犯来试酒，不介意囚犯死多少，只要求用最少的囚犯来测试出哪一桶是毒酒。

问最少需要多少囚犯才能保证找出毒酒？

然后大概可以这样操作，假设有 $t$ 个时间点可以喝酒。

给这 $n$ 瓶酒用一个 $m$ 维的向量编号，每一维的取值范围是 $(0, 1, …, t)$，这里 $m = \lceil log_{t+1}(n) \rceil$。

这样每一维对应一个人吧，然后在 $t_1$ 时让 $m_1$ 这个人喝下所有编号在第 $m_1$ 维的分量是 $t_1$ 的酒。

根据每一维对应的人的死亡时间确定这一维的分量（如果没死就是 0，如果在 $t_1$ 对应的时间死亡就是 $t_1$）。

综合所有人的死亡时间确定所有维的分量。

再把这个向量换算回原来的编号。

2017-02-10

Linux

Bash

Basic usage of Bash.

source

It executes the content of the file in the current shell.

synonym: . (period).

$-

1 2	echo $- himBH

h: hashall:
i: interactive
m: monitor mode: CTRL+Z, fg
H: history expand: ~/.bash_history, !!
B: brace expansion: cp file{,.bak}

if [ "${-#*i}" != "$-" ] checking if your shell is interactive or not

$

$*: equivalent to $1c$2c...
$@: equivalent to $1 $2 …
$#: number of position parameters in decimal
$?: exit status of the most recently executed foreground pipeline
$-: the current option flags as specified upon invocation
$$: the process ID of the shell
$!: the process ID of the job most recently placed into background
$0: the name of the shell or shell script
$_: the absolution path name used to invoke the shell

–

A double dash (--) is used in bash built-in commands and many other commands to signify the end of command options, after which only positional parameters are accepted.

Example use: lets say you want to grep a file for the string -v - normally -v will be considered the option to reverse the matching meaning (only show lines that do not match), but with -- you can grep for string -v like this:

1	grep -- -v file

[ ]

[ ] vs [[ ]] are test operators

You no longer have to quote variables like mad because [[ handles empty strings and strings with whitespace more intuitively.
It lets you use && and || operators for boolean tests and < and > for string comparisons.
It has a wonderful =~ operator for doing regular expression matches.
You get pattern matching aka globbing for free.

if [ -f "$FILE" ]
if [[ -f $FILE ]]

if [ "$ANSWER" = y -o "$ANSWER" = yes ]
if [[ $ANSWER =~ ^y(es)?$ ]]

if [[ $ANSWER = y* ]]

1 2	-z字串字串长度伪则为真。 -n字串字串长度不伪则为真。

-e文件名 如果文件存在则为真。
-r文件名 如果文件存在且可读则为真。
-w文件名 如果文件存在且可写则为真。
-x文件名 如果文件存在且可执行则为真。
-s文件名 如果文件存在且至少有一个字符则为真。
-d文件名 如果文件存在且为目录则为真。
-f文件名 如果文件存在且为普通文件则为真。
-c文件名 如果文件存在且为字符型特殊文件则为真。
-b文件名 如果文件存在且为块特殊文件则为真

()

$() is command substitution

1 2	$ echo "my hostname is: $(hostname)" my uptime is: MYPC

$(( )) is arithmetic expansion

1 2	$ echo "$(( 5 + 5 ))" 10

${ } This is used to refer to variables and avoid confusion over their name.

$ v="hello"
$ echo "$vbye"

$ echo "${v}bye"
hellobye

Also, it is used to reference array elements:

$ declare -A my_arr
$ my_arr[a]="hello"
$ echo "${my_arr[a]}"
hello

( ) and { } are also used as grouping commands

( ) runs in a subshell:

$ v=5
$ ( v=2; echo "$v" )
2
$ echo "$v"
5

Whereas { list, } does not:

$ v=5
$ { v=2; echo "$v"; }
2
$ echo "$v"
2

{ }

${value:-word}: 当变量未定义或者值为空时,返回值为word的内容,否则返回变量的值.
${value:=word}: 与前者类似,只是若变量未定义或者值为空时,在返回word的值的同时将word赋值给value
${value:?message}: 若变量以赋值的话,正常替换.否则将消息message送到标准错误输出(若此替换出现在Shell程序中,那么该程序将终止运行)
${value:+word}: 若变量以赋值的话,其值才用word替换,否则不进行任何替换
${value:offset}, ${value:offset:length}: 从变量中提取子串,这里offset和length可以是算术表达式.
${#value}: 变量的字符个数
${value#pattern}, ${value##pattern}: 去掉value中与pattern相匹配的部分,条件是value的开头与pattern相匹配 #与##的区别在于一个是最短匹配模式,一个是最长匹配模式.
${value%pattern}, ${value%%pattern}: 于(7)类似,只是是从value的尾部于pattern相匹配,%与%%的区别与#与##一样
${value/pattern/string}, ${value//pattern/string}: 进行变量内容的替换,把与pattern匹配的部分替换为string的内容,/与//的区别与上同

1	INFORMIX_HOME="${INFORMIX_HOME%/}" # Strip the trailing / (if exists)

注意: 上述条件变量替换中,除(2)外,其余均不影响变量本身的值

set

1	set -euxo pipefail

-x: print commands and their arguments as they are executed
-e: equivalent to cmd1 && cmd2 && cmd3
-u: The shell prints a message to stderr when it tries to expand a variable that is not set. Also it immediately exits.
-o option-name: set the variable corresponding to option-name.
+o option-name: using + rather than - will cause the option to be turned off.
-o pipefail: Pipelines fail on the first command which fails instead of dying later on down the pipeline. This is especially good when cmd3 is a command that always succeeds (like echo)
-f: disable filename expansion (globbing) upon seeing *, ?, etc.

bash

here

1	-s stdin Read commands from stdin

BASH_SOURCE

#!/bin/sh
echo "${BASH_SOURCE[0]}"
echo "${BASH_SOURCE}"
echo "$( dirname "${BASH_SOURCE[0]}" )"
DIR="$( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd )"
echo $DIR

./abc/test.sh
./abc/test.sh
./abc/
/home/abc

DIR="$( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd )" 得到shell脚本文件所在完整路径（绝对路径）及文件名（无论source,sh,.三种调用方式），且不改变shell的当前目录。

2016-12-21

Tool

Docker

Basic usage of Docker.

1 2	sudo docker build -t tc-informix . sudo docker run -it --name iif_developer_edition --privileged -p 9088:9088 -p 9089:9089 -p 27017:27017 -p 27018:27018 -p 27883:27883 -e LICENSE=accept tc-informix

images

1	sudo docker images

rmi

1	sudo docker rmi $(sudo docker images -q -f dangling=true)

run

1	sudo docker run -it --rm ubuntu:14.04 bash

ps

1 2	sudo docker ps sudo docker logs [container ID or NAMES]

rm

1	docker rm $(docker ps -a -q)

start, stop, attach

sudo docker stop d457395b35e2
sudo docker ps -a
sudo docker start d457395b35e2
docker exec -it d457395b35e2 bash

1	sudo docker attach nostalgic_hypatia

logs

1	sudo docker logs -t iif_developer_edition

日志文件位于 var/lib/docker/containers/<container_id>，文件名为 <container_id>-json.log

Dockerfile

1	touch Dockerfile

1 2	FROM nginx RUN echo '<h1>Hello, Docker!</h1>' > /usr/share/nginx/html/index.html

Docker has a default entrypoint which is /bin/sh -c but does not have a default command.

When you run docker like this: docker run -i -t ubuntu bash the entrypoint is the default /bin/sh -c, the image is ubuntu and the command is bash.

The command is run via the entrypoint. i.e., the actual thing that gets executed is /bin/sh -c bash. This allowed docker to implement RUN quickly by relying on the shell’s parser. Later on, people asked to be able to customize this so ENTRYPOINT and -entrypoint has been introduced.

An other example would be to have any cli as entrypoint. For instance, if you have a redis image, instead of running docker run redisimg redis -H something -u toto get key, you can simply have ENTRYPOINT ["redis", "-H", "something", "-u", "toto"] and then run like this for the same result: docker run redisimg get key.

When the operator executes docker run --privileged, Docker will enable to access to all devices on the host as well as set some configuration in AppArmor or SELinux to allow the container nearly all the same access to the host as processes running outside containers on the host.

install

1
2
3

sudo apt-get install docker-engine
sudo service docker start
sudo docker run hello-world

service

1	Cannot connect to the Docker daemon. Is the docker daemon running on this host?

1 2	sudo service docker start sudo docker build -t tc-cache .

pull

1	sudo docker pull ubuntu:14.04

commit

1
2
3

sudo docker pull nginx
sudo docker run --name webserver -d -p 80:80 nginx
sudo docker exec -it webserver bash

1 2	echo '<h1>Hello, Docker!</h1>' > /usr/share/nginx/html/index.html exit

sudo docker diff webserver
sudo docker commit \
    --author "Tao Wang <twang2218@gmail.com>" \
    --message "修改了默认网页" \
    webserver \
    nginx:v2
sudo docker images nginx
sudo docker history nginx:v2
sudo docker run --name web2 -d -p 81:80 nginx:v2

build

1	docker build -t nginx:v3 .

因此，COPY 这类指令中的源文件的路径都是相对路径。这也是初学者经常会问的为什么 COPY ../package.json /app 或者 COPY /opt/xxxx /app 无法工作的原因，因为这些路径已经超出了上下文的范围，Docker 引擎无法获得这些位置的文件。如果真的需要那些文件，应该将它们复制到上下文目录中去。

export

1 2	sudo docker export 7691a814370e > ubuntu.tar cat ubuntu.tar \| sudo docker import - test/ubuntu:v1.0

2016-12-13

Tool

Git

Basic usage of git.

Move tmp content from one computer to another

On Machine A

First, create a branch named tmp and commit your tmp work there.

1
2
3

git checkout -b tmp
git add .
git commit -m "tmp"

Then, push local tmp branch to remote tmp branch.

1	git push origin tmp

You can restore the state of your local workspace by:

git checkout master

git merge tmp
git reset --soft HEAD~1
git restore --staged .

git branch -D tmp

On Machine B

Fetch the tmp remote branch locally:

1	git fetch origin tmp:tmp

Merge content of tmp branch into your main branch:

1	git merge tmp

Reset soft and restore so that the last commit is reverted:

1 2	git reset --soft HEAD~1 git restore --staged .

Delete the local and remote tmp branch:

1
2
3

git branch -D tmp

git push origin --delete tmp

Sync with Remote

Stash your unstaged work to make your working dir clean:

git stash

Fetch remote branch and merge:

1	git pull origin main

Git stash pop:

1	git stash pop

Alternatively, you can use the --autostash flag to handle this entire workflow in a single command:

1	git pull origin main --autostash

Squashing Git Commits

https://gist.github.com/patik/b8a9dc5cd356f9f6f980

1 2	git reset --soft HEAD~3 git commit -m "Squashing Git Commits"

1	git push origin +master

git log --author=songzy
git reset f7f4aec68
git log -2
git reset 7e26106
git log -2
git clean -df
git checkout -- .

git reset

1	git reset <file>

Remove the specified file from the staging area, but leave the working directory unchanged.

git reset

Reset the staging area to match the most recent commit, but leave the working directory unchanged.

1	git reset --hard

Reset the staging area and the working directory to match the most recent commit.

1	git reset <commit>

Move the current branch tip backward to , reset the staging area to match, but leave the working directory alone.

1 2	git reset --hard <commit>

Move the current branch tip backward to and reset both the staging area and the working directory to match.

Whereas reverting is designed to safely undo a public commit, git reset is designed to undo local changes.

git add foo.py
git commit -m "Start developing a crazy feature"
git commit -a -m "Continue my crazy feature"
git reset --hard HEAD~2

The git reset HEAD~2 command moves the current branch backward by two commits.

git rebase

# Add the remote, call it "upstream":

git remote add upstream https://github.com/whoever/whatever.git

# Fetch all the branches of that remote into remote-tracking branches,
# such as upstream/master:

git fetch upstream

# Make sure that you're on your master branch:

git checkout master

# Rewrite your master branch so that any commits of yours that
# aren't already in upstream/master are replayed on top of that
# other branch:

git rebase upstream/master

git push -f origin master

git branch

1	git show-branch -a

Show branches and their commits

1	git branch <branch>

Create a new branch called . This does not check out the new branch.

1	git branch -d <branch>

Delete the specified branch.

1	git branch -D <branch>

Force delete the specified branch, even if it has unmerged changes.

1	git branch -m <branch>

Rename the current branch to <branch>.

1 2	git checkout $branch2 git merge $branch1

Merge branch1 into branch2.

1	warning: refname 'HEAD' is ambiguous.

1 2	git branch -m HEAD temp git branch -d temp

git checkout

Give up the current modification and go back to the last commit

1	git checkout -- .

git log --oneline

b7119f2 Continue doing crazy things
872fa7e Try something crazy
a1e8fb5 Make some important changes to hello.py
435b61d Create hello.py
9773e52 Initial import

You can find the ID of the revision you want to see.

1 2	git checkout a1e8fb5 git checkout master

Nothing you do in here will be saved in your repository.

1 2	git checkout a1e8fb5 hello.py git checkout HEAD hello.py

Unlike checking out a commit, this does affect the current state of your project.

1 2	git status HEAD detached From 91ea20b

git checkout source
error: Your local changes to the following files would be overwritten by checkout:
        source/_posts/2016-02-25-github.markdown
Please, commit your changes or stash them before you can switch branches.
Aborting

1 2	git stash git checkout source

git clean

1	git clean -n

This will show you which files are going to be removed without actually doing it.

1	git clean -f

Remove untracked files from the current directory.

1	git clean -f <path>

Remove untracked files, but limit the operation to the specified path.

1	git clean -df

Remove untracked files and untracked directories from the current directory.

1	git clean -xf

Remove untracked files from the current directory as well as any files that Git usually ignores.

git clone

If you clone a repository, the default branch you have is whatever the remote’s HEAD points to (HEAD is actually a symbolic ref that points to a branch name).

A symbolic ref is a regular file that stores a string that begins with ref: refs/. For example, your .git/HEAD is a regular file whose contents is ref: refs/heads/master.

HEAD@{1} is always last value of HEAD, ORIG_HEAD is last value of HEAD before dangerous operation.

git commit

1	git commit --amend

Combine the staged changes with the previous commit and replace the previous commit with the resulting snapshot.

1	git commit -a

Commit all your local changes. (like git add . followed by git commit)

git config

1	vi ~/.gitconfig

1 2	git config --global user.email "your_email@example.com" git config --global user.email

git diff

1	git diff filename

git fetch

git fetch

Fetch all of the branches from the repository. This also downloads all of the required commits and files from the other repository.

1
2
3

git checkout master
git log origin/master
git merge origin/master

1	error: RPC failed; result=18, HTTP code = 0

1 2	git fetch origin master git merge origin/master

git format-patch

1
2
3

$ git format-patch -o ./patches -2
0001-C.patch
0002-D.patch

1	git am ./patches/*

git log

Check all the change paths to file Predictor.java.

1 2	git log --follow -p Predictor.java git log -p -1

git merge

1	git merge --squash <branch_name>

將另一個 branch 的 commit 合併為一筆，特別適合需要做實驗的 fixes bug 或 new feature，最後只留結果。合併完不會幫你先 commit。

git pull

1	git pull <远程主机名> <远程分支名>:<本地分支名>

如果远程分支是与当前分支合并，则冒号后面的部分可以省略。

Here.

1	ssh: connect to host github.com port 22: Connection refused

vi ~/.ssh/config

Host github.com
  Hostname ssh.github.com
  Port 443

git push

1	git push <远程主机名> <本地分支名>:<远程分支名>

1	git push origin HEAD:master

See the commits tab(rather than project tab). It is all there.

1	ssh -v -T songzy12@git.tsinghuax.org

IP filtered, move to your lab.

1	fatal: Could not read from remote repository.

Server down.

git remote

1	git remote set-url origin git@github.com:songzy12/certificate_predictor.git

git revert

1	git revert <commit>

Generate a new commit that undoes all of the changes introduced in <commit>, then apply it to the current branch.

it doesn’t change the project history
it is able to target an individual commit at an arbitrary point in the history

1 2	git commit -m "Make some changes that will be undone" git revert HEAD

git rm

1	git rm -r --cached ".\source\_posts\Git Shell.lnk"

The git rm command will allows you to remote a file from git control. The –cached option to git remove allows you to leave it on your hard drive.

git stash

git stash
git stash list
git stash pop
git stash clear
git stash drop

fileMode

100644: normal file
100755: executable file
120000: symbolic link

The mode is taken from normal UNIX modes but is much less flexible – these three modes are the only ones that are valid for files (blobs) in Git (although other modes are used for directories and submodules).

The 6 digits show the file mode using the classical UNIX notations. First two digits show file type, the third one is about set-uid/set-gid/sticky bits, and you know the last three. 4\2\1 is just r\w\x.

1	man 2 stat

S_IFLNK    0120000   symbolic link
S_IFREG    0100000   regular file

S_IRWXU    00700     mask for file owner permissions
S_IRUSR    00400     owner has read permission
S_IWUSR    00200     owner has write permission
S_IXUSR    00100     owner has execute permission
S_IRWXG    00070     mask for group permissions
S_IRGRP    00040     group has read permission
S_IWGRP    00020     group has write permission
S_IXGRP    00010     group has execute permission
S_IRWXO    00007     mask for permissions for others (not in group)
S_IROTH    00004     others have read permission           
S_IWOTH    00002     others have write permission
S_IXOTH    00001     others have execute permission

To ignore file mode changes:

1	repo forall -c git config core.fileMode false

2016-10-29

Tool

Tmux

Basic usage of tmux.

copy paste

enter copy mode using Control+b [
navigate to beginning of text, you want to select and hit Control+Space
move around using arrow keys to select region
when you reach end of region simply hit Alt+w to copy the region
now Control+b ] will paste the selection

scroll

1	vi ~/.tmux.conf

1	set -g mouse on

session

session指的是按下tmux命令后存在的连接便是session

创建session
tmux

创建并指定session名字
tmux new -s $session_name

tmux rename -t target_session new_name

重命名session
Ctrl+b $

删除session
Ctrl+b :kill-session

临时退出session
Ctrl+b d

列出session
tmux ls

进入已存在的session
tmux a -t $session_name

删除所有session
Ctrl+b :kill-server

删除指定session
tmux kill-session -t $session_name

panel

pane在window里，可以有N个pane，并且pane可以在不同的window里移动、合并、拆分

创建pane
横切split pane horizontal
Ctrl+b ” (问号的上面，shift+’)

竖切split pane vertical
Ctrl+b % （shift+5）

按顺序在pane之间移动
Ctrl+b o

上下左右选择pane
Ctrl+b 方向键上下左右

调整pane的大小
Ctrl+b :resize-pane -U #向上
Ctrl+b :resize-pane -D #向下
Ctrl+b :resize-pane -L #向左
Ctrl+b :resize-pane -R #向右
在上下左右的调整里，最后的参数可以加数字 用以控制移动的大小，例如：
Ctrl+b :resize-pane -D 50

在同一个window里左右移动pane
Ctrl+b { （往左边，往上面）
Ctrl+b } （往右边，往下面）

删除pane
Ctrl+b x

更换pane排版
Ctrl+b “空格”

移动pane至window
Ctrl+b !

移动pane合并至某个window
Ctrl+b :join-pane -t $window_name

显示pane编号
Ctrl+b q

按顺序移动pane位置
Ctrl+b Ctrl+o

滚动输出
Ctrl+b [

default-terminal

https://unix.stackexchange.com/questions/1045/getting-256-colors-to-work-in-tmux

❯ echo $TERM
xterm-256color

❯ echo $TERM
screen

1
2
3

vi ~/.tmux.conf

set -g default-terminal "xterm-256color"

2016-08-16

Security - RE

Apktool

Android RE.

apk

AndroidManifest.xml
classes.dex
res/
lib/
META-INF

arsc: Android package Resource file.

hacking approach

unzip apk & disassemble classes.dex
perform static analysis on the app
inject byte-code into the app
reassemble classes.dex & zip/sign apk

dex: dalvik executable

apktool

1 2	apktool d RecentContest_beta.apk apktool b RecentContest_beta

RecentContest

contests.

To remove Private access contests from the json result, just insert the following lines after :cond_1 of file JsonStringAnalysis.smali

const-string v8, "Private"

invoke-virtual {v0, v8}, Ljava/lang/String;->equals(Ljava/lang/Object;)Z

move-result v8

if-nez v8, :try_end_0

testsign

1	java -jar testsign.jar RecentContest_beta.apk RecentContest_beta-signed.apk

smali

Types

V: void
Z: boolean
B: byte
S: short
C: char
F: float
I: int
J: long
D: double
[: array

Classes

full name space slash separated
prefixed with L
suffixed with ;

1	Lcom/example/myapp/MyClass;

Methods

.method keyword method-name parameters/return

1	.method private delayedAnimationFrame(J)Z

Registers

.locals
.parameters

Opcodes

invoke-super vx, vy, …
new-instance vx
invoke-direct vx, vy, …
const-string vx
invoke-virtual vx, vy, …
return-void