Word Count

public class WordCount {

public static void main(String[] args) {

// TODO Auto-generated method stub

String filename = "/Users/jane/Desktop/file.txt";

Integer line_num=0;

Integer word_num=0;

Integer char_num=0;

try{

            FileReader newFile = new FileReader(filename);

            BufferedReader br = new BufferedReader(newFile);

            String line = br.readLine();

            while (line != null) {

                line_num++;

                char c;

                int i=0;

                boolean newword = false;

                while(i< line.length()){

                c = line.charAt(i);

                if(c==' ' || c=='\t'){

                newword = false;

                }else if(c=='\n'){

                newword = false;

                }else{

                if(newword ==false){

                newword=true;

                word_num++;

                }

                        char_num++;

                }

                ++i;

                }

                line = br.readLine();

            }

}catch(Exception e){

e.printStackTrace();

}

        System.out.println("File:" + filename + ": line number = "+ line_num + " word number = "+ word_num 

        +" char number = "+ char_num );  

}

}

Furniture test -- OOD

public class FurnitureTest {

    public static void main(String [] args) {

        Furniture [] furnitures = new Furniture[4];

        furnitures[0] = new Table(Furniture.Material.WOOD);

        furnitures[1] = new Table(Furniture.Material.STEEL);

        furnitures[2] = new Chair(Furniture.Material.WOOD);

        furnitures[3] = new Chair(Furniture.Material.STEEL);

        System.out.println("Test begin: ");

        for(Furniture f : furnitures) {

            System.out.println(f.getMaterialName() + " " + f.getName());

            if(f.addWeight(60)) {

                System.out.println("Weight test success");

            } else {

                System.out.println("Weigth test fail");

            }

            if(f.putFire()) {

                System.out.println("Fire test success");

            } else {

                System.out.println("Fire test fail");

            }

        }

    }

}

abstract class Furniture {

    enum Material {

        WOOD, STEEL

    }

    Material m_material;

    

    public abstract boolean addWeight(int w);

    public boolean putFire() {

        if(m_material.equals(Material.WOOD)){

        return false;

        }

        else if(m_material.equals(Material.STEEL)){

        return true;

        }

        return false;

    }

    public abstract String getName();

    public String getMaterialName() {

        return m_material.toString();

    }

}

class Table extends Furniture {

    public Table(Furniture.Material m) {

        super.m_material = m;

    }

    public boolean addWeight(int w) {

        return w < 100;

    }

    public String getName() {

        return "Table";

    }

}

class Chair extends Furniture {

    public Chair(Furniture.Material m) {

        super.m_material = m;

    }

    public boolean addWeight(int w) {

        return w < 50;

    }

    public String getName() {

        return "Chair";

    }

}

Parking Lot -- OOD

enum VehicleSize{
    MotoCycle, Compact, Large
}

abstract class Vehicle{
    protected ArrayList<ParkingSpot> parkingspots = new ArrayList<ParkingSpot>();
    protected String license;
    protected int spotsNeeded;
    protected VehicleSize size;    //enum type VehicleSize
   
    public int getSpotsNeeded(){
        return spotsNeeded;
    }
    public VehicleSize getSize(){
        return size;
    }
   
    public void parkInSpot(ParkingSpot s){
        parkingspots.add(s);
    }
   
    public void removeFromSpot(){
       
    }
   
    public abstract boolean canFitInSpot(ParkingSpot spot);
}


class Bus extends Vehicle{
    public Bus(){
        spotsNeeded = 5;
        size = VehicleSize.Large;
    }
   
    @Override
    public boolean canFitInSpot(ParkingSpot spot){
       
        return true;
    }  
}


class Car extends Vehicle{
    public Car(){
        spotsNeeded = 1;
        size = VehicleSize.Compact;
    }
   
    @Override
    public boolean canFitInSpot(ParkingSpot spot){
       
        return true;
    }  
}


class MotoCycle extends Vehicle{
    public MotoCycle(){
        spotsNeeded = 1;
        size = VehicleSize.MotoCycle;
    }
   
