All You Can Eat - Java

JDK, JRE, JVM

Java Development Kit (JDK)

JDK contains:

  • Java Runtime Envirumnet (JRE)
  • Java interpreter/loader (java)
  • Java compiler (javac)
  • Java archiver (jar)
  • documentation generator (javadoc)

Java Runtime Envirumnet (JRE)

  • JRE provides the minimum requirements for executing a Java application

JRE contains:

  • Java Virtual Machine (JVM)
  • core classes, and supporting files

Java Virtual Machine (JVM)

  • runs Java byte code

https://www.geeksforgeeks.org/differences-jdk-jre-jvm/

Summary

JDK = JRE + Development tool
JRE = JVM + Library classes

Traversal/Iteration for Array and List

Array

Method1: Basic for-loop:

1
2
3
for (int i = 0; i < nums.len; i++) {
...
}

Method2: Enhanced for-loop (implicit iteratior):

1
2
3
for (int n : nums) { 
...
}

List

Method1: Basic for-loop:

1
2
3
4

for (int i = 0; i < list.size(); i++) {
E element = list.get(i);
}

Method2: Enhanced for-loop:

Note: The enhanced for statement is equivalent to a basic iterator form:
https://docs.oracle.com/javase/specs/jls/se7/html/jls-14.html#jls-14.14.2

1
2
3
for (E e : list) { 
...
}

Method3: Iterator:

1
2
3
4
5
Iterator<String> it = list.iterator();  
while (it.hasNext()) {
it.next();
...
}

or

1
2
3
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
it.next();
}

Note: for list, Method2 and 3 lock data, hence, remove perform via it.remove(), should NOT use list.remove(). Method1 does not lock data, hence better perforamnce, more suitable for simple iteration.

if List uses ArrayList as implementation class, method 1 has better performance becuase it does not require allocation of resource for iterator http://ganbiao2205.iteye.com/blog/2113745

Reference:
http://blog.csdn.net/yasi_xi/article/details/24797807

已知可用enhanced forloop的数据结构 (array/collection):array, HashMap, HashSet

Modify element while iterating List

  • this not changing structure of the list (ex. NOT add or remove element from list)
  • using enhanced for-loop in this case is NOT recommand since we are not using the iteration feature provided by enhanced for-loop.
1
2
3
4
5
6
// correct way to modify elment
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == 'C') {
list.set(i) = 'D';
}
}

ref: https://stackoverflow.com/questions/20639098/in-java-can-you-modify-a-list-while-iterating-through-it

Add/Remove element while iterating List

Approach 1: Collect and Remove (removeAll)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

List<Book> books = new ArrayList<Book>();
books.add(new Book(new ISBN("0-201-63361-2")));
books.add(new Book(new ISBN("0-201-63361-3")));
books.add(new Book(new ISBN("0-201-63361-4")));

ISBN isbn = new ISBN("0-201-63361-2");
List<Book> found = new ArrayList<Book>();
for(Book book : books){
if(book.getIsbn().equals(isbn)){
found.add(book);
}
}
books.removeAll(found);

ref: https://docs.oracle.com/javase/7/docs/api/java/util/ListIterator.html

Approach 2: Using ListIterator

  • ListIterator() supports both add() and remove() while iterating a list

note: iterator() supports remove() but NOT add().

1
2
3
4
5
6
ListIterator<Integer> iter = list.listIterator();
while(iter.hasNext()){
if(iter.next().equals(2)){
iter.remove();
}
}

ref: https://stackoverflow.com/questions/10431981/remove-elements-from-collection-while-iterating

Element e vs Object o TODO

Trap of equals vs ==

Java primitative type includes: int, float, double, short, long, byte, char, and boolean

Primitative type stores actual value in variable, non-primitative type stores reference to the data. Hence, == can be used to compare value for primitative type. == only compares address for non-primitative type. Non-primitative type uses/override equals() to compare content.

Examples:

1
2
3
4
5
6
1 == 1 // return true

str1 = "123";
str2 = "123";
str1 == str2; // return fales
str1.equals(str2); // return true

new ArrayList in one line

Arrays.asList("xyz", "abc") returns a fixed-size list backed by the specified array, hence, it can be iterated, but NOT be modified

If you need to add/remove to th list later:

1
List<String> x = new ArrayList<>(Arrays.asList("xyz", "abc"));

If you don’t want to add new elements to the list later, you can also use (Arrays.asList returns a fixed-size list):

1
List<String> x = Arrays.asList("xyz", "abc");

src: https://stackoverflow.com/questions/21696784/how-to-declare-an-arraylist-with-values
https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#asList(T...)

Trap of Arrays.asList()

Arrays.asList() converts an array to a List representation of the array. List allows us to manipulate elements within array (add/remove) which cannot be achived easily with array.

Example of initialize a List with one element.

1
2
3
4
5
List<Integer> list = new ArrayList<>(Arrays.asList(1));

// OR
List<Integer> list = new ArrayList<>();
list.add(1);

Here is an important detail when passing primitive type array to Arrays.asList():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int[] array = {1,2,3}; // primitive type array
Integer[] array2 = new Integer[]{1,2,3}; // Wrapper type array

for(Object i : Arrays.asList(array)) { // only print ONCE
print (i);
}

for(Object i : Arrays.asList(array2)) { // prints all element
print (i);
}

for(Object i : Arrays.asList(1,2,3)) { // prints all element w/ auto-boxing
print (i);
}

Arrays.asList(T... a)

  • if a is a primitive type array (int[]{1,2,3}): it treats the entire array reference as ONE element in new list
  • if a is a wrapper type array (Integer[]{1,2,3}): each element within array will be added to new list
  • if a is a list of primitive values (1,2,3): each primitive value first auto-box to wrapper type and be added to new list.

