AdSense

Wednesday, February 25, 2015

Hanoi Game

In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower.The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one).You have the following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks.


Consider the easiest problem, if we have 2 disks, how should we move from Tower 0 to Tower 2? See the following illustration:


Now what if we have 3 disks? So in the end we want to move all 3 disks to Tower 2, we would have to move disk0 and disk1 to Tower 1 first, because disk2 will be at the bottom of Tower 2, so we need to leave the space for it. 


Yes, we will use recursion to solve the problem. 


import java.util.Stack;
public class HanoiGame {
 private Stack disks;
 private int index;
 public HanoiGame(int i) {
  disks = new Stack();
  index = i;
 }
 /**
  * tower id
  * @return
  */
 public int index() {
  return index;
 }
 /**
  * add disk with length d to the tower
  * if the last disk on the top of the tower is smaller
  * than d, then d cannot be added to the tower
  * @param d
  * @return
  */
 public boolean add(int d) {
  if (!disks.isEmpty() && disks.peek() <= d) {
   System.out.println("Error placing disk: " + d);
   return false;
  }
  else
   disks.push(d);
  return true;
 }
 /**
  * move the top disk to the desired tower
  * @param hg
  */
 public void moveTopTo(HanoiGame tower) {
  int top = disks.pop();
  if (!tower.add(top))
   disks.push(top);
  //System.out.println("Move disk " + top + " from " + index() 
   // + " to " + tower.index());
 }
 public void print() {
  System.out.println("Contents of Tower: " + index());
  for (int i = disks.size() - 1; i >= 0; i--) {
   System.out.println(disks.get(i) + " ");
  }
 }
 /**
  * move the disks to the destination
  * use recursion to solve the problem
  * @param n
  * @param destination
  * @param intermediate
  */
 public void moveDisks(int n, HanoiGame destination, HanoiGame intermediate) {
  if (n > 0) {
   //since the last disk must be placed at the destination
   //we need to move n - 1 disks above it to the intermediate first
   moveDisks(n - 1, intermediate, destination);
   //move the last disk to the destination
   moveTopTo(destination);
   //from intermediate move the n - 1 disks to the destination, 
   //using current tower as the new intermediate
   intermediate.moveDisks(n - 1, destination, this);
  }
 }
 public static void main(String[] args) {
  int n = 5;
  HanoiGame[] towers = new HanoiGame[3];
  for (int i = 0; i < 3; i++)
   towers[i] = new HanoiGame(i);
  for (int i = n - 1; i >= 0; i--)
   towers[0].add(i);
  towers[0].print();
  towers[0].moveDisks(n, towers[2], towers[1]);
  towers[2].print();
 }

}

Min Stack

The stack can be implemented using LinkedList implementation. So the problem is how to track the minimum efficiently. One way to do it is to design a structure and store the minimum of all elements prior to head into the stack. Thus each node will also contain the information of the local minimum. The problem with this method is that there will be lots of duplicate data. For example, if I have a stack (0, 1, 2, 3, 4), the head is 4, with the minimum 0, every node stores 0, which is unnecessary and infeasible for very large stack.

So the question is, how can we do better?

One approach may be to use another List, or another stack to only track the local minimum. If the pushed node is smaller than the minimum of all existing nodes in the stack, push the node to the second stack. So for (0, 1, 2, 3, 4), we will have another list/stack only contains (0).
class MinStack {
    ListNode head;
    ListNode currMin;
    public MinStack() {
        head = null;
        currMin = null;
    }
    public MinStack(int val) {
        head = new ListNode(val);
        currMin = new ListNode(val);
    }
    
    public void push(int x) {
        if (head == null) {
            head = new ListNode(x);
            currMin = new ListNode(x);
        }
        else {
            ListNode node = new ListNode(x);
            node.next = head;
            head = node;
            //if there are two nodes with the same minimum value in the stack, 
            //if we delete the first one, or the one pushed in later, the minimum
            //of the stack is still the same value, thus we need to push the node
            //to the min stack as long as it equals the minimum
            if (x <= currMin.val) {
                //need to create a new node and push it
                //to the second list, 
                //otherwise the current node's next will points to next min
                //because we override it with the previous min
                ListNode tmp = node;
                tmp.next = currMin;
                currMin = tmp;
            }
        }
    }

    public void pop() {
        if (head == null)
            return;
        if (currMin.val == head.val) {
            currMin = currMin.next;
        }
        head = head.next;
    }

    public int top() {
        if (head == null)
            return -1;
        return head.val;
    }

    public int getMin() {
        if (head == null)
            return -1;
        return currMin.val;
    }
    private class ListNode{
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
            next = null;
        }
    }
}

Tuesday, February 24, 2015