    @Override
    public boolean canFitInSpot(ParkingSpot spot){
       
        return true;
    }  
}




public class ParkingLot{
    private Level[] levels;
    private final int NUM_LEVELS = 5;
   
    public ParkingLot(){
       
    }
   
    public boolean parkVehicle(Vehicle vehicle){
       
        return true;
    }
   
   
}


class Level{
   private int floor;
   private ParkingSpot[] spot;
   private int availableSpots = 0;
   private static final int SPOTS_PER_ROW = 10;
   private static final int NUM_OF_ROW = 5;
 
   public Level(int floor, int numberSports){
 
   }
 
   public int getavailableSpots(){
       return availableSpots;
   }
 
   public boolean parkVehicles(Vehicle vehicle){
     
       return true;
   }
 
   private boolean parkStaringAtSpot(int num, Vehicle v){
     
       return true;
   }
   
   private int findAvailableSpot(Vehicle v){
     
       return 0;
   }
 
   public void spotFreed(){
       availableSpots++;
   }
}


class ParkingSpot{
    private Vehicle vehicle;
    private VehicleSize spotSize;
    private int row;
    private int spotNumber;
    private Level level;
   
    public ParkingSpot(Level level, int r, int n, VehicleSize s){
       
   
    }
   
    public boolean isAvailable(){
        return vehicle == null;
    }
   
    public boolean canFitVehicle(Vehicle v){
       
        return true;
    }
   
    public boolean park(Vehicle v){
       
        return true;
    }
   
    public int getRow(){
        return row;
    }
   
    public int getSpotNumber(){
        return spotNumber;
    }
   
    public void removeVehicle(){
       
    }
}

Ceiling Node of BST + Floor Node of BST

1. find ceil node of BST. 

O(longn)

/*

 *        8

 *   4        10

 * 3    7   9    11

 *    6

 */

public class CeilingNodeOfBST {

static class Node{

int val;

Node left;

Node right;

public Node(int v){

this.val = v;

left = null;

right = null;

}

}

public static int CeilUtil(Node root, int target, int min, int max){

if(target >= root.val){

if(root.right!=null){

return CeilUtil(root.right, target, root.val, max);

}else{

return max;

}

}else{

//target < root.val now.

if(root.left!=null){

return CeilUtil(root.left, target, min, root.val);

}else{

return root.val;

}

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

        Node root = new Node(8);

        root.left = new Node(4);

        root.right = new Node(10);

        root.left.left = new Node(3);

        root.left.right = new Node(7);

        root.right.left = new Node(9);

        root.right.right = new Node(11);

        root.left.right.left = new Node(6);

        int res = CeilUtil(root, -1, Integer.MIN_VALUE, Integer.MAX_VALUE);

        if(res==Integer.MAX_VALUE){

        res = -1;

        }

        System.out.println(res);

return; 

}

}

2. Only modify in find ceiling node util function, can find floor node of BST:

O(logn)

public class FloorNodeOfBST {

static class Node{

int val;

Node left;

Node right;

public Node(int v){

this.val = v;

left = null;

right = null;

}

}

public static int FloorUtil(Node root, int target, int min, int max){

if(target <= root.val){

if(root.left!=null){

return FloorUtil(root.left, target, min, root.val);

}else{

return min;

}

}else{

//target > root.val now.

if(root.right!=null){

return FloorUtil(root.right, target, root.val, max);

}else{

return root.val;

}

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

        Node root = new Node(8);

        root.left = new Node(4);

        root.right = new Node(10);

        root.left.left = new Node(3);

        root.left.right = new Node(7);

        root.right.left = new Node(9);

        root.right.right = new Node(11);

        root.left.right.left = new Node(6);

        int res = FloorUtil(root, 4, Integer.MIN_VALUE, Integer.MAX_VALUE);

        if(res==Integer.MIN_VALUE){

        res = -1;

        }

        System.out.println(res);

return; 

}

}

Jump Game I + II -- Leetcode

1.Jump Game I:
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.

Answer:
Greedy method:

 public boolean canJump(int[] nums) {
        int max=nums[0];
        for(int i=0;i<=max;++i){
           if(max>=nums.length-1){
               return true;
           }
           if(i+nums[i]>max){
               max=i+nums[i];
           }
        }
        return false;
    }


2.Jump Game II:
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.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

Answer:
Greedy method:

 public int jump(int[] nums) {

        int len=nums.length;

        int max=0;

        int[] count=new int[len];

        

        for(int i=0;i<=max;++i){

            if(max>=len-1){

                return count[len-1];

            }

            int curMax=i+nums[i];

            if(curMax > max){

                for(int k=max+1;k<=curMax&&k<=len-1;++k){

                    count[k] = count[i] + 1;

                }

                max = curMax;

            }

        }

        return -1;

    }

Burst Balloons -- Leetcode -- dp

Question:

https://leetcode.com/problems/burst-balloons/

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

Answer:

Method: DP + divide & conquer!

Suppose num[k] is the last balloon bursted in interval [i,j], so last step we will get coin:  

num[i-1]*num[k]*num[j+1]

//dp formular:

dp(i,j) = Max{dp(i,k-1) + num[i-1]*num[k]*num[j+1] + dp(k+1,j)} , k=[i,j], when i<=j
dp(i,j) = 0, when i>j

public class Solution {

    public int maxCoins(int[] nums) {

        int m=nums.length;

        if(m==0)return 0;

        int[] nums2 = new int[m+2];

        int[][] dp = new int[m+2][m+2];

        

//trick: add head and tail element with 1 for edge usage, final result return dp[1][m]!

        nums2[0]=1;

        nums2[m+1]=1;

        for(int i=1;i<=m;++i){

           nums2[i]=nums[i-1];

        }

        

        for(int j=1;j<=m;++j){

            for(int i=j;i>=1;--i){

                //dp common case func

                for(int k=i;k<=j;++k){

             

                    dp[i][j]=Math.max(dp[i][j], dp[i][k-1]+dp[k+1][j] + nums2[i-1]*nums2[k]*nums2[j+1]);

                }

            }

        }

        return dp[1][m];

    }

}

Stone Game -- Lintcode -- dp

Question:

http://www.lintcode.com/en/problem/stone-game/

There is a stone game.At the beginning of the game the player picksn piles of stones in a line.

The goal is to merge the stones in one pile observing the following rules:

1. At each step of the game,the player can merge two adjacent piles to a new pile.
2. The score is the number of stones in the new pile.

You are to determine the minimum of the total score.

Have you met this question in a real interview? 

Yes

Example

For [4, 1, 1, 4], in the best solution, the total score is 18:

1. Merge second and third piles => [4, 2, 4], score +2
2. Merge the first two piles => [6, 4]，score +6
3. Merge the last two piles => [10], score +10

Other two examples:
[1, 1, 1, 1] return 8
[4, 4, 5, 9] return 43

Solution:

dp mothod:

dp(i,j) = min{dp(i,k) + dp(k+1,j) + sum(i,j)},  when i<j

dp(i,j) = 0, when i=j

Space: sum[m][m], dp[m][m], O(2*m*m) = O(m*m); Time:O(m*m)

public class Solution {

    /**

     * @param A an integer array

     * @return an integer

     */

    public int stoneGame(int[] A) {

        // Write your code here

        int m=A.length;

        if(m==0)return 0;

        if(m==1)return 0;

        int[][] sum = new int[m][m];

        int[][] dp = new int[m][m];

        

        for(int i=0;i<m;++i){

            sum[i][i]=A[i];

            for(int j=i+1;j<m;++j){

                sum[i][j]=sum[i][j-1]+A[j];

            }

        }

        

        for(int j=1;j<m;++j){

            //dp edge case

            dp[j][j]=0;

            

            for(int i=j-1;i>=0;--i){

                

                int min = Integer.MAX_VALUE;

                //dp common case func

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

                    int tmp = dp[i][k] + dp[k+1][j];

                    if(tmp < min){

                        min = tmp;

                    }

                }

                dp[i][j] = min + sum[i][j];

            }

        }

        return dp[0][m-1];

    }

}