Essential Coding Skills and Tricks in Java

Data Structure Operation

Array

Array is a consecutive allocated memory space, no overhead
It’s size is fixed.
它是mutable类型可以直接在原来位置进行CURD
Iterate an array from left to right
```
for (int i = 0; i < array.length; i++)
```

Iterate an array from right to left

for (int i = array.length - 1; i >= 0; i++)

Iterate an array custom step

for (int i = 0; i < array.length - 1; i+=k) // k is step

Convert a List to an array

int[] array = new int[size];
for (int i = 0; i < list.size(); i++) {
  array[i] = list.get(i);
}

One array && two loops, skip cur element

int[] array = {1,2,3};
int[] result = new int[array.length];
for (int i = 0; i < array.length; i++) {
  int sum = 0;
  for (int j = 0; j < array.length; j++) {
    if (i == j) {
      continue;
    }
    sum += i * j;
  }
  result[i] = sum;
}
//result = [5,8,9]

Convert an array in to a 2D array

/* [1,2,3,4,5,6,7,8]
    [[1,2,3,4],
     [5,6,7,8]] 
*/
r = 2;
c = 4;
for (int i = 0; i < r; i++) {
  for (int j = 0; j < c; j++) {
    board[i][j] = array[i * c + j];
  }
}

Print each character using loop

for (char c = 'a'; c <= 'z'; c++) {
  System.out.println(c);
}

Comparesion and Range of Array

Question laicode119
- Use the least number of comparisons to get the largest and smallest number in the given integer array. Return the largest number and the smallest number.
- Answer:
  - We can use 2 / n times swap to make sure that left half of array contain the largest num and right half contain the smallest num
  - [7, 4, 5, 6, 3, 9] –> swap(i, n - 1- i) –> [9, 4, 6, 5, 3, 7]
    - (0, (n -1) / 2) ; (n / 2, n - 1)
  - [7, 4, 5, 10, 6, 3, 9] –> swap(i, n - 1- i) –> [9, 4, 6, 10, 5, 3, 7]
    - (0, (n -1) / 2) ; (n / 2, n - 1) include middle value 10

/ and %

Example:
- 3 % 10 = 3, 3 / 10 = 0
- 12 % 10 = 2, 12 / 10 = 1
In 2D array: Given a index of element to find coresponding row and column
```
row = index / column;
column = index % column;
```

Convert digit number to single number

int num = 123;
while (num != 0) {
  int cur = num % 10;
  System.out.println(cur);
  num /= 10;
}

Implement adder

//plus one
//input: [9,9,9]
//output: [1,0,0,0]
public int[] plueOne(int[] input) {
  int carry = 1;
  for (int i = input.length - 1; i >= 0; i--) {
    int cur = input[i] + carry;
    carry = cur / 10;
    input[i] = cur % 10;
  }
  if (carry != 0) {
    int[] result = new int[input.length + 1];
    result[0] = carry;
    for (int i = 0; i < input.length - 1; i++) {
      result[i + 1] = input[i];
    }
    return result;
  }
  return input;
}

Slope

int slope = (y1 - y0) / (x1 - x0)
double slope = ()(y1 - y0) + 0.0) / (x1 - x0)

String

String 是一个object, it is immutable type in java. If we want to operate(CRUD) it, it must be a charArray
Convert to charArray

char[] array = string.toCharArray();

Linked List

It is a non-consecutive structure, overhead of multiple objects with the “next” reference
Using fast and slow pointer
- find middle of linked list
- find if linked list has a cycle
reverse linked list
dummy node

Tree

Tree Travseral
- Pre-order
- In-order
- Post-order

HashMap

hashMap是一个array形式的数组,每个index存

Guarantee the hashcode always be positive
```
key.hashCode() & 0x7FFFFFFF;
```

Generate a hashMap from a list or an array

HashMap<Character, Integer> map = new HashMap<>();
//Method 1 in Java 8
for (char cur : s.toCharArray()) {
  Integer count = map.getOrDefault(cur, 0);
  map.put(cur, count + 1)
}
  
//Method 2
for (char cur : s.toCharArray()) {
  Integer count = map.get(cur);
  if (count == null) {
    count = 1;
  } else {
    count++;
  }
  map.put(cur, count);
}

Iterate each of the key, value pairs in a hashMap

for (Map.Entry<K, V> entry : map.entrySet()) {
  entry.getValue();
  entry.getKey();
}

HashSet

Generate HashSet

Set<Character> set = new HashSet<>();
for (char cur : s.toCharArray()) {
  if (set.add(cur)) {
    System.out.println("adding new char to the set");
  } else {
    return false;
  }
}

Java Concepts

Object-Oriented-Design (OOD)

key words: class, object, reference, dereference, primitive type, class types, fields, constructor, stack, heap, final, static
pass by value;
- primitive type: copy of the value itself
- objects: copy of the object reference
array
- it is a object
- “length” is a field of the array object, it also is a final type
NullPointerException (NPE) vs. Empty
- NPE: deference to null, null is object
linked list vs. LinkedList
eager computation and lazy computation
Interface
- It has some abality
- Can’t be instantiate, should implements

Abstract class

Can’t be instantiate

Abstract class	Interface
It have abstract and non-abstract methods	has only abstact method
doesn’t support multiple inheritance	supports multiple inheritance
have final, non-final, static and non-static variables	has only static and final variables
have static methods, main method and constructor	can’t have static methods, main method or constructor
provide the implementation of interface	can’t provide the implementation of abstract class
abstract keyword is used to declare abstract class	interface keyword is used to declare interface

Good Practice:
- Declare into a general type, initialize into a concrete trap(Interface are also types)
Amortized Time Complexity
- ArrayList
- HashMap
ArrayList vs. LinkedList
- If we have a lot of random access operations, or always add/remove at the end, or time complexity is similar for using ArrayList and LinkedList, use ArrayList (overhead and locality)
Logical Operator Short Circuit