References:
http://blog.csdn.net/champgauss/article/details/50183523
http://blog.csdn.net/cntanghai/article/details/7188296
http://blog.csdn.net/chenleixing/article/details/43775127

Convert between String <-> int

String to int

  • int i = Integer.parseInt(str) // preferred: support binary/hex form
  • int i = Integer.valueOf(str).intValue()
1
2
3
parseInt("-0", 10) returns 0
parseInt("-FF", 16) returns -255
parseInt("1100110", 2) returns 102

int to String

  • String s = String.valueOf(i);
  • String s = Integer.toString(i); // preferred

References:
https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#parseInt(java.lang.String,%20int)
http://blog.csdn.net/memray/article/details/7312817/

Convert between char <-> int

char to int

  • char -> charArray -> String -> Integer.parseInt(str)
  • Character.getNumericValue(numChar)) // preferred
  • s.charAt(i) - '0' also preferred.
1
2
3
4
5
6
7
8
9
10
11
char numChar = '9';
int intNum = (int)numChar;
System.out.println(numChar + ": " + intNum); // numChar: 57 (ASCII)

// method1: new instance, memory consummed
char[] charArray = {numChar};
intNum = Integer.parseInt(new String(charArray));
System.out.println("method 1: " + numChar + ":" + intNum);

// method2: static method, Preferred!
System.out.println("method 2: " + numChar + ":" + Character.getNumericValue(numChar));

int to char

1
2
3
4
5
int a = 10;
String aStr = Integer.toString(a);
for (Character c : aStr.toCharArray()) {
print(c);
}

References:
http://blog.csdn.net/sxb0841901116/article/details/20623123

Convert between String <-> char/charArray

String to char

For string String str = "string"

  • char c = str.charAt(index);

String to charArray

char to String

  • String s1 = String.valueOf('c'); // prefered
  • String s2 = String.valueOf('abc');
  • String s3 = Character.toString('c'); // easier to remember, call String.valueOf() implicitly

Reference:
http://blog.csdn.net/yaokai_assultmaster/article/details/52082763

Convert String, int, char summary

java.util.Arrays vs java.lang.reflect.Array

java.lang.reflect.Array is a data type

java.util.Arrays provides useful methods for Array data type

  • Arrays.fill(array, initial_val) // good way to initialize array with same default value
  • Arrays.asList(stringArray) // convert to List data type for more functionalities
  • Arrays.toString(intArray) // without using for loop to print array
  • Arrays.sort()

Fill array with default values

1
2
3
4
int[] a = new int[10];
Arrays.fill(a, 10);
// output
a = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]

more: https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html

int vs long vs BigInteger

  • int: $[-2^{31}, 2^{31}-1]$ (32bit)
  • BigInteger class: unlimited size via dynamic memory
1
2
3
4
5
BigInteger sum = new BigInteger(0);
for (int i = 0; i < 10; i++) {
sum = sum.add(BigInteger.valueOf(i));
}
return sum;

How to sort a String in Java

1
2
3
4
5
6
7
8
9
10
11
public static String sortString(String inputString)
{
// convert input string to char array
char tempArray[] = inputString.toCharArray();

// sort tempArray
Arrays.sort(tempArray);

// return new sorted string
return new String(tempArray);
}

Recursion vs Iteration

Recursion cleaner than Iteration, is recursion faster than iteration?

https://leetcode.com/problems/add-two-numbers/description/

recursive approach faster than iterative approach. (This is incorrect, I dont think we can conclude that just from the run time from leetcode, could be the case when your solution is running, executation server is under heavy load. etc)

Below is what is the main difference between iteration and recursion from my other post: http://xuyiruan.com/2018/02/24/five-most-frequent-use-alogrithms-1-divide-and-conquer/

difference between iteration and recurrsion?

why manual stack is better than recursion (callstack):

非递归其实是模拟递归用的stack

为什么自己模拟的可以, 调用计算机的就不行呢?

因为我们new出来的stack在heap memory里面, 能用的空间≈ memory size

stack memory ≈ process memory是计算机分给每个程序的一个很小的独占的空间,所以递归的深度太深,就不够用了

How to properly compare two Integers in Java?

1
2
3
4
5
6
7
8
9
10
11
12

Stack<Integer> stack;
Stack<Integer> min;

public void pop() {
if (!stack.isEmpty()) {
if (stack.peek() == min.peek()) { // wrong, returns false most of time
min.pop();
}
stack.pop();
}
}

Integer is a wrapper class for int, only primitive type can be compared with == for eqaulity. Non-primitive type should use .equals() to compare.

Package in Java

  • import java.util.* will import all classes in util package. However, subpackages within util will NOT be imported. ex, java.util.searchUtil will not be imported.
  • using * is not always recommanded to avoid conflict of libraries in different packeage with the same name.
1
2
3
4
5
6
import java.util.*;
import java.sql.*;

//And then use Date class , then we will get a compile time error :

Date today ; //ERROR-- java.util.Date or java.sql.Date?

Compare Integer in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
List<Integer> pList = levelOrderTraversal(p);
List<Integer> qList = levelOrderTraversal(q);

// check pList identical to qList
if (pList.size() != qList.size()) {
return false;
}
for (int i = 0; i < pList.size(); i++) {
if (pList.get(i) != qList.get(i)) {
return false;
}
}
return true;

