SDE实践

List

ListNode

class ListNode {
    public int value;  // any type
    public ListNode next;
    // public ListNode prev;
    public ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}

ListNode head = new ListNode(3);
head.next

image-20200118131650193

temp.next = temp.next.next // is okay what if: current.next = current.next.next // NullPointerException

Examples of Linked List Operations:

// length()  1 -> 2 -> 3 -> null
int length(ListNode head) {
    int length = 0;
    while (head != null) {
        length++;
        head = head.next;
    }
    // head == null
    return length;
}

/**
* get(index)
* 1 -> 2 -> 3 -> null
* index = 0 -> return 1
* index = 4 -> return null
*/
ListNode get(ListNode head, int index) {
    while (index > 0 && head != null) {
        head = head.next;
        index--;
    }
    // index <= 0 || head == null
    return head;
}

// appendHead()
ListNode appendHead(ListNode head, int value) {
    ListNode newHead = new ListNode(value);
    newHead.next = head;
    return newHead;
}

//appendTail()
ListNode appendTAil(ListNode head, int value) {
    // 1. head == null
    if (head == null) {
        return new ListNode(value);
    }
    // 2. head != null, find the last node in the list.
    ListNode prev = head;
    while (prev.next != null) {
        prev = prev.next;
    }
    // exit the while loop when prev.next == null
    prev.next = new ListNode(value);
    return head;
}

head could be changed - we need to return the new head if changed usually need to consider

• head == null
• head.next = null

while loop - we need to understand what is the terminate condition

List Interface

• An ordered collection (sometimes called a sequence).

• Lists can contain duplicate elements.

The user of a List generally has precise control over where in the list each element is inserted and can access elements by their index.

Provided functionalities(interfaces)

• Random Access: set(int index, E e) get(int index) add(int index, E e), add(E e) remove(int index)
• Search
• Iterator
• Range-View
• Other useful methods: isEmpty(); size();

Most popular implementation class: ArrayList, LinkedList.

Abstract class, interface

Both can have methods declared without implementation (abstract methods).

interface Dictionary {
	// index out of bound, it will return null.
	public Integer get(int index);
}

Dictionary myDict = new Dictionary(); // Wrong!

class Dictionarylmpl implements Dictionary {
	@Override
	public Integer get(int index) {
    }
}

//abstract class/Interface: you cannot instantiate an object by abstract class or interface

public int search(Dictionary dict, int target) {
    return dict.get(target);
}

interface A {
    public void print();
}

class B implements A {
    @Override
    public void printf() {
        System.out.println("B");
    }
}

Declare into a general type, initialize into a concrete type (Interfaces are also types):

List<Node> myList = new LinkedList<Node>();
myList.get(5);  // fine
myList.set(5,7);// fine
myList.poll();  // not fine

Preserve the general semantic of a List

• Can only use methods in a List interface
• Not to make any assumptions on implementation
• Make sure interchangeable in future

Provide concrete implementation by using LinkedList

• Choose the best implementation for the current use case

list: size() is O(1) time complexity because of eager computation

isEmpty() {
	return (size == 0);
}

节省代码量，同时使逻辑更清晰。

Comparison

Operation	ArrayList	LinkedList
get(int index) at head/tail	O(1)	O(1) - maintain both head and tail
get(int index) in middle	O(1)	O(n)
set(int index) at head/tail	O(1)	O(1)
set(int index) in middle	O(1)	O(n)
add(int index, E e) in middle	O(n)	O(n)
add(int index, E e) at head	O(n)	O(1)
add(E e) at tail	amortized: O(1)	O(1)
remove(int index) at head	O(n)	O(1)
remove(int index) at tail	O(1)	O(1)
remove(int index) at middle	O(n)	O(n)
size()	O(1)	O(1)
isEmpty()	O(1)	O(1)

When to choose what? ArrayList or LinkedList?

1. If you have a lot of random access operations, use ArrayList.

2. If you always add/remove at the end, use ArrayList

   • When the time complexity is similar for using ArrayList and LinkedList, use ArrayList. (ArrayList use memory more efficiently - For each element LinkedList need to create different ListNode in memory, there is extra cost of storing the "next", "prev" reference, and the allocation is not contiguous).
3. Stack and Vector class are not recommended, whenever you need a Vector, use ArrayList, whenever you need a Stack, use LinkedLIst.
   • E.g. reason: http://stackoverflow.com/questions/25922201/linkedlist-vs-stack

image-20200119125154342

ArrayList

ArrayList is regarded as a resizable array.

• maintain an array with potential unused cells
• will expand the array if there is no unused cells available
  • by replacing the maintained array with a new larger array (1.5 times larger by default)

class ArrayList<E> {
    private E[] array;  // the maintained array, the current maximum capacity is array.length
    private int size;  // the number of actually used cells in the maintained array
    // But, you don't have direct access to these internal implementation details.
    ……
}

get(int index): array[index]

set(int index, E e): array[index] = e

size(): // size means the number of used cells, not the capacity.

when call add(), remove(), size is modified as well

call add(11): array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, size = 10, capacity = 10 (array.length). call add(11):

1. check if it is full (size = capacity)
2. if it is full, create a new array1, array1's size= 1.5 * array's size, copy all the element in array to array1, and change the maintained array to array1. array1 = new Integer[size * 1.5] array1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, null, null, null, null, null} size = 10, capacity= 15 array = array1
3. set the 11th element's value to 11, size++. array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, null, null, null, null} size= 11, capacity= 15

call add(int index, E e):

1. expand if necessary

2. then right move all the elements after index by 1,

3. set the element at index.

Example: array= {1, 3, 4, 5, 6, null, null, null, null, null}, size = 5, capacity = 10 call add(1, 2) - add Integer 2 at index 1

1. do not need to expand since size < capacity

2. move all the elements of {3, 4, 5, 6} right by 1 position, size++ array= {1, 2, 3, 4, 5, 6, null, null, null, null}, size = 6, capacity = 10

3. set index 1 as Integer 2 array = {1, 2, 3, 4, 5, 6, null, null, null, null}

call remove(1): remove the element at index 1

1. check if index out of bound first.

2. move all the elements of {3, 4, 5, 6} left by 1 position, size--

LinkedList

backend by a doubly linked list, wrap the size, head and tail information.

class ListNode<E> {
    E e;
    private ListNode<E> prev;
    private ListNode<E> next;
}

class LinkedList<E> {
    private ListNode<E> head;
    private ListNode<E> tail;
    private size;
}

public E get(int index) {
    // traverse from head and find the node at index.
}

get(int index) - from the head/tail, traverse the list to get the element at index

set(int index, E e) - from the head/tail, traverse the list to the get the element at index, and change it

add(int index, E e), add(E e)

• at tail - append new node after tail and update tail to the new added node
• at head - insert in front of the head, and update head to the new added node
• at middle

remove(int index)

• at head - update the head to head.next
• at tail - update the tail to tail.prev
• at middle · from head/tail, traverse the list to get the element at index, and remove it.

size() - O(1) - eager computation.

isEmpty()

Something about coding

null & empty collections, array

int[] array = null;
int[] array = new int[O];  // can contain 0 element. is okay!

ArrayList<lnteger> list = null;
ArrayList<lnteger> list = new ArrayList<Integer>();

They are DIFFERENT!

null - there is no array object associated with the reference empty array/list - there is an array/list object, but the array/list object does not contain any element, yet (length/size == 0).

Example

// 1 
ArrayList<Integer> list = null;

if (list.isEmpty()) { // NullPointerException
    System.out.println(list.size());
}
System.out.println(list.get(0));
                       
// 2
ArrayList<Integer> list = new ArrayList<Integer>();
if (list.isEmpty()) {
	System.out.println(list.size());
}
System.out.println(list.get(0)); // ArraylndexOutOfBoundException
                       
// 3
int[] array = null;
System.out.println(array[0]); // NullPointerException

// 4
int[] array = new int[0];
System.out.println(array[0]); // ArraylndexOutOfBoundException

Check corner cases & boundary conditions if (array.length == 0 || array == null) X NullPointerException if (array == null || array.length == 0) Remember: always do null check before any ofher checks. The logic expressions are evaluated from left to right (short circuit)

The things to keep in mind

• Check null - check at very first place
• Check length/size/head == null/head.next == null/other initial check conditions.
• Check index out of bound/NullPointer (even inside the for/while loop)
  • keep in mind any index can not be out of range(< 0 ll >= array.length).
  • keep in mind some ListNode reference might be null.
• What is the termination condition of for/while loop Make some concrete examples to determine if the logic is correct.

About dummy node It is not a must, but can make your life much easier, there are several suitable conditions using dummy will be very handy.

• the head could be changed when solving the problem

Example - insert a value into a sorted list 1-> 3 -> 5

insert 4

dummy -> 0 -> 1 -> 3 -> 5. prev while (prev.next != null && prev.next.val < val){ prev = prev.next; }

1). With dummy node's help

public ListNode insert(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode newNode = new ListNode(val);
    ListNode curr = dummy.next, prev = dummy;
    while (curr != null && curr.val < val) {
        prev = curr;
        curr = curr.next;
    }
    prev.next = newNode;
    newNode.next = curr;
    return dummy.next;
}

2). Without dummy node's help

public ListNode insert(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    // check head.
    if (head == null || val <= head.val) {
        newNode.next = head;
        return newNode;
    }
    // the inserted node is not the new head.
    ListNode cur = head;
    // find first node >= val     cur, cur.next
    while (cur.next != null && cur.next.val < val) {
        cur = cur.next;
    }
    // cur.next == null || cur.next.val >= val
    newNode.next = cur.next;
    cur.next = newNode;
    return head;
}

• not sure yet which node will be head when constructing the list

3 -> 5

4 -> 6

dummy -> 1 -> 2 -> ……

Example - merge two sorted list

1). With dummy node's help

public ListNode merge(ListNode h1, ListNode h2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (h1 != null && h2 != null) {
        if (h1.value <= h2.value) {
            curr.next = h1;
            h1 = h1.next;
        } else {
            curr.next = h2;
            h2 = h2.next;
        }
        curr = curr.next;
    }
    
    if (h1 != null) {
        curr.next = h1;
    }
    if (h2 != null) {
        curr.next = h2;
    }
    return dummy.next;
}

2). Without dummy node's help

