Tuesday, June 9, 2015

Google : QuadNode

public class QuadNode{
  private QuadNode[] children;
  private Color color;
  final Rectangle rectangle;
  
  public QuadNode(boolean boolColor, int x, int y, int w, int h){
    this.color = colorFor(boolColor);
    rectangle = new Rectangle(x, y, w, h);
  }

  public void setColor(int x, int y, boolean boolColor){
    if (!rectangle.contains(x,y)) throw new IllegalArgumentException(“index out of range”);;

    if (isLeaf()){
      if (colorMatch(boolColor)){
        return;
      } else if (rectangle.area() == 1){
        setColor(boolColor);
        return;
      } else {
        //adding 4 new children
        split();
      }
    }

    QuadNode child = childFor(x,y);
    child.setColor(x, y, boolColor);

    //all kids have same color
    if (isCompressable()){
      removeChildren();
      setColor(boolColor);
    }
  }

  public int numberOfPixelsGivenColor(boolean boolColor){
    if (isLeaf()){
       if (colorMatch(boolColor)){
         return rectangle.area();
       } else {
         return 0;
       }
    }

    int ret = 0;
    for(QuadNode child : children){
      ret += child.numberOfPixelsGivenColor(boolColor);
    }
    return ret;
  }
  ...
}
class Rectangle{
  int x, y, w, h;
  ....
}

Google : Same Inorder of BST

package binaryTree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


public class Tree<T> {
 Node<T> root;
 
 public Tree(){
  
 }
 public Node<T> getRoot(){
  return root;
 }
 public void setRoot(T data){
  root = new Node<T>();
  root.setData(data);
 }
 
 public void addLeftChild(T par, T chld){
  Node<T> parNode = getNode(par);
  if(parNode != null){
   Node<T> leftNode = parNode.getLeft();
   if(leftNode == null){
    leftNode = new Node<T>();
    parNode.setLeft(leftNode);
   }
   leftNode.setData(chld);
  }
 }
 
 public void addRightChild(T par, T chld){
  Node<T> parNode = getNode(par);
  if(parNode != null){
   Node<T> rightNode = parNode.getRight();
   if(rightNode == null){
    rightNode = new Node<T>();
    parNode.setRight(rightNode);
   }
   rightNode.setData(chld);
  }
 }
 
 public Node<T> getNode(T data){
  return getNode(getRoot(), data);
 }
 public Node<T> getNode(Node<T> node, T data){
  if(node != null){
   if(node.getData().equals(data)){
    return node;
   }
   Node<T> leftNodeResult = getNode(node.getLeft(),data);
   if(leftNodeResult != null){
    return leftNodeResult;
   }
   Node<T> rightNodeResult = getNode(node.getRight(),data);
   if(rightNodeResult != null){
    return rightNodeResult;
   }
  }
  return null;
 }
 
 public void inOrder(Node<T> node,List<T> list){
  if(node != null){
   if(node.getLeft() != null){
    inOrder(node.getLeft(),list);
   }
   list.add(node.getData());
   if(node.getRight() != null){
    inOrder(node.getRight(),list);
   }
  }
 }
 
 public List<T> inOrder(){
  List<T> list = new ArrayList<T>();
  inOrder(root,list);
  return list;
 }
 
 public boolean isSameInorder(Tree<T> other){
  Iterator<T> thisListIter = inOrder().iterator();
  Iterator<T> otherListIter = other.inOrder().iterator();
  while(thisListIter.hasNext() && otherListIter.hasNext()){
   if (thisListIter.next() != otherListIter.next()){
    return false;
   }
  }
  if(thisListIter.hasNext() || otherListIter.hasNext()){
   return false;
  }
  return true;
 }
}