code snippet above compares if content of two lists pList, qList are identical. However, line 5 has some bug. Since get() returns Integer type, which is boxed value for int. Direct using == to compare Integer is comparing reference of Integer. Hence, we need to use intValue() to convert Integer type to int before comparison w/ == OR simply uses .equal() to compare two Integer.

1
2
3
4
5
if (pList.get(i).intValue() != qList.get(i).intValue())

OR

if (pList.get(i).equals(qList.get(i))

diamond operator <> in JDK7

instead of writing

1
Box<Integer> integerBox = new Box<Integer>();

you could replace explicit declaration on the right with diamond operator <>

1
Box<Integer> integerBox = new Box<>();

compiler will infer the type arguments from the context.

keyword: abstract & interface

1
2
3
4
5
6
7
8
9
10
11
12
13
abstract class Animal {

// no abstract method

}

public class Dog extends Animal {

}

public class Cat extends Animal {

}

another example with abstract method:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
abstract class Animal {
public void eat(Food food) {
// do something with food....
}

public void sleep(int hours)
{
try
{
// 1000 milliseconds * 60 seconds * 60 minutes * hours
Thread.sleep ( 1000 * 60 * 60 * hours);
}
catch (InterruptedException ie) { /* ignore */ }
}


// abstract method
public abstract makeNoise();
}

public class Dog extends Animal {
public void makeNoise() { System.out.println ("Bark! Bark!"); }
}

public class Cat extends Animal {
public void makeNoise() { System.out.println ("Mua~! Mua~"); }
}

Declaring a class abstract only means that you don’t allow it to be instantiated on its own (Need other class to extends it and then can only be instantiated with the new Class(eg, Dog, Cat)).

Declaring a method abstract means that subclasses have to provide an implementation for that method.

Interface should also works. Howerver, abstract classes allows classs to inherit the implementation of other (non-abstract) methods, while interface cannot

Interface cannot provide any method implementations (like, eat(), sleep())

Note: A class implements an interface, A class extends an abstract class. Java only allow class to extends ONE class, because of that, interface sometimes is more preferred when current class need to extends other class.

https://stackoverflow.com/questions/6007089/how-and-when-to-use-an-abstract-class

keyword: static

static variable

  • static indicates variable is a class variable
  • static variable create only one copy and share among all instances
  • static variable can be manipulated without creating an instance

Static variable initialization

  • Static variables are initialized when class is loaded.
  • Static variables are initialized before any object of that class is created.
  • Static variables are initialized before any static method of the class executes.

ref: https://beginnersbook.com/2013/05/static-variable/

static method

Rule of thumb when or not to use static method:

  1. does it make sense to call this method, even if no object has been constructed yet?

ref: https://stackoverflow.com/questions/37717885/making-all-methods-static

  • static method means this method does NOT require an instance to call the method.
  • hence, a static method belongs to the class rather than object of a class.
  • static method cannot access instance variable (non-static variable), since static method is a class mothod, which does NOT tie to any specific instance. Hence, not able to know what the instance variable is. (see below for work around)
  • this and super cannot be used within static method context

ref: https://www.javatpoint.com/static-keyword-in-java

Example of HashMap implementation:

1
2
3
4
5
6
7
8
9
10
11
private int mapSize = 100; // no static since each instance has a different mapSize

// static -> class method, not an instance method
// hash index based on mapSize, however mapSize is an instance variable
// class method cannot access isntance varible
private static int hash(int key) {
return key % mapSize;
}

// run error
int index = hash(key);

work around:

1
2
3
4
5
6
7
8
9
10
11
private int mapSize = 100; // no static, instance variable

// static -> class method, not an instance method
// hash index based on mapSize, however mapSize is an instance variable
// class method cannot access instance varible
private static int hash(int key, int mapSize) {
return key % mapSize;
}

// run okay
int index = hash(key, this.mapSize);

keyword: this and super

  • this is a pointer to current object
  • super is a pointer to closest parent object
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode {
int val;
ListNode(int val) {
this.val = val; // use this to distinguish local `val` from instance variable `this.val`
}
}

instead we could write:

ListNode {
int val;
ListNode(int v) {
val = v; // no this need since name of two variables different
}
}

Other usages of this and super: https://www.cnblogs.com/hasse/p/5023392.html

keyword: transient

  • variable with transient key word will NOT be serialized (to ensure confidentiality, password, ssn, credit card no, etc) when object is serialzed
  • varaible marked with transient will NOT be stored into file, only remain in memory.
  • transient can only be used to declare variable, NOT class nor method

ref: http://www.cnblogs.com/lanxuezaipiao/p/3369962.html

keyword: final

Final Varaible

  • constant variable, can NOT be modfied
  • must be initialized when decleared
  • final reference variable can NOT be re-bounded to reference anther object, while object content CAN be changed

Final Method

  • A final method cannot be overridden

Final Class

  • a final class can NOT be extended (inherited)
  • All warapper classes (Integer, Float, etc) are final classes, which cannot be extented
1
2
3
4
5
6
7
8
9
final class A
{
// methods and fields
}
// The following class is illegal.
class B extends A
{
// COMPILE-ERROR! Can't subclass A
}

ref: https://www.geeksforgeeks.org/final-keyword-java/

String parsing techniques

given:
String exp2 = "2+0+1-1+0+5*194/5"
how do we parse the string to extract operands and operators to evaluate/calculate the math expression.

https://leetcode.com/problems/basic-calculator-ii/

Generic Algorithm Approach:

  • appends + in the front of the exp, implict insert + to exp
  • num = 0 implicit change first operand to 0

Approach 1:
use str.split() function w/ regular expression to split string into String[] of operands and operators

1
2
3
4
String[] nums = s.split("[-+*/]"); // why +-*/ not work?
String[] ops = s.split("[0-9]+");

// total O(2n) for two calls on split()

useful regex:

  • ^ matches begining of the string
  • [] matches any characters inside bracket
  • \\s first \ tells java that whatever goes after is a regex string. \s means one empty space. Without escaping char, it will be indistinguishable from s letter. Hence, this reges matches one space.

ref: https://stackoverflow.com/questions/11009320/validate-mathematical-expressions-using-regular-expression

note: str.split() incure O(n) traverse time for string of n characters.

Approach 2:

  • Character.isDigit() method
  • traverse entire string only once $O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0; i < s.length(); i++) {
int num = 0;

// extract number bit by bit
if (Character.isDigit(s.charAt(i))) {
num = 10 * num + s.charAt(i) - '0';
}

// extract operator
if (!Character.isDigit(s.charAt(i))) {
op = s.charAt(i);
}
}

