Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.
https://leetcode.com/problems/divide-two-integers/

需要注意的点：

1. 除数为零的情况
2. 被除数为Integer.MIN_VALUE，除数为-1时会超出Integer的表示范围，可以把被除数和除数都转换成long
3. 被除数和除数的符号问题：先计算结果的符号（如果被除数和除数异号，那么结果为负），然后把被除数和除数取绝对值
4. 被除数减除数的过程可以通过除数左移来加速

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

public int divide(int dividend, int divisor) {
    if(divisor == 0) return Integer.MAX_VALUE;
    long a = dividend, b = divisor;
    boolean positive = true;
    if(a < 0 && b > 0 || a > 0 && b < 0) positive = false;
    a = Math.abs(a);
    b = Math.abs(b);
    long res = 0;
    while(a >= b) {
        long bt = b, rt = 1;
        while((bt << 1) <= a) {
            bt = bt << 1;
            rt = rt << 1;
        }
        a -= bt;
        res += rt;
    }
    if(positive && res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
    return positive ? (int)res : -(int)res;
}

Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.
https://leetcode.com/problems/container-with-most-water/

使用首尾两个指针，每次收缩高度较小的那个。因为如果收缩高度大的那端，无论收缩后高度变高还是变低，收缩后面积一定变小（因为收缩后宽度减1，高度不会大于高度小的那端）。

1
2
3
4
5
6
7
8
9
10
11
12

public int maxArea(int[] height) {
    if(height == null || height.length <= 1) return 0;
    int left = 0, right = height.length - 1, max = 0;
    while(left < right) {
        max = Math.max(max, (right - left) * Math.min(height[left], height[right]));
        if(height[left] < height[right])
            ++left;
        else
            --right;
    }
    return max;
}

LIMIT

LIMIT 5 表示返回不多于5行的结果，带一个值的LIMIT总是从第一行开始，返回指定的行数
LIMIT 5, 5表示返回从第5行开始的5行，第一个数为开始位置，第二个数为要检索的行数

检索出来的第一行为行0而不是行1，因此，LIMIT 1，1将检索出第二行而不是第一行。LIMIT 3，4表示从第三行开始4行，LIMIT 4 OFFSET3表示同样意思

LIKE

LIKE用于过滤部分匹配的情况，可以使用通配符表示若干字符，其中%表示任何字符出现任何次数（包括0次），但是%不能匹配NULL。下划线_可以匹配单个字符。

SELECT子句及其顺序

联结

1. 等值联结（内部联结），等值联结是在WHERE子句中指定两表中联结的字段：SELECT id FROM ta, tb WHERE ta.vid = tb.vid，内联结可以达到同样的效果：SELECT id FROM ta INNER JOIN tb ON ta.vid = tb.vid。ANSI SQL规范首选INNER JOIN语法。
2. 自联结，如果需要多次使用同一个表，可以用表别名和自联结来实现：SELCT p1.proc_id, p1.proc_name FROM products AS p1, product AS p2 WHERE p1.vend_id = p2.vend_id AND p2.proc_id = “DTNTR”
3. 外部联结，外部联结可以查询到没有关联在一起的行，使用OUTER JOIN时，必须使用RIGHT或LEFT关键字指定包括其所有行的表，RIGHT指出是OUTER JOIN右边的表，LEFT指出是OUTER JOIN左边的表。

UNION

TCP（传输控制协议）在两个端点之间提供可靠的、面向连接的、双向字节流通信信道。

确认、重传和超时

当一个TCP报文无错地到达目的地时，接受TCP会发送一个确认报文给发送端，该报文的确认序号字段被设置为接收方期望接收的下一个报文的逻辑序号。如果报文存在错误，那么这个报文会被丢弃，确认信息也不会被发送。发送方在发送报文后一段时间没有收到确认，就会重传报文。

流量控制（滑动窗口机制）

为了防止发送方发送速度过快而导致接收方来不及接收，在三次握手建立TCP连接的过程中就会告知对方接收缓冲区大小。从发送方接收数据到缓冲区时，空闲缓冲区大小减小；当上层应用从缓冲区读取数据时，空闲缓冲区大小增大。每次确认时，会告诉对方空闲缓冲区大小。如果缓冲区被填满，发送方暂停传输数据。

TCP连接的建立

在套接字API层，两个流式套接字通过以下步骤建立连接：

1. 服务器调用listen()在套接字上执行被动打开，然后调用accept()阻塞服务器进程直到连接建立完成。
2. 客户端调用connect()在套接字上执行主动打开，以此来同服务器端的被动打开套接字之间建立连接。

三次握手

建立一个TCP连接，需要传送3个报文，步骤如下：

每个进程各自有不同的用户地址空间，任何一个进程的全局变量在另一个进程中都是看不到的，所以进程间要交换数据必须通过内核，在内核中开辟一个缓冲区，进程1把数据从用户空间拷到内核缓冲区，进程2再从内核缓冲区把数据读走，内核提供的这种机制称为进程间通信（IPC， InterProcess Communication）。

管道

管道是一种最基本的IPC机制，由pipe函数创建, pipe函数在内核中开辟一块缓冲区（称为管道）用于通信，它有一个读端和一个写端。

1
2

# include<unistd.h>
int pipe(int fd[2]);

fd[0]指向管道的读端，fd[1]指向管道的写端。管道在用户程序看来就像一个打开的文件，通过read(fd[0])或者write(fd[1])向这个文件读写数据其实是在读写内核缓冲区。pipe函数调用成功返回0，调用失败返回-1.

FIFO

FIFO有时候被称为命名管道，未命名的pipe只能在两个相关的进程间通信，FIFO可以用在不相关的进程间通信。FIFO有如下两种用途：

1. Shell命令使用FIFO将数据从一条管道传递到另一条时，无需创建中间临时文件
2. 客户端-服务器进程应用中，FIFO用作汇聚点，在客户进程和服务器进程之间传递数据

进程之间传递信息的途径总结如下：

• 父进程通过fork将打开的文件描述符传递给子进程
• 子进程结束时，父进程调用wait可以得到子进程的终止信息
• 几个进程可以在文件系统中读写某个共享文件，也可以通过给文件加锁来实现进程间同步
• 进程之间互发信号，一般使用SIGUSR1和SIGUSR2实现用户自定义功能
• 管道
• FIFO
• 通过mmap函数，几个进程可以映射同一内存区
• SYS V IPC，包括消息队列、信号量和共享内存，现在已经基本废弃
• UNIX Domain Socket，目前最广泛使用的IPC机制

Process Identifiers

Every process has a unique ID, a non-negative integer. Process ID 0 is usually the scheduler process and is often known as the swapper. No process on disk correspons to this process, which is part of the kernel and is konwn as a system process. Process ID 1 is usually the init process and is invoked by the kernel at the end of the bootstrap procedure. The program file for this process was /etc/init in older verion of the UNIX System and is /sbin/init in newer version. This process is responsible for bringing up a UNIX system after the kernel has been bootstraped. init usually reads the system-dependent initialization files - the /etc/rc* files or /etc/inittab and the files in /etc/init.d - and brings the system to a certain state, such as multiuser. The init process never dies, it is a normal user process althrough it runs with superuser privileges.

fork function

An existing process can create a new one by calling the fork function.

1
2
3

# include<unistd.h>
//Returns: 0 in child, process ID of child in parent, -1 on error
pid_t fork(void);

This function is called once but return twice. The reason the child’s process ID is returned to the parent is that a process can have more than one child, and there is no function that allows a process to obtain the process IDs of its children. The reason fork returns 0 to the child is that a process can have only a single parent, and the child can always call getppid to obtain the process ID of its parent.(Process ID 0 is reserved for use by the kernelit’s not possible for 0 to by the process ID of a child).

Both the child and the parent continue executing with the instruction that follows the call to fork. The child is a copy of the parent, for example, the child gets a copy of the parent’s data space, heap, and stack. This is a copy for the child, the parent and the child do not share these portions of memory. The parent and the child share the text segment.

Modern implements don’t perform a complete copy of the parent’s data, stack and heap, since a fork is often followed by an exec. Instend, a technique called copy-on-write(COM) is used. These regions are shared by the parent and the child and have their protection changed by the kernel to read-only. If either process tries to modify these regions, the kernel then makes a copy of that piece of memeory only, typically a “page” in a virtual memory system.

All file descriptors that are open in the parent are duplicated in the child. The parent and the child share a fiel table entry for every open descriptor. There are two normal cases for handling the descriptors after a fork.

1. The parent waits for the child to complete. In this case, the parent docs not need to do anything with its descriptors. When the child terminates, any of the shared descriptors that the child read from or wrote to will have their file offsets updated accordingly.
2. Both the parent and the child go their own ways. Here after the fork, the parent closes the descriptors that it doesn’t need and the child does the same thing. This way neither interferes with the other’s open descriptors. This scenario is often found with network servers.

TreeSet和TreeMap

Java 中的TreeSet直接使用了TreeMap来实现，当向TreeSet中存放值时，实际保存在TreeMap的Key中，所有的value都是同一个Object对象。

1
2
3

public TreeSet() {
    this(new TreeMap<E,Object>());
}

对于 TreeMap 来说，它采用一种被称为“红黑树”的排序二叉树来保存 Map 中每个 Entry —— 每个 Entry 都被当成“红黑树”的一个节点对待。

1
2
3
4
5
6
7
8

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
}