public ListNode merge(ListNode h1, ListNode h2) {
    if (h1 == null) {
        return h2;
    }
    if (h2 == null) {
        return h1;
    }
    ListNode head = null;
    if (h1.val <= h2.val) {
        head = h1;
        h1 = h1.next;
    } else {
        head = h2;
        h2 = h2.next;
    }
    ListNode curr = head;
    while (h1 != null && h2 != null) {
        if (h1.value <= h2.value) {
            curr.next = h1;
            h1 = h1.next;
        } else {
            curr.next = h2;
            h2 = h2.next;
        }
        curr = curr.next;
    }
    
    if (h1 != null) {
        curr.next = h1;
    }
    if (h2 != null) {
        curr.next = h2;
    }
    return head;
}

Tips: 尽量不使用global variable

image-20200119190001164

Queue & Stack & Deque

In Java In Java, we usually refer it to Queue and Deque interface. A collection to hold multiple elements prior to processing. Contains a buffer and specifies a mechanism to choose which is the next element to process.

• Queue - FIFO (exception: PriorityQueue) http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

  • offer() - offer at the tail

  • poll()- poll at the head

  • peek() - look at the head without polling it out

• Deque - FIFO & LIFO (both queue and stack) http://docs.oracle.com/javase/7/docs/api/java/util/Deque.html
  • provide both offer at head/tail, poll at head/tail, and peek at head/tail
  • so it can be used as a queue, or a stack.

Common APIs

image-20200119190313790

1. Use the same set of APIs
2. What's the point: java Queue中 add/offer，element/peek，remove/poll区别

image-20200119191230171

Other useful methods:

• isEmpty();
• size();

All the operations' cost is O(1). Most popular implementation class: LinkedList, ArrayDeque(Java 6 onwards).

When you need a queue or stack, you can just use LinkedList, as it implements both Queue and Deque interfaces. (Do not use Stack class. )

ArrayDeque: no null values in deque.

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) {

        // head(first) -> {1, 2, 3} <- tail(last)
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        while (!queue.isEmpty()) {
            System.out.println(queue.peek());
            System.out.println(queue.poll());
        }
        System.out.println(queue.peek());
        System.out.println(queue.poll());

        /**
         * If you are using deque as stack, you can choose the group of methods:
         * offerFirst() - push()
         * pollFirst() - pop()
         * peekFirst() - peek()
         */
        // head(first) -> {3, 2, 1} <- tail(last)
        Deque<Integer> stack = new LinkedList<>();
        stack.offerFirst(1);
        stack.offerFirst(2);
        stack.offerFirst(3);
        while (!stack.isEmpty()) {
            System.out.println(stack.peekFirst());
            System.out.println(stack.pollFirst());
        }
        System.out.println(stack.peekFirst());
        System.out.println(stack.pollFirst());

        // head(first) -> {3, 2, 1, 4, 5, 6} <- tail(last)
        // 3, 6, 2, 5, 1, 4, null, null, null, null
        Deque<Integer> deque = new LinkedList<>();
        deque.offerFirst(1);
        deque.offerFirst(2);
        deque.offerFirst(3);
        deque.offerLast(4);
        deque.offerLast(5);
        deque.offerLast(6);
        int size = deque.size();
        for (int i = 0; i < size; i++) {
            if (i % 2 == 0) {
                System.out.println(deque.peekFirst());
                System.out.println(deque.pollFirst());
            } else {
                System.out.println(deque.peekLast());
                System.out.println(deque.pollLast());
            }
        }
        System.out.println(deque.peekFirst());
        System.out.println(deque.pollFirst());
        System.out.println(deque.peekLast());
        System.out.println(deque.pollLast());
    }
}

Our Own Implementation Stack, Queue and Deque are not premier data structures, their implementation depend on other data structures - what could be the candidates? - sequence type(线性的)

In general, two ways:

• use array

• use Linked list

Let's see how to use Linked List to do so. Usually, when we use Linked List, we might want to determine

• singly linked list?
• doubly linked list?

Stack implemented by Linked List

class ListNode {
    int value;
    ListNode next;
    public ListNode(int value) {
        this.value = value;
    }
}

public class Stack {
    private ListNode head;
    public Stack() {
        head = null;
    }

    public void push(Integer value) {
        ListNode newNode = new ListNode(value);
        newNode.next = head;
        head = newNode;
    }

    public Integer pop() {
        if (head == null) {
            return null;
        }
        ListNode temp = head;
        head = head.next;
        temp.next = null;  // 好习惯，可省略
        return temp.value;
    }

    public Integer peek() {
        if (head == null) {
            return null;
        }
        return head.value;
    }
}

Queue implemented by Linked List

public class Queue {
    ListNode head;
    ListNode tail;
    public Queue() {
        head = tail = null;
    }

    public void offer(Integer ele) {
        if (head == null) {
            head = new ListNode(ele);
            tail = head;
        } else {
            tail.next = new ListNode(ele);
            tail = tail.next;
        }
    }
    public Integer poll() {
        if (head == null) {
            return null;
        }
        ListNode node = head;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        node.next = null;
        return node.value;
    }

    public Integer peek() {
        if (head == null) {
            return null;
        }
        return head.value;
    }
}

Queue implemented by array

Let's make a simpler case first, assume the capacity of the queue is bounded.

First, we need to maintain the position of head and tail - use two pointers.

offer = put one element, tail++ (tail points to the next available position) poll = grab element at head, head++ (head points to the next element in queue)

What is the problem here? what if tail == array.length - 1 and we need to do tail++?

Circular Array - we can connect the start and end of the array, so that it is a cycle. index of array.length <=> index of 0

Quick tip: head = head + 1 == array.length ? 0 : head + 1; // (head + 1) % array.length;

Second, we need to know when empty, when full. head == tail -> empty head == tail -> full two solutions:

1. record size, size = 0 (empty), size == array.length (full)
2. head + 1 == tail -> empty, head == tail -> full, capacity =array.length- 1(next of head points to the head of the queue)

public class BoundedQueue {
    int head;
    int tail;
    int size;
    Integer[] array;
    public BoundedQueue(int cap) {
        array = new Integer[cap];
        head = tail = 0;
        size = 0;
    }

    public boolean offer(Integer ele) {
        // 1.
        if (size == array.length) {
            return false;
        }
        // 2.
        array[tail] = ele;
        tail = tail + 1 == array.length ? 0 : tail + 1;
        size++;
        return true;
    }

    public Integer poll() {
        if (size == 0) {
            return null;
        }
        Integer result = array[head];
        head = head + 1 == array.length ? 0 : head + 1;
        size--;
        return result;
    }

    public Integer peek() {
        if (size == 0) {
            return null;
        }
        return array[head];
    }
}

Stack implemented by array

public class BoundedStack {
    int[] array;
    int head;
    public BoundedStack(int cap) {
        // check cap
        array = new int[cap];
        head = -1;
    }

    public boolean push(int ele) {
        if (head == array.length - 1) {
            return false;
        }
        array[++head] = ele;
        return true;
    }

    public Integer pop() {
        return head == -1 ?null : array[head--];
    }

    public Integer top() {
        return head == -1 ? null : array[head];
    }
}

Exercise We have done Queue and Stack, how about Deque?

• Use Linked List
  • can we still use singly linked list or we need doubly linked list?
• Use Circular Array

PriorityQueue

It is a heap with the same Queue interface with offer(), peek(), poll(). But, it is not FIFO, when poll() or peek() we always look at the smallest/largest element (min heap/max heap).

The PriorityQueue will arrange the elements based on the order of the elements (who is smaller/larger by comparing any two of them) and it is optimized for problems about "who is the smallest/largest element'.

Internally it is implemented using an array.

• offer(E e) - insert one element into the heap
• peek() - peek the top element in the heap (smallest/largest based on how to order the elements)
• poll() - remove the top element from the heap, and return it (smallest/largest based on how to order the elements)
• size()
• isEmpty()

time complexity:

• offer(E e) - O(log n)
• peek() - O(1)
• poll() - O(log n)
• remove() - O(log n), from AbstractQueue, remove(Object) - O(n) 删除任意一个元素
• size()- O(1)
• isEmpty · O(1)

Order - The PriorityQueue need to know how to compare the elements and determine which one is smaller/larger.

There are two ways to do so: The element type implementing Comparable interface

Example:

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
minHeap.offer(4);
minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(3);
minHeap.offer(1);
while (!minHeap.isEmpty()) {
    System.out. println(minHeap.poll());
}

How does the priorityqueue know how to compare the Integer objects?

The element's class can implement Comparable interface and thus implement the required method compare To(), PriorityQueue will use this method to compare any two elements.

interface Comparable<E> {
    int compareTo(E ele);
}

// part of the Integer class implementation
class Integer implements Comparable<Integer> {
    private int value;
    
    public Interger(int value) {
        this.value = value;
    }
    
    @Override
    public int compareTo(Interger another) {
        if (this.value == another.value) {
            return 0;
        }
        return this.value < another.value ? -1 : 1;
    }
}

The return value of compareTo(another) method determines the order of this and another: 0 - this and another are of the same priority -1 (< 0) - this has higher priority than another 1 (> 0) - this has less priority than another

Another Example using custom class: Suppose you have an integer matrix, each row is sorted by ascending order and each column is also sorted by ascending order, we need a class to representing each cell in the matrix, and we need to compare two cells with their value in the matrix.

class Cell implements Comparable<Cell> {
    public int row;
    public int col;
    public int value;
    public Cell(int row, int col, int value) {
        this.row = row;
        this.col = col;
        this.value = value;
    }

    @Override
    public int compareTo(Cell another) {
        if (this.value == another.value) {
            return 0;
        }
        return this.value < another.value ? -1 : 1;
    }
}

// We want to have a minHeap by the value of the Cell elements.
PriorityQueue<Cell> minHeap = new PriorityQueue<Cell>();
Cell c1 = new Cell(0, 0, 0);
Cell c2 = new Cell(0, 1, 2);
minHeap.offer(c1);
minHeap.offer(c2);
int result = c1.comparedTo(c2);
System.out.println(result);

Provide an extra Comparator object to compare the elements There is another interface Comparator, it is used to compare two elements with same type E.

interface Comparator<E> {
	int compare(E o1, E o2); 
}

import java.util.Comparator;

class Cell {
    public int row;
    public int col;
    public int value;
    public Cell(int row, int col, int value) {
        this.row = row;
        this.col = col;
        this.value = value;
    }
}

class MyComparator implements Comparator<Cell> {
    @Override
    public int compare(Cell c1, Cell c2) {
        if (c1.value == c2.value) {
            return 0;
        }
        return c1.value < c2.value ? -1 : 1;
    }
}

PriorityQueue<Cell> minHeap = new PriorityQueue<>(11, new MyComparator());
Cell c1 = new Cell(0, 0, 0);
Cell c2 = new Cell(0, 1, 2);
minHeap.offer(c1);
minHeap.offer(c2);
System.out.println(minHeap.size());
System.out.println(minHeap.poll().value);
System.out.println(minHeap.size());