Check letter and digit

  • Alphabets: 26 letters (lower case only)
  • alphanumeric: 26 letters + 9 digit numbers

Character.isLetterOrDigit(); // check alphanumeric
Character.isDigit() // check digit (0-9)
Character.isLetter() // check english character

Note: isAlphabetic() > isLetter()

  • use isLetter() for english text
  • use isAlphabetic() if Greek letter, etc invovled

Vector in Java

Vector is almost identical to ArrayList, and the difference is that Vector is synchronized. Because of this, it has an overhead than ArrayList. Normally, most Java programmers use ArrayList instead of Vector because they can synchronize explicitly by themselves.

Key factors:

  • fail-fast behavior of an iterator when not using add() or remove() method, ensure concurency and exit cleanly
  • Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector.

ref: https://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

What is the difference between final, finally, and finalize?

  • final - control whether a variable, method, or class is change-able
  • finally - used in a try/catch block to ensure that a segment of code is always executed
  • finalize() - called by garbage collector once it determines that no more references exist.

Generics in Java

  • generalize parameter type to methods/functions
  • use <> to specify generics Parameter type
  • enhance code reusablility: write once, use for any type Type Safety
  • type safety: Generics make errors to appear compile time than at run time

ref: https://www.geeksforgeeks.org/generics-in-java/

Overriding equals() method in Java

  • key1: @Override notation
  • key2: parameter Object o
  • key3: instanceof to check Class type

Example from GeekforGeeks:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Complex {

private double re, im;

public Complex(double re, double im) {
this.re = re;
this.im = im;
}

// Overriding equals() to compare two Complex objects
@Override
public boolean equals(Object o) {

// If the object is compared with itself then return true
if (o == this) {
return true;
}

/* Check if o is an instance of Complex or not
"null instanceof [type]" also returns false */
if (!(o instanceof Complex)) {
return false;
}

// typecast o to Complex so that we can compare data members
Complex c = (Complex) o;

// Compare the data members and return accordingly
return Double.compare(re, c.re) == 0
&& Double.compare(im, c.im) == 0;
}
}

// Driver class to test the Complex class
public class Main {

public static void main(String[] args) {
Complex c1 = new Complex(10, 15);
Complex c2 = new Complex(10, 15);
if (c1.equals(c2)) {
System.out.println("Equal ");
} else {
System.out.println("Not Equal ");
}
}
}

ref: https://www.geeksforgeeks.org/overriding-equals-method-in-java/

Garabge collection in JAVA

  • GC frees the memory occupied by the unreachable objects
  • GC is a daemon thread. A daemon thread runs behind the application. It is started by JVM. The thread stops when all non-daemon threads stop.

how does GC know which memory to collect?

  • start from application root, marked those objects pointed by variable using, those NOT marked are eligble for reclaiming.

what is finalize() method in GC?

  • Ans) The finalize() method should be overridden for an object to include the clean up code or to dispose of the system resources that should to be done before the object is garbage collected.

Note: sometimes it is too expensive to run GC when system is busy. Hence, GC should only be runned when system is idle.

ref: http://java-questions.com/garbagecollection-interview-questions.html

浅析JAVA的垃圾回收机制(GC)ref: https://www.jianshu.com/p/5261a62e4d29

Strong/Soft/Weak reference

引用类型 被垃圾回收时间 用途 生存时间
强引用 从来不会 对象的一般状态 JVM停止运行时终止
软引用 在内存不足时 cache, such as the image cache 内存不足时终止
弱引用 在垃圾回收时 对象done, set to = null gc运行后终止

ref: http://blog.csdn.net/mazhimazh/article/details/19752475

Design Pattern: Singleton

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Logger {
private static Logger log = null;

private Logger() { // key1 private
}

public static getInstance() { // key2 static
if (log == null) {
synchronized(this) { // t1 waitting. since t2 is creating instance, t1 after synchronized block should create instance
if (log == null) {
log = new Logger(); // t2 already created instance
}
}
}
return log;
}
}
  • key0: private constructor
  • key1: static singleton object
  • key2: check if singleton object has already been initialized
  • key3: synchronized w/ lock
  • key4: second check if singleton object has been initialized (in case of delay or cache)

ref: http://blog.jobbole.com/109449/

detail tutorial: http://www.runoob.com/design-pattern/design-pattern-intro.html

Java Lock

TODO:

ref: http://wiki.jikexueyuan.com/project/java-concurrent/locks-in-java.html

Queue APIs

  • add(E e): insert to queue, throws IllegalStateException if no space is currently available (ex. fixed size queue)
  • offer(E e): [prefered] insert to queue, return false when size-limited queue is full without throwing an exception
  • remove(): Retrieves and removes the head of this queue. This method differs from poll only in that it throws an NoSuchElementException exception if this queue is empty.
  • poll(): [prefered] Retrieves and removes the head of this queue, or returns null if this queue is empty.

