努橙刷题编: 2015

2015年12月23日星期三

[LintCode] Restore IP Addresses Show result

public class Solution {
/**
* @param s the IP string
* @return All possible valid IP addresses
*/
public ArrayList<String> restoreIpAddresses(String s) {
// Write your code here
ArrayList<String> result = new ArrayList<String>();
if (s == null || s.length() < 4 || s.length() > 12) {
return result;
}
helper(s, 0, "", result, 0);
return result;
}

private void helper(String s, int start, String tmp, ArrayList<String> result, int points) {
if (start == s.length() && points == 4) {
result.add(tmp);
return;
}
for (int i = 1; i <= 3 && start + i <= s.length(); i++) {
if (Integer.parseInt(s.substring(start, start + i)) <= 255) {
String tail = s.substring(start, start + i);
if (!tail.equals(Integer.toString(Integer.parseInt(tail)))) {
return;
}
if (points != 3) tail += ".";
helper(s, start + i, tmp + tail, result, points + 1);
}
}
}
}

好久不练，一个dfs写了半小时也是太差T_T

2015年12月3日星期四

Dec 3

Java RuntimeException serialVersionUID:
http://stackoverflow.com/questions/285793/what-is-a-serialversionuid-and-why-should-i-use-it

2015年12月1日星期二

Dec 1

Singleton and Prototype:
http://www.studytrails.com/frameworks/spring/spring-singleton-and-prototype.jsp

2015年11月27日星期五

Nov 27

How to write a unit test?
https://developer.salesforce.com/page/How_to_Write_Good_Unit_Tests

2015年11月24日星期二

Nov 24

Mockito:
http://liuzhijun.iteye.com/blog/1512780
http://examples.javacodegeeks.com/core-java/mockito/mockito-verify-example/

2015年11月23日星期一

Nov 23

Spring Framework:
http://www.ibm.com/developerworks/cn/java/wa-spring1/
http://blog.csdn.net/liuxiaogangqq/article/details/8848844

Call Graph:
https://en.wikipedia.org/wiki/Call_graph

How to use mocking object?

2015年11月20日星期五

Nov 20

How graph run in parallel?

How to send http get request?
http://www.mkyong.com/java/how-to-send-http-request-getpost-in-java/

2015年11月19日星期四

Nov 19

Is there any VAST WRAPPER example?

2015年11月17日星期二

Nov 17

Strategy Pattern:
https://en.wikipedia.org/wiki/Strategy_pattern

2015年11月16日星期一

Nov 16

Difference between HTTP cookie and session?
http://stackoverflow.com/questions/6922145/what-is-the-difference-between-server-side-cookie-and-client-side-cookie

What is RESTful?

2015年11月15日星期日

Nov 15

What is the difference between VAST, VMAP and VPAID?
VAST & VMAP:
http://support.jwplayer.com/customer/portal/articles/1432026-vmap-ad-schedule

VPAID:
https://support.google.com/dfp_premium/answer/1663924?hl=en

？？？
VAST: 一个广告
VMAP: 一堆广告
VPAID: 一堆会动的广告

What is frequency capping?
https://en.wikipedia.org/wiki/Frequency_capping

2015年11月10日星期二

2015 October 总结

Git

git status

git diff <name_of_a_file>

git add <name_of_a_file>

git commit -m "..."

git pull

git checkout <name_of_another_branch>

git push
git rebase -i

Undo all uncommitted changes:
http://stackoverflow.com/questions/14075581/git-undo-all-uncommitted-changes?answertab=votes#tab-top

Can I undo a 'git clean -fdx'?
http://stackoverflow.com/questions/6267180/can-i-undo-a-git-clean-fdx?answertab=votes#tab-top

Compare two branches in git:
http://stackoverflow.com/questions/9834689/comparing-two-branches-in-git

How to roll back a git repository to a particular commit?
http://stackoverflow.com/questions/1616957/how-do-you-roll-back-reset-a-git-repository-to-a-particular-commit

Java

How to define a class of constants?
http://stackoverflow.com/questions/479565/how-do-you-define-a-class-of-constants-in-java?answertab=votes#tab-top

Controlling Access to Members of a Class
https://docs.oracle.com/javase/tutorial/java/javaOO/accesscontrol.html

About naming convention:
http://www.oracle.com/technetwork/java/javase/documentation/codeconventions-135099.html#367

Java Access Control:
https://docs.oracle.com/javase/tutorial/java/javaOO/accesscontrol.html

About inner class and nested class:
http://stackoverflow.com/questions/5714727/can-a-method-in-an-inner-class-access-a-parent-class-method
https://docs.oracle.com/javase/tutorial/java/javaOO/nested.html

About JUnit
1) Wiki
https://en.wikipedia.org/wiki/JUnit

2) Class Assert
http://junit.sourceforge.net/javadoc/org/junit/Assert.html

3) Enable assertions in Eclipse
http://stackoverflow.com/questions/5509082/eclipse-enable-assertions

Networking

Status Code definitions:
http://www.w3.org/Protocols/rfc2616/rfc2616-sec10.html

Difference between GET method and POST method:
http://www.w3schools.com/tags/ref_httpmethods.asp

Wireshark:
https://www.wireshark.org/download.html

Linux

Write your first script:
http://linuxcommand.org/lc3_wss0010.php

About tail:
http://linux.about.com/library/cmd/blcmdl1_tail.htm

About vi:
search: :/
http://stackoverflow.com/questions/1183001/how-can-i-tail-a-zipped-file-without-reading-its-entire-contents
http://www.lagmonster.org/docs/vi.html

2015年9月17日星期四

[笔记] Speaking JavaScript Chapter 9 Operators

1. Equality Operators

Equality is not customizable. Operators can't be overloaded in JavaScript, and you can't customize how equality works. There are some operations where you often need to influence comparison-for example, Array.prototype.sort(). That method optionally accepts a callback that perform all comparisons between elements.

Pitfall: NaN !== NaN

Normal(Lenient) Equality (==, !=)

The following comparison ensures that x is neither undefined nor null:

if (x != null) ...

Use case: working with numbers in strings

if (x == 123) ...

The preceding checks whether x is either 123 or '123'. It is better to be explicit:

if (Number(x) === 123) ...

Use case: comparing wrapper instances with primitives

> 'abc' == new String('abc')
true

> new String('abc') == new String('abc')
false

Lenient equality does not work between wrapped primitives.

2. The Plus Operator

You evaluate an addition:

value1 + value2
by taking the following steps:
(1) Ensure that both operands are primitives. Objects obj are converted to primitives
via the internal operation ToPrimitive(obj) (refer to “Algorithm: ToPrimitive()—
Converting a Value to a Primitive” on page 79), which calls obj.valueOf() and,
possibly, obj.toString() to do so. For dates, obj.toString() is called first.
(2) If either operand is a string, then convert both to strings and return the concatenation
of the results.
(3) Otherwise, convert both operands to numbers and return the sum of the results.

3. Special Operators

What is void for?
(1) void 0 as a synonym for undefined
(2) Discarding the result of an expression
If you want to open a new window without changing the currently displayed content, you can do the following:
javascript:void window.open("http://example.com/")

Pitfall: typeof null
Unfortunately, typeof null is 'object'. The following function checks whether value is an object:
function isObject(value) {
return (value !== null
&& (typeof value === 'object'
|| typeof value === 'function'));
}

2015年9月15日星期二

[笔记] Speaking JavaScript Chapter 8 Values

1.JavaScript's Type System

JavaScript has only six types: undefined, null Boolean, String, Number, and Object.

1.1 Static versus Dynamic
static: at compile time
dynamic: at runtime

Object foo = "abc";

The static type of foo is Object; its dynamic type is String.
JavaScript is dynamically typed; types of variables are generally not known at compile time.

coerce: implicit type conversion

2. Primitive Values versus Objects

(1) The primitive values are booleans, numbers, strings, null and undefined.
(2) All other values are objects.

The most common kinds of objects are: palin objects/ arrays/ regex
Objects have the following characteristics: Compared by reference/ Mutable by default/ User-extensible

Changing undefined:

if (x === void 0) // always safe

3. Wrapper Objects