If class E already implements Comparable interface, and we need another way of ordering the elements in our PriorityQueue, we can pass the new Comparator.

// I want a max heap here...
// So I need to provide a new Comparator, the ordering defined by the Comparator is the reversed natural order provided by Integer class
import java.util.Comparator;
public class Main {

    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap =
                new PriorityQueue<>(16, new ReverseComparator());
        maxHeap.offer(4);
        maxHeap.offer(2);
        maxHeap.offer(5);
        maxHeap.offer(3);
        maxHeap.offer(1);
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }
    }
}

class ReverseComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer i1, Integer i2) {
        if (i1.equals(i2)) {
            return 0;
        }
        return i1 < i2 ? 1 : -1;
    }
}

Or, there is a utility method Collections.reverseOrder(), it will return a comparator that reverses the natural order.

equals() method of a comparator: if the incoming comparator equals the current comparator, not about orders!

Conclusion: To make PriorityQueue work, there are two ways:

1. The element class E implements Comparable interface
2. Provide a Comparator< E > class to compare elements. and pass an comparator object to the PriorityQueue.

if E already implements Comparable< E >, but still you provide a Comparator, PriorityQueue will choose the order specified in Comparator.

Most frequently used constructors of PriorityQueue 1. PriorityQueue<Cell> heap = new PriorityQueue<Cell>(); initialize the internal array with default capacity(11) class Cell must implements Comparable<Cell> ! 2. PriorityQueue<Cell> heap = new PriorityQueue<Cell>(16); initialize the internal array with specified capacity(16) class Cell implements Comparable<Cell> ! 3. PriorityQueue<Cell> heap = new PriorityQueue<Cell>(16, new MyComparator(); initialize the internal array with specified capacity(16) class MyComparator implements Comparator<Cell> !

Be Careful the initial capacity has to be > 0: // if k <= 0, IllegalArgumentException will be thrown in the constructor. PriorityQueue<Cell> minHeap = new PriorityQueue<Cell>(k, new MyComparator();

Method 1 and 2, the object inside the PQ should be comparable! Otherwise, Java will throw runtime exception (it will cast anything inside into a Comparable to do the comparison).

heapify() - convert an array to heap in O(n) time ArrayList list = new ArrayList(); PriorityQueue heap = new PriorityQueue(list);

• initialize the internal array with heapify() internally

• class Cell implements Comparable !

it is not exposed to outside from PriorityQueue class, it is a private method. the only way to utilize the heapify() is to use the constructor

// Part of the PriorityQueue implementation……
class PriorityQueue<E> {
    private E[] heapArray;
    private int size;
    
    public PriorityQueue(Collection<? extends E> c) {
        heapArray = c.toArray();
        size = heapArray.length;
        heapify(); // the only place heapify is called.
    }
    private void heapify() {
        // heapify the heapArray.
        for (int i = size / 2 - 1; i >= 0; i--) {
            percolateDown(i);
        }
    }
}

Nested class: define a class within a class. Static nested class vs. non-static nested class: belong to class, or belong to instance. Anonymous class: nested class with no name. Often replaceable by lambda expressions in Java8.

Something about coding: nested classes Nested class: A class within another class. Why? (Official tutorial)

• It is a way of logically grouping classes that are only used in one place: If a class is useful to only one other class, then it is logical to embed it in that class and keep the two together. Nesting such "helper classes" makes their package more streamlined.
• It increases encapsulation: Consider two top-level classes, A and B, where B needs access to members of A that would otherwise be declared private. By hiding class B within class A, A's members can be declared private and B can access them. In addition, B itself can be hidden from the outside world.
• It can lead to more readable and maintainable code: Nesting small classes within top-level classes places the code closer to where it is used.

Static nested class: a nested class associated with the outside class. Can access class variables and methods. Inner class: a nested class associated with an instance of the class. Can access instance variables and methods. Anonymous inner class (defined in a method with just new and no definition)

PriorityQueue<Cell> pQueue = new PriorityQueue<>(16, new Comparator<Cell>() {
    @Override
    public int compare(Cell o1, Cell o2) {
        if (o1.value == o2.value) {
            return 0;
        }
        return o1.value < o2.value ? -1 : 1;
    }
});

Heap

Implement PriorityQueue (Heap) Definition

• Heap is a (binary) tree based data structure
• Across the entire tree, the relation between a parent node and a child node stays consistent.
  • Example: min heap
    1. the parent node is always <= its two child nodes (parent node is the smallest node in the subtree rooted at itself).
    2. the relation between the two child nodes can differ.
• The common implementation of a heap is using a complete binary tree. * A "complete binary tree" is a binary tree in which every level, except possibly the last level, is completely filled, and all nodes are as far left as possible.

image-20200121202717092

image-20200121202754707

Representation

• it can also be represented as an array (by the level order traversal of the binary tree), since it is a complete binary tree.

  • Why? - if it is a complete binary tree, the matching between the nodes and the index of the array is determined, and the relation of parent and child nodes can be well transferred to the relation between two indices.

• Example:

  • index of parent = i, what is the index of the two child nodes?

    • left child of index i = 2 * i + 1

    • right child of index i = 2 * i + 2

    • parent of index i = (i - 1) / 2

  • the root of the tree is at index 0.

Basic Heap Internal Operations

percolateUp()

• when to use?
  • the element need to be moved up to maintain the heap's property, for example, when offering a new element into the heap.
• how?
  • compare the element with its parent, move it up when necessary. do this until the element does not need to be moved.

percolateDown()

• when to use?
  • the element need to be moved down to maintain the heap's property, for example, when poll the root element from the heap.
• how?
  • compare the element with its two children, if the smallest one of the two children is smaller than the element, swap the element with that child. do this until the element does not need to be moved.

Heapify()

• convert an array into a heap in O(n) time.(percolateDown)
• how?
  • for each node that has at least one child, we perform percolateDown() action, in the order of from the nodes on the deepest level to the root.(从底向上，从右向左)
  • the time complexity of heapify() is O(n)

image-20200122143516838

​ {10, 11, 7, 2, 8, 4, 6, 13, 3}

all the red nodes are the nodes has at least one child. perform percolateDown() on each of them following the order: 2, 7, 11, 10:

image-20200122143731581

if the heap has n elements, n = 9 : range [0, 3] n = 8 : range [0, 3] n = 7 : range [0, 2] .... the range of indices need to perform percolateDown() is: [0, n / 2 - 1] last index's parent = ((n - 1) - 1) / 2 = (n - 2) / 2 = n / 2 - 1

image-20200122144437341

update()

• if you know the position of the element you want to update, it will take O(logn).
• how?
  • either you need percolateUp(), or percolateDown() on that element.
• what if you do not know the position of the element?
  • you need to find the position of the element first, if not asking for help with other additional data structures, this operation is O(n)

image-20200122144847244

image-20200122144914975

Time Complexity: percolateUp() - O(height) == O(logn) percolateDown() - O(height) == O(logn)

Key points

1. child index -> parent index

• parent = (child - 1) / 2

2. parent index -> children index

• left child = parent * 2 + 1
• right child = parent * 2 + 2

3. basic internal operations of heap:

• percolateUp(int index)
  • offer()
  • update()
• percolateDown(int index)
  • poll()
  • update()
  • heapify()

Sorting algorithms (and heap)

int[] array = {4, 5, 0, 1, 2, 3}
Arrays.sort(array); // quicksort.
Integer[] array;
Arrays.sort(array); // mergesort.

quicksort:

1. wоrѕt саѕе О(n^2), аvеrаgе О(nlоgn), ѕрасе wоrѕt саѕе О(n), аvеrаgе О(lоgn)
2. unstable sort

mergesort:

1. worst case O(nlogn), average O(nlogn), space worst case/average O(n)
2. stable sort

Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.

Why object sorting needs to be stable? Example: sorting by scores, then by gender.

two male students m1 and m2, if m1's score is higher than m2, then after the sort the order is preserved.

https://www.youtube.com/watch?v=ZZuD6iUe3Pc

Sorting algorithm: time O(nlogn), space O(1) ? heapSort (not stable):

1. heapify the input array to maxHeap. - O(n)
2. n times poll operation. - O(nlogn)

image-20200122150620960

// max heap
private void percolateDown(int index) {
    // check if index is legal?
    while (index <= (size - 2) / 2) {
        int leftChildIndex = index * 2 + 1;
        int rightChildIndex = index * 2 + 2;
        int swapCandidate = leftChildIndex; // biggest one among left child and right child
        // update swapCandidate if right child exists and it is bigger than left child
        if (rightChildIndex <= size - 1 && array[leftChildIndex] <= array[rightChildIndex]) {
            swapCandidate = rightChildIndex;
        }
        // swap if necessary
        if (array[index] < array[swapCandidate]) {
            swap(array, index, swapCandidate);
        } else {
            break;
        }
        index = swapCandidate;
    }
}

count sort/bucket sort/radix sort/rainbow sort

Heap Implementation

import java.util.NoSuchElementException;

/**
 * An example implementation of capacity limited min heap containing only int values
 * with the capability to do update and poll at a specific index.
 *
 * This is for demonstration of percolateUp/percolateDown methods and
 * how to utilize these methods to do basic heap operations.
 *
 * The public methods provided are:
 * size()
 * isEmpty()
 * isFull()
 * peek()
 * poll()
 * offer()
 * update(int index, int value) - update the element at index to a given new value
 *
 */

public class MinHeap {
    private int[] array;
    private int size;

    public MinHeap(int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("input array cannot be null or empty");
        }
        this.array = array;
        size = array.length;
        heapify();
    }

    private void heapify() {
        for (int i = size / 2 - 1; i >= 0; i--) {
            percolateDown(i);
        }
    }

    public MinHeap(int cap) {
        if (cap <= 0) {
            throw new IllegalArgumentException("capacity cannot be <= 0");
        }
        array = new int[cap];
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == array.length;
    }

    private void percolateUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (array[parentIndex] > array[index]) {
                swap(array, parentIndex, index);
            } else {
                break;
            }
            index = parentIndex;
        }
    }

    private void percolateDown(int index) {
        // check if index is legal?
        while (index <= (size - 2) / 2) {
            int leftChildIndex = index * 2 + 1;
            int rightChildIndex = index * 2 + 2;
            int swapCandidate = leftChildIndex; // smallest one among left child and right child
            // update swapCandidate if right child exists and it is smaller than left child
            if (rightChildIndex <= size - 1 && array[leftChildIndex] >= array[rightChildIndex]) {
                swapCandidate = rightChildIndex;
            }
            // swap if necessary
            if (array[index] > array[swapCandidate]) {
                swap(array, index, swapCandidate);
            } else {
                break;
            }
            index = swapCandidate;
        }
    }

    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public int peek() {
        if (size == 0) {
            return -1;
        }
        return array[0];
    }

    public int poll() {
        if (size == 0) {
            throw new NoSuchElementException("heap is empty");
        }
        int result = array[0];
        array[0] = array[size - 1];
        size--;
        percolateDown(0);
        return result;
    }

    public void offer(int ele) {
        if (size == array.length) {
            int[] newArray = new int[(int)Math.round(array.length * 1.5)];
            //copy(array, newArray);
            for (int i = 0; i < array.length; i++) {
                newArray[i] = array[i];
            }
            array = newArray;
        }
        array[size] = ele;
        size++;
        percolateUp(size - 1);
    }

    // return the original value.
    public int update(int index, int ele) {
        if (index < 0 || index > size - 1) {
            throw new ArrayIndexOutOfBoundsException("invalid index range");
        }
        int result = array[index];
        array[index] = ele;
        if (result > ele) {
            percolateUp(index);
        } else {
            percolateDown(index);
        }
        return result;
    }
}