When we add to queue, we want to know when it is failed because of size-limited queue, hence, it is preferred to use add().

We use poll() to remove, since we always check queue.isEmpty() before poll(), hence, no requirement of throwing exception in this case. (use add(), and remove() with/ exception checking for good practice).

ref: https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

class vs public class

  • wo/ public: package default as protected
  • protected means only accesable within the same package

https://stackoverflow.com/questions/16779245/what-is-the-difference-between-public-class-and-just-class

Dynamic size array

  • java supports array w/ dynamic size at run time
  • memory allocate at new keyword
  • JVM allocates memory dynamically based on the value of size.

https://stackoverflow.com/questions/20207969/java-textbook-the-size-of-an-array-must-be-known-at-compile-time

generate random number between a and b

https://www.mkyong.com/java/java-generate-random-integers-in-a-range/

Polymorphlism

key:
One message invokes different methods based on object type (ex. “lets get back to work”, one message invokes different people continue working on different things)

In Java, polymorphism is possible through

inheritance

  • Override toString() to return different values that are textual representations of that type.

interfaces

  • Collections.sort(List<?>) sends compareTo messages to objects that must have
    implemented Comparable

src: https://www2.cs.arizona.edu/~mercer/Presentations/OOPD/05-PolymorphismViaInterfaces.pdf

Benefit of Polymorihpism, and why polymorphism

  • 解耦性 (less tightly coupled -> decouple -> more generic method)

没有Poly的时候:

1
2
3
public void generatePayroll(Manager manager)
public void generatePayroll(Accountant accountant)
..etc
  • 每个子类(Manager, Staff, SDE, HR,etc) extends 父亲类 (Employee)
  • 每个子类可以override 父亲的方法实现自己的payroll. call的时候只需要call generalize的method
1
public void generatePayroll(Employee employee)

https://www.quora.com/What-are-the-advantages-of-polymorphism-in-java
https://www.zhihu.com/question/30082151

List of OOP Concepts in Java

Abstraction

  • abstraction is a process of hiding the implementation details from the user
  • only the functionality will be provided to the user.
  • In other words, the user will have the information on what the object does instead of how it does it.
  • In Java, abstraction is achieved using Abstract classes and interfaces.
  • 比如对于对象dog有一个方法叫做bark()。可以通过dog.bark() 来使用此方法而不必关心方法内部怎么实现。

Encapsulation

variables of a class will be hidden from other classes, and can be accessed only through the methods of their current class. Therefore, it is also known as data hiding.

To achieve encapsulation in Java:

  1. Declare the variables of a class as private.
  2. Provide public setter and getter methods to modify and view the variables values.

封装性:也就是把客观事物封装成抽象的类,并且类可以把自己的数据和方法只让可信的类或者对象操作,对不可信的进行信息隐藏(setter/getter)

Inheritance

2) 继承性: 当两类属于is-a 关系时可用继承。(eg. cat is an animal) 通过继承子类可以拥有父类的属性和方法

Polymorphism

3) 多态性: 同一操作作用于不同的对象,可以有不同的解释,产生不同的执行结果。
举个上课的例子,我们现在有一个类叫女神,另外有两个类:群主类和系花类。群主和系花都继承女神类,即群主是女神,系花是女神。现在女神有一个技能叫做拒绝追求者。但是呢群主和系花都有不同的拒绝方式,比如群主喜欢面拒,系花喜欢拉黑。所以在群主和系花类里分别重写了拒绝这个方法。现在通过如下代码我们可以用都是女神类型的变量实现不同的拒绝方式,即为多态。

src:

int, long, BigInteger, float, double, BigDecimal

Integers

  • int 32bit [-2^31, 2^31-1], want larger range?
  • long 64bit [-2^63, 2^63-1]
  • BigInteger unlimited, base on memory size

decimal

  • float 32bits
  • double 64bits
  • BigDecimal even more.

https://stackoverflow.com/questions/27598078/float-and-double-datatype-in-java

read from a file

  • BufferedReader for larger sized file
  • Scanner supports parsing operation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static List<String> readFromFile(String fileName) {
File inFile = new File(fileName);
BufferedReader bufferedReader = null;
List<String> data = new ArrayList<>();

String line = null;
try {
bufferedReader = new BufferedReader(new FileReader(inFile));
// read db_op a line at a time
while ((line = bufferedReader.readLine()) != null) {
data.add(line);
}

bufferedReader.close();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (bufferedReader != null) {
try {
bufferedReader.close();
} catch (IOException e1) {

}
}
}
return data;
}

OR

1
2
3
4
5
6
7
File file = new File(filePath);
Scanner sc = new Scanner(file);
while (sc.hasNextLine()) {
String[] tokens = sc.nextLine().trim().split("\\s+");
// trim() remove leading and trailing spaces
// split("regex") where '\\s+' splits on multiple spaces
}

https://www.geeksforgeeks.org/different-ways-reading-text-file-java/
https://docs.oracle.com/javase/7/docs/api/java/util/Scanner.html

write to file

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void writeToFile(List<String> data, String fileName) {
File outFile = new File(fileName);
BufferedWriter bufferedWriter = null;

try {
bufferedWriter = new BufferedWriter(new FileWriter(outFile));
for (Iterator<String> iter = data.iterator(); iter.hasNext(); ) {
String line = iter.next();
bufferedWriter.write(line);
if (iter.hasNext()) {
bufferedWriter.write("\n");
}
}
bufferedWriter.close();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (bufferedWriter != null) {
try {
bufferedWriter.close();
} catch (IOException e1) {

}
}
}
}