The three primitive types boolean, number, and string have corresponding constructors: Boolean, Number, String. Their instance (so-called wrapper objects) contain (wrap) primitive values. The constructors can be used in two ways:

(1) As constructors:

> typeof new String('abc')
'object'
> new String('abc') === 'abc'
false

(2) As functions:

> String(123)
'123'

It is considered a best practice to avoid wrapper objects

Primitives Borrow Their Methods from Wrappers

> 'abc'.charAt == String.prototype.charAt
true

2015年9月14日星期一

[笔记] Speaking JavaScript Chapter 7 JavaScript's Syntax

1. Expression Versus Statements

An expression produces a value and can be written wherever a value is expected.
Wherever JavaScript expects a statement, you can also write an expression. Such a statement is called expression statement. The reverse does not hold: you cannot write a statement where JavaScript expects an expression. For example, an if statement cannot become the argument of a function.

conditional operator:
var salutation = (male ? 'Mr.' : 'Mrs.');

Using ambiguous expressions as statements: JavaScript does not let you use object literals and function expressions as statements. That is, expression statements must not start with: A curly brace / The keyword function

Immediately invoking a function expression

> (function () { return 'abc'}())
'abc'

If you omit the parentheses, you get a syntax error, because JavaScript see a function declaration, which can't be anonymous. If you add a name, you also get a syntax error, because function declaration can't be immediately invoked.

2. Rules for Using Semicolons

Normally, statements are terminated by semicolons.
The following statements are not terminated by semicolons if they end with a block.
Loops: for, while(but not do-while)
Branching: if, switch, try
Function declarations(but not function expressions)

while versus do-while:

while (a > 0) {
a--;
} // no semicolon

do {
a--;
} while (a > 0);

function declaration versus function expression:

function foo() {
//...
} // no semicolon

var foo = function () {
//...
};

3. Legal Identifiers

Reserved words are part of the syntax and can't be used as variable names.

4. Invoking Methods on Number Literals

It is important to distinguish between the floating-point dot and the method invocation dot. You can't write 1.toString(); you must use the one of the following altrnatives:
1..toString()
1 .toString() // space before dot
(1).toString()
1.0.toString()

5. Strict Mode

The normal(nonstrict) mode is sometimes called "sloppy mode".
In strict mode, all variables must be expicitly declared.
In strict mode, all functions must be declared at the top level of a scope.

function strictFunc() {
'use strict';
{
//Syntax Error:
function nested() {

}
}
}

function strictFunc() {
'use strict';
{
//OK
var nested = function () {
};
}
}

2015年9月8日星期二

[笔记] Speaking JavaScript Chapter 1

Speaking JavaScript

Preface

Don't get bogged down by the details.
JavaScript Command Lines: Node.js

Chapter 1: Basic JavaScript

1.1 Syntax

1.1.1 Overview of Syntax

// two slashes start single-line comments

var x; // declaring a variable

x = 3 + y; // assigning a value to the variable 'x'

foo(x, y); // calling function 'foo' with parameters 'x' and 'y'
obj.bar(3); // calling method 'bar' for object 'obj'

//A conditional statement
if (x === 0) { // Is 'x' equal to zero?
x = 123;
}

//Defining function 'baz' with parameters 'a' and 'b'
function baz(a, b) {
return a + b;
}

Note the two different uses of the equal sign:
(1) A single equals sign (=) is used to assign a value to a variable.
(2) A triple equal sign (===) is used to compare two values.

1.1.2 Statements v. Expression

statement: do things
expression: value

JS has two different ways to do if-then-else
(1) statement:
var x;
if (y >= 0) {
x = y;
} else {
x = -y;
}
(2) expression
var x = y >= 0 ? y : -y;

1.1.3 Semicolons: recommended

semicolons terminate statements, but not blocks. There is one case where you will see a semicolon after a block: a function expression is an expression that ends with a block.

var f = function () { }; // function expr. inside var decl.

1.2 Values

1.2.1 Primitive Values v. Objects

JavaScript makes a somewhat arbitrary distinction between values:
(1) The primitive values are booleans, numbers, strings, null and undefined.
(2) All other values are objects.

A major difference between the two is how they are compared; each object has a unique identity and is only(strictly) equal to itself.
In contrast, all primitive values encoding the same value are considered the same.

1.2.2 Primitive Values

(1) Compared by value: the "content" is compared
e.g. 3 === 3 , 'abc' === 'abc'

(2) Always immutable: properties can't be changed

> var str = 'abc';
> str.length = 1; // try to change property 'length'
> str.length // no effect
3

1.2.3 Objects

(1) Plain Objects
{
firstName: 'Jane',
lastName: 'Doe'
}

(2) Arrays
['apple', 'banana', 'cherry']

(3) Regular Expression
/^a+b+$/

(4) Characteristics
Comapred Reference:
1)
> {} === {}
false

2)
> var obj1 = {};
> var obj2 = obj1;
> obj1 === obj2;
true

Mutable by Default:
> var obj = {};
> obj.foo = 123; // add property 'foo'
> obj.foo
123

1.2.4 undefined and null

undefined: no value
null: no object

checking for undefined and null:
if (!x) {...}

1.2.5 typeof and instanceof

(1) type of value
> typeof true
'boolean'
>typeof null
'object' // this is a bug and cannot be fixed

(2) instance of
> {} instanceof Object
true

1.3 Booleans

JavaScript has two kinds of equalty:
(1) Normal, or "lenient", (in) equalty: == and !=
(2) Strict (in)equalty: === and !==
Normal equality is considered (too) many values to be equal (p84) which hide bugs. Therefore, always using strict equality is recommended.

1.4 Numbers

All numbers in JavaScript are floating-point
Special Numbers:
(1) NaN ("Not a Number")
> Number('xyz')
NaN
(2) Infinity: Infinity is LARGER and SMALLER than any other number
> 3 / 0
Infinity

1.5 Operators

+-*/%++--
The global object Math(P31) provides more arithmatic operators

1.6 Strings

slice/trim/indexOf

1.7 Functions

function add(param1, param2) {
return param1 + param2;
}

> add(6, 1)
7
> add('a', 'b')
'ab'

Another way of defining add() is:

var add = function (param1, param2) {
return param1 + param2;
};

1.7.1 Function and var declaration are hoisted, while assignments performed by them are not.

function foo() {
bar(); // OK, bar is hoisted
function bar() {
...
}
}

function foo() {
bar(); // Not OK, bar is still undefined
var bar = function() {
...
}
}

1.7.2 You can call any function in JavaScript with an arbitrary amount of arguments; the language will never complain.

1.7.3 special variable argument

1.8 Strict Mode

1.9 Variables Are Function-Scoped, Hoisted

1.10 Closure

Each function stays connected to the variables of the functions that surround it, even after it leaves the scope in which it is created.

function createIncrementor(start) {
return function() { // (1)
start++;
return start;
}
}

The function starting in line (1) leaves the context in which it is created, but stays connected to a live version of start:

> var inc = cerateIncrement(5);
> inc()
6
> inc()
7
> inc()
8

A closure is a function plus the connection to the variables of its surrounding scopes. Thus, what createIncrementor() returns a closure.

1.11 Objects and Constructors

1.11.1 Single Objects

You could consider an object to be a set of properties, where each property is a (key, value) pair. The key is a string, and the value is any JavaScript value.

'use strict'
var jane = {
name: 'Jane',

describe: function () {
return 'Person named' + this.name;
}
}

> jane.name // get
'Jane'
> jane.name = 'John'; // set
> jane.newProperty = 'abc'; // property created automatically

The in operator checks whether a property exists:

> 'newProperty' in jane
true
> 'foo' in jane
false

The delete operator removes a property:

> delete jane.newProperty
true

1.11.2 Arbitrary Property Keys

Use square brackets to get and set the property:

> var obj = { hello: 'world' };
> var x = 'hello';

> obj[x]
'world'
> obj['hel' + 'lo']
'world'

1.11.3 Extracting Methods

If you extract a method, it loses its connection with the object. On its own, the function is not a method anymore, and this has the value undefined (in strict mode).

Extract the method describe from jane, put it into a variable func, and call it. However, that doesn't work:

> var func = jane.describe;
> func()
TypeError: Cannot read property 'name' of undefined

Solution: use the method bind(). It creates a new function whose this always has the given value.

> var func2 = jane.describe.bind(jane);
> func2()
'Person named Jane'

1.11.4 Functions inside a method (这里有点没搞懂)

Every function has its own special variable this. This is inconvenient if you nest a function inside a method, because you can't access the method's this from the function. The following is an example where we call forEach with a function to iterate over an array:

var jane = {
name: 'Jane',
friends: [ 'Tarzan', 'Cheeta' ],
logHiToFriends: function () {
'use strict';
this.friends.forEach(function (friend) {
// 'this' is undefined here
console.log(this.name + ' says hi to ' + friend);
});
}
}

> jane.logHiToFriends()
TypeError: Cannot read property 'name' of undefined

Solution 1: store this in a different variable

logHiToFriends: function () {
'use strict';
var that = this;
this.friends.forEach(function (friend) {
console.log(that.name + ' says hi to ' + friend);
});
}

Solution 2: forEach has a second parameter that allows you to provide a value for this:

logHiToFriends: function () {
'use strict';
this.firends.forEach(function (friend) {
console.log(that.name + ' says hi to ' + friend);
}, this);
}

Attention: Function expression are often used as arguments in function calls in JavaScript. Always be careful when you refer to this from one of those function expressions.

1.11.5 Constructors: Factories for Objects

// Set up instance data
function Point(x, y) {
this.x = x;
this.y = y;
}

//Method
Point.prototyoe.dist = function () {
return Math.sqrt(this.x*this.x + this.y*this.y);
}

> var p = new Point(3, 5);
> p.x
3
> p.dist()
5.83....

p is an instance of Point:

> p instanceof Point
true

1.12 Arrays

Array Methods:
slice/push/pop/shift/indexOf/join

map creates a new array by applying a function to each element of an existing array:
> [1,2,3].map(function (x) { return x*x })
[ 1, 4, 9 ]

1.13 Regular Expression(Chapter 19)

Method: test(): Is There a Match?
> /^a+b+$/.test('aaab')
true
> /^a+b+$/.test('aaa')
false

2015年9月6日星期日

[笔记][Computer Networks] Chapter 1

Computer Networks (Fifth Edition)
Chapter 1

Difference between distributed system and computer network:
In a distributed system, a collection of independent computers appears to its users as a single coherent system. Usually, it has a single model of paradigm that it presents to the users. Of a layer of software on top of the operating system, called middleware, is responsible for implementing this model. A well-known example of a distributed system is the World Wide Web. It runs on top of the Internet and presents a model in which everything looks like a document.
In a computer network, this coherence, model and software are absent. Users are exposed to actual machines, without any attempt by the system to make the machine look and act in a coherent way. If the machines have different hardware or different operating systems, this is fully visible to the users. If a user wants to run a program on a remote machine, he has to log onto that machine and run it here.

1.1 Uses of Computer Networks

Client-Server Model:
In this model, the data are stored on powerful computers called servers. Often there are centrally housed and maintained by a system administrator.
In contrast, the employees have simpler machines, called client, on their desk, with which they access remote data, for example, to include in spreadsheet they are constructing.
Peer-to-peer communication:
In this form, individuals who form a loose group can communicate with others in the group. Every person can, in principle, communicate with one or more other people; there is no fixed division into client and servers.

1.2 Network Hardware

Broadly speaking, there are two types of transmission technology that are in widespread use: broadcast links and point-to-point link.
Point-to-pint links: exactly one sender and exactly one receiver, packets may have to first visit one or more intermediate machines, multiple routes (finding a good one is important)
Broadcast links: packets sent by any machine are received by all the others
Classification of Network by Scale:
(1) PAN: Bluetooth to connect mouse to computer, RFID on smart card
(2) LAN: IEEE 802.11(WiFi), switched Ethernet
Static and dynamic allocation of channel
(3) MAN: cable television networks
(4) WAN: span a country or continent

1.3 Network Software

Fig 1-13
The entities comprising the corresponding layers on different machines are called peers. It is peers that communicate by using the protocol to talk to each other.
Each layer passes data and control information to the layer immediately below it. Between each adjacent layer is an interface.

Fig 1-15
Service: Connection-oriented vs. connection-less
The relationship of Services to Protocols:
A service is a set of primitives (operations) that a layer provides to the layer above it. A service relates to an interface between two layers, with the lower layer being the service provider and the upper layer being the service user.
A protocol, in the contrast, is a set of rules governing the format and meaning of the packets, or messages that are exchanged by the peer entities within a layer.

1.4 Reference Models

1.4.1 The OSI Reference Model (seven layers)

(1) The Physical Layer: transmitting raw bits over a communication channel
(2) The Data Link Layer: transform a raw transmission facility into a line that appears free of undetected transmission errors.
(3) The Network Layer: controls the operation of the subnet. (determine how packets are routed from source to destination)
(4) The Transport Layer: is to accept data from above it, split it up into units if need be, pass these to the network layer, and ensure that the pieces all arrive correctly at the other end.
(5) The Session Layer: allows users on different machines to establish sessions between them
(6) The Presentation Layer: concerned with the syntax and semantics of the information transmitted
(7) The Application Layer: contains a variety of protocols that are commonly used by users, e.g. HTTP

1.4.2 The TCP/IP Reference Model
Fig 1-21

2015年8月15日星期六

[LeetCode] Binary Tree Paths

Problem:

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
["1->2->5", "1->3"]

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<String>();
        if (root == null) {
            return result;
        }
        
        List<Integer> path = new ArrayList<Integer>();
        helper(root, path, result);
        return result;
    }
    
    private void helper(TreeNode root, List<Integer> path, List<String> result) {
        path.add(root.val);
        if (root.left != null) {
            helper(root.left, path, result);
        }
        if (root.right != null) {
            helper(root.right, path, result);
        } 
        if (root.left == null && root.right == null) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < path.size(); i++) {
                sb.append(path.get(i));
                if (i != path.size() - 1) {
                    sb.append("->");
                }
            }
            result.add(new String(sb));
        }
        path.remove(path.size() - 1);
    }
}

这个递归解法感觉有些复杂了，有没有更简单的解法呢？

2015年8月9日星期日

[吐槽][口袋宝石] Room isConnected

package is.room.connected;

//How to calculate the time complexity of an algorithm using queue (or other data structure)?

//The time complexity of BFS is greater than DFS. Because the positions are enqueued multiple times?
//If use DFS the enqueued positions will never be enqueued again.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        List<Room> rooms = new ArrayList<Room>();
        rooms.add(new Room(0,0,5,5));
        rooms.add(new Room(5,4,1,1));
        System.out.println(isConnected(rooms, 9, 9));
    }
    
    public static boolean isConnected(List<Room> rooms, int m, int n) {
        if (rooms == null || rooms.size() == 0) {
            return false;
        }
        boolean[][] board = new boolean[m][n];
        
        //Calaulate the area of all the rooms
        int area = 0;
        for (Room r : rooms) {
            area += r.h * r.w;
            for (int i = r.x; i < r.x + r.w && i < m; i++) {
                for (int j = r.y; j < r.y + r.h && j < n; j++) {
                    board[i][j] = true;
                }
            }
        }
        
        //Use BFS to traverse start from the first room, take down the area of it
        Queue<Coordinate> queue = new LinkedList<Coordinate>();
        queue.offer(new Coordinate(rooms.get(0).x, rooms.get(0).y));
        
        int bfs_area = 0;
        while (!queue.isEmpty()) {
            Coordinate tmp = queue.poll();
            bfs_area += board[tmp.x][tmp.y] ? 1 : 0;
            board[tmp.x][tmp.y] = false;
            
            if (tmp.x + 1 < m && board[tmp.x + 1][tmp.y]) {
                queue.offer(new Coordinate(tmp.x + 1, tmp.y));
            }
            if (tmp.x - 1 >= 0 && board[tmp.x - 1][tmp.y]) {
                queue.offer(new Coordinate(tmp.x - 1, tmp.y));
            }
            if (tmp.y + 1 < n && board[tmp.x][tmp.y + 1]) {
                queue.offer(new Coordinate(tmp.x, tmp.y + 1));
            }
            if (tmp.y - 1 >= 0 && board[tmp.x][tmp.y - 1]) {
                queue.offer(new Coordinate(tmp.x, tmp.y - 1));
            }
        }

        return area == bfs_area;
    }
}