Extensions:

• How to make it capacity unbounded?
  • when size++ && is Full, need to allocate a new larger array.
• How to pass in a Comparator and use the Comparator to compare and determine the priority of different elements.
  • whenever you need to compare two elements

Tree

Tree nodes

class TreeNode {
    int key;
    TreeNode left;
    TreeNode right;
    // TreeNode parent;
    // We can store parent reference as well, this will be useful for solving some problems.
    public TreeNode(int key) {
        this.key = key;
    }
}

Usually, we use the root to represent the binary tree.

General Tree, each node can have arbitrary number of children.

image-20200122185120370

class TreeNode {
    int key;
    List<TreeNode> children;
    // TreeNode parent;
    public TreeNode(int key) {
        this.key = key;
        children = new ArrayList<TreeNode>();
    }
}

Tree is special kind of Graph:

class GraphNode {
    int key;
    List<GraphNode> neightbors;
    public GraphNode(int key) {
        this.key = key;
        neighbors = new ArrayList<GraphNode>();
    }
}

Other representation: Adjacency list Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.

When coding, you can use integers to represent vertex. In this way, a graph can be represented as:

List<List< Integer >> graph = ...

graph.get(1) -> Node 1's neighbors graph.get(2) -> Node 2's neighbors .... graph.get( i ) -> Node i's neighbors for (Integer i : graph.get(1)) { // i is a neighbor of node 1 }

LinkedList is a special kind of Tree (if there is only one child for each of the node in the binary tree, it can be reduced to a linked list)

Binary Search Tree

is a binary tree maintains the following property: for any of the nodes in the binary tree, all the nodes in its right subtree is larger than itself, all the nodes in its left subtree is smaller than itself (compared by the key stored in each of the nodes).

image-20200122190629893

Basic Operations of Binary Search Tree

search() - worst case O(n), average O(logn) insert() - worst case O(n), average O(logn) remove() - worst case O(n), average O(logn)

Balanced Binary Search Tree

search(), insert(), remove() operations are all guaranteed to be O(logn). Eg. AVL Tree, Red-Black Tree, etc.

Red-Black tree

• in Java: TreeMap/TreeSet
• in C++: map/set.

We are not going to implement balanced binary search tree, instead we are more interested in basic implementation.

Traversals of Binary Tree

preorder - root, left sub, right sub inorder - left sub, root, right sub postorder - left sub, right sub, root

Like LinkedList, General ways of solving problems about binary (search) tree: Recursion divide and conquer is nature of binary tree - binary tree can be easily divided into three parts

• solve problem for left/right subtree
• solve the problem for root.

Iterative

• could be complicated for binary tree but we need to know how.

Level order traversal: Try to build one for your LaiCode test cases.

Search in BST

// recursive 
public TreeNode search(TreeNode root, int target) {
    // 1. process root
    if (root == null || root.key == target) { // terminate condition
        return root;
    }
    // 2. check left node if target less than root.key
    if (target < root.key) {
        return search(root.left, target); // break point
    } else {
        return search(root.right, target);
    }
}

Tail Recursion The recursive call is always the last execution statement. We can easily transfer the tail recursive to iterative solution.

image-20200122195648939

Not a tail recursion:

... return isBst(root.left, ...) && isBst(root.right, ...)

// iterative
public TreeNode search(TreeNode root, int target) {
    TreeNode currentNode = root;
    while (currentNode != null && currentNode.key != target) { // terminate condition
        if (target < currentNode) {
            currentNode = currentNode.left;
        } else {
            currentNode = currentNode.right;
        }
    }
    // exit while loop: currentNode = null || currentNode.key = target
    return currentNode;
}

Insert in BST

image-20200122210638563

Recursion I A very common way when the tree structure could be changed, in this case, we return the new root after the change (remind about the same case of Linked List? ).

public TreeNode insert(TreeNode root, int key) {
    if (root == null) {
        TreeNode newRoot = new TreeNode(key);
        return newRoot;
    }
    if (root.key < key) {
        root.right = insert(root.right, key);
    } else if (root.key > key) {
        root.left = insert(root.left, key);
    }
    return root;
}

Recursion II (Remove redundant operation)

public TreeNode insert(TreeNode root, int target) {
    if (root == null) {
        return new TreeNode(target);
    }
    helper(root, target);
    return root;
}

public void helper(TreeNode root, int target) {
    if (target == root.key) {
        return;
    } else if (target < root.key) {
        if (root.left == null) {
            root.left = new TreeNode(target);
        } else {
            helper(root.left, target);
        }
    } else {
        if (root.right == null) {
            root.right = new TreeNode(target);
        } else {
            helper(root.right, target);
        }
    }
}

1. (target == root.key) return; // terminate

2. target < root.key:

   • root.left == null; root.left = new TreeNode(target); // terminate
   • else: helper(root.left, target);
3. target > root.key:
   • root.right == null; root.right = new TreeNode(target); //terminate
   • else: helper(root.right, target);

第二种只做了一次赋值，第一种做了多次赋值，但第一种对以后的问题有启发。

Iterative I

public TreeNode insert(TreeNode root, int target) {
    TreeNode newNode = new TreeNode(target);
    if (root == null) {
        return newNode;
    }
    TreeNode current = root;
    while (current.key != target) {
        if (current.key > target) {
            if (current.left != null) {
                current = current.left;
            } else {
                current.left = newNode;
                break;
            }
        } else {
            if (current.right != null) {
                current = current.right;
            } else {
                current.right = newNode;
                break;
            }
        }
    }
    return root;
}

Iterative II

public TreeNode insert(TreeNode root, int target) {
    if (root == null) {
        return new TreeNode(target);
    }
    TreeNode returnRoot = root;
    TreeNode pre = null;
    while (root != null) {
        pre = root;
        if (root.key < target) {
            root = root.right;
        } else if (root.key > target) {
            root = root.left;
        } else {
            return returnRoot;
        }
    }
    if (pre.target < target) {
        pre.right = new TreeNode(target);
    } else if (pre.target > target) {
        pre.left = new TreeNode(target);
    }
    return returnRoot;
}

Delete in BST

delete(root, 8) step one: find the node to be deleted - trivial? step two: delete it ... - not trivial? how many possible situations?

image-20200122213854361

image-20200122213935139

image-20200123111451639

image-20200123111633573

// return: the node that replace target
public TreeNode delete(TreeNode root, int target) {
    if (root == null) {
        return null;
    }
    // find target node
    if (root.val > target) {
        root.left = delete(root.left, target);
        return root
    } else if (root.val < target) {
        root.right = delete(root.right, target);
        return root;
    }
    // guarantee root != null && root.val == target
    if (root.left == null) {  // case 1, 2
        return root.right;
    } else if (root.right == null) {  // case 3
        return root.left;
    }
    
    // guarentee root.left != null && root.right != null
    // 4.1
    if (root.right.left == null) {
        root.right.left = root.left;
        return root.right;
    }
    //4.2
    // 1. find and delete smallest node in root.right.
    TreeNode smallest = deleteSmallest(root.right);
    // 2. connect the smallest node with root.left and root.right.
    smallest.left = root.left;
    smallest.right = root.right;
    // 3. return the smallest node.
    return smallest;
}

private TreeNode deleteSmallest(TreeNode cur) {
    TreeNode prev = cur;
    cur = cur.left;
    while (cur.left != null) {
        prev = cur;
        cur = cur.left;
    }
    // cur is the smallest one, and prev is its parent.
    // invariance: cur (prev.left) does not have left child
    prev.left = prev.left.right;
    return cur;
}

Binary Tree Traversals (iteratively)

Too easy to use recursion to solve the traversal problem.

public void inorder(TreeNode root) {
    if (root == null) {
        return;
    }
    inorder(root.left);
	System.out.println(root.key);
	inorder(root.right);
}

Why do we need the Iterative solution? since we already have the simple, elegant recursive solution.

Recall here for Java memory areas:

• STACK: storing the local variables and other information for each of the method calls
• HEAP: allocating spaces for dynamically created objects

How recursion works

public void print(int x) {
    if (x <= 0) {
        return;
    }
    print(x-1); // bp
    System.out.println(x);
    //return;
}

print(10)
   
/**
* 1
* 2
* 3
* 4
* 5
* 7
* 8
* 9
* 10
*/

The unfinished methods must be retained in STACK before it can return: when we call print(10), what will happen?

STACK: tail -> { } <- head

Does recursion consume extra spaces? - YES, the method calls use spaces on STACK. Think about calling print(1000000) now, what will happen?

