Question:

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Thinking:

It’s a problem can be solved in greedy algorithm. Because we should go as far as possible in current position until we can’t go father. And we should gurantee the value of current position + i (steps can be reached from current postion) + nums[cur + i] be as big as possible.

Solution:

public boolean canJump(int[] nums) {
    int l = nums.length;
    if (nums[0] == 0 && l > 1)
        return false;
    int cur = 0;
    int temp = nums[0];
    int step = nums[0];
    int max = nums[0];
    int tempcur = 0;

    while (cur + step < l-1){
        for (int i = 1; i <= step; i++){
            temp = cur + i + nums[cur + i];
            if (temp >= max){//current max greedy value
                max = temp;
                if (max >= l)
                    return true;
                tempcur = cur + i;
            }
        }
        if (cur == tempcur)
            return false;
        cur = tempcur;
        step = nums[cur];
    }

    if (max >= l-1)
        return true;
    else
        return false;
}

What’s more, we can make it easier by max the value of index.

public boolean canJump(int[] nums) {
    if(nums.length <= 1)
        return true;

    int max = nums[0]; //max stands for the largest index that can be reached.

    for(int i=0; i<nums.length; i++){
        //if not enough to go to next
        if(max <= i && nums[i] == 0) 
            return false;

        //update max    
        if(i + nums[i] > max){
            max = i + nums[i];
        }

        //max is enough to reach the end
        if(max >= nums.length-1) 
            return true;
    }

    return false;    
}

Question:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Thinking:

In order to improve the performance of algorithm, we should sort the array. Because of that, we can determine where to go using current result.

Solution:

public int threeSumClosest(int[] nums, int target) {
    int l = nums.length;
    if (l < 3)
        return 0;
    int min = Integer.MAX_VALUE;
    int res = 0;
    Arrays.sort(nums);

    for (int i = 0; i < l; i++){
        int j = i + 1;
        int k = l - 1;

        while (j < k){
            int sum = nums[i] + nums[j] + nums[k];
            if (sum == target)
                return sum;
            int diff = Math.abs(sum - target);
            if (diff < min){
                min = diff;
                res = sum;
            }
            if (sum > target)
                k--;
            else
                j++;
        }

    }
    return res;
}

Question:

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Thinking:

Inorder traversal will search in order: left, root, right;

Postorder travelsal will search in order: left, right, root.

So we can find the root in postorder and search it in inorder by the value. And find root’s left child and right child node by recursion.

public TreeNode buildTree(int[] inorder, int[] postorder) {
    int l = inorder.length;
    if (l == 0)
        return null;
    TreeNode root = new TreeNode(postorder[l-1]);
    TreeNode left = null;
    TreeNode right = null;
    int index = 0;
    for (; index < l; index++){
        if (inorder[index] == postorder[l-1])
            break;
    }


    if (index > 0){
        int[] leftinorder = new int[index];
        int[] leftpostorder = new int[index];
        System.arraycopy(inorder, 0, leftinorder, 0, index);
        System.arraycopy(postorder, 0, leftpostorder, 0, index);
        left = buildTree(leftinorder, leftpostorder);
    }
    if (index < l-1){
        int[] rightinorder = new int[l-index-1];
        int[] rightpostorder = new int[l-index-1];
        System.arraycopy(inorder, index+1, rightinorder, 0, l-index-1);
        System.arraycopy(postorder, index, rightpostorder, 0, l-index-1);
        right = buildTree(rightinorder, rightpostorder);
    }
    root.left = left;
    root.right = right;

    return root;
}

By the way, this code can be improved because in Java we can not easily get the subarray and I use the System.arraycopy. It can be replaced by recording the postion of array.

Question:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

           _______3______
         /              \
  ___5__           ___1___
    /      \         /          \
6        2       0         8
         /  \
        7    4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Thinking:

The point to find the lowest common ancestor is to find a node whose left and right childs both have the node we want to find. Because if it’s not the lowest, the node will only belong to one of their child. If search in a pre-order from the root, if one node’s left child and right child both have the keynode or if the node itself is one of the keynode which means the other node will in lower level of this node, it’s the answer we want.

