Woodstock Blog

a tech blog for general algorithmic interview questions

[Design] Strategy Design Pattern

Overview

Strategy pattern (also known as the policy pattern) is a design pattern that enables an algorithm’s behavior to be selected at runtime.

For instance, a class that performs validation on incoming data may use a strategy pattern to select a validation algorithm based on the type of data, the source of the data, user choice… These factors are not known until run-time

A car example

Since accelerate and brake behaviors change frequently between models, a common approach is to implement these behaviors in subclasses. This approach has significant drawbacks: accelerate and brake behaviors must be declared in each new Car model.

The strategy pattern uses composition instead of inheritance. This allows:

  1. better decoupling between the behavior and the class that uses it. (i.e. behavior can be changed without breaking the classes that use it)

  2. classes can switch between behaviors by changing the specific implementation used without requiring any significant code changes.

Code:

/* Encapsulated family of Algorithms 
 * Interface and its implementations
 */
public interface IBrakeBehavior {
    public void brake(); 
}

public class BrakeWithABS implements IBrakeBehavior {
    public void brake() {
        System.out.println("Brake with ABS applied");
    }
}

public class Brake implements IBrakeBehavior {
    public void brake() {
        System.out.println("Simple Brake applied");
    }
}


/* Client which can use the algorithms above interchangeably */
public abstract class Car {
    protected IBrakeBehavior brakeBehavior;

    public void applyBrake() {
        brakeBehavior.brake();
    }

    public void setBrakeBehavior(IBrakeBehavior brakeType) {
        this.brakeBehavior = brakeType;
    }
}

/* Client 1 uses one algorithm (Brake) in the constructor */
public class Sedan extends Car {
    public Sedan() {
        this.brakeBehavior = new Brake();
    }
}

/* Client 2 uses another algorithm (BrakeWithABS) in the constructor */
public class SUV extends Car {
    public SUV() {
        this.brakeBehavior = new BrakeWithABS();
    }
}


/* Using the Car Example */
public class CarExample {
    public static void main(String[] args) {
        Car sedanCar = new Sedan();
        sedanCar.applyBrake();  // This will invoke class "Brake"

        Car suvCar = new SUV(); 
        suvCar.applyBrake();    // This will invoke class "BrakeWithABS"

        // set brake behavior dynamically
        suvCar.setBrakeBehavior( new Brake() ); 
        suvCar.applyBrake();    // This will invoke class "Brake" 
    }
}

This gives greater flexibility in design and is in harmony with the Open/closed principle (OCP) that states that classes should be open for extension but closed for modification.

[Question] Partition Problem (Divide Array Into Halves)

Question

link

partition problem is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2.

Examples

arr[] = {1, 5, 11, 5}
Output: true 
The array can be partitioned as {1, 5, 5} and {11}

arr[] = {1, 5, 3}
Output: false 
The array cannot be partitioned into equal sum sets.

Solution

DP (only if sum of the elements is not too big).

We can create a 2D array of size (sum/2)*(n+1). And we can construct the solution in bottom up manner such that every filled entry has following property:

part[i][j] = 
    true if a subset of {arr[0], arr[1], ..arr[j-1]} has sum equal to i
    false otherwise

Note that we always cares about whether there exist a valid subset from beginning to index i.

Example DP array for input “3,1,1,2,2,1”:

Code

[LeetCode 188] Best Time to Buy and Sell Stock IV

Question

link

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Show Tags
Dynamic Programming

Solution

This question is very difficult. We need to do DP with 2 DP arrays, available to read here.

The 2 arrays' definition as follow:

global[i][j]=max(local[i][j],global[i-1][j])

当前到达第i天可以最多进行j次交易,最好的利润是多少(global[i][j])

当前到达第i天,最多可进行j次交易,并且最后一次交易在当天卖出的最好的利润是多少(local[i][j])

And the formula for calculating local[] is:

local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff),

第一个是全局到i-1天进行j-1次交易,然后加上今天的交易,如果今天是赚钱的话(也就是前面只要j-1次交易,最后一次交易取当前天),

第二个量则是取local第i-1天j次交易,然后加上今天的差值。

And the final code (by blogger Code_Ganker from the same link) would look like this:

public int maxProfit(int[] prices) {
    if(prices==null || prices.length==0)
        return 0;
    int[] local = new int[3];
    int[] global = new int[3];
    for(int i=0;i<prices.length-1;i++)
    {
        int diff = prices[i+1]-prices[i];
        for(int j=2;j>=1;j--)
        {
            local[j] = Math.max(global[j-1]+(diff>0?diff:0), local[j]+diff);
            global[j] = Math.max(local[j],global[j]);
        }
    }
    return global[2];
}

[Java OOP] Java ArrayList Implementation

Overview

Resizable-array implementation of the List interface. (it’s actually an array of Object)

It’s not synced.