package is.room.connected;

public class Room {
    int x, y, w, h;
    
    //Assume (x, y) is the left bottom of the room
    //h is the height of the room
    //w is the width of the room
    
    public Room(int x, int y, int w, int h) {
        this.x = x;
        this.y = y;
        this.w = w;
        this.h = h;
    }
}

package is.room.connected;

public class Coordinate {
    int x;
    int y;
    
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

[吐槽][口袋宝石] Top View of Binary Tree

//reference: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
//Question: Is it possible to solve this problem using BFS?
package binaryTree.top.view;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Solution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        // TreeNode root = new TreeNode(1);//Used DFS first, caught a bug in
        // this test case, change to BFS
        // root.left = new TreeNode(2);
        // root.right = new TreeNode(3);
        // root.left.right = new TreeNode(4);
        // root.left.right.right = new TreeNode(5);
        // root.left.right.right.right = new TreeNode(6);

        topView(root);
    }

    public static void topView(TreeNode root) {
        if (root == null) {
            return;
        }

        Deque<TreeNode> deque = new LinkedList<TreeNode>();
        Set<Integer> set = new HashSet<Integer>();
        Queue<QueueItem> queue = new LinkedList<QueueItem>();

        queue.offer(new QueueItem(root, 0));

        while (!queue.isEmpty()) {
            QueueItem item = queue.poll();
            if (item.node == null) {
                continue;
            }

            if (!set.contains(item.order)) {
                set.add(item.order);
                if (item.order <= 0) {
                    deque.addFirst(item.node);
                } else {
                    deque.addLast(item.node);
                }
            }

            queue.offer(new QueueItem(item.node.left, item.order - 1));
            queue.offer(new QueueItem(item.node.right, item.order + 1));
        }

        for (TreeNode t : deque) {
            System.out.print(t.value);
            System.out.print(" ");
        }
    }
}

package binaryTree.top.view;

public class QueueItem {
    TreeNode node;
    int order;
    public QueueItem(TreeNode node, int order) {
        this.node = node;
        this.order = order;
    }
}

package binaryTree.top.view;

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int value) {
        this.value = value;
    }
}

[吐槽][口袋宝石] Serialize/Deserialize a Binary Tree

import java.util.ArrayList;
import java.util.List;


public class SerializeSolution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        
        System.out.println(serialize(root));
        System.out.println(deserialize("0 1 3 # # 4 # # 2 5 # # 6 # #"));
    }
    
    public static String serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        return Integer.toString(root.val) + " " + 
                serialize(root.left) + " " + serialize(root.right);
    }
    
    public static TreeNode deserialize(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        List<String> nodes = new ArrayList<String>();
        for (String tmp : s.split(" ")) {
            nodes.add(tmp);
        }
        return helper(nodes);    
    }
    
    public static TreeNode helper(List<String> nodes) {
        if (nodes.size() == 0) {
            return null;
        }
        
        if (nodes.get(0).equals("#")) {
            nodes.remove(0);
            return null;
        }
        
        int val = Integer.parseInt(nodes.get(0));
        nodes.remove(0);
        TreeNode root = new TreeNode(val);
        root.left = helper(nodes);
        root.right = helper(nodes);
        
        return root;
    }
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "TreeNode [val=" + val + ", left=" + left + ", right=" + right
                + "]";
    }
}

2015年8月1日星期六

[吐槽] Snake Sequence

Problem:

You are given a grid of numbers. A snake sequence is made up of adjacent numbers such that for each number, the number on the right or the number below it is +1 or -1 its value. For example,

1 3 2 6 8

-9 7 1 -1 2

1 5 0 1 9

In this grid, (3, 2, 1, 0, 1) is a snake sequence.

Given a grid, find the longest snake sequences and their lengths (so there can be multiple snake sequences with the maximum length).

Thinking:

Use dynamic programming to find the possible maximum of snake sequence in the matrix. Then, use another method to get that snake sequence.

Java Code:

import java.util.ArrayList;
import java.util.List;

public class Snake {
    public static void findSnake(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int[][] dp = new int[matrix.length][matrix[0].length];
        int max = findMax(matrix, dp);

        List<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (dp[i][j] == max) {
                    backtrack(matrix, dp, i, j, result, new ArrayList<String>());
                }
            }
        }

        for (List<String> list : result) {
            for (String s : list) {
                System.out.println(s);
            }
            System.out.println();
        }
    }

    public static int findMax(int[][] matrix, int[][] dp) {
        int max = 1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dp[i][j] = 1;
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (i > 0 && Math.abs(matrix[i - 1][j] - matrix[i][j]) == 1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + 1);
                }
                if (j > 0 && Math.abs(matrix[i][j - 1] - matrix[i][j]) == 1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + 1);
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }

    public static void backtrack(int[][] matrix, int[][] dp, int i, int j,
            List<ArrayList<String>> result, List<String> path) {
        if (dp[i][j] == 1) {
            path.add("matrix[" + i + "][" + j + "]: " + matrix[i][j]);
            result.add(new ArrayList<String>(path));
            return;
        }

        if (i > 0 && dp[i - 1][j] == dp[i][j] - 1
                && Math.abs(matrix[i - 1][j] - matrix[i][j]) == 1) {
            path.add("matrix[" + i + "][" + j + "]: " + matrix[i][j]);
            backtrack(matrix, dp, i - 1, j, result, path);
            path.remove(path.size() - 1);
        }

        if (j > 0 && dp[i][j - 1] == dp[i][j] - 1
                && Math.abs(matrix[i][j - 1] - matrix[i][j]) == 1) {
            path.add("matrix[" + i + "][" + j + "]: " + matrix[i][j]);
            backtrack(matrix, dp, i, j - 1, result, path);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[][] matrix = { { 5, 3, 2, 4 }, { 4, 3, 1, -1 }, { 2, 1, 0, -1 },
                { 6, 0, 7, 0 } };
        findSnake(matrix);
    }
}

Reference:
http://www.1point3acres.com/bbs/thread-111959-1-1.html
http://www.careercup.com/question?id=14946605

2015年7月31日星期五

[笔记] 关于 Soptify 和摆臂频率

Soptify 的教程，直接照着做就行了：
https://developer.spotify.com/technologies/spotify-ios-sdk/tutorial/

检测当前跑者摆臂频率：
这个是自己写的，逻辑上分为两个部分：

维护摆臂时间记录的数组：当垂直方向y的加速度绝对值大于0.8且距离上次有效的摆臂超过一定时间间隔时，记为摆臂有效，把当前时间存入一个NSMutableArray中。当这个NSMutableArray中的元素个数超过20时，删掉其中 index＝0 的元素。

当前摆臂频率：根据上面提到的数组，取出第一个和最后一个元素，算时间间隔 interval1。再计算当前时刻和数组中最后一个元素的时间间隔 interval2。给出速度的定义为：每秒钟摆臂的次数。那么，这个速度的值就与 interval1 和 interval2 成正比。这个速度越大，说明摆臂的频率越低。

现在有一个问题就是，如果使用者一直竖着拿着手机，即使没有动，也会识别为摆臂频率很高。

GitHub链接：https://github.com/1992chenlu/TempoDemo

[笔记] 使用 CLLocationManager 实现 RunKeeper

这篇难度系数极低，主要关于如何维护使用者已经跑出的距离(distance 变量)……
算两个CLLocation之间的距离本来想用一个地球半径相关复杂公式算的，但是既然有现成的，还是省省吧……

用这个初始化CLLocationManager：

- (void)startLocationUpdates
{
    // Create the location manager if this object does not
    // already have one.
    if (self.locationManager == nil) {
        self.locationManager = [[CLLocationManager alloc] init];
    }
 
    self.locationManager.delegate = self;
    self.locationManager.desiredAccuracy = kCLLocationAccuracyBest;
    self.locationManager.activityType = CLActivityTypeFitness;
 
    // Movement threshold for new events.
    self.locationManager.distanceFilter = 10; // meters
 
    [self.locationManager startUpdatingLocation];
}