Rotate array

So how to do it in place? The answer is easy but tricky. Reverse the array 3 times. First reverse the whole array, second reverse (0, k - 1) and third reverse(k, n -1).
Take a look of the example.




public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0 || k == nums.length)
            return;
        int l = nums.length;
        k = k % l;
        reverse(nums, 0, l - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, l - 1);
        
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }

Monday, February 23, 2015

Number of pages in a book

A book contains with pages numbered from 1 - N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string.
You can compute number of occurrences 'k' of certain digit 'd' in this string.
For example, let N=12, d=1, hence
s = '123456789101112' => k=5
since digit '1' occur five times in that string.

Problem: Write a method that, given a digit 'd' and number of its occurrences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.
Example:
input: d=4, k=1;
output {4, 13} - the book has 4-14 pages
input d=4 k=0;
output {1, 3} - the book has 1-3 pages
 I don't consider my solution is the most efficient one, but it is reasonable, and at least, correct.

For every 100 pages, or more precisely, 0 - 99 (100 - 199, ...) pages, there exists 20 occurrences of any digit d, except for 0 for (0 - 99 pages), there are only 9,  because there is no 0 from 0 - 9 pages. So the first step is to calculate how many hundreds of pages in the book.

hundreds = k / 20;

Next, we want to know how many d's left in tens. This is done by mod k by 20;

tens = k % 20;

If tens = 6, then there are 6 ds in (0 - 99) pages, or (hundreds * 100, hundreds * 100 + 99) pages.

Now we have the tricky part. Let's take d = 7as an example.

If tens = 0, then it is easy, the range of the pages will include all d's in one hundred pages.

(hundreds - 1) * 100 + 90 + d, range[0] + 10 - 1)

Take 7 as an example, if k = 20, then the range is
(97, 106).
Note we need to decrement hundreds by 1 when tens = 0.

If tens != 0, we will have different cases. Note that we will have d of ds if  tens (the second digit in the page number) is less than d. Then we will have 11 ds from d * 10 to d * 10 + 9. Then we will have another 9 - d ds after that.
If d = 7, we will have 7 7s from 0 - 69, 11 7s from 70 - 79 and another 2 ds from 80 - 99. Thus we need to calculate ranges based on different situations.

If tens < d,


range[0] = hundreds * 100 + (tens - 1) * 10 + d;
range[1] = range[0] + 10 - 1;

d = 7, k = 25 -> hundreds = 1, tens = 5
(147, 156)

If tens = d
we have to exclude d * 10 to d * 10 + d - 1
so 

range[0] = hundreds * 100 + (tens - 1) * 10 + d;
range[1] = hundreds * 100 + (tens - 1) * 10 + 9;

d = 7, k = 27 ->  hundreds = 1, tens = 7
(167, 169)

Now if tens > d, let dInTens, which is the number of ds from ( d * 10,  d * 10 + 9) = tens - d

start from the easier one, if dInTens > 11, then the range must be from (d + 1) * 10 - 99, for d = 7, it is 80 - 99

range[0] = hundreds * 100 + (tens - 11) * 10 + d;
range[1] = range[0] + 10 - 1;

d = 7, k = 39 -> hundreds = 1, tens = 19
range (187, 196)

if dInTens < 11, then we are in the range d * 10 to d * 10 + 8. In this situation, increment any page will increase k, thus the range is an exact number. Moreover, when the single digit equals to d, we will have 2 ds. 


If dInTens <= d, then the range is from d * 10 to d * 10 + d - 1. 
For d = 7, k = 13 -> tens = 13, dInTens = 6, the range is (70, 76), more precisely, 

range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 1;

so (75, 75)

If dInTens > d, then 

range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 2;

Because d* 10 + d takes 2 ds. 
For d = 7, k = 17 -> tens = 17, dInTens = 10, range (77, 77)

Now we have one more situation, where dInTens = 11, we are in the range ( d * 10 + 9, d * 10 + 9 + d). Because the next d will occur when the next single digit = d. 

range[0] = hundreds * 100 + d * 10 + 9;
range[1] = range[0] + d;

for d = 7, k = 18 -> tens = 18, dInTens = 11, range (79, 96)


I know the explanation looks tedious. Honestly I am also looking for a more concrete code. 