Underlying design

  1. Random access – no need to traverse thru all nodes.

  2. Circular array - Array size is pre-defined. Use head and tail to keep track of list position.

  3. Insertion and deletion - Implement shiftRight() and shiftLeft() methods.

Actual code will come later…

[Java OOP] Static Class and Inner Class

Nested classes

Both Static class and Inner class are called nested class.

The purpose of a nested class is to clearly group the nested class with its surrounding class, signaling that these two classes are to be used together.

Now the 2 types:

  1. Static nested classes (also: Static Classes )
  2. Non-static nested classes (also: Inner Class)

Static Classes

Declare:

public class Outer {
    public static class Nested {

    }
}

Instantiate (just like a normal class):

Outer.Nested instance = new Outer.Nested();

Inner Classes

public class Outer {
    public class Inner {

    }
}

Instantiate (you MUST have an instance of enclosing class, and look weird the ‘new’ keyword looks):

Outer outer = new Outer();
Outer.Inner inner = outer.new Inner();

access level

Inner class can access private members in enclosing class (static or non-static).

public class Outer {

    private String text = "I am private!";

    public class Inner {

        public void printText() {
            System.out.println(text);
        }
    }
}

Static class cannot access non-static members.

top-level static class?

Java has no way of making a top-level class static but you can simulate a static class like this:

  1. Declare your class final

  2. Make the constructor private

  3. Make all the members and functions of the class static

(this basically is a Singleton)

[Java OOP] What Is Java Exception

The class

The class Exception and its subclasses are a form of Throwable that indicates conditions that a reasonable application might want to catch.

The object

An exception is an event, which occurs during the execution of a program, that disrupts the normal flow of the program’s instructions.

When an error occurs within a method, the method creates an object and hands it off to the runtime system. The object, called an exception object, contains information about the error(eg. type, state etc).

throw this object out!

Creating an exception object and handing it to the runtime system is called throwing an exception.

After a method throws an exception, the runtime system (i.e. JVM) attempts to find something to handle it. This is exception handler.

[Java OOP] Java Vector and ArrayList

Vector in Java

Vector class implements a growable array of objects.

It’s an array, not a list.

Vector VS ArrayList

  1. Vectors are synchronized, ArrayLists are not.
  2. Data Growth Methods (ArrayList grow by ½ of its size, while Vector doubles)

Usage: ALWAYS use ArrayLists

The vector was not the part of collection framework, it has been included in collections later. It can be considered as Legacy code.

There is nothing about Vector which List collection cannot do. Therefore Vector should be avoided.

[Java OOP] Template Method Pattern (Abstract Class)

Overview

Template method pattern is a behavioral design pattern that defines the program skeleton of an algorithm in a method, called template method, which defers some steps to subclasses.

It lets one redefine certain steps of an algorithm without changing the algorithm’s structure.

Usage

The template method is used in frameworks, where each implements the invariant parts of a domain’s architecture.

Example in Java

Refer to code from WIKI:

/**
 * An abstract class that is common to several games in
 * which players play against the others, but only one is
 * playing at a given time.
 */

abstract class Game {
 /* Hook methods. Concrete implementation may differ in each subclass*/
    protected int playersCount;
    abstract void initializeGame();
    abstract void makePlay(int player);
    abstract boolean endOfGame();
    abstract void printWinner();

    /* A template method : */
    public final void playOneGame(int playersCount) {
        this.playersCount = playersCount;
        initializeGame();
        int j = 0;
        while (!endOfGame()) {
            makePlay(j);
            j = (j + 1) % playersCount;
        }
        printWinner();
    }
}

//Now we can extend this class in order 
//to implement actual games:

class Monopoly extends Game {

    /* Implementation of necessary concrete methods */
    void initializeGame() {
        // Initialize players
        // Initialize money
    }
    void makePlay(int player) {
        // Process one turn of player
    }
    boolean endOfGame() {
        // Return true if game is over 
        // according to Monopoly rules
    }
    void printWinner() {
        // Display who won
    }
    /* Specific declarations for the Monopoly game. */

    // ...
}

class Chess extends Game {

    /* Implementation of necessary concrete methods */
    void initializeGame() {
        // Initialize players
        // Put the pieces on the board
    }
    void makePlay(int player) {
        // Process a turn for the player
    }
    boolean endOfGame() {
        // Return true if in Checkmate or 
        // Stalemate has been reached
    }
    void printWinner() {
        // Display the winning player
    }
    /* Specific declarations for the chess game. */

    // ...
}

[Fundamental] Reflexive, Symmetric and Transitive Rules

Overview

O(n) time complexity is both reflexive, symmetric and transitive.

Reflexive Property

The Reflexive Property states that for every real number x, x = x.

Symmetric Property

The Symmetric Property states that for all real numbers x and y,

if x = y, then y = x.

Transitive Property

The Transitive Property states that for all real numbers x, y, and z,

if x = y and y = z, then x = z.