The space consumed on STACK: O(# of method call levels).

In Java, STACK is usually a size limited memory area. By default, a several thousands levels recursion call would easily eat up all the space and throw StackOverFlowException - this is something you have to keep in mind(especially when the solution is in recursive way).

Iterative way is good because it needs much less space of STACK(There is probably only O(1) method call levels, so O(1) space on STACK).

It is not easy to convert all recursion solutions to a "while loop" solution without any other auxiliary data structures' help.

public void inorder(TreeNode root) {
    if (root == null) {
        return;
    }
    inorder(root.left);
	System.out.println(root.key);
	inorder(root.right);
}

There are two paths of recursion need to follow instead of one, and we need to finish the first branch, then the second one.

In this case, we will need something else to help us: The recursion is internally done by using STACK to maintain the method call levels and directions, we can simulate this ourselves, so a stack will be needed.

The difference is, we use our own stack and the space used by our own stack is on HEAP. The space consumed on STACK is trivial. - We do not change the total space consumption, but we move out the space consumption of STACK to HEAP.

image-20200123201938717

Once the root is traversed, we can print it directly and we do not need to store it in the stack any more.

1. We always print root first, then root can be eliminated from stack.
2. We traverse left sub first, so the right sub should be retained in the stack before the left sub is done.

image-20200123202142846

public void preOrder(TreeNode) {
    if (root == null) {
        return;
    }
    Deque<TreeNode> stack = new LinkedList<TreeNode>();
    stack.offerFirst(root);
    while (!stack.isEmpty) {
        TreeNode cur = stack.pollFisrt();
        System.out.println(cur.value);
        if (cur.right != null) {
            stack.offerFirst(cur.right);
        }
        if (cur.left != null) {
            stack.offerFirst(cur.left);
        }
    }
}

image-20200123204430689

The problem is, we can not throw away the root in the stack before we traversed all the nodes in left subtree. How can we know we have already traversed all the nodes in left sub?

The root is the top element in the stack, use a helper node to store the next "visiting" node and subtree.

1. when helper node is not null, we should traverse the subtree, so we push helper and we go left
2. when helper is null. means the left subtree of the root is finished, the root is the top element in the stack. We can print the top and let helper = top.right. (traverse the left subtree first, then top, then right subtree)
3. do 1 and 2 until helper is null and there is no nodes left in the stack.

image-20200123205810909

public void inOrder(TreeNode root) {
    // 1. initial check
    if (root == null) {
        return;
    }
    // 2. we need a stack and a helper node.
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode helper = root;
    // 3. 
    while (helper != null || !stack.isEmpty()) {
        if (helper != null) {
            stack.offerFirst(helper);
            helper = helper.left;
        } else {
            helper = stack.pollFirst();
            System.out.println(helper.value);
            helper = helper.right;
        }
    }
}

image-20200123210455528

public void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Deque<TreeNode> stack = new LinkedList<TreeNode>();
    Deque<TreeNode> temp = new LinkedList<TreeNode>();
    stack.offerFist(root);
    while (!stack.isEmpty) {
        TreeNode cur = stack.pollFirst();
        temp.offerFirst(cur);
        if (root.left != null) {
            stack.offerFirst(root.left);
        }
        if (root.right != null) {
            stack.offerFirst(root.right);
        }
    }
    while (!temp.isEmpty()) {
        System.out.println(temp.pollFirst().value);
    }
}

What is the drawback of Method 1 if we print the nodes on the fly? Need to store everything in memory before we can get the whole post order traversal sequence.

Method 2:

The problem is, we need to traverse both left and right subtrees first, then we can eliminate the root from the stack. We need a mechanism to know, when we finished visiting all subtrees' nodes.

image-20200123213157747

What we need to know?

• The Direction! we are visiting down? or returning from left? or returning from right?

The root is the top element in the stack Maintain a previous Node, to record the previous visiting node on the traversing path, so that we know what the direction we are taking now and what is the direction we are taking next.

• root = stack.top
• if previous is null -> going down (left subtree has priority) (初始情况)
• if previous is current's parent, -> going down(left subtree has priority)
• if previous == current.left, -> left subtree finished, going current.right
• if previous == current.right, -> right subtree finished, pop current, going up

public void postOrder(TreeNode root) {
    // inital check
    if (root == null) {
        return;
    }
    // local variables
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode prev = null;
    stack.offerFirst(root);
    
  	while (!stack.isEmpty()) {
        TreeNode current = stack.peekFirst();
        // going down
        if (prev == null || current == prev.left || current = prev.right) {
            if (current.left != null) {
                stack.offerFirst(current.left);
            } else if (current.right != null) {
                stack.offerFrist(current.right);
            } else {
                System.out.println(current.value);
                stack.pollFirst();
            }
        } else if (prev == current.left) { // from left subtree
            if (current.right != null) {
                stack.offerFirst(current.right);
            } else {
                System.out.println(current.value);
                stack.pollFirst();
            }
        } else { // from right subtree
            System.out.println(current.value);
            stack.pollFirst();
        }
        prev = current;
    }  
}

This solution is important because this is the closest imitation of how actually the recursion is done in STACK, and it can be used as a general framework to iteratively do pre-order and in-order traversal as well.

If you look closely, the recursion is actually a DFS procedure on the binary tree. pre-order, in-order, post-order are following the same DFS procedure, and the only difference is when you want to print the node.

Map & Set & Hash

Set A collection that can not contain duplicate elements.

The Java platform contains three general-purpose Set implementations: HashSet, TreeSet, and LinkedHashSet.

• HashSet: which stores its elements in a hashtable, is the best-performing implementation; however it makes no guarantee concerning the order of iteration

• TreeSet: which stores its elements in a red-black tree(balanced binary search tree), orders its elements based on their values

• LinkedHashSet: it is a HashSet and also it is a LinkedList, it maintains the order when each of the elements is inserted into the HashSet.

Map

A collection that maps keys to values. A Map cannot contain duplicate keys; each key can map to one value.

• A collection that stores <key, value> pairs, such that no duplicate keys are allowed.

The Java platform contains three general-purpose Map implementations: HashMap, TreeMap, and LinkedHashMap.

HashMap

Common API http://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

V put(K key, V value) V get(K key) V remove(K key) boolean containsKey(K key) Set<Map.Entry<K, V>> entrySet() - get the set view of all the entries in the hashmap Set< K > keySet() - get the set view of all the keys in the hashmap Collection< V > values() - get the collection view of all the values in the hashmap boolean containsValue(V value) - O(n) void clear() int size() boolean isEmpty()

image-20200125192204047

Map<String, Integer> employerNumbers = new HashMap<>();
employerNumbers.put("yahoo", 1);
System.out.println(employerNumbers); // {yahoo=1}
employerNumbers.put("google", 2);
System.out.println(employerNumbers); // {yahoo=1, google=2}
Integer yc = employerNumbers.get("yahoo"); // yc = 1
yc = employerNumbers.put("yahoo", 5); // yc is the previous value for key "yahoo"
System.out.println(employerNumbers); // {yahoo=5, google=2}
System.out.println(yc); // yc = 1
yc = employerNumbers.get("yahoo"); // yc = 5
Integer fc = employerNumbers.get("facebook"); // fc = null
// if the key is not in the map, get(key) will return null
boolean fe = employerNumbers.containsKey("facebook"); // fe = false
System.out.println(fc); // null
System.out.println(fe); // false
fc = employerNumbers.remove("facebook");
System.out.println(fc); // null
Integer gc = employerNumbers.remove("google");
System.out.println(gc); // 2
System.out.println(employerNumbers); // {yahoo=5}

HashMap vs. Hashtable Similar to Vector vs. ArrayList

Vector, Hashtable exist from Java 1.0 ArrayList, HashMap introduced from Java 5

1. Hashtable not allow null key, but HashMap allow one null key.

2. Vector, Hashtable operations are synchronized (thread safe), introduce a lot of performance penalty

We do not use Hashtable anymore.

A Hashtable implementation.

• A table of buckets(an array of buckets), using the array index to denote each bucket.
• For each <key, value>, it goes to one of the buckets, the bucket index is determined by a hash function applied on key and the size of array.

image-20200125195818722

• Collision Control
  • Collision - two keys mapped to the same bucket
  • Separate Chaining(Close Addressing) - the element of each of the buckets is actually a single linked list.
  • If different Keys are determined to use the same bucket, they will be chained in the list.

image-20200125200213475

• What are the elements in the buckets? Singly Linked List, each node contains one <key, value> pair

  class Entry<K, V> {
      K key;
      V value;
      Entry<K, V> next;
  }

  https://docs.oracle.com/javase/8/docs/api/java/util/Map.Entry.html

HashMap operations

• put(key, value)

  1. int hash = hash(key) -- hash

  2. int index = hash % table_size -- index

  3. search for the list resides in the bucket to see if the key already exists

     • if not find the same key already existed, add a new Entry node to the list
     • if find an Entry with the same key, update the value of that Entry
• get(key)
  1. int hash = hash(key) -- hash
  2. int index = hash % table_size -- index
  3. search for the list resides in the bucket to see if the key already exists

HashMap can only has one null key, it is always mapped to bucket 0.

Get into a little details about HashMap Implementation:

• array of entries
• each entry is actually a singly linked list (handle collision)
  • contains the <key, value> pair

1. Define the class for each entry:

   class Entry<K, V> {
       final K key;
       V value;
       Entry<K, V> next;
       Entry(K key, V value) {
           this.key = key;
           this.value = value;
       }
       
       public K getKey() {
           return key;
       }
       
       public V getValue() {
           return value;
       }
       
       public void setValue(V value) {
           this.value = value;
       }
   }

2. maintain an array of entries

   Entry<K, V>[] array

   • To get(K key), put(K key, V value), remove(K key), we follow the steps
     • hash(key) to hash#
     • hash# to entry index in the array
     • from the corresponding singly linked list, iterate all of the nodes to find if the same key exists.

3. hash(key) to get the hash#

   private int hash(K key) {
       // return the hash# of the key
       if (key == null) {
           return 0;
       }
       int hashNumber = key.hashCode();
       // postprocessing to make the hashNumber non-negative.
   }

4. from the hash#, mapped to the entry index.

   int getIndex(int hashNumber) {
       // return the corrsponding index of array.
       return hashNumber % array.length;
   }

5. When iterate the corresponding entry for the given key, which is actually a singly linked list, we need compare each of the entry in the list, if the key is the same as the key we want, then it is the entry we want to find.

   Entry<K, V> cur = array[index];
   while (cur != null) {
       K curKey = cur.getKey();
       if (curKey is the same as given key) {
           ...
       }
   }

Two Questions Here:

1. "HashMap get(key), put(key, value), remove(key) is O(1)", is it always true? What is the major factor affecting the time complexity? hash(key) -> key.hashCode()
2. When we need to know if a key is already in the HashMap, we need to find its bucket, then traverse the linked list in that bucket to see if there is a same key already existed. how do we define "the same key"? key.equals(anotherKey)

Very Important: HashMap use

• key.hashCode() to determine the entry index for the key
• key.equals() to determine whether two keys are the same keys.

==, equals(), hashCode()

• ==
  • determine if two primitive type has the same value.
  • determine if two reference are pointed to the same object.

• equals(), hashCode()

  • defined in Object class, Object is the root class for any Java class

  • any Java class implicitly extends Object class, so if in the subclass these two methods are not overridden, it inherits what it defines in Object class.

  • the default implementation of equals() is to check if the two references are pointed to the same object "==".

  • the default implementation of hashCode() returns a "unique hash value" for the object based on its memory address.

  class Object {
      public boolean equals(Object obj) {
      return this == obj;
      }
  public int hashCode() {
          // here it returns the object's hash value(based on its memory address)
          // it is unique for each object.
      }
      public String toString() {
          
      }
  }

