File Types

1. Regular file. There is no distinction to the Unix kernel whether this data is text or binary. Any interpretation of the contents of a regular fiel is left to the application processing the file.

   To execute a program, the kernel must understand its format. All binary executable files conform to a format that allows the kernel to identify where to load a program’s text and data.

2. Directory file. A file that contains the name of other files and pointers to information on these files. Any process that has read permission for a directory file can read the contents of the directory, but only the kernel can write directly to a directory file. Processes must use specify functions to make change to a directory.
3. Block special file. A type of file proving buffered I/O access in fixed-size units to devices as disk drives.
4. Character special file. A type of file providing unbuffered I/O access in variable-sized units to devices. All devices on a system are either block-special files or character special files.
5. FIFO. A type of file used for communication between process. It’s sometimes called a named pipe.
6. Socket. A type of file used for network commucation between processes. A socket can also be used for non-network communication between processes on a single host.
7. Symbolic link. A type of file that points to another file.

File Access

The file access tests that the kernel perform each time a process opens, creates or deletes a file. The tests depend on the owners of the file and the effective IDs of the process. The tests performed by the kernel are as follows:

1. If the effective Id of the process is 0(the superuser), access is allowed.
2. If the effective user ID of the process equals the owner ID of the file, access is allowed if the appropriate access permission bit is set. Otherwise, permission is denied.
3. If the effective user ID of the process of one of the supplementary group IDs of the process equals the group ID of the file, access is allowed if the appropriate group access permission bit is set. Otherwise, permission is denied.
4. If the appropriate other access permission bit is set, access is allowed. Otherwise, permission is denied.

These four steps are tried in sequence. For example, if the process owns the file, access is granted or denied based only on the user access permission; the froup permission are never looked at.

Reference

Adcanced Programming in the Unix Environment(Third Edition)

The term unbuffered means that each read or write invokes a system call in the kernel. These unbuffered I/O functions are not part of ISO C, but are part of POSIX.1.

File descriptors

To the kernel, all open files are refered to by file descriptors. A file descriptor is a non-negative integer. When we open an existing file or create a new file, the kernel returns a file descriptor to the process. When we want to read or write a file, we identify the file with the file descriptor that was returned by the open or create as an argument.

By convention, Unix shells associate file descriptor 0 with standard input of a process, file descriptor 1 with the standard output, and file descriptor 2 with the standard error.

The file descriptors returned by open and openat is guaranteed to be the lowest-numbered unused descriptor.

File sharing

The Unix supports the sharing of open files among different processes. The kernel uses three data structures to present an open file, and the relationships among them determine the effect one process has on another with regard to file sharing.

1. Every process has an entry in the process table. Within each process table entry is a table of open file descriptors, which we can think of as a vector, with one entry per descriptor. Associated with each file descriptor are:

• The file descriptor flags(close-on-exec)
• A pointer to a file table entry

2. The kernel maintains a file table for all open files. Each file table entry contains

数据结构

对于点稠密的图，可以使用邻接矩阵表示g[n][n]，其中n表示图中的节点数，g[i][j]表示是否存在从i到j的路径（无权图）或者从节点i到节点j的权重（有权图）。

