Ruby on Rails

Tools:
 Rake - Create/migrate database, clear web session data.
 WEBrick - Web server for hosting Rails web applications.
 SQLite - A simple database system.
 Rack Middleware - Standardized interface for interaction between web server and web application.

rails new hello_www
cd hello_www
rails server (start a web server)

Under hello_www (Rails root):
app: models, views, and controllers code
bin: helper scripts (bundle, rails, rake)
config: App, database and route configuration
db: database schema and migrations
Gemfile: specify the required gems
lib:
log: application logging directory
pulic: webroot of the application
test: Tests - Agile development

Popular web application frameworks

- Ruby on Rails (Ruby)
- Play (Java and Scala)
- ASP.NET MVC (Microsoft)
- Django (Python)
- Sinatra (Ruby) (very light-weight)
- Symfony (PHP)
- Sails.js (Node.js, JavaScript)

Content management systems (CMSs):
WordPress, Drupal, Joomla!

The MVC Design pattern
Model-View-Controller model
 - Decouples data (model) and presentation (view)
 - A controller handles requests, and coordinates between the model and the view
 - More robust applications, easier to maintain

MVC control flow:
 1. User interface (view) awaits user input
 2. User provides input, e.g., clicks a button
 3. Controller handles the input event -> some action (handler or callback) understandable by the model
 4. Controller notifies the model, possibly changing the model's state
 5. Controller notifies the view (if it needs to be updated). Back to step 1.

PriorityQueue

Operations:
add O(logn), find largest O(1), remove largest O(log(n))

Application:
scheduling long streams of actions to occur at various future times.
useful for sorting.

Common implementation is Heap.

Heap:
max-heap is a binary tree that:
Both labels in both children of each node are less than node's label

So node at the top has largest label.

Longest Increasing Subsequence

Leetcode 300
Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

O(n^2):
Naive solution is use array T[] to track the LIS for each element in the original array. We have to track all the elements because the LIS can only increase for previous element which are smaller than current element.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        // naive solution, keep another array to store the LIS so far. O(n^2)
        if (nums==null || nums.length == 0) return 0;
        int[] lens = new int[nums.length];
        int maxsofar = 1;
        for (int i = 0; i < nums.length; i++) {
            lens[i] = 1;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if ((lens[j]+1) > lens[i]) {
                        lens[i] = lens[j] + 1;
                    }
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (lens[i] > maxsofar) maxsofar = lens[i];
        }
        return maxsofar;
    }
}

Best Time to Buy and Sell Stock

1. Best Time to Buy and Sell Stock

Leetcode 121 (M)
只能买卖一次。
只能一次的话，就是要寻找最小和最大的值（同时必须满足最大值在最小值后面）
可以用两个值来存,maxcurr记录对于第i天可以拿到的最大利润，maxsofar记录到目前为止见过的最大利润（最大的maxcurr)。
所以唯一的问题是如何计算maxcurr，如果maxcurr小于0，那么就是0，对于第i天的maxcurr来说，如果maxcurr + (p[i] - p[i-1]) > 0, 那么更新maxcurr。

或者可以，一直寻找最小的minprice，然后用prices[i]-minprice，同时即时更新minprice。

code1:

public class Solution {
    public int maxProfit(int[] prices) {
        int maxcurr = 0;
        int maxsofar = 0;
        for (int i = 1; i < prices.length; i++) {
            maxcurr = Math.max(0, maxcurr + (prices[i] - prices[i-1]));
            maxsofar = Math.max(maxsofar, maxcurr);
        }
        return maxsofar;
    }
}

code2:

public int maxProfit(int[] prices) {
    int profit = 0;
    int minElement = Integer.MAX_VALUE;
    for(int i=0; i < prices.length; i++){
       profit = Math.max(profit, prices[i]-minElement);
       minElement = Math.min(minElement, prices[i]);
    }
    return profit;
}

1. Best Time to Buy and Sell Stock II

Leetcode 122 (M)