sometimes we do not want to compare the reference ... we want to compare the object's content. Example: (from an existing class)

// s1 and s2 are different String objects
String s1 = "abc";
String s2 = new String("abc");
// this will return false, "==" always compare if they are the same object
s1 == s2;
// this will return true, equals() for String class actually checks the "value"
s1.equals(s2);

Why s1.equals(s2) == true ?

in String class, the equals() method is overridden:

class String {
    char[] array;
    int offset;
    int length;
    
    @Override
    public boolean equals(Object obj) {
        if (obj == this) return true;
        if (!(obj instanceof String)) return false;
        String another = (String) obj;
        // check each of the characters of the two String object if they are the same
        if (this.length != another.length) return false;
        for (int i = 0; i < this.length; i++) {
            if (this.array[this.offset + i] ! = another.array[another.offset + i] {
                return false;
            }
        }
        // return true if they match
        return true;
    }
}

Example(our own class):

class has to override equals(), hashCode() if you want to have a different meaning than comparing the references.

// representing a (x, y) coordinate on the grid.
class Coordinate {
    public int x;
    public int y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

Coordinate one = new Coordinate(0, 0);
Coordinate another = new Coordinate(0, 0);

one == another; // false
one.equals(another); // false

public class Coordinate {
    public int x;
    public int y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (!(obj instanceof Coordinate)) {
            return false;
        }
        Coordinate another = (Coordinate) obj;
        return this.x == another.x && this.y == another.y;
    }

    @Override
    public int hashCode() {
        return x * 101 + y;
    }
}

Coordinate one = new Coordinate(0, 0);
Coordinate another = new Coordinate(0, 0);

one == another; // false
one.equals(another); // true

What about hashCode() ?

Remember, in Hashmap, key.hashCode() method determines which entry the key will go to, we need to guarantee the same keys always go to the same entry.

("yahoo"(1), 2) -- index = 1 put("yahoo"(2), 5), -> "yahoo"(2).hashCode() -- index,

In Java, There is a contract between equals() and hashCode(), the developers need to maintain:

• If one.equals(two), it is a must that one.hashCode() == two.hashCode()
• If one.hashCode() == two.hashCode(), it is not necessary one.equals(two)

When you want to override equals(), please definitely override hashCode() as well Only by doing this, you can make sure the HashMap will still work for the key type.

Example:

not override equals(), hashCode()

public class Coordinate {
    public int x;
    public int y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }
}

public class Main {
    public static void main(String[] args) {
        Map<Coordinate, Integer> map = new HashMap<>();
        Coordinate c1 = new Coordinate(1,2);
        map.put(c1, 5);
        Coordinate c2 = new Coordinate(1,2);
        map.put(c2, 6);
        System.out.println(map);
    }
}

// {(1,2)=5, (1,2)=6}

override equals(), override hashCode()

public class Coordinate {
    public int x;
    public int y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (!(obj instanceof Coordinate)) {
            return false;
        }
        Coordinate another = (Coordinate) obj;
        return this.x == another.x && this.y == another.y;
    }

    @Override
    public int hashCode() {
        return x * 101 + y;
    }
}

public class Main {
    public static void main(String[] args) {
        Map<Coordinate, Integer> map = new HashMap<>();
        Coordinate c1 = new Coordinate(1,2);
        map.put(c1, 5);
        Coordinate c2 = new Coordinate(1,2);
        map.put(c2, 6);
        System.out.println(map);
    }
}

// {(1,2)=6}

hashCode() is VERY important!

1. The performance of HashMap solely depends on how good the hashCode() is.

• bad hashCode() can lead to linear time complexity in extreme case, for example, if all the keys has the same hash number returned by .hashCode().

2. easy, fast, efficient
3. minimize collision, as evenly distributed as possible

Common hashCode() implementation

class Combo {
    int a;
    B b;
    C c;
    public Combo(int a, B b, C c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
    
    @Override
    public int hashCode() {
        return a * 31 * 31 + b.hashCode() * 31 + c.hashCode();
    }
}

image-20200126142048373

一般直接采取自动生成的方式

Rehashing, load factor

• Rehashing
  • is needed when there are too many <key, value> pairs maintained in the hashmap, -> too many collisions.
  • expand the array to a larger one and move all the <key, value> pairs to the new array (in HashMap by default, the array size is doubled each time.)
  • Rehashing is global wise - meaning all the <key, value> pairs need to participate.
• load factor
  • to control when rehashing is needed, maintain the ratio of number of <key, value> pairs / number of buckets
  • default 0.75
  • when the the ratio exceeds the limit, rehashing will happen.

HashSet

It is backed up by a HashMap instance. Only care about the Key here.

Common API https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html boolean add(E e) boolean remove(Object o) boolean contains(Object o) void clear() int size() boolean isEmpty()

class HashSet<K> {
    private HashMap<K, Object> map;
    
    // special object used for all the existing keys
    private static final Object PRESENT = new Object();
    
    public HashSet() {
        map = new HashMap<K, Object>();
    }
    public boolean contains(K key) {
        return map.containsKey(key);
    }
    public boolean add(K key) {
        return map.put(key, PRESENT) == null;
    }
    ...
}

HashMap Implementation, Arrays, Collections

Review About HashMap:

• where are equals() and hashCode() from?
  • the difference between "==" and equals()
• The contract between equals() and hashCode()
  • If o1.equals(o2) = true, then you have to guarantee o1.hashCode() == o2.hashCode()
  • If o1.hashCode() == o2.hashCode(), it is not necessary o1.equals(o2)

• The performance of HashMap is controlled by hashCode()

• If hashCode() return the same int value for all the objects, what will happen? It will be transferred to a single linked list.

HashMap Implementation

import java.util.Arrays;

/**
 * A hashtable implementation of map, demonstration purpose, generic type is provided
 *
 * supported operations:
 * size()
 * isEmpty()
 * clear()
 * put(K key, V value)
 * get(K key)
 * containsKey(K key)
 * containsValue(V value) // check if the desired value is in the map. O(n)
 * remove(K key)
 */
public class MyHashMap<K, V> {

    // Node is a static class of MyHashMap, since it is:
    // very closely bonded to MyHashMap class.
    // we probably need to access this class outside from MyHashMap class.
    public static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;
        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }

    // static final variable are global constants
    public static final int DEFAULT_CAPACIT = 16;
    public static final float DEFULT_LOAD_FACTOR = 0.75f;

    private Node<K, V>[] array;
    private int size; // how many key-value pairs are actually stored in the HashMap
    private float loadFactor; // determine when to rehash.

    public MyHashMap() {
        this(DEFAULT_CAPACIT, DEFULT_LOAD_FACTOR);
    }

    public MyHashMap(int cap, float loadFactor) {
        if (cap <= 0) {
            throw new IllegalArgumentException("cap can not be <= 0");
        }
        this.array = (Node<K, V>[])(new Node[cap]); // create an array and make it usable for generics
        this.size = 0;
        this.loadFactor = loadFactor;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        Arrays.fill(this.array, null);
        size = 0;
    }

    // non-negative
    private int hash(K key) {
        // 1. null key
        if (key == null) {
            return 0;
        }
        // 2. 3. hashCode()
        // int code = key.hashCode();
        // return code >= 0 ? code : -code;
        // int range = [-2^31, 2^31-1]
        // -Interger.MIN_VALUE = Integer.MIN_VALUE; -> overflow.
        return key.hashCode() & 0X7FFFFFFF; // guarantee non-negative
        // 01111111 11111111 11111111 11111111
        // Reason: java's % return remainder rather than modulus. The remainder can be negative.
    }

    private int getIndex(K key) {
        return hash(key) % array.length;
    }

    private boolean equalsValue(V v1, V v2) {
        // v1, v2 all possibly to be null
        if (v1 == null && v2 == null) {
            return true;
        }
        if (v1 == null || v2 == null) {
            return false;
        }
        return v1.equals(v2);

        // return v1 == v2 || v1 != null && v1.equals(v2);
    }

    // O(n), traverse the whole array, and traverse each of the linked list in the array.
    public boolean containsValue(V value) {
        // special case.
        if (isEmpty()) {
            return false;
        }
        for (Node<K, V> node : array) {
            while (node != null) {
                // check if the value equals()
                // value, node.getValue() all possible to be null.
                if (equalsValue(node.value, value)) {
                    return true;
                }
                node = node.next;
            }
        }
        return false;
    }

    private boolean equalsKey(K k1, K k2) {
        // k1, k2 all possibly to be null.
        if (k1 == null && k2 == null) {
            return true;
        }
        if (k1 == null || k2 == null) {
            return false;
        }
        return k1.equals(k2);

        // return k1 == k2 || k1 != null && k1.equals(k2);
    }

