HTTP (short for Hypertext Transfer Protocol) is a protocol for transmitting hypermedia documents, such as HTML, XML, script, CSS, image and text in the format of JSON. It can be used for communication between browsers and web servers, or between mobile applications and web servers, or among web severs.

A typical HTTP transaction consists of two parts: an HTTP request (from client to server) and an HTTP response (from server to client), and both include protocol version (like “HTTP/1.1”), headers and entity body.

An HTTP request header:

1
2
3
4
5
6
7
8

GET / HTTP/1.1
Host: qconferences.com
Connection: keep-alive
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) ...
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8
Referer: https://www.google.com/
Accept-Encoding: gzip, deflate, br
Accept-Language: en-US,en;q=0.9,zh-CN;q=0.8,zh;q=0.7,zh-TW;q=0.6

An HTTP response header:

1
2
3
4
5
6
7

HTTP/1.1 200 OK
Content-Encoding: gzip
Content-Language: en
Content-Type: text/html; charset=utf-8
Server: Apache/2.4.7 (Ubuntu)
Content-Length: 17089
Connection: keep-alive

Let’s say, A wants to send a secret message to B. Hypothetically, A owns a key which is also owned by B. Thus, A can encrypt the message using the key and then B can decipher the encoded message using the same key. This is known as symmetric cryptography.

In contrast, asymmetric cryptography doesn’t require A and B to share the same private key; instead, A and B hold two different keys - one public key and one private key (it is impossible to compute the private key based on the public key). If A wants to send a secret message to B, A can first get a public key from B and use it to encode the message, and then B can decode the ciphertext using the private key.

In summary, symmetric cryptography

uses the same cryptographic keys for both encryption of plaintext and decryption of ciphertext.

Asymmetric cryptography

uses public and private keys to encrypt and decrypt data; either of the keys can be used to encrypt a message, and the other key can be used for decryption.

Both cryptography can be used for data confidential, as shown in the example above. Besides, asymmetric cryptography can be applied in other scenarios, like representing the authentication of digital messages (aka. digital signature).

Semaphore is a data structure for solving concurrency problems. It enforces constraints on how multiple threads or processes access the common resource (or known as enter the critical section).

It keeps a counter whose meaning depends on how you want to use it. And there are two operations which are performend on the counter.

• P: decrement & wait, i.e. decrease the value of the counter, if the value has become negative, then the current thread or process must wait until it is waked
• V: increament & signal, i.e. increase the value of the counter, and signal a waiting thread or process if there is any

If the semaphore is bounded, then the value of its counter cannot exceed its initial value - if the value exceeds its initial value, an error should exceed its value.

Semaphore also keeps a queue to manage the waiting threads or processes - it might follow the FIFO ordering or randomly pick an element from the queue.

Now we have a rough impression of how semaphore is, let’s check out how it is implemented first and then how it is applied to solve concurrency problems.

An array is a data structure of fixed size. It contains a collection of elements of the same type. They are ordered and each element is identified by an array index. It is easy to access or modify any element in the array through the array index, and the time complexity is O(1).

1
2
3
4
5
6
7

// a one-dimensional array
String[] array = new String[16];
array[14] = "hello";

// a two-dimensional array, aka. matrix
int[][] matrix = new int[200][200];
matrix[10][0] = 123;

But it is a little more complex when an element is removed from the array or a new one is inserted in the array. To maintain the order of elements in the array, the right part of the array needs to be shifted to the left or to the right, and the time complexity is O(n).

1
2
3
4
5
6

int remove(int[] array, int len, int index) {
    for (int i = index; i < len - 1; i++) {
        array[i] = array[i + 1];
    }
    len--;
}

A list is a abstract data structure which consists of ordered elements of the same type. It is resizable. One of the concrete implementations of list is linked list, where elements are connected through pointers or references.

1
2
3
4
5
6
7
8

public class SingleLinkedListNode <T> {
    private T obj;
    private SingleLinkedListNode next;

    public SingleLinkedListNode(T obj) {
        this.obj = obj;
    }
}

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

public class SingleLinkedList {
    private SingleLinkedListNode head;

    public SingleLinkedList(T[] array) {
        if (array == null || array.length == 0) {
            throw new RuntimeException();
        }
        head = new SingleLinkedListNode(array[0]);
        SingleLinkedListNode pre = head;
        for (int i = 1; i < array.length; i++) {
            SingleLinkedListNode node = new SingleLinkedListNode(array[i]);
            pre.next = node;
            pre = node;
        }
    }
}