用这段更新已经跑出的距离：

- (void)locationManager:(CLLocationManager *)manager
     didUpdateLocations:(NSArray *)locations
{
    for (CLLocation *newLocation in locations) {
        if (newLocation.horizontalAccuracy < 20) {
 
            // update distance
            if (self.locations.count > 0) {
                self.distance += [newLocation distanceFromLocation:self.locations.lastObject];
            }
 
            [self.locations addObject:newLocation];
        }
    }
}

注意：在使用CLLocationManager时，需要在Supporting File 的 info.plist 中加这样两行，否则没有办法用（调了好久才发现，还没搞清楚为啥）。

<!-- for requestAlwaysAuthorization -->
    <key>NSLocationAlwaysUsageDescription</key>
    <string>Explain for what are you using the user location</string>
    <!-- for requestWhenInUseAuthorization -->
    <key>NSLocationWhenInUseUsageDescription</key>
    <string>Explain for what are you using the user location</string>

代码链接：https://gist.github.com/1992chenlu/2ec71e9dc5d3d6588160

Reference: http://www.raywenderlich.com/73984/make-app-like-runkeeper-part-1

[笔记] 关于 NSThread

这回的作业需要一直根据x,y,z三个方向的加速度维护一个变量，另外有个线程每隔一秒访问一次这个变量，根据变量的值判断输出音乐的频率。于是就先写了下面这么个程序练手。

下面这个东西干了这么个事情：分出两个Thread，都执行对value值+1，并打印的操作。
吐槽：笔者写似乎是个线程不安全的典型，请勿参考。

//
//  ViewController.m
//  MTTest
//
//  Created by 鲁辰 on 7/29/15.
//  Copyright (c) 2015 ChenLu. All rights reserved.
//

#import "ViewController.h"

@interface ViewController ()

@property (nonatomic, assign) NSUInteger value;

@end

@implementation ViewController
@synthesize value;

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    
    //NSThread
    [NSThread detachNewThreadSelector:@selector(run) toTarget:self withObject:nil];
    
    NSThread* myThread = [[NSThread alloc] initWithTarget:self
                                                   selector:@selector(run)
                                                     object:nil];
    [myThread start];

}

- (void)didReceiveMemoryWarning {
    [super didReceiveMemoryWarning];
    // Dispose of any resources that can be recreated.
}

- (void)run {
    while (YES) {
        @synchronized(self) {
            value++;
        }
        NSThread *current = [NSThread currentThread];
        NSLog(@"Value: %lu, Thread: %@", (unsigned long)value, current);
        sleep(1);
    }
}

@end

代码链接：https://gist.github.com/1992chenlu/41b3adfb10d01ac36dda

Reference:
http://www.raywenderlich.com/60749/grand-central-dispatch-in-depth-part-1（这一篇很好，有时间应该细读）
http://www.cnblogs.com/likwo/archive/2011/11/01/2232309.html
http://sodecon.blogspot.com/2012/08/ios-multithreading-thread-safety-in-ios.html
http://www.libaocai.com/network/ios/2014/12/30/608

http://blog.csdn.net/zhangao0086/article/details/38904923（这篇关于GCD，还没搞明白T_T）

2015年7月29日星期三

[吐槽]YouTube Play On Repeat

YouTube video URL:

吐槽: 总是找不到YouTube重复播放的功能在哪里选，干脆写了一个……汗

https://gist.github.com/1992chenlu/0c3035086ea4c12b297e

2015年7月27日星期一

[LeetCode] Different Ways to Add Parentheses

Java Code:

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList<Integer>();
        if (input == null || input.length() == 0) {
            return result;
        }
        
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c != '+' && c != '-' && c != '*') {
                continue;
            }
            
            List<Integer> part1Result = 
                diffWaysToCompute(input.substring(0, i));
            List<Integer> part2Result = 
                diffWaysToCompute(input.substring(i + 1, input.length()));
            
            for (Integer m : part1Result) {
                for (Integer n : part2Result) {
                    if (c == '+') {
                        result.add(m + n);
                    } else if (c == '-') {
                        result.add(m - n);
                    } else if (c == '*') {
                        result.add(m * n);
                    }
                }
            }
        }
        
        if (result.size() == 0) {
            result.add(Integer.parseInt(input));
        }
        
        return result;
    }
}

reference:
https://leetcode.com/discuss/48477/a-recursive-java-solution-284-ms

[LeetCode] Search a 2D Matrix II

Java Code:

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 
            || matrix[0].length == 0) {
            return false;
        }
        
        int i = 0;
        int j = matrix[0].length - 1;
        
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        
        return false;
    }
}

reference:
https://leetcode.com/discuss/47660/my-java-solution-using-binary-search

2015年7月26日星期日

[笔记] About XML Parser

http://www.javacodegeeks.com/2012/01/xml-parsing-using-saxparser-with.html

http://www.saxproject.org/quickstart.html

2015年7月24日星期五

[LeetCode] Maximum Product Subarray

Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Java Code:

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int result = nums[0];
        int[] maxProduct = new int[nums.length];
        int[] minProduct = new int[nums.length];
        maxProduct[0] = nums[0];
        minProduct[0] = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            int[] tmp = new int[3];
            tmp[0] = nums[i];
            tmp[1] = nums[i] * maxProduct[i - 1];
            tmp[2] = nums[i] * minProduct[i - 1];
            
            Arrays.sort(tmp);
            
            result = Math.max(result, tmp[2]);
            maxProduct[i] = tmp[2];
            minProduct[i] = tmp[0];
        }
        
        return result;
    }
}

reference: https://leetcode.com/discuss/41102/share-accepted-dp-java-o-n-solution

2015年7月22日星期三

"Layers" of Cache

There are in fact many layers of cache in a modern PC. This does not even include looking at caches included on some peripherals, such as hard disks. Each layer is closer to the processor and faster than the layer below it. Each layer also caches the layers below it, due to its increased speed relative to the lower levels:

Level	Devices Cached
Level 1 Cache	Level 2 Cache, System RAM, Hard Disk / CD-ROM
Level 2 Cache	System RAM, Hard Disk / CD-ROM
System RAM	Hard Disk / CD-ROM
Hard Disk / CD-ROM	--

What happens in general terms is this. The processor requests a piece of information. The first place it looks is in the level 1 cache, since it is the fastest. If it finds it there (called a hit on the cache), great; it uses it with no performance delay. If not, it's a miss and the level 2 cache is searched. If it finds it there (level 2 "hit"), it is able to carry on with relatively little delay. Otherwise, it must issue a request to read it from the system RAM. The system RAM may in turn either have the information available or have to get it from the still slower hard disk or CD-ROM. The mechanics of how the processor (really the chipset controlling the cache and memory) "look" for the information in these various places is discussed here.

It is important to realize just how slow some of these devices are compared to the processor. Even the fastest hard disks have an access time measuring around 10 milliseconds. If it has to wait 10 milliseconds, a 200 MHz processor will waste 2 million clock cycles! And CD-ROMs are generally at least 10 times slower. This is why using caches to avoid accesses to these slow devices is so crucial.

Caching actually goes even beyond the level of the hardware. For example, your web browser uses caching itself, in fact, two levels of caching! Since loading a web page over the Internet is very slow for most people, the browser will hold recently-accessed pages to save it having to re-access them. It checks first in its memory cache and then in its disk cache to see if it already has a copy of the page you want. Only if it does not find the page will it actually go to the Internet to retrieve it.

reference: http://www.pcguide.com/ref/mbsys/cache/layers.htm

Difference between Virtual Memory and Physical Memory

Virtual memory is, among other things, an abstraction to give the programmer the illusion of having infinite memory available on their system.