public class NumberOfPages {
 public static int[] pages(int d, int k) {
  if (d < 0 || k < 0)
   throw new IllegalArgumentException("pages must be non negative!");
  int[] range = new int[2];
  if (k == 0) {
   if (d == 1)
    range[0] = range[1] = 0;
   else {
    range[0] = 1;
    range[1] = d - 1;
   }
   return range;
  }
  //the number of hundreds of pages
  int hundreds = k / 20;
  if (d == 0) {
   hundreds = k > 9 ? ((k - 9) / 20) + 1 : 0;
  }
  //the number of d's from 0 - 99 pages
  int tens = k % 20;
  if (tens == 0) {
   range[0] = (hundreds - 1) * 100 + 90 + d;
   range[1] = range[0] + 10 - 1;
  }
  else if (tens - d  <= 0) {
   range[0] = hundreds * 100 + (tens - 1) * 10 + d;
   //System.out.println("range[0]: " + range[0]);
   if (tens - d  == 0) 
    range[1] = hundreds * 100 + (tens - 1) * 10 + 9;
   else
    range[1] = range[0] + 10 - 1;
   //System.out.println("range[1]: " + range[1]);
  }
  else {
   int dInTens = tens - d;
   if (dInTens > 11) {
    range[0] = hundreds * 100 + (tens - 11) * 10 + d;
    range[1] = range[0] + 10 - 1;
   }
   else {
    if (dInTens <= d)
     range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 1;
    else if (dInTens == 11) {
     range[0] = hundreds * 100 + d * 10 + 9;
     range[1] = range[0] + d;
    }
    else 
     range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 2;
   }
  }
  return range;
 }

 public static void main(String[] args) {
  for (int k = 0; k <= 20; k++) {
   for (int i : pages(7, k))
    System.out.print(i + " ");
   System.out.println();
  }
  for (int i : pages(7, 18))
   System.out.print(i + " ");
 }

}


Sunday, February 22, 2015

Find minimum number K such that given integer N can be represented by K number of squares


You are given a positive integer number N. Return the minimum number K, such that N can be represented as K integer squares.
Examples:
9 --> 1 (9 = 3^2)
8 --> 2 (8 = 2^2 + 2^2)
15 --> 4 (15 = 3^2 + 2^2 + 1^2 + 1^2)

See the comment on the top of the code... Sorry just don't bother to type them again...

/**
 * You are given a positive integer number N. 
 * Return the minimum number K, such that N can be 
 * represented as K integer squares. 
 * Examples: 
 * 9 --> 1 (9 = 3^2) 
 * 8 --> 2 (8 = 2^2 + 2^2) 
 * 15 --> 4 (15 = 3^2 + 2^2 + 1^2 + 1^2) 
 * First reach a solution without any assumptions, 
 * then you can improve it using this mathematical lemma (Lagrange's four-square theorem): 
 * For any positive integer N, there is at least one representation 
 * of N as 4 or less squares.
 * N = a^2 + b^2 + c^2 + d^2 such that
 * a >= b >= c >= d
 * a : {floor(sqrt(N)), ceil(sqrt(N / 4))}
 * b : {floor(sqrt(N - a * a)), ceil(sqrt((N - a * a)/3)}
 * c : {floor(sqrt(N - a * a - b * b)), ceil(sqrt((N - a * a - b* b)/2))}
 * d : N - a * a - b * b - c * c
 * if we can find a and b, then if sqrt(N - a * a - b * b) is an integer
 * we have our 3rd integer, thus we don't have to loop to find c
 * if we cannot find a, b, c such that a * a + b * b + c * c = N
 * then we need the 4th integer
 * So the complexity is O(sqrt(N) * sqrt(N)), which is O(N)
 * @author shirleyyoung
 *
 */
public class KIntegerSquares {
 public static int kSquares(int N) {
  if (N < 0)
   throw new IllegalArgumentException("Input must be positive!");
  int sqrt = (int)Math.sqrt(N);
  if (sqrt * sqrt == N)
   return 1;
  int aUpper = (int)Math.sqrt(N);
  int aLower = (int)Math.ceil(Math.sqrt(N / 4.0));
  for (int a = aUpper; a >= aLower; a--) {
   int bUpper = (int)Math.sqrt(N - a * a);
   int bLower = (int)Math.ceil(Math.sqrt((N - a * a) / 3.0));
   for (int b = bUpper; b >= bLower; b--) {
    int currSum = a * a + b * b;
    if (currSum == N)
     return 2;
    double c = Math.sqrt(N - currSum);
    if (c == Math.floor(c))
     return 3;
   }
  }
  return 4;
 }

 public static void main(String[] args) {
  System.out.println(kSquares(31));
 }
}


Update 2015 - 03 - 16
A DP solution that is much easier to understand. Note recursion will not work since it follows a greedy approach which may not give the best answer.


public static int kSquares3(int N){
  if(N < 0)
   throw new IllegalArgumentException("Input must be greater than 0!");
  if(N == 0)
   return 0;
  int[] minSquare = new int[N + 1];
  int max = (int)Math.sqrt(N);
  for (int i = 0; i <= N; i++)
   minSquare[i] = i;
  for(int i = 1; i <= N; i++){
   for(int j = 1; j <= max; j++){
    if(i - j * j < 0)
     continue;
    minSquare[i] = Math.min(minSquare[i], minSquare[i - j * j] + 1);
   }
  }
  return minSquare[N];
 }