OR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PrintWriter out = null;
try {
out = new PrintWriter(new FileWriter(fileName));
out.println("Hello World\n");
} catch (IndexOutOfBoundsException e) {
System.err.println("Caught IndexOutOfBoundsException: " + e.getMessage());
} catch (IOException e) {
System.err.println("Caught IOException: " + e.getMessage());
} finally {
if (out != null) {
print("Closing PrintWriter");
out.close();
} else {
print("PrintWriter not opened");
}
}

https://docs.oracle.com/javase/tutorial/essential/exceptions/putItTogether.html
https://stackoverflow.com/questions/2885173/how-do-i-create-a-file-and-write-to-it-in-java

random number in Java

1
2
3
4
5
6
7
8
9
10
import java.util.Random;
Random rand = new Random();

rand.nextInt(); // returns any valid integer (both + & -)
rand.nextInt(10); // returns integers from 0-9
rand.nextInt(10) + 1; // returns integers from 1-10
rand.nextInt(10) + 5; // returns integers from 5-14
rand.nextInt((B - A) + 1) + A; // returns integers between A and B

rand.nextDouble(); // returns decimal betwen [0.0, 1.0)

https://docs.oracle.com/javase/7/docs/api/java/util/Random.html#nextDouble()

enum data type

what?

  • representation of a named constant
  • represents by enum data type
  • java enum is powerful, it can add variables, methods and constructors to it

why?

1
2
3
int sweetFoobangCount = countFoobangs(3);
// vs
int sweetFoobangCount = countFoobangs(FB_TYPE.SWEET);
  • much easier to read
  • avoid errors from passing in invalid constants

https://stackoverflow.com/questions/4709175/what-are-enums-and-why-are-they-useful

when?

how?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// A simple enum example where enum is declared
// outside any class (Note enum keyword instead of
// class keyword)
enum Color
{
RED, GREEN, BLUE;
}

public class Test
{
// Driver method
public static void main(String[] args)
{
Color c1 = Color.RED;
System.out.println(c1);
}
}
  • Enums are used when we know all possible values at compile time
  • constants always declare first with ALL CAPs
  • then methods, variables and constructor can be declared after
1
2
3
4
5
6
7
/* internally above enum Color is converted to */
class Color
{
public static final Color RED = new Color();
public static final Color BLUE = new Color();
public static final Color GREEN = new Color();
}
  • enum internally implemented by using Class
  • enum constant is an object of type enum
  • enum constant is always implicitly public static final, static allows access by enum name
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Java program to demonstrate working of values(),
// ordinal() and valueOf()
enum Color
{
RED, GREEN, BLUE;
}

public class Test
{
public static void main(String[] args)
{
// Calling values()
Color arr[] = Color.values();

// enum with loop
for (Color col : arr)
{
// Calling ordinal() to find index
// of color.
System.out.println(col + " at index "
+ col.ordinal());
}

// Using valueOf(). Returns an object of
// Color with given constant.
// Uncommenting second line causes exception
// IllegalArgumentException
System.out.println(Color.valueOf("RED"));
// System.out.println(Color.valueOf("WHITE"));
}
}
  • values() method returns all values present inside enum
  • ordinal() method returns index of enum constant, just like array index
  • valueOf() method returns the enum constant of the specified string value, if exists.

enum constructor and methods:

  • enum can contain constructor and it is executed separately for each enum constant at the time of enum class loading
  • We can’t create enum objects explicitly and hence we can’t invoke enum constructor directly
  • enum can contain concrete methods only i.e. no any abstract method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Java program to demonstrate that enums can have constructor
// and concrete methods.

// An enum (Note enum keyword inplace of class keyword)
enum Color
{
RED, GREEN, BLUE;

// enum constructor called separately for each
// constant
private Color()
{
System.out.println("Constructor called for : " +
this.toString());
}

// Only concrete (not abstract) methods allowed
public void colorInfo()
{
System.out.println("Universal Color");
}
}

public class Test
{
// Driver method
public static void main(String[] args)
{
Color c1 = Color.RED;
System.out.println(c1);
c1.colorInfo();
}
}

https://www.geeksforgeeks.org/enum-in-java/

equal OR == in enum

  • == is safe to used
  • The equals method in Enum is a final method that merely invokes super.equals, which performs an identity comparison

== never throws NullPointerException

1
2
3
4
5
enum Color { BLACK, WHITE };

Color nothing = null;
if (nothing == Color.BLACK); // runs fine
if (nothing.equals(Color.BLACK)); // throws NullPointerException

== is subject to type compatibility check at compile time

1
2
3
4
5
enum Color { BLACK, WHITE };
enum Chiral { LEFT, RIGHT };

if (Color.BLACK.equals(Chiral.LEFT)); // compiles fine
if (Color.BLACK == Chiral.LEFT); // DOESN'T COMPILE!!! Incompatible types!

ref: https://stackoverflow.com/questions/1750435/comparing-java-enum-members-or-equals/2937561#2937561

Java label

  • how to jump out of a nested for loop wo/ using return statement?
  • use java label!
  • label equals to goto in C programming
  • just create a label name, place it at the begining of the loop you want to jump out
  • note: label is not where the program will go, the label just mark which loop you want to jump out of.

https://leetcode.com/problems/longest-common-prefix/description/
https://stackoverflow.com/questions/886955/breaking-out-of-nested-loops-in-java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
if (strs.length == 1) {
return strs[0];
}