可以买卖多次。这样的话很容易理解，就是把所以递增的都增量都加起来就可以了。因为如果是递增，那么price[j] - price[k] = price[j]-price[i] + price[i]-price[k]

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        
        int total = 0;
        
        for (int i = 1; i < prices.length; i++) {
            total += Math.max(0, prices[i] - prices[i-1]);
        }
        return total;
    }
}

1. Best Time to Buy and Sell Stock III
2. Best Time to Buy and Sell Stock IV
3. Best Time to Buy and Sell Stock with Cooldown

Dynamic Programming

Dynamic programming is a technique for solving problems with the following properties:

1. An instance is solved using the solutions for smaller instances.
2. The solution for a smaller instance might be needed multiple times.
3. The solutions to smaller instances are stored in a table, so that each smaller instance is solved only once.
4. Additional space is used to save time.

经典题目：

1. 买卖股票I II III IV

Java技能

Java：
1. OO, 常用Java API (collection, multithreads, I/O (NIO), Socket, JDBC, XML, reflection)。
2. JSP and Servlet (Java web). JSTL/EL。监听器，过滤器（Web组件)。MVC架构模式进行java web项目开发。
3. Spring IoC container。 AOP原理。Spring框架管理各种web组件。
4. Hibernate, MyBatis等ORM框架。熟悉他们的核心API。对hibernate的关联映射，继承映射，组件映射，缓存机制，事务管理，性能调优。
5. HTML/CSS/JavaScript web前端。JQuery和Bootstrap。Ajax在web项目中的应用。前端MVC框架(AngularJS)和JavaScript模板引擎(HandleBars)。
6. 常用的relatinal db (MySQL, Oracle)。熟练使用SQL和PL/SQL。

7. Design Pattern。GoF设计模式。UML。 TDD/DDD
8. Apache, NginX, Tomcat, WildFly, Weblogic等web服务器和应用服务器的使用。
9. 产品原型工具Axure。设计建模工具PowerDesigner和Enterprise Architect。Java开发环境Eclipse和IntelliJ。前端开发环境webstorm。版本控制svn和git。项目构建和管理工具Maven和Gradle。

项目：
本系统是X委托Y开发的用于Z的系统，系统包括A, B, C, D等模块。系统使用了java企业级开发的开源框架E以及前端技术F。表示层运用了G架构，使用H作为视图I作为控制器并实现了REST风格的请求；业务逻辑层运用了J模式，并通过K实现事务、日志和安全性等功能，通过L实现缓存服务；持久层使用了M封装CRUD操作，底层使用N实现数据存取。整个项目采用了P开发模型。

E: Spring
F: JQuery库及其插件，或者是Bootstrap框架。 SPA(单页应用）最佳方案是前端MVC框架（AngularJS）和JavaScript模板引擎(HandleBars)。
G: MVC (模型-视图-控制）。Spring MVC, Struts 2, JSF
J：事务脚本
K: AOP技术
L：memcached和Redis
M: 选择很多，Hibernate和MyBatis （一般来说增删改交给hibernate，复杂查询给MyBatis）
N: Relational DB (MySQL, Oracle, SQLServer etc.), 或者NoSQL(MongoDB, MemBase, BigTable)，和其他大数据存取方案（GFS, HDFS)。
P: 瀑布模型，快速原型模型，增量模型，螺旋模型，喷泉模型，RAD模型。

版本控制： CVS/SVN/Git
自动构建：Ant/Maven/Ivy/Gradle
持续集成： Hudson/Jenkins

系统架构：
负载均衡服务器：F5, A10
应用服务器：
    Http: Apache, NginX
    Servlet: Tomcat, Resin
    EJB容器: WildFly(JBoss Application Server), GlassFish，Weblogic, WebSphere
数据库服务器: MySQL / Oracle

第三方工具（插件）应用
图表工具: 基于jQuery的图标插件(jQchart, Flot, Charted）
报表工具： Pentaho Reporting, iReport, DynamicReports等
文档处理： POI, iText
工作流引擎：