Auto Complete method


Write a class that receives in the constructor a vector of strings representing a browser history (URLs), and a method for "auto-complete":
The method that receives a string representing a partial URL typed by the user and returns a vector of all possible completions of this partial URL (prefix).

Starts from some concepts:

Trie 
a trie/digital tree/radix tree/prefix tree, is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.  No node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.
A radix tree/radix trie/compact prefix tree is a space-optimized trie data structure where each node with only one child is merged with its parent. The result is that every internal node has up to the number of children of the radix r of the radix trie, where r is a positive integer and a power x of 2, having x >= 1. Unlike in regular tries, edges can be labeled with sequences of elements as well as single elements. This makes them much more efficient for small sets (especially if the strings are long) and for sets of strings that share long prefixes. 

Just to go through how this thing works. When we initialize a new trie object, we create an empty trie node. Every trie has an empty root, i.e., the root doesn't hold any string values. The trie uses a map to store all its children, i.e., the suffixes generated from this node.

When we insert a string, the trie first tries to find if any of its children contains the first character of the string (the prefix), if it can find one, it will recursively try to find the next character until it cannot find one, that's when it will add a new node and put it into the children map.

In order to find if a string is in the trie, similarly, it will recursively try to find if every character in the string is in the children map, if any of the character doesn't in a children map, return false, when it reaches to the end of the string, check if the current node's value equals the string.

The autocomplete method, this method is in fact ask us to return all suffixes given a prefix. Follow the same approach as the previous to methods, the trie first finds the path of the prefix, say, s-h-, then it will add all children of the node "sh" and all children's children into the list, and return the list. For example, if "sh"  has children "she", "shirt", "shirley", it will return all 3. Note that "shir" is a path that has two branches: "shirt" and "shirley". However, since "shir" itself is not a string that has been inserted to the trie, it will not be returned.


import java.util.*;
import java.util.Map.Entry;
public class AutoCompleteTrie {
 protected final Map children;
 protected String value;
 protected boolean isWord = false;
 /**
  * constructor, initialize a new ACT with empty string as the root
  * @param value
  */
 private AutoCompleteTrie(String value) {
  this.value = value;
  children = new HashMap ();
 }
 public AutoCompleteTrie() {
  this("");
 }
 /**
  * insert a word, this will construct a root to leave path
  * with the key of each node a character in the word, 
  * value the prefix of the word till the key character
  * @param word
  */
 public void insert (String word) {
  if (word == null)
   throw new IllegalArgumentException("Null string!");
  //this is a reference to the current object: 
  //the object whose method or constructor is being called
  AutoCompleteTrie node = this;
  for (char c : word.toCharArray()) {
   //System.out.println(c + ": " + node.value);
   if (!node.children.containsKey(c))
    node.add(c);
   node = node.children.get(c);
   
  }
  //System.out.println();
  node.isWord = true;
 }
 /**
  * add a child of the node
  * the child will have the key the input character
  * and the value the value of the node + key character
  * @param c
  */
 private void add(char c) {
  String val; 
  val = this.value + c;
  children.put(c, new AutoCompleteTrie(val));
 }
 
 /**
  * search if a word exists in the trie
  * @param word
  * @return
  */
 public boolean find(String word) {
  AutoCompleteTrie node = this;
  for (char c : word.toCharArray()) {
   if (!node.children.containsKey(c)) 
    return false;
   node = node.children.get(c);
  }
  return node.value.equals(word);
 }
 
 /**
  * input prefix return all possible strings 
  * with the same prefix in the trie
  * find the node of the prefix in the trie
  * call allChildren method and return the list
  * @param prefix
  * @return
  */
 public Collection autoComplete(String prefix) {
  AutoCompleteTrie node = this;
  for (char c : prefix.toCharArray()) {
   if (!node.children.containsKey(c))
    return Collections.emptyList();
   node = node.children.get(c);
  }
  return node.allChildren();
 }
 /**
  * generate the list of all children of the current node/object
  * @return
  */
 private Collection allChildren() {
  List rst = new ArrayList ();
  //if the prefix is also a previous input word, add it to the list
  if (this.isWord) {
   rst.add(this.value);
  }
  //add all children
  for (Entry entry : children.entrySet()) {
   AutoCompleteTrie child = entry.getValue();
   Collection childPrefixes = child.allChildren();
   rst.addAll(childPrefixes);
  }
  return rst;
 }
}

Object-Oriented Programming 101