    public boolean containsKey(K key) {
        // get the index of the key
        int index = getIndex(key);
        Node<K, V> node = array[index];
        while (node != null) {
            // check if the key equals()
            // key, node.key() all possible to be null.
            if (equalsKey(node.key, key)) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    // if key does not exists in the HashMap, return null.
    public V get(K key) {
        int index = getIndex(key);
        Node<K, V> node = array[index];
        while (node != null) {
            // check if the key equals()
            // key, node.key() all possible to be null
            if (equalsKey(node.key, key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    // insert/update
    // if the key already exists, return the old corresponding value.
    // if the key not exists, return null.
    public V put(K key, V value) {
        int index = getIndex(key);
        Node<K, V> head = array[index];
        Node<K, V> node = head;
        while (node != null) {
            // check if the key equals()
            // key, node.key() all possible to be null
            if (equalsKey(node.key, key)) {
                V result = node.value;
                node.value = value;
                return result;
            }
            node = node.next;
        }
        // append the new node before the head and update the new head
        // insert operation
        Node<K, V> newNode = new Node(key, value);
        newNode.next = head;
        array[index] = newNode; // new head is here.
        size++;
        if (needRehashing()) {
            rehashing();
        }
        return null;
    }

    private boolean needRehashing() {
        // float loadFactor;
        float ratio = (size + 0.0f) / array.length;
        return ratio >= loadFactor;
    }

    private boolean rehashing() {
        // new double sized array.
        // for each node in the old array.
        // do the put() operation to the new larger array.
        return true;
    }

    // if the key exists, remove the <key,value> from the HashMap, return the value.
    // if the key not exists, return null.
    public V remove(K key) {
        // get index
        // delete operation on the linked list.
        // size--
        return node;
    }
}

What is a "view"?

entrySet() -> view

public Set<Map.Entry<K,V>> entrySet()

Returns a Set view of the mappings contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation, or through the setValue operation on a map entry returned by the iterator) the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations.

Specified by: entrySet in interface Map<K,V>

Specified by: entrySet in class AbstractMap<K,V> R

Returns: a set view of the mappings contained in this map

Efficient code accessing the HashMap

Which is better？

// 1
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (char cur: s1.toCharArray()) {
    if (map.containsKey(cur)) {
        map.put(cur, map.get(cur) + 1);
    } else {
        map.put(cur, 1);
    }
}

// 2
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (char cur: s1.toCharArray()) {
    Integer count = map.get(cur);
    if (count == null) {
        count = 1;
    } else {
        count++;
    }
    map.put(cur, count);
}

// or, in Java 8, use getOrDefault();

2方法更好，1方法访问了3次，2方法访问了2次。

Which is better?

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

// 2
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;
    }
}

2更好，set.add(cur) 同时可以返回信息

How to iterate each of the key, value pairs in a HashMap?

HashMap<String, Interger> map = new HashMap<String, Interger>();
map.put("google", 1);
map.put("yahoo", 2);
...

Which is better? A : 2

// 1
for (String key: map.keySet()) {
    System.out.println(key);
    System.out.println(map.get(key));
}

// 2
for (Map.Entry<String, Integer> entry: map.entrySet()) {
    System.out.println(entry.getKey());
    Syetem.out.println(entry.getValue());
}

Remove when traverse

HashMap<String, Interger> map = new HashMap<String, Interger>();
map.put("google", 1);
map.put("yahoo", 2);
...

Which is correct? A : 2

// 1
for (Map.Entry<String, Integer> entry: map.entrySet()) {
    if (entry.getValue() == 0) {
        map.remove(entry.getKey());
    }
}
// throw ConcurrentModificationException();

// 2
Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
    Map.Entry<String, Integer> cur = iter.next();
    if (cur.getValue() == 0) {
        iter.remove();
    }
}

LinkedList -> Tree in HashMap

Optimization -> from Java 8 Search() operation

Balanced Binary Search Tree -> O(logn)

1. if the LinkedList is very short, we do not do this optimization.
2. require order of the keys, but how?

1. If the key does not implement Comparable, use a system hash function to decide the order.

Data Structures vs. Java Implementations

Data Structures

• array new int[5];
• array(sorted) -- search O(n) -> O(logn)
  • O(1) random access(get by index)
  • limitation of array, fixed size or resizable.
• linked list
  • singly
  • doubly
  • O(n) random access(get by index)
  • O(1) append at head/tail
• queue
  • O(1) offer, poll, peek
  • FIFO
  • Circular Array
• stack
  • O(1) push, pop, top
  • LIFO
• deque
  • O(1) insert/remove/peek at both end
• heap
  • elements are ordered by their values
  • O(1) peek smallest/largest
  • O(logn) offer, poll
• hashtable
  • elements are not ordered
  • average O(1) search, insert, remove
• binary tree
  • O(n) search
• balanced binary search tree
  • elements are ordered
  • O(logn) search, insert, remove
  • O(logn) smallest/largest
  • O(logn) nextLarger(), nextSmaller()

Java Implementation

• array (int[] array, int[m] [n] matrix, ArrayList)
• linked list
• singly
• doubly (LinkedList)
• queue (LinkedList)
• stack (LinkedList)
• deque (LinkedList, ArrayDeque)
• heap (PriorityQueue)
• hashtable (HashMap, HashSet)
• Balanced Binary Search Tree (TreeMap, TreeSet)
• ......

Extra Reading

Java Collection Framework

• The most most frequently used classes and APls during practices/interviews.
• The representation classes of data structures(called collections/containers).
• Collections Framework is available from Java 5 (a set of the classes and interfaces conducting a hierarchical structure, following the strong OO paradigm, containing all the interfaces and implementations)
• Official tutorial: https://docs.oracle.com/javase/tutorial/collections

Interfaces/Classes Hierarchy

image-20200127142607895

The arrows means "implements"

Collection - Defines what operations should be provided for any classes that is a "Collection". Any class that is a kind of collection should implement the defined method. http://docs.oracle.com/javase/7/docs/api/java/util/Collection.html int size() boolean isEmpty() boolean add(E element) boolean contains(E element) boolean remove(E element) void clear()

List - Defines a group of data structures, that can contain duplicate elements, maintain the order of insertion of the elements and provide the capability of random access by using index. http://docs.oracle.com/javase/7/docs/api/java/util/List.html E get(int index) E remove(int index) E set(int index, E element)

ArrayList - A concrete implementation of List by resizable-array. http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html It is a List It is a Collection It implements all the methods specified in List and Collection. List list = new ArrayList(); ArrayList list = new ArrayList();

Queue - Defines a group of data structures, that is designated to 1). hold and buffer elements before processing 2). provide a way of choosing which element buffered is the next one to be processed 3). there are usually two ends of the Queue, and offer always at tail, poll() always at head. http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html boolean add(E element); E element(); E remove(); // group two operations boolean offer(E element); E peek(); E poll();

Deque - Defines a subtype of queue, where it is double ended. (FIFO & LIFO are both provided) http://docs.oracle.com/javase/7/docs/api/java/uti/Deque.html boolean offerFirst(E element); boolean offerLast(E element); E pollFirst(); E pollLast(); E peekFirst(); E peekLast();

LinkedList - A List implementation that backed by a doubly linked list. It also can be used as queue/deque/stack. http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html It is a List lt is a Queue It is a Deque It is a Collection It implements all the methods specified in Collection, List, Queue, Deque.

PriorityQueue - Defines a special implementation of queue, where it is using priority to determine which element is the next to process(using order). http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html It implements all the methods specified in Collection, Queue.

Set - Defines a group of data structures, that contains no duplicate elements. http://docs.oracle.com/javase/7/docs/api/java/util/Set.html

HashSet - A concrete implementation of Set using hashtable. http://docs.oracle.com/javase/7/docs/api/java/uti/HashSet.html It is a Set It is a Collection It implements all the methods specified in Set and Collection.

SortedSet - Define a subtype of Set, that contains no duplicate elements, and the elements are sorted. It is a subtype of Set. http://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html E first(); // smallest one E last(); // largest one SortedSet headSet(E toElement); // all the elements smaller than toElement SortedSet tailSet(E fromElement); // all the elements larger than fromElement ...

TreeSet - A concrete implementation of SortedSet using red-black tree. http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html It is a SortedSet It is a Set : It is a Collection It implements all the methods specified in SortedSet, Set and Collection.

Similar to Map, SortedMap, HashMap and TreeMap: http://docs.oracle.com/javase/7/docs/api/java/util/Map.html http://docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html http://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

About Arrays and Collections

They are the placeholders of a set of utility methods for manipulating arrays and collections objects.

• They are NOT the class for array and Collection
• All the methods in Arrays/Collections are static methods, so there is no need to create Arrays/Collections object to utilize them

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

• Arrays.sort(int[] array) int[] array = new int[] {3, 2, 1}; Arrays.sort(array); // array = {1, 2, 3}

• Arrays.sort(T[], Comparator comparator) use the order defined in the comparator to sort the array.

      class Cell {
      	int x;
      	int y;
      	int value;
  }
      
      class CellComparator implements Comparator<Cell> {
      	@Override
      	public int compare(Cell c1, Cell c2) {
      		if (c1.value == c2.value) {
      			return 0;
      		}
      		return c1.value < c2.value ? -1 : 1;
      	}
      }
      
      Cell[] cells = ...;
      Arrays.sort(cells, new CellComparator());

Arrays.sort(int[] array); -> quicksort Arrays.sort(Integer[] array); -> optimized mergesort

quicksort - average fastest comparison based sorting algorithm average time O(nlogn), space O(logn) worst time O(n^2) space O(n) not stable

mergesort - guaranteed O(nlogn) time, O(n) space stable

heapsort - O(nlogn) time, O(1) space {1, 4, 3, 2, 5} Stable sort: the order of entries with equal keys will be preserved. Example: Sort student on score first, then gender. Two male student with score 90 and 80 will preserve their order after the sort on gender.

• Arrays.asList(T... a) - convert an array to a List Returns a fixed-size list backed by the specified array. (Changes to the returned list "write through" to the array.)

  List<Integer> list = Arays.asList(1, 2, 3);
  //list is a List of [1, 2, 3] (Integer[])
  
  list.set(0, 4);
  //list is [4, 2, 3]
  
  list.add(5);
  // throw UnsupportedOperationException - fixed-sized

• Arrays.copyOf(original, int newLength)

  int[] array = new int[] {1, 2, 3};
  int[] copy = Arrays.copyOf(array, 1);
  // copy = {1}
  copy = Arrays.copyOf(array, 5);
  // copy= {1, 2, 3, 0, 0}, padding default values at the end

• Arrays.fill(original, value)

  int[] array = new int[] {1, 2, 3};
  Arrays.fill(array, 1);
  // array = {1, 1, 1}

• Arrays.toString(int[] array), Arrays.deepToString(int[] [] matrix)

  int[] array = new int[] {1, 2, 3};
  String s = Arrays.toString(array);
  // s = "[1, 2, 3]";
  
  int[][] matrix = new int[] {{1, 2}, {1, 2}};
  String t = Arrays.deepToString(matrix);
  // t = "[[1, 2], [1, 2]]"

• Arrays.binarySearch(original, value)

  int[] array = new int[] {3, 2, 1};
  Arrays.sort(array);
  // the array must be guaranteed to be sorted before using binarySearch
  int i = Arrays.binarySearch(array, 2);
  // i = 1

Collections

http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html

• Collections.sort(List list), Collections.sort(List list, Comparator comparator)
• Collections.binarySearch(List list)
• Collections.swap(List list, int i, int j)
• Collections.fill(List list, T value)
• Collections.reverse(List list)
• Collections.reverseOrder() : reverse the natural order defined by a class implementing Comparable interface

// You can use Collections.reverseOrder() this way. PriorityQueue maxHeap = new PriorityQueue(11, Collections.reverseOrder());

Convert List to array(or, Collection to array)

interface Collection<T> {
    ...
	Object[] toArray()
    T[] toArray(T[] array)
    ...
}

interface List<T> implements Collection<T> {
  
}

List<String> list = new ArrayList<String>();
Integer[] array = list.toArray(new Integer[list.size()]);

in Java - The elements in the generic Collection can not be primitive type. There is no List, List ... etc.

List to int[] array ?

There is no existing utility / method in Java plain API, in another way, you have to write your own method to do this.

Bit Representation

