jingz8804

public class GasStation{
    public int canCompleteCircuit(int[] gas, int[] cost){
        // first check special cases
        if(gas == null || cost == null) return -1;
        if(gas.length != cost.length) return -1;
        
        // get the number of the gas stations
        int N = gas.length;
        
        int leftAmount = 0; // the amount of gas left in the tank when we are at station i

jingz8804

import java.util.Queue;
import java.util.LinkedList;
import java.util.Hashtable;
import java.util.Arrays;
public class Solution {
    	public int ladderLength(String start, String end, Set<String> dict) {
		if (start.equals(end))
			return 1;

		// add the string end to the dict

jingz8804

import java.util.Hashtable;
import java.util.ArrayList;
public class TwoSum {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        if(numbers == null || numbers.length <= 1) return result;
        
        Hashtable<Integer, Integer> freqs = new Hashtable<Integer, Integer>();
        Hashtable<Integer, ArrayList<Integer>> indices = new Hashtable<Integer, ArrayList<Integer>>();
        // first pass, count the frequency and save the index

jingz8804

import java.util.Stack;
public class ValidParenthesis {
    public boolean isValid(String s) {
        if(s == null || s.length() == 0 || s.length() % 2 == 1) return false;
        
        Stack<Character> chars = new Stack<Character>();
        int len = s.length();
        for(int i = 0; i < len; i++){
            char c = s.charAt(i);
            if(!validCharacter(c)) return false;

jingz8804

// the recursive mergesort divides an array with length N to N singlton array
// and then merge them together back to one sorted array. It's a top down approach.
// All the work of sorting is done by the merge action.
// the iterative version is however, a bottom up approach. we skip the divide step
// and iteratively call the merge action from the beginning.
// however, the indexing tuning can be a bit annoying. A goog alternative is to use
// a queue. We dequeue two arrays from the queue, merge them together and put the merged
// array back to the queue. This repeats until there's only one array in the queue, the final
// sorted one.
import java.util.Queue;

jingz8804

// we know how to do it if the path must start at the root.
// we can use this to solve this problem. At first glance,
// at each node we should look for sum path start there.
// actually, we could think about print out all the paths that
// ends there instead.
public class PrintPath{
    public void printPath(Node root, int target){
        if(root == null) return;
        int depth = getDepth(root);
        int[] path = new int[depth]; // the path is at most depth.

jingz8804

// since the subtree has only hundreds of nodes while the larger three has millions
// maybe it is better to use BFS instead of DFS to search for the subtree
// since we could end up searching millions of nodes without finding the subtree 
import java.util.Queue;
import java.util.LinkedList;
public SubtreeCheck{
    public boolean isSubtree(Node r1, Node r2){
        if(r1 == null || r2 == null) return false; // discuss with your interviewer
        
        Queue<Node> nodes = new LinkedList<Node>();

jingz8804

public class NumToEnglish{
    // a number like 1,897,234 can be considered as
    // 1 million 897 thousand 234
    // we can divide them into several 3 digits sequence and insert
    // thousand or million in between
    // private String[] digits = {"One", ..., "Nine"};
    // private String[] tens = {"Ten", ..., "Ninety"};
    // private String[] teens = {"Eleven", ..., "Nineteen"};
    // private String[] bigs = {"", "Thousand", "Million"};
    

jingz8804

public class HasPalidrome{
    // technically speaking, every non-empty string contains palidromes because a string with length 1
    // is a palidrome itself. But I guess we are looking at palidromes with length at least 2.
    public boolean containsPalidrome(String s){
        if (s == null || s.length() == 0) return false;
        if (s.length() == 1) return true;
        
        // every palidrome has a center point
        // and for a string with length n, there are 2n - 1 center points.
        // so we can just check each center for a possible palidrome

jingz8804

public class ExpressionTerm implements Comparable{
    double coefficient;
    double exponent;
    
    // getter and setter
    
    public int compareTo(ExpressionTerm term){
        if (this.exponent < term.exponent) return -1;
        if (this.exponent == term.exponent) return 0;
        if (this.exponent > term.exponent) return 1;