Object:
An object stores its state in fields/variable and exposes its behavior through methods/functions.
Objects define their interaction with the outside world through the methods they expose.
encapsulation: Hiding internal variables and requiring all interaction to be performed through an object's method.

public class demo {
    private int x;
    private int y;
    
    public demo() {
        x = 0;
        y = 0;
    }
    public void setX(int x) {
        this.x = x;
    }
    public void setY(int y) {
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }
}

Memory of object: 
Any Java object occupies at least 16 bytes, 12 out of which are occupied by a Java object header. Besides, all Java objects are aligned by 8 bytes boundary. It means that, for example, an object containing 2 fields: int and byte will occupy not (12 + 4 + 1) = 17, but 24 bytes (17 aligned by 8 bytes).
Each Object reference occupies 4 bytes if the Java heap is under 32G and is turned on (it is turned on by default in the recent Oracle JVM versions). Otherwise, Object references occupy 8 bytes.

Arrays:
Consume 12 bytes plus their length multiplied by element size (rounded by 8 bytes alignment).

String:
contains 3 fields:

  • a char[] with the string data
  • 2 int fields with 2 hash codes calculated by different algorithms.
Thus, a String itself needs 12(header) + 4(char[] reference)
Class:
A class is the blueprint from which individual objects are created. Object a is an instance of  the class of objects known as A.
A class CLASS may not have a main() method. That's because the class may not be a complete application, it's just the blueprint for CLASS that might be used in an application. The responsibility of creating and using CLASS objects belongs to some other class in the application.


Difference between object and class:

  • An object is an instance of a class, an object must belong to a class. 
  • An object has a lifespan but a class does not. Objects are created and eventually destroyed, so they only live in the program for a limited time. While objects are 'living', their properties may also be changed significantly. 
  • A constructor allows actual properties (fields/variables) to be passed to the object. A constructor constructs a specific instance of a class. 

Inheritance:
Object-oriented programming allows classes to inherit commonly used state (fields/variables) and behaviors (methods/functions) from other classes. Class SUPER may become superclass of Class SUB1, SUB2, ... . In Java, each class is allowed to have only one direct superclass, and each superclass has the potential for an unlimited number of subclasses.


public class SUPER {
    int variable1;
    int variable2;
    public int method1() {
        Some awesome code...
    }
}
public class SUB1 extends SUPER {
    int variable1;
    int variable2;
    int variable_sub1;
    public int method1() {
        Some awesome code...
    }
    public int method_sub1() {
        Other awesome code...
    }
}


Interface:
An interface is a reference type, that can contain only constants. method signatures, default methods, static methods, and nested types. Method bodies exist only for default methods and static methods. Interfaces can only be implemented by classes or extended by other interfaces. Implementing an interface allows a class to become more formal about the behavior it promises to provide. Interfaces form a contract between the class and the outside world (through method), and this contract is enforced at build time by the compiler. If a class claims to implement an interface, all methods defined by that interface must appear in its source code before the class will successfully compile.

Default methods enable you to add new functionality to the interfaces of your libraries and ensure binary compatibility with code written for older versions of those interfaces. The classes that implements the old version of the interface will automatically have the new default method defined.
When you extend interfaces that contain default methods, you can:

  • Not mention the default method at all, which lets your extended interface inherit the default method;
  • Redeclare the default method, which makes it abstract
  • Redefine the default method, which overrides it. 


public interface INTERFACE {
    //automatically public, static, and final
    int variable1;
    int variable2;
    public void iMustAppearInClass1() {
    }
    public void iMustAppearInClass2() {
    }
}
public class CLASS implements INTERFACE {
    public void iMustAppearInClass1() {
        Some awesome code...
    }
    public void iMustAppearInClass2() {
        Other awesome code...
    }
    public void iBelongToThisClass() {
        More awesome code...
    }
}



Abstract classes and methods:
An abstract class is a class that is declared abstract, it may or may not include abstract methods. Abstract classes cannot be instantiated, but they can be subclassed.

An abstract method is a method that is declared without an implementation (without braces, and followed by a semicolon). If a class include abstract methods, then the class itself must be declared abstract.

public abstract class ABSTRACT {
    int variable1;
    int variable2;
    abstract void iAmAbstract();
}

When an abstract class is subclassed, the subclass usually provides implementations for all of the abstract methods in its parent class. If it does not, the subclass must also be declared abstract. 

Abstract classes and interfaces:

  • Both abstract classes and interfaces cannot be instantiated
  • Both abstract classes and interfaces may contain a mix of methods declared with or without an implementation (default method for implementation). 
  • With interfaces, all fields are automatically public, static, and final, and all methods that you declare or define (as default methods) are public. With abstract classes, you can declare fields that are not static and final, and defined public protected and private concrete methods
  • Only one class can be extended, whether or not it is abstract, but any number of interfaces can be implemented