排序二叉树

红黑树是一种自平衡排序二叉树，排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：

• 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 它的左、右子树也分别为排序二叉树。

排序二叉树的插入过程

当程序希望添加新节点时：系统总是从树的根节点开始比较 —— 即将根节点当成当前节点，如果新增节点大于当前节点、并且当前节点的右子节点存在，则以右子节点作为当前节点；如果新增节点小于当前节点、并且当前节点的左子节点存在，则以左子节点作为当前节点；如果新增节点等于当前节点，则用新增节点覆盖当前节点，并结束循环 —— 直到找到某个节点的左、右子节点不存在，将新节点添加该节点的子节点 —— 如果新节点比该节点大，则添加为右子节点；如果新节点比该节点小，则添加为左子节点。

C程序存储空间布局

• 正文段（Text Segment），由CPU执行的机器指令部分，通常是只读并共享的，即使频繁执行的程序（文本编辑器，编译器，Shell等等）
• 初始化数据段（数据段，Data Segment），包含了程序中明确赋予初始值的变量，例如在所有函数体外定义int max = 99;
• 未初始化数据段（bss， block started by symbol 由符号开始的块），内核会在程序执行之前将包含在bss段的变量初始化为0或者空指针。例如在所有函数体外定义long sum[100];，sum存放在未初始化数据段中。
• 栈，自动变量以及每次函数调用时需要保存的信息都存放在栈中。每次函数调用时，返回地址以及调用者的环境信息（如某些机器寄存器的值）都存放在栈中。新调用的函数会在栈上分配自动变量和临时变量，这种机制使得递归函数可以正常工作。每次函数调用它自身，都会在栈中创建一个新的栈帧，栈帧中的变量不会相互影响。
• 堆，通常在堆中动态分配内存，堆位于未初始化数据段和栈之间

