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 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;

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 Fibonacci{
    public int get(int n){
        int[] res = new int[n];
        res[0] = 1;
        res[1] = 1;
        
        for(int i = 2; i < n; i++){
            res[i] = res[i-1] + res[i-2];
        }
        return res[n-1];

jingz8804

// Suppose we have a Node class that representing the node in the BT
// public class Node{
//     int val;
//     Node left;
//     Node right;
// }
public class HeightOfBT{
    private int height;
    public int getHeight(Node root){
        height = 0;

jingz8804

public class DoublyLinkedList<T>{
    private class Node{
        T val;
        Node next;
        Node previous;
        
        public Node(T val){
            this.val = val;
        }
    }

jingz8804

// First of all, we need to know if the nodes p and q both exist in the tree
// if not, then return null.

// if yes, we need to figure out which side they are in.
// if they are in the same side, then we go to that side to find the ancestor (in this way, we eliminate half the tree)
// otherwise, we have found the first common ancestor.
public class FirstCommonAncestor{
    public Node findAncestor(Node root, Node p, Node q){
        // first of all, we need to know if p and q actually exist in the tree
        // if either is not in the tree, then we should return null

jingz8804

// it is always doable to just XX-order traverse the whole tree and save them somewhere 
// if we have the root and then find the next node of our target node.
//
// however, in this question we are only given the target node and we know that we have
// node back to its parent. I guess we have to work from there.
// 
// if the target node has a right child, then its in-order successor is just the first node
// without a left child in the target node's right sub tree.
//
// the tricky part is when the target node has no right child.

jingz8804

// a binary tree is a binary search tree if and only if 
// 1. all left children are less or equal to the current root and, 
// 2. all right children are larger than the current root.

// at first we may think that we can just recursion. Yeah we could.
// say for a subtree if his left child is less than the root
// and the right child is greater than root, then it's a BST.
// Well not quite. Consider the following example
//           11
//     6           16