Using abstract classes when:

  • Share code among several closely related classes;
  • Expect that classes that extend the abstract class have many common methods or fields, or require access modifiers other than public (such as protected and private);
  • Declare non-static or non-final fields. 


Using interfaces when:

  • Expect unrelated classes would implement the interface. E.g., Comparable and Cloneable;
  • Specify the behavior of a particular data type, but not concerned about who implements its behavior;
  • Take advantage of multiple inheritance of type. 

Package:
A package is a namespace that organizes a set of related classes and interfaces. The Java platform provides an enormous class library (a set of packages) suitable for use. This library is known as the "Application Programming Interface (API)".


Instantiation:
The new operator instantiates (aka, creating an object, creating an instance of a class) a class by allocating memory for a new object and returning a reference to that memory. The new operator also invokes the object constructor.
The new operator requires a single, postfix argument: a call to a constructor. It returns a reference to the object it created.


Initialization:
The constructor lets you to provide initial values for the fields of the object of a class.

Method and function: 
A function is a piece of code that is called by name. It can be passed data to operate on (i.e., parameters) and can optionally return data (the return value). All data that is passed to a function is explicitly passed. Functions have independent existence, meaning they can be defined outside of the class. (E.g., main() in C, C++).
A method is a piece of code that is called by name that is associated with an object. It does not have independent existence, it is always defined within the class. Methods are called using objects/instances.


Inheritance:
In Java, classes can be derived from other classes, thereby inheriting fields and methods from those classes.
Subclass/derived class/extended class/child class: a class that is derived from another class.
Superclass/base class/parent class: the class from which the subclass is derived.
Object class in Java has no superclass. In the absence of any other explicit superclass, every class in Java is implicitly a subclass of Object. Every class has at most one parent.
A subclass inherits all of the public and protected members of its parent, regardless what package the subclass is in. If the subclass is in the same package as its parent, it also inherits the package-private members of the parent. A subclass does NOT inherit the private members of its parent. However, if the superclass has public or protected methods for accessing its private fields, these can also be used by the subclass. A nested class has access to all the private members of its enclosing class -- both fields and methods. Therefore, a public or protected nested class inherited by a subclass has indirect access to all of the private members of the superclass.
Declare a field in the subclass with the same name as the one in the superclass will hide that in the superclass (not recommended).
Write a new instance method in the subclass with the same signature as the one in the superclass will override that in the superclass.
Write a new static method in the subclass that has the same signature as the one in the superclass will hide that in the superclass.
You can write a subclass constructor that invokes the constructor of the superclass, either implicitly or by using the keyword super.

Multiple inheritance: 
An object or class can inherit characteristics and features from more than one parent object or parent class. It may be ambiguous as to which parent class a particular feature is inherited from if more than one parent class implements said feature. C++ allows multiple inheritance.

Diamond problem:

An ambiguity that arises when two classes B and C inherit from A, and class D inherits from both B and C. If there is a method in A that B and/or C has overridden, and D does not override it, then which version of the method does D inherit?

Example, in the context of GUI software development, a class Button may inherit from both classes Rectangle and Clickable, and both Rectangle and Clickable inherit from Object class. Now if the equals method is called for a Button object and there is no such method in the Button class but there is an overridden equals method in Rectangle or Clickable (or both), which method should be eventually called? 

Virtual inheritance
A base class in an inheritance hierarchy is declared to share its member data instances with any other inclusions of that same base in further derived classes. This technique makes the virtual base a common subobject for the deriving class and all classes that are derived from it. It clarifies ambiguity over which ancestor class to use, as from the perspective of the deriving class, the virtual base acts as though it were direct base of the deriving class.



class Animal {
    public:
        virtual void eat();
};
class Mammal : public virtual Animal {
    public:
        virtual void breathe();
};
class WingedAnimal : public virtual Animal {
    public:
        virtual void flap();
};
// A bat is a winged mammal
class Bat : public Mammal, public WingedAnimal {
}

In the above example, the Animal portion of Bat :: WingedAnimal is now the same Animal instance as the one used by Bat::Mammal, so Bat has only one, shared, Animal instance in its representation, and so a call to Bat::eat() is unambiguous. The Bat becomes (vpointer, Mammal, vpointer, WingedAnimal, Bat, Animal)

Java 8 introduces default methods on interfaces. If A, B, C are interfaces, B, C can each provide a different implementation to an abstract method of A, causing the diamond problem. Either class D must reimplement the method, or the ambiguity will be rejected as a compile error. The default interface method capability added with Java 8 introduced a type of multiple inheritance since classes can implement more than one interface, which can contain default methods that have the same name. However, the Java compiler provides rules to determine which default method a particular class uses, which prevents the Diamond problem.