public class Bit {
    // print binary representation of a int value.
    public static void printBinary(int value) {
        System.out.println(value + ":");
        StringBuilder builder = new StringBuilder();
        for (int shift = 31; shift >= 0; shift--) {
            builder.append((value >>> shift) & 1);
        }
        System.out.println(builder.toString());
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {

        // 0
        int a = 0;
        Bit.printBinary(a);

        // positive number
        a = 5;
        Bit.printBinary(a);

        // negative number
        a = -5;
        Bit.printBinary(a);

        a = Integer.MIN_VALUE;
        Bit.printBinary(a);

        a = Integer.MAX_VALUE;
        Bit.printBinary(a);

        a = -1;
        Bit.printBinary(a);

        // signed shift - leftmost bit depends on previous leftmost bit
        int b = a >> 5;
        Bit.printBinary(b);

        // unsigned shift - leftmost bit "0"
        b = a >>> 5;
        Bit.printBinary(b);

    }
}

• ">>>" vs. ">>"

  • signed shift ">>" - arithmetical

    The leftmost position after signed shift depends on sign extension(the most significant bit)

• unsigned shift ">>>" - logical

    The signed right shift operator ">>>" shifts a zero into the leftmost position
    ![image-20200127204304752](SDE实践/image-20200127204304752.png)

Note: There is no "unsigned int" in Java, but there is unsigned right shift.

two view of int:

• 32 bits, each of which is either 0 or 1
• arithmetic number http://stackoverflow.com/questions/1023373/findbugs-warning-integer-shift-by-32-what-does-it-mean

Autoboxing and Unboxing

• Primitive type vs. Wrapper class
  • int: Integer
  • long: Long
  • char: Character
  • double: Double
  • boolean: Boolean
  • ......

A wrapper class is just a wrapper of the corresponding primitive type, the Object representation of primitive type values. Similar to String, all the wrapper class objects are IMMUTABLE - internal values can not be changed after initialization. It can help:

1. Generic type can not be primitive type, List ; there can not be List
2. It can help provide useful functionalities and contracts (json serializer: obj -> json)
3. How do you represent a "not existed" int value? "null"

Prefer primitive types to wrapper classes.

// example:
class Integer implements Comparable<Integer> {
    private final int value; // wrap the primitive type value inside.
    public Integer(int value) {
        this.value = value;
    }
    
    public int intValue() {
        return value;
    }
    
    public Integer plus(Integer another) {
        return Integer.valueOf(value + another.intValue());
    }
    
    @Override
    public int compareTo(Integer another) {
        if (value == another.value) {
            return 0;
        }
        return value < another ? -1 : 1;
    }
}

• autoboxing Autoboxing is the automatic conversion that the Java compiler makes between the primitive types and their corresponding object wrapper classes.

  For example, converting an int to an Integer, a double to a Double, and so on.

  List<Integer> integerList = new ArrayList<Integer>();
  
  for (int i = 0; i < 50; i++) {
      integerList.add(i); // ==> integerList.add(Integer.valueOf(i));
  }

• unboxing Unboxing is the reverse operation of autoboxing.

  Integer a = 4; // autoboxing => Integer a = Integer.valueOf(4);
  a += 4;

What happened when Integer++?

• Integer is immutable, the int value of the Integer object can never change

  // a++:
  int temp = a.intValue();
  temp++;
  a = Integer.valueOf(temp); // a is pointing to another Integer object.
  
  // a += 4;
  int temp = a.intValue();
  temp += 4;
  a = Integer.valueOf(temp); // a is pointing to another Integer object.

More Examples:

+, -, *, /, >, <, >=, <= ... only applied to primitive type.

public class Main {
    public static void main(String[] args) {

        Integer a = 1115; // autoboxing
        int b = 5; // primitive
        System.out.println(a > b); // unboxing. => a.intValue() > b false
        System.out.println(a + 2);
        System.out.println(a * 3);
        System.out.println(a == b); // unboxing, true
        Integer c = 1115;
        System.out.println(a > c); // unboxing => a.intValue() > c.intValue() false
        System.out.println(a >= c); // unboxing => a.intValue() > c.intValue() true
        System.out.println(a == c); // true

        // == both operand can be Object type and it is comparing if the two references are pointed to the same Object.

        a = 129; // Integer.valueOf(129);
        c = 129; // Integer.valueOf(129);
        System.out.println(a > c); // false
        System.out.println(a >= c); // true
        System.out.println(a == c); // false
    }
}

• Integer class cache the Integer object with value from -128 to 127, so every time an Integer object within this range is needed, it will always return the corresponding object.
• The unboxing is done only when it is necessary, for example, a > b. Be very careful about using "=="

int[] vs. Integer[] They are totally different types, and there is no auto conversion directly between them. Integer[] objArray = new Integer[5]; int[] array = objArray; // compile error. But, Integer[] objArray = new Integer[5]; objArray[0] = 1; // will work. int[] array = new int[5]; Integer a = 5; array[0] = a; // will work.

When you implement your own Comparator or override equals(), keep in mind:

• be very careful if you see "==" on Object type.

Bad:

class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer i1, Integer i2) {
        if (i1 == i2) { // we do not want to check the references.
            return 0;
        }
        return i1 < i2 ? 1 : -1;
    }
}

3 alternative ways:

1. return i1.compareTo(i2);
2. if (i1.equals(i2)) {}
3. if (i1.intValue() == i2.intValue()) {}

Bad: It could overflow.

class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer i1, Integer i2) {
        return i1 - i2;
    }
}

Good:

class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer i1, Integer i2) {
        if (i1 < i2) {
            return -1;
        } else if (i1 > i2) {
            return 1;
        }
        return 0;
    }
}

class MyComparator implements Comparator<Long> {
    @Override
    public int compare(Long i1, Long i2) {
        if (i1 < i2) {
            return -1;
        } else if (i1 > i2) {
            return 1;
        }
        return 0;
    }
}

String

• a sequence of characters "abc"

• in Java, they are objects

  class String {
      private final char[] value;
      // different String objects can reuse the same char array,
      // but can start with different offset index.
      private int offset;
      // maintains the length of the part in the char array
      // represented by this String object.
      private int count;
      public String() {
          value = new char[0];
          offset = 0;
          count = 0;
      }
      ......
  }
  char[] array = {'a', 'b', 'c', 'd'};
  offset = 1; count = 2; // array(1, 2); "bc";

• creating Strings

  • String literal:
    • a series of characters in your code that is enclosed in double quotes "abc"

  • Whenever it encounters a string literal in your code, the compiler creates a String Object with its value(really?) String s1 = "abc"; String s2 = "abc"; System.out.println(s1 == s2); // true

  • Pooling for String objects There is no need for maintaining several copies of String objects with the same literal, since String objects are immutable. Usually compiler and JVM will optimize for the number of String objects created, it will maintain an intern area in HEAP, for the same String literal it will only has one String object associated.

  • String s1 = "abc"; String s2 = new String("abc"); // String(String another)

  • // how many Strings are created? System.out.println(s1 == s2); // false System.out.println(s1.equals(s2)); // true The String objects created with "new" will not use the intern pool;

  • Another Example: String sa = "a"; String sb = "b"; String sab = "a" + "b"; // compile time concat, "ab" // <=> String sab = "ab";

  • System.out.println(sab == "a" + "b"); // true System.out.println(sab == sa + "b"); // false, sa.concat("b"); System.out.println(sab == sa + sb); // false, sa.concat(sb);

  • The optimization is at compile time, the literals will be concatenated if possible before getting the String object.

  • Question: how many String objects are created?

    for (int i = 0; i < 100; i++) {
        String s = new String("abc"); // new String(String another)
    }
    
    for (int i = 0; i < 100; i++) {
        String temp = "abc";
        String s = new String(temp);
    }

    100: if "abc" is in the pool 101: if "abc" is not in the pool

  • Constructors - http://oracle.com/javase/7/docs/api/java/lang/String.html String() String(String value) String(char[] array) String(char[] array, int offset, int length) String(StringBuilder builder)

• Immutable

  • the value of the String object cannot be changed after creation.

    String s1 = "abc"; String s2 = s1; // this is another String object, the previous object's value is not changed. s2 = "def" System.out.println(s1); // "abc" System.out.println(s2); // "def"

• String length

  • s1.length() vs. int[] length;

• Concatenate Strings

  • s1.concat(s2) // again, this will create a new String object rather than change the value of s1 or s2.
  • s1 = "abc" + "def"; // 等价于s1 = "abcdef", compile time concatenation.
  • s1 = s1 + "def"; // <==> s1.concat("def");
  • s1 = 1 + "def"; // String.valueOf(1), (1 -> Integer(1) -> Integer(1).toString()) -> "1"
  • s1 = "id: " + 2 + "isStudent: " + true + 'y';

Interface, Abstract Class, Access Modifier, Exceptions

Inheritance

Definitions: A class that is derived from another class is called a subclass (also a derived class, extended class, or child class). The class from which the subclass is derived is called a superclass(also a base class or a parent class).

public class Person {
    private String name;

    public String getName() { return name; }

    public void setName(String name) {
        this.name = name;
    }
}

public class Employee extends Person {
    private String company;

    public void setCompany(String company) {
        this.company = company;
    }

    public String getCompany() { return company; }
}

public class Main {
    public static void main(String[] args) {

        Employee e = new Employee();
        e.setCompany("google");
        e.setName("elon");
        String name = e.getName(); // 依旧可以调用
        String company = e.getCompany();
        System.out.println(name);
        System.out.println(company);
    }
}

Override vs. Overload

Override is when you redefine a method that has been defined in a parent class (using the same signature). Resolved at runtime.

Overload is when you define two methods with the same name, in the same class, distinguished by their signatures (different), Resolved at compile time.

class A {
    public String show(D obj) {
        return ("A and D");
    }

    public String show(A obj) {
        return ("A and A");
    }
}

class B extends A {
    public String show(B obj) {
        return ("B and B");
    }

    public String show(A obj) {
        return ("B and A");
    }
}

class C extends B {

}

class D extends B {

}

public class Test {
    public static void main(String[] args) {
        A a1 = new A();
        A a2 = new B();
        B b = new B();
        C c = new C();
        D d = new D();
        System.out.println("1--" + a1.show(b));
        System.out.println("2--" + a1.show(c));
        System.out.println("3--" + a1.show(d));
        System.out.println("4--" + a2.show(b));
        System.out.println("5--" + a2.show(c));
        System.out.println("6--" + a2.show(d));
        System.out.println("7--" + b.show(b));
        System.out.println("8--" + b.show(c));
        System.out.println("9--" + b.show(d));
    }
}

/*
1--A and A
2--A and A
3--A and D
4--B and A
5--B and A
6--A and D
7--B and B
8--B and B
9--A and D
 */