Virtual memory mappings are made to correspond to actual physical addresses. The operating system creates and deals with these mappings - utilizing the page table, among other data structures to maintain the mappings. Virtual memory mappings are always found in the page table or some similar data structure (in case of other implementations of virtual memory, we maybe shouldn't call it the "page table"). The page table is in physical memory as well - often in kernel-reserved spaces that user programs cannot write over.

Virtual memory is typically larger than physical memory - there wouldn't be much reason for virtual memory mappings if virtual memory and physical memory were the same size.

Only the needed part of a program is resident in memory, typically - this is a topic called "paging". Virtual memory and paging are tightly related, but not the same topic. There are other implementations of virtual memory, such as segmentation.

I could be assuming wrong here, but I'd bet the things you are finding hard to wrap your head around have to do with specific implementations of virtual memory, most likely paging. There is no one way to do paging - there are many implementations and the one your textbook describes is likely not the same as the one that appears in real OSes like Linux/Windows - there are probably subtle differences.

reference: http://stackoverflow.com/questions/14347206/what-are-the-differences-between-virtual-memory-and-physical-memory

2015年7月21日星期二

Database/SQL Interview Questions and Answers

1. What is a field in database?
A field is an area within a record reserved for a specific piece of data.

2. What is a record in a database?
A record is the collection of values/fields of a specific entity.

3. What is a table in database?
A table is a collection of records of a specific type.

4. What is a database transaction?
Database transaction takes database from one state to another. At the end of the transaction the system must be in the prior state if the transaction fails or the status of the system reflect the successful completion if the transaction goes through.

5. What are properties of a transaction? (ACID properties)
(1) Atomicity
A transaction consists of many steps. When all the steps in a transaction get completed, it will get reflected in DB or if any step fails, all the transactions are rolled back.

(2) Consistency (* What is the difference between consistency and atomocity?)
The database will move from one consistent state to another, if the transaction succeeds and remainin the original state, if transaction fails.

(3) Isolation
Every transaction should operate as if it is the only transaction in the system.

(4) Durability
Once a transaction has been completed successfully, the update rows/records must be available for all the other transactions on a permanent basis.

5. What is a composite key?
A composite primary key is a type of candidate key, which represents a set of columns whose values uniquely identified every row in a table.
e.g. Combination of "employee id" and "employee name" in a table is combined to uniquely to identify a row its called a composite key.

6. What is a foreign key?
A foreign key is a column (or columns) that references a column (most often the primary key) of another table.

7. What is a unique key?
Unique key is same as primary with the difference being the existence of null.

8. SQL insert statement:
SQL INSERT statement is used to add rows to a table. For a full row insert, SQL query should start with "insert into" statement followed by name and value command. The insert can be used in several ways:
(1) to insert a single complete row
(2) to insert a single partial row

9. SQL update statement:

10. SQL delete statement:

11. What are wild cards used in database for pattern matching?
SQL like operator is used for pattern matching.

12. Define join and explain different type of joins:
In order to avoid data duplications, data is stored in related tables. Join keyword is used to fetch data from related tables. "join" return rows when there is at least one match in both table. Type of joins are:
(1) right join: return all rows from the right table, even if there are no matches in the left table
(2) left join: return all rows from the left table even if there are no matches in the right table
(3) full join: return rows when there is a match in one of the tables

13. What is self join?
Self join is query used to join a table itself.
(* When will self join be used?)

14. What is cross join?(*)

15. What is a view?
The views are virtual tables. Unlike tables that contain data, views simply contain queries that dynamically retrieve data when used.

16. What is a materialized view?
Materialized views are also a view but are disk based. Materialized views get updates on specific duration, base upon the interval specified in the query definition.

17. What are the advantages and disadvantages of views in a database?
Advantages:
(1) Views don't store data in a physical location
(2) The view can be used to hide some of the columns from the table
(3) Views can provide access restriction, since data insertion, update and deletion is not possible with the view.

Disadvantages:
(1) When a table is dropped, associate view become irrelevant.
(2) Since the view is created when a query requesting data from view is triggered, its a bit slow
(3) When viwes are created for large tables, it occupies memory

18. What is a stored procedure?
Stored procedure is a function which contains a collection of SQL queries. The procedure can take inputs, process tham and send back output.

19. What are the advantages of a stored procedure?
Stored procedure are precompiled and stored in the database. This enables the database to execute the queries much faster. Since many queries can be included in a stored procedure, round trip time to execute multiple queries from source code to database and back is avoided.

20. What is a trigger?
Database triggers are sets of commands that get executed when an event (before insert, after insert, on update, on delete of a row) occurs on a table, vies.

21. Explain the difference between delete, truncate and drop commands?
Once delete operation is performed, commit and rollback can be performed to retrieve data.
Once truncate statement is executed, commit and rollback statement cannot be performed. Where condition can be used along with delete statement but it can't be used with truncate statement.
Drop command is used to drop the table or keys like primary foreign key from a table.

22. What is the difference between cluster and non cluster index?
A cluster index reorders the way records in the table are physically stored. There can be only one clustered index per table. It makes data retrieval faster.
A non clustered index does not alter the way it was stored but creates a completely separate object within the table. As a result insert and update command will be faster.

23. What is union, minus and interact command?
minus operator is used to return rows from the first query but not from the second query.
intersect operator is used to return rows returned by both queries.

reference: http://a4academics.com/interview-questions/53-database-and-sql/411-sql-interview-questions-and-answers-database

24. 1NF/2NF/3NF
First normal form (1NF) is a property of a relation in a relational database. A relation is in first normal form if the domain of each attribute contains only atomic values, and the value of each attribute contains only a single value from that domain.

A table that is in first normal form (1NF) must meet additional criteria if it is to qualify for second normal form. Specifically: a table is in 2NF if and only if it is in 1NF and no non-prime attribute is dependent on any proper subset of any candidate key of the table. A non-prime attribute of a table is an attribute that is not a part of any candidate key of the table.

Put simply, a table is in 2NF if and only if it is in 1NF and every non-prime attribute of the table is dependent on the whole of every candidate key.

Third normal form(3NF) is a normal form used in normalizing a database design to reduce the duplication of data and ensure referential integrity by ensuring that the entity is in second normal form and all the attributes in a table are determined only by the candidate keys of that table and not by any non-prime attributes.

Linux系统生成，进（线）程同步与通信，并发程序的誊抄，文件目录操作

脑洞：都忘光了，捞出来补一补

reference:

http://wenku.baidu.com/view/20f19b276c175f0e7cd137b7.html

http://wenku.baidu.com/view/522c5b27e2bd960590c677cf.html

0 Linux系统生成

步骤：
（1）安装Linux系统Ubuntu10.12
（2）使用ctrl+alt+T打开终端
（3）设置root用户及root用户密码：使用的命令如图所示

（4）进入root用户
（5）把源码包解压到 /usr/src/linux-3.6.3

（6）编译内核：使用make命令

（7）安装编译好的内核

（8）查看内核版本

1 实验一LINUX系统用户界面实验二进（线）程同步与通信

1.1 实验目的

1、掌握Linux系统用户界面中键盘命令的使用。
2、学会一种Linux下的编程环境。
3、掌握Linux下进（线）程的概念。
4、了解Linux进程同步与通信的主要机制，并通过信号灯操作实现进程间的同步与互斥。

1.2 预备知识

1.2.1 Linux下的信号灯及其P、V操作

表1. 1 P、V操作定义

P操作	V操作
void P(int semid,int index) { struct sembuf sem; sem.sem_num = index; sem.sem_op = -1; sem.sem_flg = 0; //：操作标记：0或IPC_NOWAIT等 semop(semid,&sem,1); //1:表示执行命令的个数 return; }	void V(int semid,int index) { struct sembuf sem; sem.sem_num = index; sem.sem_op = 1; sem.sem_flg = 0; semop(semid,&sem,1); return; }

1.2.2 线程

表1. 2 线程相关函数

线程创建	pthread_create(pthread_t thread, pthread_attr_t attr, void (start_routine)(void ),void arg);
线程挂起	pthread_join(pthread_t th, void **thread_retrun);

1.2.3 共享内存
使用共享内存是运行在同一计算机上的进程进行进程间通信的最快的方法，shmget与shmat 系统调用。

1.2.4 进程控制
fork与execv系统调用

1.2.5 编译、编辑、调试

表1. 3 编译、编辑、调试

编译	cc –o test -g test.c –lpthread cc –o sub1 sub1.c
编辑	vi
调试	gdb

1.3 实验内容

实验一的程序要求:
两个线程,共享公共变量a
线程1负责计算(+1)
线程2负责打印
实现：
1、线程的同步与互斥
2、进程的同步与互斥
3、子进程的创建
1.4 运行结果

图1. 1 运行结果

1.5 源代码

#include <stdio.h>

#include <stdlib.h>

#include <pthread.h>

#include <sys/types.h>

#include <linux/sem.h>

#define LOOPS 10

void P(int semid,int index);

void V(int semid,int index);

int semid;int a=0;

pthread_t p1,p2;

void *subp1();void *subp2();

void P(int semid,int index)

{

struct sembuf sem;

sem.sem_num = index;

sem.sem_op = -1;

sem.sem_flg = 0; //：操作标记：0或IPC_NOWAIT等

semop(semid,&sem,1); //1:表示执行命令的个数

return;

}

void V(int semid,int index)

{

struct sembuf sem;

sem.sem_num = index;

sem.sem_op = 1;

sem.sem_flg = 0;

semop(semid,&sem,1);

return;

}

void *subp1()

{

int i,j;

for (i=0; i< LOOPS;i++)

{

P(semid,0);

printf("subp1:a=%d\n",a);

V(semid,1);

}

return;

}

void *subp2()

{

int i,j;

for (i=0;i<LOOPS;i++)

{

P(semid,1);

a+=1;

V(semid,0);

}

return;

}

main()

{

union semun semopts;

int res;

semid =semget(11,2,IPC_CREAT|0666);

semopts.val = 0;

res=semctl(semid,0,SETVAL,semopts);

semopts.val = 1;

res=semctl(semid,1,SETVAL,semopts);

pthread_create(&p1,NULL,subp1,NULL);

pthread_create(&p2,NULL,subp2,NULL);

pthread_join(p1,NULL);

pthread_join(p2,NULL);

semctl(semid,0,IPC_RMID,0);

}

2在linux下编程实现P98 4-11

2.1 实验目的

了解并发程序的执行过程和实现原理

2.2 预备知识

2.2.1 并发程序的誊抄

图2. 1 誊抄过程

get程序：负责从输入序列f中读取字符并送到缓冲区s中;
copy程序：把缓冲区s中的数据复制到缓冲区t中去;
put程序：从缓冲区t中取出数据打印。

2.2.2 誊抄的实现

图2. 2 誊抄的实现

在相应的圆圈对应的进程中，通过修改箭头上对应序号的信号灯控制进程的运行，设有4个信号灯分别为0、1、2、3
在进程中对信号灯的控制可简写为：

get() { p(0); get操作； v(2); }	copy() { p(1); p(2); copy操作； v(0); v(3); }	put() { p(3); put操作； v(1); }
通过设置信号灯0的初值和利用copy对信号灯0做v操作，使得当信号灯0的资源个数>0时，可以进行get操作	通过设置信号灯1、2的初值和利用put对信号灯1做v操作、利用get对信号灯2做v操作，使得当信号灯1和信号灯2的资源个数均>0时，可以进行copy操作	通过设置信号灯3的初值和利用copy对信号灯3做v操作，使得当信号灯3的资源个数>0时，可以进行put操作

2.3 实验内容

1、实现: main、get、copy、put 4个函数
2、将这四个函数编译链接（使用makefile）
2.4 运行结果

图2. 3 运行结果

使用./main打开程序

2.5 源代码

main.c

#include<stdio.h>

#include<stdlib.h>

#include<linux/shm.h>

#include<sys/types.h>

#include<linux/sem.h>

#define LOOPS 10

#define IPCKEY (key_t)0x11

#define SHMKEY1 (key_t)0x222

#define SHMKEY2 (key_t)0x333

void P(int semid,int index);

void V(int semid,int index);

int semid;

void V(int semid,int index)

{

struct sembuf sem;

sem.sem_num = index;/*信号灯数组灯的一个索引，指明哪个信号灯*/

sem.sem_op = 1;/*加到当前信号灯的数值*/

sem.sem_flg = 0;

semop(semid,&sem,1);

return;

}

void P(int semid,int index)

{

struct sembuf sem;

sem.sem_num = index;

sem.sem_op = -1;

sem.sem_flg = 0;

semop(semid,&sem,1);

return;

}

int main(void)

{

union semun semopts;

int res,i;

struct shmid_ds *buf;

int cmd;

int shmid1,shmid2;

char *s,*t,ss[]="";

pid_t p1,p2,p3;

semid = semget(IPCKEY,4,IPC_CREAT|0666);

semopts.val = 1;

res = semctl(semid,0,SETVAL,semopts);

semopts.val = 1;

res = semctl(semid,1,SETVAL,semopts);

semopts.val = 0;

res = semctl(semid,2,SETVAL,semopts);

semopts.val = 0;

res = semctl(semid,3,SETVAL,semopts);

shmid1 = shmget(SHMKEY1,sizeof(char),IPC_CREAT|0666);

s=(char *)shmat(shmid1,NULL,SHM_R|SHM_W);

shmid2 = shmget(SHMKEY2,sizeof(char),IPC_CREAT|0666);

t=(char *)shmat(shmid2,NULL,SHM_R|SHM_W);

if((p1=fork()) == 0){

execv("./get",NULL);

}

else

{

if((p2=fork()) == 0){

execv("./copy",NULL);

}

else

{

if((p3=fork())==0){

execv("./put",NULL);

}

p1=wait(&p1);

p2=wait(&p2);

p3=wait(&p3);

/*for(i=0;i<3;i++)

{

while(-1!=wait())

;

}*/

if(semctl(semid,0,IPC_RMID,0)<0)

printf("error");

shmctl(shmid1,IPC_RMID,0);

shmctl(shmid2,IPC_RMID,0);

return 0;

}

get.c

#include<stdio.h>

#include<stdlib.h>

#include<sys/types.h>

#include<linux/sem.h>

#include<linux/shm.h>

#define LOOPS 10

#define IPCKEY (key_t)0x11

#define SHMKEY1 (key_t)0x222

#define SHMKEY2 (key_t)0x333

void P(int semid,int index);

void V(int semid,int index);

int semid;

void V(int semid,int index)

{

struct sembuf sem;

sem.sem_num = index;/*信号灯数组灯的一个索引，指明哪个信号灯*/

sem.sem_op = 1;/*加到当前信号灯的数值*/

sem.sem_flg = 0;

semop(semid,&sem,1);

return;

}

void P(int semid,int index)

{

struct sembuf sem;

sem.sem_num = index;

sem.sem_op = -1;

sem.sem_flg = 0;

semop(semid,&sem,1);

return;

}

int main(void)

{

int i=0;

int shmid1;

char *s,*t,str[]="linux!";/*str为输入的字符，实现一个一个字符的输入，输出，s，t指针当单个字符使用，即s[0],t[0]*/

semid = semget(IPCKEY,4,IPC_CREAT|0666);

shmid1 = shmget(SHMKEY1,sizeof(char),IPC_CREAT|0666);

s=(char *)shmat(shmid1,NULL,SHM_R|SHM_W);/* 绑定到共享内存块 */

{

P(semid,0);

s[0]=str[i];

printf("get\n");

i++;

V(semid,2);

}while(s[0]!='\0');

}

copy.c

#include<stdio.h>

#include<stdlib.h>

#include<sys/types.h>

#include<linux/sem.h>

#include<linux/shm.h>

#define LOOPS 10

#define IPCKEY (key_t)0x11

#define SHMKEY1 (key_t)0x222

#define SHMKEY2 (key_t)0x333

void P(int semid,int index);

void V(int semid,int index);

int semid;

void V(int semid,int index)

{

struct sembuf sem;

sem.sem_num = index;/*信号灯数组灯的一个索引，指明哪个信号灯*/

sem.sem_op = 1;/*加到当前信号灯的数值*/

sem.sem_flg = 0;

semop(semid,&sem,1);

return;

}

void P(int semid,int index)

{

struct sembuf sem;

sem.sem_num = index;

sem.sem_op = -1;

sem.sem_flg = 0;

semop(semid,&sem,1);

return;

}

int main(void)

{

int j=0;

int shmid1,shmid2;

char *s,*t;

semid = semget(IPCKEY,4,IPC_CREAT|0666);

shmid1 = shmget(SHMKEY1,sizeof(char),IPC_CREAT|0666);

s=(char *)shmat(shmid1,NULL,SHM_R|SHM_W);/* 绑定到共享内存块 */

shmid2 = shmget(SHMKEY2,sizeof(char),IPC_CREAT|0666);

t=(char *)shmat(shmid2,NULL,SHM_R|SHM_W);

{

P(semid,1);

P(semid,2);

strcpy(t,s);

printf("copy\n");

V(semid,0);

V(semid,3);

}while(t[0]!='\0');

}

put.c

#include<stdio.h>

#include<stdlib.h>

#include<sys/types.h>

#include<linux/sem.h>

#include<linux/shm.h>

#define LOOPS 10

#define IPCKEY (key_t)0x11

#define SHMKEY1 (key_t)0x222

#define SHMKEY2 (key_t)0x333

void P(int semid,int index);

void V(int semid,int index);

int semid;

void V(int semid,int index)

{

struct sembuf sem;

sem.sem_num = index;/*信号灯数组灯的一个索引，指明哪个信号灯*/

sem.sem_op = 1;/*加到当前信号灯的数值*/

sem.sem_flg = 0;

semop(semid,&sem,1);

return;

}

void P(int semid,int index)

{

struct sembuf sem;

sem.sem_num = index;

sem.sem_op = -1;

sem.sem_flg = 0;

semop(semid,&sem,1);

return;

}

int main(void)

{

int k=0;

int shmid1,shmid2;

char *s,*t;

semid = semget(IPCKEY,4,IPC_CREAT|0666);

shmid2 = shmget(SHMKEY2,sizeof(char),IPC_CREAT|0666);

t=(char *)shmat(shmid2,NULL,SHM_R|SHM_W);/* 绑定到共享内存块 */

{

/*if(t[0]=='\0')break;*/

P(semid,3);

if(t[0]!='\0')printf("put---->%c\n",*t);

else printf("put---->\\0\n");

V(semid,1);

}while(t[0]!='\0');

}

makefile

all:get copy put main

echo "complete"

get:get.o

gcc -o get get.o

copy:copy.o

gcc -o copy copy.o

put:put.o

gcc -o put put.o

main:main.o

gcc -o main main.o

get.o:get.c

gcc -c get.c

copy.o:copy.c

gcc -c copy.c

put.o:put.c

gcc -c put.c

main.o:main.c

gcc -c main.c

3 实验三 Linux文件目录操作

3.1 实验目的、实验要求

3.1.1实验目的
了解并掌握Linux文件目录结构。

3.1.2 实验要求
了解Linux文件系统与目录操作：
（1） Linux文件系统：文件属性；
（2）Linux目录结构：目录文件；
（3）目录相关函数接口；

3.2 实验内容
1、熟悉Linux文件系统的使用；
2、了解Linux文件系统目录结构；
3、编程实现目录查询命令；
• 功能类似ls -lR；
• 查询指定目录下的文件及子目录信息；
显示文件的类型、大小、时间等信息；
• 递归显示子目录中的文件信息；

3.3 预备知识

3.3.1 Linux文件属性接口

表3. 1 文件属性接口

函数	功能
int fstat(int fildes,struct stat *buf);	返回文件描述符相关的文件的状态信息
int lstat(const char path, struct stat buf);	如读取到了符号连接，读取符号连接本身的状态信息
int stat(const char path, struct stat buf);	如读取到了符号连接，读取的是符号连接指向文件的信息

stat结构体几乎保存了所有的文件状态信息：
本程序中主要用到st_mode 文件的权限信息和类型信息，检查类型时使用S_ISDIR(); 宏，检查是否是目录

3.3.2 Linux目录结构接口

表3. 2 目录结构接口

函数	功能
DIR opendir(const char name);	通过路径打开一个目录，返回一个DIR结构体指针(目录流)，失败返回NULL；
struct dirent readdir(DIR )	读取目录中的下一个目录项，没有目录项可以读取时，返回为NULL；
int chdir(const char *path);	改变目录,与用户通过cd命令改变目录一样，程序也可以通过chdir来改变目录，这样使得 fopen(),opendir(),这里需要路径的系统调用，可以使用相对于当前目录的相对路径打开文件(目录)。
int closedir(DIR*)	关闭目录流

在本程序中，用到结构dirent中的char d_name[256]; （文件名）项

3.4 运行结果

图3. 1 运行结果

3.5 源代码

#include <unistd.h>

#include <sys/stat.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <dirent.h>

void printdir(char *dir, int depth){

DIR *dp;

struct dirent *entry;

struct stat statbuf;

if (((dp = opendir(dir)))== NULL){ // opendir

printf("Open Dir Failed!\n");

return ;

}

chdir(dir); //chdir

while( (entry=readdir(dp))!=NULL){ //readdir

lstat(entry->d_name,&statbuf);

if(S_ISDIR(statbuf.st_mode)){

if(strcmp(entry->d_name,"..")==0||strcmp(entry->d_name,".")==0)

continue;

printf("DIR DEPTH: %d ",depth);

printf("DIR NAME: %s\n",entry->d_name);

printdir(entry->d_name,depth+1);

}

else

{

printf("FILE DEPTH: %d ",depth);

printf("FILE NAME: %s\n",entry->d_name);

} }

chdir("..");//chdir

closedir(dp); //closedir

}

int main(void){

char a[50];

printf("Input Dir Name!\n");

scanf("%s",a);

printdir(a,0);

return 0;

}

订阅：博文 (Atom)

2015年12月23日星期三

2015年12月3日星期四

2015年12月1日星期二

2015年11月27日星期五

2015年11月24日星期二

2015年11月23日星期一

2015年11月20日星期五

2015年11月19日星期四

2015年11月17日星期二

2015年11月16日星期一

2015年11月15日星期日

2015年11月10日星期二

Git

Java

Networking

Linux

2015年9月17日星期四

1. Equality Operators

2. The Plus Operator

3. Special Operators

2015年9月15日星期二

1.JavaScript's Type System

2. Primitive Values versus Objects

3. Wrapper Objects

2015年9月14日星期一

1. Expression Versus Statements

2. Rules for Using Semicolons

3. Legal Identifiers

4. Invoking Methods on Number Literals

5. Strict Mode

2015年9月8日星期二

Speaking JavaScript

Preface

Chapter 1: Basic JavaScript

1.1 Syntax1.1.1 Overview of Syntax

1.1.2 Statements v. Expression

1.1.3 Semicolons: recommended

1.2 Values

1.2.1 Primitive Values v. Objects

1.2.2 Primitive Values

1.2.3 Objects

1.2.4 undefined and null

1.2.5 typeof and instanceof

1.3 Booleans

1.4 Numbers

1.5 Operators

1.6 Strings

1.7 Functions

1.7.1 Function and var declaration are hoisted, while assignments performed by them are not.

1.7.2 You can call any function in JavaScript with an arbitrary amount of arguments; the language will never complain.

1.7.3 special variable argument

1.8 Strict Mode

1.9 Variables Are Function-Scoped, Hoisted

1.10 Closure

1.11 Objects and Constructors

1.11.1 Single Objects

1.11.2 Arbitrary Property Keys

1.11.3 Extracting Methods

1.11.4 Functions inside a method (这里有点没搞懂)

1.11.5 Constructors: Factories for Objects

1.12 Arrays

1.13 Regular Expression(Chapter 19)

2015年9月6日星期日

Computer Networks (Fifth Edition)Chapter 1

1.1 Uses of Computer Networks

1.2 Network Hardware

1.3 Network Software

1.4 Reference Models

2015年8月15日星期六

Problem:

Java Code:

2015年8月9日星期日

2015年8月1日星期六

Problem:

Thinking:

Java Code:

2015年7月31日星期五

2015年7月29日星期三

2015年7月27日星期一

Java Code:

1.1 Syntax

1.1.1 Overview of Syntax

Computer Networks (Fifth Edition)
Chapter 1

1 实验一LINUX系统用户界面实验二进（线）程同步与通信