Multiple inheritance of state: the ability to inherit fields from multiple classes;
Multiple inheritance of implementation: the ability to inherit method definitions from multiple classes;
Multiple inheritance of type: the ability of a class to implement more than one interface.

Instance method: an instance method in a subclass with the same signature and return type as an instance method in the superclass overrides the superclass's method. An overriding method can also return a subtype of the type returned by the overridden method. This subtype is called a covariant return type.



Polymorphism:
Subclasses of a class can define their own unique behaviors and yet share some of the same functionality of the parent class. Subclasses overrides the corresponding instance method in the parent class. The Java virtual machine (JVM) calls the appropriate method for the object that is referred to in each variable. It does not call the method that is defined by the variable's type. This behavior is referred to as virtual method invocation.


Virtual method and pure virtual method: 
A virtual function/method is a function or method whose behavior can be overridden within an inheriting class/subclass by a function with the same signature. The overridden method called by such a reference or pointer can be bound either 'early' (by the compiler), according to the declared type of the pointer or reference, or 'late' (i.e., by the runtime system of the language), according to the actual type of the object referred to. Virtual functions are resolved 'late'. If the function is 'virtual' in the base class, the most-derived class's implementation of the function is called according to the actual type of the object referred to, regardless of the declared type of the pointer or reference. If it is not 'virtual', the method is resolved 'early' and the function called is selected according to the declared type of the pointer or reference. Virtual functions allow a program to call methods that don't necessarily even exist at the moment the code is compiled. Non-virtual members can not be accessed through a reference of the base class: i.e., if virtual is removed from the declaration of the method in the base class, call the method will call the method in the base class.

Early binding/static binding: the compiler is able to directly associate the identifier name (such as a function or variable name) with a machine address.
Late binding/dynamic binding: In some programs, it is not possible to know which function will be called until runtime.

A pure virtual function/method is a virtual function that is required to be implemented by a derived class if that class is not abstract. Classes containing pure virtual methods are termed "abstract" and they cannot be instantiated directly. A subclass of an abstract class can only be instantiated directly if all inherited pure virtual methods have been implemented by that class or a parent class. Pure virtual methods typically have a declaration (signature) and no definition(implementation).

Methods:
Method signature: the method's name and the parameter types.
calculateAnswer(double, int, double, String, char)


Overloading methods: Methods within a class can have the same name if they have different parameter lists.

Final methods: The method CANNOT be overridden by subclasses.
Access control of classes: 
At the top level: public, or package-private (no explicit modifier)
At the member level: public, private, protected, or package-private
public: the class is visible to all classes everywhere;
private: the member can only be accessed in its own class;
protected: the member can only be accessed in its own package and by a subclass of its class in another package. 





Class initializer/Static Initialization Blocks: 
A static initialization block is a normal block of code enclosed in braces, {}, and preceded by static keyword. Without the static modifier, the code block is an instance initializer.  

static {
    write some awesome code...
}


A class can have any number of static initialization blocks, and they can appear anywhere in the class body. The runtime system guarantees that static initialization blocks are called in the order that they appear in the source code.

Instance initializers are executed in the order defined when the class is instantiated, immediately before the constructor code is executed, immediately after the invocation of the super constructor.


public class Test {
    static {
        System.out.println("Static");
    }
    {
        System.out.println("Non-static block");
    }
    public static void main(String[] args) {
        Test t = new Test();
        Test t2 = new Test();
    }
}


The above example will print:

Static
Non-static block
Non-static block


The non static block gets called every time the class is instantiated. The static block only gets called once, no matter how many objects of that type you create.


Constructors:
A class contains constructors that are invoked to create objects from the class blueprint. As with methods, the Java platform differentiates constructors on the basis of the number of arguments in the list and their types. If no explicit constructor is provided, the compiler automatically provides a no-argument, default constructor. This default constructor will call the no-argument constructor of the superclass. In this situation, the compiler will complain if the superclass doesn't have a no-argument constructor so you must verify that it does. If your class has no explicit superclass, then it has an implicit superclass of Object, which DOES have a no-argument constructor.

Destructors/Finalizers: 
A destructor is a method which is automatically invoked when the object is destroyed. It can happen when its lifetime is bound to scope and the execution leaves the scope, when it is embedded into another object whose lifetime ends, or when it was allocated dynamically and is released explicitly.
Its main purpose is to free the resources (memory allocations, open files or sockets, database connections, resource locks, etc.) which were acquired by the object along its life cycle and/or deregister from other entities which may keep references to it.