对于边稠密的图，如果是无权图可以使用邻接表List<Integer>[] g表示，其中g[i]表示与节点i邻接的点；如果是有权图，可以使用邻接表’List<Integer, Map<Integer, Integer>> g`或者

1
2
3
4
5

class Edge {
    int to;
    int cost;
}
List<Integer, Edge> g;

两种表示图的数据结构方法的算法分析如下：

搜索

深度优先搜索（DFS）

使用一个标记数组标记已被访问过的节点，每次递归标记当前节点并访问与当前节点邻接的节点。可使用并查集记录dfs过程中节点的前驱节点，需要求源点到某节点路径时，从并查集中恢复即可。

1
2
3
4
5
6
7

void dfs(List<Integer>[] g, boolean[] marked, int cur) {
    marked[cur] = true;
    for(int i : g[cur]) {
        if(!marked[i])
            dfs(g, marked, i);
    }
}

Permutations without duplicates

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

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

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    helper(nums, 0, new ArrayList<Integer>(), res);
    return res;
}

private void helper(int[] nums, int cur, List<Integer> list, List<List<Integer>> res) {
    if(cur == nums.length) {
        List<Integer> t = new ArrayList<Integer>(list);
        res.add(t);
        return;
    }
    for(int i = cur; i < nums.length; ++i) {
        swap(nums, cur, i);
        list.add(nums[cur]);
        helper(nums, cur + 1, list, res);
        swap(nums, cur, i);
        list.remove(list.size() - 1);
    }
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

Permutations with duplicates

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
https://leetcode.com/problems/permutations-ii/

Start with the first element, swap current element with every element after it. To void duplicates, check if the same element has been swaped before.

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
31
32
33
34
35

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(nums == null || nums.length == 0) return result;
    Arrays.sort(nums);
    dfs(result, nums, 0);
    return result;
}

private void dfs(List<List<Integer>> result, int[] nums, int cur) {
    if(cur == nums.length) {
        List<Integer> list = new ArrayList<Integer>();
        for(int i : nums) list.add(i);
        result.add(list);
        return;
    }
    for(int i = cur; i < nums.length; ++i) {
        if(contain(nums, cur, i)) continue;
        swap(nums, cur, i);
        dfs(result, nums, cur + 1);
        swap(nums, cur, i);
    }
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

private boolean contain(int[] nums, int beg, int end) {
    for(int i = beg; i < end; ++i)
        if(nums[i] == nums[end])
            return true;
    return false;
}

Behivioral patterns are specifically concerned with communication between objects.

Chain of responsibility

Chain of responsibility pattern creates a chain of receiver objects for a request. normally each receiver contains reference to another receiver. If one object cannot handle the request then it passes the same to the next receiver and so on.

In this example we have different roles, each having a fixed purchasing limit and a successor. Every time a user in a role receives a purchase request that exceeds his or her limit, the request is passed to his or her successor.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

abstract class PurchasePower {
    protected static final double BASE = 500;
    protected PurchasePower successor;

    public void setSuccessor(PurchasePower successor) {
        this.successor = successor;
    }

    abstract public void processRequest(PurchaseRequest request);
}

class ManagerPPower extends PurchasePower {
    private final double ALLOWABLE = 10 * BASE;

    public void processRequest(PurchaseRequest request) {
        if (request.getAmount() < ALLOWABLE) {
            System.out.println("Manager will approve $" + request.getAmount());
        } else if (successor != null) {
            successor.processRequest(request);
        }
    }
}

class DirectorPPower extends PurchasePower {
    private final double ALLOWABLE = 20 * BASE;

    public void processRequest(PurchaseRequest request) {
        if (request.getAmount() < ALLOWABLE) {
            System.out.println("Director will approve $" + request.getAmount());
        } else if (successor != null) {
            successor.processRequest(request);
        }
    }
}

class VicePresidentPPower extends PurchasePower {
    private final double ALLOWABLE = 40 * BASE;

    public void processRequest(PurchaseRequest request) {
        if (request.getAmount() < ALLOWABLE) {
            System.out.println("Vice President will approve $" + request.getAmount());
        } else if (successor != null) {
            successor.processRequest(request);
        }
    }
}

class PresidentPPower extends PurchasePower {
    private final double ALLOWABLE = 60 * BASE;

    public void processRequest(PurchaseRequest request) {
        if (request.getAmount() < ALLOWABLE) {
            System.out.println("President will approve $" + request.getAmount());
        } else {
            System.out.println( "Your request for $" + request.getAmount() + " needs a board meeting!");
        }
    }
}

class PurchaseRequest {
    private double amount;
    private String purpose;

    public PurchaseRequest(double amount, String purpose) {
        this.amount = amount;
        this.purpose = purpose;
    }

    public double getAmount() {
        return amount;
    }
    public void setAmount(double amt)  {
        amount = amt;
    }

    public String getPurpose() {
        return purpose;
    }
    public void setPurpose(String reason) {
        purpose = reason;
    }
}

class CheckAuthority {
    public static void main(String[] args) {
        ManagerPPower manager = new ManagerPPower();
        DirectorPPower director = new DirectorPPower();
        VicePresidentPPower vp = new VicePresidentPPower();
        PresidentPPower president = new PresidentPPower();
        manager.setSuccessor(director);
        director.setSuccessor(vp);
        vp.setSuccessor(president);

        // Press Ctrl+C to end.
        try {
            while (true) {
                System.out.println("Enter the amount to check who should approve your expenditure.");
                System.out.print(">");
                double d = Double.parseDouble(new BufferedReader(new InputStreamReader(System.in)).readLine());
                manager.processRequest(new PurchaseRequest(d, "General"));
           }
        } catch(Exception e) {
            System.exit(1);
        }
    }
}

Command Pattern

Command pattern is a behavioral design pattern in which an object is used to encapsulate all information needed to perform an action or trigger an event at a later time. A request is wrapped under an object as command and passed to invoker object. Invoker object looks for the appropriate object which can handle this command and passes the command to the corresponding object which executes the command.

Four terms always associated with the command pattern are command, receiver, invoker and client. A command object knows about receiver and invokes a method of the receiver. Values for parameters of the receiver method are stored in the command. The receiver then does the work. An invoker object knows how to execute a command, and optionally does bookkeeping about the command execution. The invoker does not know anything about a concrete command, it knows only about command interface. Both an invoker object and several command objects are held by a client object. The client decides which commands to execute at which points. To execute a command, it passes the command object to the invoker object.

We have created an interface Order which is acting as a command. We have created a Stock class which acts as a request. We have concrete command classes BuyStock and SellStock implementing Order interface which will do actual command processing. A class Broker is created which acts as an invoker object. It can take and place orders.
Broker object uses command pattern to identify which object will execute which command based on the type of command. CommandPatternDemo, our demo class, will use Broker class to demonstrate command pattern.

Structural design patterns are design patterns that ease the design by identifying a simple way to realize relationships between entities.

Adapter Pattern

Adapter pattern involves a single class which is responsible to join functionalities of independent or incompatible interfaces. It allows incompatible classes to work together by converting the interface of one class into an interface expected by the clients.

A real life example could be a case of card reader which acts as an adapter between memory card and a laptop. You plugin the memory card into card reader and card reader into the laptop so that memory card can be read via laptop.

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

public class AdapteeToClientAdapter implements Client {

    private final Adaptee instance;

    public AdapteeToClientAdapter(final Adaptee instance) {
         this.instance = instance;
    }

    @Override
    public void clientMethod() {
       // call Adaptee's method(s) to implement Client's clientMethod
    }

}

Bridge Pattern

Bridge pattern is used when we need to decouple an abstraction from its implementation so that the two can vary independently. This pattern involves an interface which acts as a bridge which makes the functionality of concrete classes independent from interface implementer classes. Both types of classes can be altered structurally without affecting each other.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

public interface DrawAPI {
    void draw();
}

public class DrawCircle implements DrawAPI {
    @Override
    public void draw() {
        System.out.println("Draw a circle");
    }
}

public class DrawSquare implements DrawAPI {
    @Override
    public void draw() {
        System.out.println("Draw a Square");
    }
}

public abstract class Shape {
    DrawAPI drawAPI;
    public Shape(DrawAPI drawAPI) {
        this.drawAPI = drawAPI;
    }
    public abstract void draw();
}

public class ShapeDemo extends Shape {
    public ShapeDemo(DrawAPI drawAPI) {
        super(drawAPI);
    }
    
    @Override
    public void draw() {
        drawAPI.draw();
    }
}

public class BridgeTest {
    public static void main(String[] args) {
        ShapeDemo demo1 = new ShapeDemo(new DrawCircle());
        ShapeDemo demo2 = new ShapeDemo(new DrawSquare());
        demo1.draw();
        demo2.draw();
    }
}

Terminology: Nested classes are divided into two categories: static and non-static. Nested classes that are declared static are called static nested classes. Non-static nested classes are called inner classes.

A nested class is a member of its enclosing class. Non-static nested classes (inner classes) have access to other members of the enclosing class, even if they are declared private. Static nested classes do not have access to other members of the enclosing class. As a member of the OuterClass, a nested class can be declared private, public, protected, or package private. (Recall that outer classes can only be declared public or package private.)

Static nested class

As with class methods and variables, a static nested class is associated with its outer class. And like static class methods, a static nested class cannot refer directly to instance variables or methods defined in its enclosing class: it can use them only through an object reference.

A static nested class interacts with the instance members of its outer class (and other classes) just like any other top-level class. In effect, a static nested class is behaviorally a top-level class that has been nested in another top-level class for packaging convenience.
Static nested classes are accessed using the enclosing class name: OuterClass.StaticNestedClass
For example, to create an object for the static nested class, use this syntax:

1
2

OuterClass.StaticNestedClass nestedObject =
     new OuterClass.StaticNestedClass();

Inner Classes

As with instance methods and variables, an inner class is associated with an instance of its enclosing class and has direct access to that object’s methods and fields. Also, because an inner class is associated with an instance, it cannot define any static members itself.

Objects that are instances of an inner class exist within an instance of the outer class. Consider the following classes:

1
2
3
4
5
6

class OuterClass {
    ...
    class InnerClass {
        ...
    }
}

Creational patterns provide a way to create objects while hiding the creation logic, rather than instantiating objects directly using new operator. This gives program more flexibility in deciding which objects need to be created for a given use case.

Factory Method Pattern

With factory pattern, objects are created without exposing the creation logic to the client. It refers to the factory method that encapsulates the creation of objects such that factory method can be override in a subclass.

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

public class MazeGame {
    public MazeGame() {
        Room room1 = makeRoom();
        Room room2 = makeRoom();
        room1.connect(room2);
        this.addRoom(room1);
        this.addRoom(room2);
    }

    protected Room makeRoom() {
        return new OrdinaryRoom();
    }
}

public class MagicMazeGame extends MazeGame {
    @Override
    protected Room makeRoom() {
        return new MagicRoom(); 
    }
}

Abstract Factory Pattern

Abstract factory pattern works around a super factory which creates other factories. This factory is also called the factory of factories.

The method createButton on the GuiFactory interface returns objects of type Button. What implementation of Button is returned depends on which implementation of GuiFactory is handling the method call.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

interface Button {
	void paint();
}
//Abstract Product
interface Label {
	void paint();
}

//Abstract Factory
interface GUIFactory {
	Button createButton();
	Label createLabel();
}

//Concrete Factory
class WinFactory implements GUIFactory {
	public Button createButton() {
		return new WinButton();
	}

	public Label createLabel() {
		return new WinLabel();
	}
}

//Concrete Factory
class OSXFactory implements GUIFactory {
	public Button createButton() {
		return new OSXButton();
	}

	public Label createLabel() {
		return new OSXLabel();
	}

}

//Concrete Product
class OSXButton implements Button {
	public void paint() {
		System.out.println("I'm an OSXButton");
	}
}

//Concrete Product
class WinButton implements Button {
	public void paint() {
		System.out.println("I'm a WinButton");
	}
}

//Concrete Product
class OSXLabel implements Label {
	public void paint() {
		System.out.println("I'm an OSXLabel");
	}
}

//Concrete Product
class WinLabel implements Label {
	public void paint() {
		System.out.println("I'm a WinLabel");
	}
}

//Client application is not aware about the how the product is created. Its only responsible to give a name of 
//concrete factory
class Application {
	public Application(GUIFactory factory) {
		Button button = factory.createButton();
		Label label = factory.createLabel();
		button.paint();
		label.paint();
	}
}

public class ApplicationRunner {
	public static void main(String[] args) {
		new Application(createOsSpecificFactory());
	}

	public static GUIFactory createOsSpecificFactory() {
		String osname = System.getProperty("os.name").toLowerCase();
		if(osname != null && osname.contains("windows"))
			return new WinFactory();
		else
			return new OSXFactory();
	}
}

1
2
3
4
5
6
7
8
9
10
11

int pow(int a, int n) {
    if(n == 0) return 1;
    boolean positive = n < 0 ? true : false;
    int res = 1;
    while(n > 0) {
        if(n % 2 != 0)
            res *= a;
        a *= a;
        n >>= 1;
    }
}

1
2
3
4
5
6
7
8
9
10

private void muti(int[][] a, int[][] b, int[][] c, int m) {
    int t00 = (a[0][0]*b[0][0] + a[0][1]*b[1][0]) % m;
    int t01 = (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % m;
    int t10 = (a[1][0]*b[0][0] + a[1][1]*b[1][0]) % m;
    int t11 = (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % m;
    c[0][0] = t00;
    c[0][1] = t01;
    c[1][0] = t10;
    c[1][1] = t11;
}

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

private int fib(int n, int m) {
    if(n == 0) return 0;
    else if(n <= 2) return 1;
    int[][] b = {{1,1},{1,0}}, res = {{1,0},{0,1}};
    n -= 2;
    while(n > 0) {
        if(n % 2 != 0)
            muti(b,res,res,m);
        muti(b,b,b,m);
        n /= 2;
    }
    return (res[0][0] + res[0][1]) % m;
}

参考资料
求斐波那契(Fibonacci)数列通项的七种实现方法

What are design patterns

Design patterns represent the best practices used by experienced object-oriented software developers. Design patterns are solutions to general probloms that software developer faced during software development.

As Design pattern - Elements of reusable Object-Oriented Software, there are 23 design patterns which can be classified in three categories: Creational, Structural and Behavioral patterns.

Principles of object-oriented design(SOLID)

S.O.L.I.D is an acronym for the first five object-oriented design(OOD) principles by Robert C. Martin, popularly known as Uncle Bob.

These principles, when combined together, make it easy for a programmer to develop software that are easy to maintain and extend.

1. Single-responsibility Principle(S.R.P for short – this principle states that: A class should have one and only one reason to change, meaning that a class should have only one job.
2. Open-closed Principle: Objects or entities should be open for extension, but closed for modification. This simply means that a class should be easily extendable without modifying the class itself.
3. Liskov substitution principle: if S is a subtype of T, then objects of type T may be replaced with objects of type S without altering any of the desirable properties of that program (correctness, task performed, etc.).
4. Interface segregation principle: Clients should not be forced to implement interfaces they don’t use. Many client specific interfaces are better than one general purpose interface.
5. Dependency Inversion principle: Entities must depend on abstractions not on concretions. It states that the high level module must not depend on the low level module, but they should depend on abstractions.

Orther principles

• Program to Interface Not Implementation.
• Don’t Repeat Yourself.
• Encapsulate What Varies.
• Depend on Abstractions, Not Concrete
• classes. Least Knowledge Principle.
• Favor Composition over
• Inheritance. Hollywood Principle.
• Apply Design Pattern wherever possible.
• Strive for Loosely Coupled System.
• Keep it Simple and Sweet / Stupid.

References