共享库

共享库中包含了多个可执行文件需要的库，在内存中只维护一个副本。这会减小可执行文件的大小，但是会增加一些运行时开销，这种开销产生于程序第一次执行或者共享库函数第一次被调用时。共享库的另一个优势在于，更新库函数版本时不用重新链接每个使用共享库的程序。

存储空间分配

1
2
3
4
5
6

# include<stdlib.c>
void *malloc(size_t size);
void *calloc(size_t nobj, size_t size);
void *realloc(size_t *ptr, size_t newsize);

void free(void *ptr);

这三个分配函数返回的指针一定是适当对齐的，使得它可以用于任何数据对象。alloc函数的返回值都是void *，当把这些函数返回的指针赋予一个不同类型的指针时，不需要显式地执行强制类型转换。

free释放ptr指向的存储空间，被释放的空间通常被送入可用存储区池，可被malloc函数再次分配。

realloc函数可以增减以前分配的存储区长度，如果该存储区后有足够的空间可以扩充，则可以在原存储区位置上向高地址方向扩充，无需移动任何原先的内容；如果在原存储区后没有足够的空间，则realloc分配另一个足够大的存储区，将当前存储区的内容复制到新分配的存储区，然后释放原存储区。

Spring并不直接管理事务，而是提供了多种事务管理器，它们将事务管理的职责委托给Hibernate或JPA等持久化机制提供的事务来实现。

Java EE应用的事务有两种策略：全局事务和局部事务。全局事务由应用服务器管理，需要底层服务器的JTA支持。局部事务与底层采用的持久化技术有关，当采用JDBC持久化技术时，需要使用Connection对象来操作事务；采用Hibernate持久化技术时，需要使用Session对象来操作事务。全局事务可以跨多个事务性资源（典型例子是关系数据库和消息队列）；使用局部事务时，应用服务器不需要参与事务管理，因此不能保证跨多个事务性资源事务的正确性，不过大部分应用都使用单一事务性资源。

接口定义

Spring框架中有三个重要的类涉及事务管理：TransactionDefinition、PlatformTransactionManager、TransactionStatus。Spring事务管理器的接口是：org.springframework.transaction.PlatformTransactionManager。通过这个接口，Spring为各个平台如JDBC、Hibernate等都提供了对应的事务管理器，具体的事务实现由各平台提供。

PlatformTransactionManager

PlatformTransactionManager接口定义了三个方法：

1
2
3
4
5
6
7
8

public interface PlatformTransactionManager extends TransactionManager {
  // Return a currently active transaction or create a new one, according to the specified propagation behavior.
	TransactionStatus getTransaction(@Nullable TransactionDefinition definition) throws TransactionException;
  // Commit the given transaction, with regard to its status. If the transaction has been marked rollback-only programmatically, perform a rollback.
  void commit(TransactionStatus status) throws TransactionException;
  // Perform a rollback of the given transaction.
  void rollback(TransactionStatus status) throws TransactionException;
}

根据底层所使用的不同的持久化 API 或框架，PlatformTransactionManager 的主要实现类大致如下：

• DataSourceTransactionManager：适用于使用JDBC和iBatis进行数据持久化操作的情况。
• HibernateTransactionManager：适用于使用Hibernate进行数据持久化操作的情况。
• JpaTransactionManager：适用于使用JPA进行数据持久化操作的情况。

另外还有JtaTransactionManager 、JdoTransactionManager、JmsTransactionManager等等。