C++
In C++, the destructor has the same name as the class, but with a tilde (~) in front of it. If the object was created as an automatic variable, its destructor is automatically called when it goes out of scope. If the object was created with a new expression, then its destructor is called when the delete operator is applied to a pointer to the object. In inheritance hierarchies, the declaration of a virtual destructor in the base class ensures that the destructors of derived classes are invoked properly when an object is deleted through a pointer-to-base class. Object that may be deleted in this way need to inherit a virtual destructor.

A finalizer/finalize method is a special method that performs finalization, generally some form of cleanup. A finalizer is executed during object destruction, prior to object being deallocated, and is complementary to an initializer, which is executed during object creation, following allocation.
Finalizer is primarily used in OO languages that use garbage collection, e.g., Java. This is contrasted with a destructor, which is a method called for finalization in languages with deterministic object lifetimes, e.g., C++. These are generally exclusive, but in rare cases a language may have both, such as C++.

Garbage collection: A form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program.


Primitive types (Java):
byte, short, int, long, float (single-precision 32-bit IEEE 754 floating point), double (double-precision 64-bit IEEE 754 floating point). boolean, char.

Generic Types (Java): 
A generic type is a generic class or interface that is parameterized over types. A type variable can be any non-primitive type you specify: any class type, any interface type, any array type, or even another type variable.

Type parameter:
E - Element;
K -Key;
N - Number;
T - Type;
V - Value;
S, U, V etc. - 2nd, 3rd, 4th types

Memory Layout: Java
When we run a java program, JVM will create a main thread for execution. Different types of data areas are required for execution of the thread. Some of these data areas are created when a java thread is created. These are per thread areas and are destroyed when the thread exits. There are other data areas which are created when the JVM starts and are destroyed when the JVM exits.

The Program counter: Each JVM thread will have its own PC register. A thread may have multiple methods and at a time, only one method's code is executed. If that method is not a native method, then PC register will contain address of the current instruction. If the method is a native one, then the content of PC register is undefined.

JVM Stacks: Each thread has its own stack. The stack is created when the thread is created. It stores local variables and intermediate results and is used for method invocation and return. The memory of JVM stack may not be contiguous (shared).

JVM Heap: The JVM heap is shared among all the threads. It is a run-time data area. Memory for all class instances is allocated from heap. Heap is created when JVM starts. Memory allocated to a class instance from heap is reclaimed back. there is an automatic storage management system also known as garbage collector which does this job. Heap need not be a contiguous memory and can dynamically expand or contract as and when required.

JVM Method Area: The OS processes have an area called as text area. Method area is analogous to that. It is shared among all threads. It is created on virtual machine start-up. The memory may not be contiguous. It stores per class structures such as code for methods, constructors, interface initialization, run-time constant pool, field and method data etc.

JVM Frames: A frame is created every time a method is invoked. The frame is destroyed when the invocation completes. The completion may be normal or abrupt. Frames are created from stack of the JVM for that thread. The frame has its own local variables, run-time constant pool, etc. In a given thread control, at any point of time only the frame of the executing method method is active and is called current frame.

Java Native method: There can be situations when an application cannot be completely developed in java probably because there are some platform specific features which java class library does not support. Java native interface, JNI enables writing native methods to handle such situations.
Java Native Interface (JNI): a programming framework that enables Java code running in a JVM to call and be called by native applications(programs specific to a hardware and OS platform) and libraries written in other languages such as C, C++ and assembly.

Execution Engine: The execution engine has the virtual processor an interpreter and a just-in-time compiler.

Source: http://www.mybodhizone.com/Core_Java/mbz_corejava_memoylayout.php

Enum type
An enum type is a special data type that enables for a variable to be a set of predefined constants. The variable must be equal to one of the values that have been predefined for it. The names of an enum type's fields are in uppercase letters.

You should use enum types any time you need to represent a fixed set of constants. That includes natural enum types such as the planets in our solar system and data sets where you know all possible values at compile time.

The enum declaration defines a class. The enum class body can include methods and other fields. The compiler automatically adds some special methods when it creates an enum. For example, they have  a static values method that returns an array containing all of the values of the enum in the order they are declared.

An enum cannot extend any other classes because it is implicitly extend java.lang.Enum.

Each enum constant is declared with values. These values are passed to the constructor when the constant is created. Java requires that the constants be defined first, prior to any fields or methods, the list of enum constants must end with semicolon.

The constructor for an enum type must be package-private or private access. It automatically creates the constants that are defined at the beginning of the enum body. You cannot invoke an enum constructor yourself.

Serialization
A process of convert an object to a byte stream so that it can be stored (e.g., in a file system or memory buffer) and reconstructed later into a copy of the object. It is a standardized and already available way of converting the object to a stream of bytes.