int minLen = Integer.MAX_VALUE;
for (String s : strs) {
minLen = Math.min(minLen, s.length());
}

StringBuilder sb = new StringBuilder();

outerloop:
for (int i = 0; i < minLen; i++) {
char c = strs[0].charAt(i);

for (int j = 1; j < strs.length; j++) {
if (c != strs[j].charAt(i)) {
break outerloop;
}
}
sb.append(c);
}
return sb.toString();
}
}

Method Signatures

method signature includes:

  1. method name
  2. parameter count
  3. parameter type
  4. parameter order

Note: return type and thrown exception are not considered part of method signature

The following three methods do have the same signatures:

1
2
3
int doSomething(int y) 
String doSomething(int x)
int doSomething(int z) throws java.lang.Exception

src: https://en.wikipedia.org/wiki/Type_signature#Examples

Iteratior.forEachRemaining() and method reference

  • method signature: forEachRemaining(Consumer<? super E> action)
  • a method in Iterator class, which iterate through all remaining elements in the collection
  • for each of the element, perform action
  • action could be simple println() or add to list
  • action defines in lambda expression or method reference

lambda expression:

1
names.forEach(name -> System.out.println(name));

method reference:

1
names.forEach(System.out::println);

Note: even both method above perform the same opeartion, method reference seems more concise.

Class Optional

  • A container object which may or may not contain a non-null value
  • If a value is present, isPresent() will return true and get() will return the value

Benefits:

  • Optional<T> could help prevents NULL_POINTER_EXCEPTION

Arrays.equals(a1, a2) vs a1.equals(a2)

a1.equals(a2) is the same as array1 == array2, which check if two objects are the same. Arrays.equals(a1, a2) compares the contents of the arrays.

Similarly a1.toString() returns address of pointer. Arrays.toString(a1) returns string representation of array

src: https://stackoverflow.com/a/8777279

Lambda expression Java slow in Leetcode

  • when I was working one of the Leetcode problem https://leetcode.com/problems/evaluate-division/description/
  • solution with lambda expression is significantly slower than one without using one (2ms vs 50ms).
  • Search a bit on google and found the reason behind.
  • even in general Lambda is more concise, and faster, but it requries a one time setup process which might will be ran everytime on leetcode.

https://stackoverflow.com/questions/34585444/java-lambdas-20-times-slower-than-anonymous-classes

Thread vs Process

Thread:

  • thread has its own stack, but sharing heap space of the parent process
  • inter-thread communication betwwen threads via shared memory (sharing same address space)
  • context-switch between threads is cheaper than process (virtual addr. same, TLB, virtual address cache remain same)
  • thread shared memory, one bad thread might screw up all other threads, the entire process (security, stablility low)

Process:

  • a process can contains mutliple threads
  • process has dedicated stack and heap
  • single process has at least one thread of execution (which is the main thread)
  • communication between process via IPC (inter-process communication)
  • context-switch between processes is expensive
  • process stand alone memory, one bad process not affect other process, and it is also more secure with respected to privacy (Chrome tabs)

What is the difference between a process and a thread?
https://stackoverflow.com/a/2477945

面试高频题 Mutli-thread program 和 Multi-process program
https://www.youtube.com/watch?v=sv-9egZeLGE&t=8s

Note: in linux, base unit for scheduler is not thread, not heap, but task

Address space: address space is set of memory addresses that the process/thread can use without error

Access Modifier

public

1
2
3
public class Test{
// Test is accesable everywhere
}

private

1
2
3
private class Test {
// Test is only accesable within the class
}

protected

1
2
3
class Test {
// default is protected, which means only accesable in the same package
}

Nested Class

  • Test2 only be accessible within Test class, as helper class for Test
  • Test2 obj can access private variable in Test (ex. a)
1
2
3
4
5
6
7
class Test{
private int a = 0;

private class Test2{

}
}

non-static class cannot be referenced from a static context

  • TrieNode node = new TrieNode(); generates a compiling error
1
2
3
4
5
6
7
8
9
10
public class Trie
{
private class TrieNode{
...
}
...
public static void main(String[] args){
TrieNode node = new TrieNode(); // generates a compiling error
}
}
  • non-static nested class contains an implicit reference (Trie.TrieNode) to an instance of the parent class
  • hence, to instantiate TrieNode, an instance of Trie is also needed
  • but main is a static method, where it does not carry any object instance, hence complier complains

Solutions:

Explicitly create a Trie instance

1
2
3
4
5
6
7
8
9
10
public class Trie
{
private class TrieNode{
...
}
...
public static void main(String[] args){
TrieNode node = new Trie().new TrieNode();
}
}

OR changes TrieNode class to static:

1
2
3
4
5
6
7
8
9
10
public class Trie
{
private static class TrieNode{
...
}
...
public static void main(String[] args){
TrieNode node = new TrieNode();
}
}

ref: https://stackoverflow.com/questions/13373779/non-static-class-cannot-be-referenced-from-a-static-context

HashMap vs TreeMap vs LinkedHashMap

HashMap

  • $O(1)$ insert and lookup
  • arbitrary order
  • implemented by array of linkedlist

TreeMap

  • $O(log N)$ insert and lookup
  • sorted keys
  • implemented by Red-Black Tree (TreeNode contains key and value)

ex: https://leetcode.com/problems/hand-of-straights/description/

LinkedHashMap

  • $O(1)$ insert and lookup
  • sorted by insertion order
  • implemented by double-linked list + hashmap
  • hashmap’s value stores ListNode, (which contains key and val).

ex: https://leetcode.com/problems/lru-cache/description/

HashSet vs. TreeSet vs. LinkedHashSet