It takes O(n) to find the target element in a linked list, but it takes only O(1) to insert or remove an element in a linked list. Compared to array, linked list is more suitable for the senarios where the insertion and deletion operations are more needed than random access.

Heap is a tree-based data structure which satisfies the heap ordering property:

• If it is a max-heap, the value of any node is greater than or equal to the value of its children, with the maximum value at the root
• If it is a min-heap, the value of any node is less than or equal to the value of its children, with the minimum value at the root

The binary heap is the most common implementation of a heap. It is a complete binary tree where every level (except possibly the last one) is completely filled, and all nodes are as far let as possible. Thus, a binary heap can be implemented based on an array instead of a binary tree. Suppose the index of a node is i, then

1
2
3

int leftChild = i * 2 + 1;  // index of its left child
int rightChild = i * 2 + 2; // index of its right child
int parent = (i - 1) / 2;   // index of its parent

When an element is inserted or removed, the heap needs to be adjusted to maintain the ordering property, and the time complexity depends on the height of the heap, i.e. O(log(n)). Unlike a sorted array which takes O(n*log(n)) to sort and O(1) to fetch the next element, it takes O(n*log(n)) to build a heap and O(log(n)) to adjust the heap for fetching the next element, so it does not make sense to use heap to sort a fixed size collection (aka. heapsort), but if we need to sort out the top k elements from a stream or a file which cannot be fit into memory, a heap is exactly what we need.

Queue is a linear data structure where insertion of items takes place at the rear and deletion takes place at the head - Following the FIFO principal: First In First Out.

Queue and stack have many features in common. They are linear data structures, so they both can be implemented based on an array or a list. The insertion and deletion of items are not allowed to take place at the middle of the data structure. There is only one difference: for stack, the insertion and deletion takes place at one end; for queue, the two operations takes place at different ends - and this has made all the differences on how these two data structures are used.

Applications of queue include:

• BFS
• Producer-Consumer problem, e.g. message queue

Stack is a linear data structure where insertion and deletion of items takes place at one end (i.e. the top), which is known as LIFO - Last In First Out.

Here is a structural definition of stack (which is quite interesting):

A stack is a recursive data structure.
It is either empty or it consists of a top and the rest of which is a stack.

There are three basic operations performed on stack:

• push: add an item to the top of the stack
• pop: remove the item on the top of the stack
• peek: access to the top of the stack

A stack can be implemented through an array or a linked list. The key is to maintain the index of the top element.

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

public class MyStack<T> {
    private List<T> array;

    public MyStack() {
        array = new ArrayList<>();
    }

    public void push(T obj) {
        array.add(obj);
    }

    public T pop() {
        int e = peek();
        array.remove(array.size() - 1);
        return e;
    }

    public T peek() {
        if (array.isEmpty()) {
            throw new RuntimeException();
        }
        return array.get(array.size() - 1);
    }
}

Applications of stack include:

• DFS and backtracking due to its support for recursion
• evaluating expressions
• undo operations

The rest of this post will be focused on the applications.

Have you ever wondered what happens after you log in to a website? You may think it is like opening a drawer of your own using your key and then having access to everything inside. But this is not a proper metaphor. Whenever you request a resource from the website, you actually sends a HTTP request to the server through your browser. HTTP is a stateless protocol, meaning that

• each request/response happens in isolation
• each request is not aware of the state of the communication

Thus, a server cannot tell if an HTTP request comes from an authenticated user unless you provide your user name and password in each request, or the server and/or the client keeps track of the state of the communication. Of course, it is silly to ask the user for password every time when a request requires authentication, so it leaves us with the second option.

This post is about how to keep track of the state of the communication between the client and server, and it covers two solutions.

Adapter pattern is a structural pattern. Here is the definition:

Convert the interface of a class into another interface clients expect.
Adapter lets classes work together that couldn’t otherwise because of incompatible interfaces.

In other words, clients expect A, but all we’ve got is B, and yet we want to reuse B, so we introduce an adapter for B, allowing clients to use B in the way they use A without making changes to their code. Note that the adapter does not change the underline behavior implemented by B.

This post is about how to come up with solutions applying dynamic programming when all I can think about is brutal force.