Solution:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null)
        return root;

    if (root.equals(q) || root.equals(p)){
        return root;
    }

    TreeNode l = lowestCommonAncestor(root.left, p, q);
    TreeNode r = lowestCommonAncestor(root.right, p, q);
    if (l != null && r != null)
        return root;

    return l == null? r: l;
}

Survey:

Node.js is an open-source, cross-platform runtime environment for developing server-side Web applications. Node.js is not a JavaScript framework,[3] but its applications are written in JavaScript and can be run within the Node.js runtime on a wide variety of platforms.

This is my first time to learn Node.js, and I’ll write casully about the process and experience of learning.

---

Content:

–1– Argument variables with process.argv

app.js

function grab(flag){
    var index = process.argv.indexOf(flag);
    return (index === -1) ? null : process.argv[index+1];
}

var greeting = grab('--greeting');
var user = grab('--user');

if (!user || !greeting) {
    console.log("You blew it!");
} else {
    console.log(`Welcome, ${user}, ${greeting}`);
}

In this code, we grab the arguments from shell and print it out on the console.

For example, if in the shell:

$node app --user Martin --greeting "hello hello"

Then in the console:

Welcome, Martin, hello hello

And in this code, I also learned string temple which uses backticks.Welcome, ${user}, ${greeting}` will contain variable user and greeting.

---

–2– Standard input and standard output

 var questions = [
"What is your name?",
"What is your favorite hobby?",
"What is your preferred programming language?"
];

var answers = [];

function ask(i) {
    process.stdout.write(`\n\n\n\n ${questions[i]}`);
    process.stdout.write("  >  ");
}

process.stdin.on('data', function(data){

    answers.push(data.toString().trim());

    if (answers.length < questions.length) {
        ask(answers.length);
    } else {
        process.exit();
    }
});

process.on('exit', function(){

    process.stdout.write("\n\n\n\n");

    process.stdout.write(`Go ${answers[1]} ${answers[0]} you can finish writing ${answers[2]} later`);

    process.stdout.write("\n\n\n\n");

});

ask(0);

In the shell:

What is your name?  >  Martin




 What is your favorite hobby?  >  play games




 What is your preferred programming language?  >  python




Go play games Martin you can finish writing python later

Is that funny:)?

---

–3– Global timing functions

There are several functions about the timing such as setInterval, setTimeout and clearInterval. It’s useful while developing web interactive program.

Code:

var waitTime = 3000;
var currentTime = 0;
var waitInterval = 10;
var percentWaited = 0;

function writeWaitingPercent(p){
    process.stdout.clearLine();
    process.stdout.cursorTo(0);
    process.stdout.write(`waiting ... ${p}%`);

}


var interval = setInterval(function(){
    currentTime += waitInterval;
    percentWaited = Math.floor((currentTime/    waitTime)*100);
    //console.log(`waiting ${currentTime/1000} seconds`);
    writeWaitingPercent(percentWaited);
}, waitInterval);

setTimeout(function(){

    clearInterval(interval);
    console.log("\ndone");
}, waitTime);

process.stdout.write("\n\n");
writeWaitingPercent(percentWaited);

In the shell:

waiting ... 81%
done

–4– Core modules:

Node.js use require function to get modules. This section is going to show some modules of Node.js.

Code:

var path = require('path');
var util = require('util');
var v8 = require('v8')


util.log( path.basename(__filename) );

var dirUploads = path.join(__dirname, 'www', 'fileds', 'uploads');

util.log(dirUploads);

util.log(v8.getHeapStatistics());

In the shell:

node core
28 Jan 23:34:37 - core.js
28 Jan 23:34:37 - /Users/Martin/Documents/martin/    Study/Node/www/fileds/uploads
28 Jan 23:34:37 - { total_heap_size: 7523616,
  total_heap_size_executable: 5242880,
  total_physical_size: 7523616,
  total_available_size: 1491271696,
  used_heap_size: 4094992,
  heap_size_limit: 1535115264 }

–5– Collecting information with Readline

Realine is a module of Node.js, it should get the input stream and output stream. Then you can use the API to operate the input and output such as setPrompt, prompt, on and etc. A string in the string can be replaced as s% like in the C, and the JSON string will be replaced as j%.

Code:

var readline = require('readline');

var rl = readline.createInterface(process.stdin, process.stdout);

var realPerson = {
    name: '',
    sayings: []
};

rl.question("What is the name of a real person?", function(answer){

    realPerson.name = answer;

    rl.setPrompt(`What would ${realPerson.name} say? `);

    rl.prompt();

    rl.on('line', function(sayings){

        realPerson.sayings.push(sayings.trim());

        if (sayings.toLowerCase().trim() == 'exit'){
            rl.close();
        }
        else{
        rl.setPrompt(`What else would ${realPerson.name} say? ('exit' to leave)`);
        rl.prompt();
        }
    });

});

rl.on('close', function(){
     console.log("%s is a real person that says j%",     realPerson.name, realPerson.sayings);
})

In the shell:

What is the name of a real person?Martin
What would Martin say? haha
What else would Martin say? ('exit' to leave)heihei
What else would Martin say? ('exit' to leave)exit
Martin is a real person that says j% [ 'haha', 'heihei', 'exit' ]

–6– Handling events with EventEmitter

There are two modules I have learned from this class. One is event and the other is util. Event has two functions which called on and emit. The fucntion on is for naming the event, and the function emit is for triggling the event. The module util is for inheriting from other class.

Code:

var events = require('events');

var emitter = new events.EventEmitter();

emitter.on('customEvent', function(message, status){

    console.log(`${status}: ${message}`);

});

emitter.emit('customEvent', "Hellow World", 200);

And

node BenFranklin.js 
Ben Franklin: You may delay, but time will not.

–7–Exporting custom modules

In this class, I learned that in one js file, we can conclude a export sentence to export a file to become a module. For example, “module.exports = Person;”

Code:

var EventEmitter = require('events').EventEmitter;
var util = require('util');

var Person = function(name) {
    this.name = name;
};

util.inherits(Person, EventEmitter);

module.exports = Person;

–8–Creating child process with exec

In this class, I learned the module called child_process. And it has a function called exec which is aiming at execute the command in the command line.

Code:

var exec = require("child_process").exec;

exec("ls", function(err, stdout){

    if (err){
        throw err;
    }

    console.log("Listing Finished");

    console.log(stdout);

});

–9–Creating child process with spawn

Spawn can deal with the situation that you want run serval commands or deal with the stdout and stdin.

Code:

var spawn = require("child_process").spawn;

var cp = spawn("node", ["alwaysTalking"]);

cp.stdout.on("data", function(data){
    console.log(`STDOUT: ${data.toString()}`);
});

cp.on("close", function() {

    console.log("Child Process has ended");

    process.exit();

});

setTimeout(function () {

    cp.stdin.write("stop");

}, 4000);

–10–Listing directory files

What’s the differences between synchronously and asynchronously:

When you execute something synchronously, you wait for it to finish before moving on to another task. When you execute something asynchronously, you can move on to another task before it finishes.

That being, said, in the context of computers this translates into executing a process or task on another “thread.” A thread is a series of commands–a block of code–that exists as a unit of work. The operating system can manage multiple threads and assign a thread a piece (“slice”) of processor time before switching to another thread to give it a turn to do some work. At its core (pardon the pun), a processor can simply execute a command–it has no concept of doing two things at one time. The operating system simulates this by allocating slices of time to different threads.

Now, if you introduce multiple cores/processors into the mix, then things CAN actually happen at the same time. The operating system can allocate time to one thread on the first processor, then allocate the same block of time to another thread on a different processor.

All of this is about allowing the operating system to manage the completion of your task while you can go on in your code and do other things.

Reference: http://stackoverflow.com/questions/748175/asynchronous-vs-synchronous-execution-what-does-it-really-mean

In this section, I learned read files synchronously or asynchronously.

Code:

var fs = require("fs");

fs.readdir('./lib', function(err, files){
    if(err){
        throw err;
    }
    console.log(files);
});

console.log("Reading Files...");

–11–Reading files

Code:

var fs = require("fs");

fs.readFile("./lib/saying.md", "UTF-8", function(err, contents){

    if (err) {
        throw err;
    }

    console.log(contents);
});