There are three common data strucutres implmented Hash Interface:

  • HashSet
    • implmented by hashtable
    • no order
    • $O(1)$ time complexity for add(), remove(), contains()
  • TreeSet
    • implmented by tree (red-blk tree, ex.)
    • maintain sorted order
    • $O(logn)$ time complexity for add(), remove(), contains()
  • LinkedHashSet
    • implmented as a hashtable with linkedlist
    • maintain insertion order
    • $O(N)$ worst case (rarely happened) time complexity for contains() and remove()
    • $O(1)$ for add(), insert to end of list

ref: https://www.programcreek.com/2013/03/hashset-vs-treeset-vs-linkedhashset/

Java Queue Null Element

  • adding null to Queue is not recommanded
  • use LinkedList implementation if really needed
  • PrioirtQueue and ArrayDeque not support adding null

Generic Classes

Generic Classes: A generic class declaration looks like a non-generic class declaration, except that the class name is followed by a type parameter section.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Box<T> { // Generic class Box, w/ type parameter <T>
private T t;

public void add(T t) {
this.t = t;
}

public T get() {
return t;
}

public static void main(String[] args) {
Box<Integer> integerBox = new Box<Integer>();
Box<String> stringBox = new Box<String>();

integerBox.add(new Integer(10));
stringBox.add(new String("Hello World"));

System.out.printf("Integer Value :%d\n\n", integerBox.get());
System.out.printf("String Value :%s\n", stringBox.get());
}
}

ref: https://www.tutorialspoint.com/java/java_generics.htm

Bounded Type Parameters:

  • restrict the kinds of types that are allowed to be passed to a type parameter
  • a method that operates on numbers might only want to accept instances of Number or its subclasses
  • To declare a bounded type parameter, list the type parameter’s name, followed by the extends keyword, followed by its upper bound.
1
2
3
public static <T extends Comparable<T>> T maximum(T x, T y, T z) { 
...
}

ref: https://www.tutorialspoint.com/java/java_generics.htm

Java class/interface dive deep

1
Queue<Integer> queue = new LinkedList<>();

We have queue data structure with LinkedList implememtation.

1
2
3
public interface Queue<E> extends Collection<E> {
...
}

Queue is an interface extends Collection, which is another interface. Collection extends Iterable interface. Hence, for Queue we have

1
Queue(Interface) --ext--> Collection(Interface) --ext--> Iterable (Interface)

LinkedList, its implementation class,

1
2
3
4
5
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
...
}

Here, extends means inheriet methods/variables of its parent class. implements is saying we are using LinkedList as data structure, to fill in all method signatures (empty shell) within the definition of the interface.

Similiarly:

1
2


instance variable vs class variable

Instance verible is tied to instance of class. Hence different instance has its own copy of instance varaible

1
2
3
public class Product {
public int Barcode;
}

A class variable is shared across all instance of that class. Use static as decleator for class variable.

1
2
3
public class Product {
public static int Barcode;
}

Default value in Java

Note: Local variables are declared mostly to do some calculation. So its the programmer’s decision to set the value of the variable and it should not take a default value. And instance/class varible use as property of object (it makes sense for instance of class to have default value, etc. Person.age = 0).

If the programmer, by mistake, did not initialize a local variable and it take default value, then the output could be some unexpected value. So in case of local variables, the compiler will ask the programmer to initialize with some value before they access the variable to avoid the usage of undefined values.
https://stackoverflow.com/a/415714

ref: https://softwareengineering.stackexchange.com/questions/293478/what-are-the-differences-between-class-variables-and-instance-variables-in-java

Override hashCode() in every class that overrides equals()

You must override hashCode() in every class that overrides equals(). Failure to do so will result in a violation of the general contract for Object.hashCode(), which will prevent your class from functioning properly in conjunction with all hash-based collections, including HashMap, HashSet, and Hashtable.

ref: https://stackoverflow.com/questions/2265503/why-do-i-need-to-override-the-equals-and-hashcode-methods-in-java

Bitwise Operators

  • & (bitwise and)
  • | (bitwise or)
  • ^ (bitwise XOR)
  • ~ (bitwise compliment)
  • << (left shift)
  • (arithmetic shift: right shift)

  • (logical shift: zero fill right shift)

ref: https://www.tutorialspoint.com/java/java_basic_operators.htm

Logs:

03/13/18: add static keyword for varible and method
03/13/18: fixed some typos
03/14/18: add this/super keyword
03/16/18: add difference between final, finally, and finalize
03/16/18: add Generics in Java
03/16/18: add GC in Java
03/29/18: add discussion about Queue API choices
04/19/18: add more string mannipulation regard to Character class
04/19/18: add more notes (Polymorphlism, Dynamic size array, Ways to read file, random num gen, class vs public class)
04/19/18: add int, long, etc
04/19/18: add random number, wirte to file
04/24/18: add enum data type
05/01/18: add enum comparsion
05/03/18: add JRE, JVM, JDK
05/30/18: update linkedhashmap
06/05/18: add java label
06/22/18: add Method Signatures, method reference, forEachRemaining(), Optional wrapper
07/05/18: add new ArrayList in one line
07/06/18: add Arrays.equals(a1, a2) vs a1.equals(a2)
08/08/18: add lambda slow run time
08/29/18: add HashSet vs. TreeSet vs. LinkedHashSet
09/14/18: add explaination for escaping character in regex section
09/25/18: add template for read/write file IO
11/26/18: add Generic Classes & Bounded Type Parameters
02/05/19: add instance vs class variable & note for default value in java
02/05/19: add Override hashCode() in every class that overrides equals()