Leetcode Java Summary

Posted on | Edited on | In

TO-DO

  1. hiring season, internal reference
  2. position: backend developer, DevOps, Infra
  3. system design from x code in my laptop? baidu cloud?
  4. company series, buy x code or leetcode?
  5. resume project chat
  6. blog review

Data Structure

java Integer notation, see this post:

1
2
3
4
// 10^9
int a = (int)1e9;
int a = (int)Math.pow(10, 9);
int b = 2_000_000_000;

Class features

basic structure and syntax nested class, inner class static class private public protected

LRU

LRU除了可以使用自定义的double linked list去实现，也可以用Java API LinkedHashMap，在constructor中指定参数:

1
2
3
4
5
6
7
8
9
10
// 设置capacity
int CAPACITY = 10;
// true表示自动实现LRU功能
LinkedHashMap<String, Integer> lru = new LinkedHashMap<>(CAPACITY, 0.75f, true){
  // override
  protected boolean removeEldestEntry​(Map.Entry<String, Integer> eldest)
  {
    return size() > CAPACITY;
  }
}

如此一来，可以直接使用put(), get()即可，其他不用操心，当达新增的量超过capacity时会自动删除least recently used item.

此外，如果不使用这个special constructor new LinkedHashMap<>(CAPACITY, 0.75f, true)，则linked list中的顺序是insertion order，即最先insert的在前面，最近的在后面，如果用keySet() iterator是按照linked list的顺序出来的，即最先insert的先出来。

经过试验发现，LRU声称的access order，都是insertion order的顺序，只不过LRU实现每次会自动把最新活动的元素重新放到linked list最后， 然后超出capacity时，把least recently used one删除了.

Pair class

https://docs.oracle.com/javase/8/javafx/api/javafx/util/Pair.html https://www.baeldung.com/java-pairs

1
import javafx.util.Pair;

https://www.geeksforgeeks.org/pair-class-in-java/

input method

Deque

如果把Deque既当stack又当queue, 不要使用他们的native method，用能明确指出操作位置的method:

1
2
3
4
5
6
7
addLast(x)
removeLast()
peekLast()

addFirst()
removeFirst()
peekFirst()

如果只充当stack or queue之一，则可以用native method:

1
2
stack: push, pop
queue: add, poll

Segment Tree

https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

1
2
3
4
5
6
7
8
9
10
// get min value >= x
// 返回的都是整数，但是是double type
Math.ceil(double x)
// get max value <= x
// 返回的都是整数，但是是double type
Math.floor(double x)
// log e of x
Math.log(double x)
// calculate log2
Math.log(x) / Math.log(2)

Complete binary tree number of nodes: 2^height - 1 (height start from 1) For segment tree, number of nodes:

1
2
3
4
// n is the length of array
int h = (int)Math.ceil(Math.log(n) / Math.log(2));
int maxSTSize = 2 * (int)Math.pow(2, h) - 1;
int[] st

Or you can define class Node to build segment tree.

List

  • LinkedList is doubly-linked!
  • change array to list
1
List<Integer> list = Arrays.<Integer>asList(1, 2, 3, ...);

but this is fixed size list backed by array, you can create a new one:

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

use slow-fast pointer to find middle of linkedlist or find cycle

1
2
3
4
5
6
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// when loop break, slow is in middle

reverse the linked list: https://leetcode.com/problems/reorder-list/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
13
// 1->2->3->4
// 1<-2<-3<-4
ListNode pre = null;
ListNode cur = <node 1>;
while (cur != null)
{
    ListNode next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
}
// 注意这里不要弄错了
ListNode newHead = pre;

PriorityQueue

Priority queue has contains(object) and remove(object) method, but that will take O(n) time.

如果要构造比较整数大小的priority queue

1
2
// if use (a, b) -> a - b, this may overflow when encounter MAX MIN
Queue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(a, b));

注意priorityQueue iterator返回的是random order!

String

String: immutable StringBuilder: mutable, not thread safe StringBuffer: mutable, thread safe

注意"\t", "\n"在string中只相当于一个长度！！！

“abcdefg” substring 是连续的: “cdef” subsequence可以不连续，但顺序要一致: “abdf”

1
2
3
4
5
6
7
8
9
String str = new String("123");
String str = "123";
// convert number 123456 to string "123"
String str = String.valueOf(123456);
str.length();
// use + to concatenate
str1 + str2
// string compare
str1.compareTo(str2);

when do replace

1
2
3
4
String str = "a.b.c.d";
str.replace(".", ""); // get "abcd"
// don't use str.replace('.',''), cannot be empty char
// there is no regex, just CharSequence type

if just want to create a string using other type:

1
"" + other type

caution:

1
2
3
4
5
6
String a = "1.2.3.";
// a.split("\\.") will get length of 3, it will ignore last '.'
String a = ".1.2.3";
// a.split("\\.") will get length of 4, it will not ignore first '.'
String b = "1..2.3";
// b.split("\\.") will get length of 4, it will not ignore consecutive '.'

Notice the parameters format

1
2
3
4
5
6
indexOf(int ch, int startIndex)
split(String reg)

// returns the index within this string of
// the last occurrence of the specified character.
int lastIndexOf​(int ch)

StringBuilder

1
2
3
4
5
6
7
8
9
StringBuilder sb = new StringBuilder(String);
sb.append(x);
// insert in head
sb.insert(0, x);
sb.toString();
// return stringbuilder
sb.reverse();
// stringbuilder does not implement equals method!!
sb.equals(another stringbuilder object); // wrong!!

more methods:

1
2
3
4
5
6
7
// return String
// 这里只有一个参数的时候是start index!
substring(int startidx)
// [start end)
substring(int startidx, int endidx) 
append(lot of types)
setLength(int len)

Character

1
2
3
4
5
6
7
8
// return Character
Character.valueOf(char)
//return char
c.charValue()

// actually the convert is auto like int and Integer!
char c1 = new Character('a');
Character c1 = 'b';

char compare in if use == if use ± with char, such as ch - 'a', don’t forget (char)(ch)

check letter:

1
2
3
Character.isDigit(ch);
Character.toLowerCase(ch);
Character.isLetterOrDigit(ch);

Non-ASCII character (> 256):

1
Character.toString((char)342)

3 items if expression

1
2
3
// I forget the precedence
// this will first 1 + 2 + 3 then compare with 3!
1 + 2 + 3 == 3? true: false

Enhenced for Loop

1
2
3
4
5
// enhanced for loop
for (Character ch : str.toCharArray())
{
  ...
}

Collection

convert list to array

1
2
3
// result is List<int[]> type
// think about it
result.toArray(new int[result.size()][]);

convert Integer list to int array (from Java8): https://stackoverflow.com/questions/718554/how-to-convert-an-arraylist-containing-integers-to-primitive-int-array

1
int[] arr = list.stream().mapToInt(i -> i).toArray();

also from int array to Integer list https://stackoverflow.com/questions/1073919/how-to-convert-int-into-listinteger-in-java

1
List<Integer> list = Arrays.stream(ints).boxed().collect(Collectors.toList());

这个是Java stream的知识点

Array

1
2
3
4
5
6
7
// one dimension
int[] arr = new int[]{1,2,3};
int[] arr = new int[4]; // default value is 0
// two dimensions
int[][] arr = new int[3][4]; // 3 rows 4 columns
int[][] arr = new int[3][]; // still ok, you can init one dimension array later
int[][] arr = new int[][]{{1,2,3}, {4,5}, {6,7,8,9}}; // each one dimension array can have different length!

Let’s see char array

1
char[] arr = str.toCharArray();

Use sort static method, if you want to use comparator, see my lambda section

1
2
3
Arrays.sort(E[] e);
// also for collections
Collections.sort(List<xx> l);

Arrays.sort(int[]) primitive type是不能自己写comparator的！

数组内容字符串化用:

1
2
3
4
5
int[] a = new int[]{1,2,3,4,5};
// correct!
Arrays.toString(a);
// wrong! 这个返回id string
a.toString()

Shuffle arrays: Every permutation of array element should equally likely: https://www.geeksforgeeks.org/shuffle-a-given-array-using-fisher-yates-shuffle-algorithm/ https://introcs.cs.princeton.edu/java/stdlib/StdRandom.java.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// nums[0] swap with element in range [0, n)
// nums[1] swap with element in range [1, n)
// nums[2] swap with element in range [2, n)
public static int[] shuffle(int[] nums)
{
  for (int i = 0; i < nums.length; i++)
  {
    int j = i + rand.nextInt(nums.length - i);
    // swap
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
  }
  return nums;
}

Set

TreeSet operation time complexity, from java TreeSet doc: This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

Map

1
import java.util.*;

HashMap<>() not thread safe HashTable<>(), thread safe but ConcurrentHash…

有时用char[26]（c - 'a'） 或者 int[256] (直接用c即可) 可以用来代替hashmap

1
2
3
4
5
6
7
8
map.containsKey()
// also has contains value method!
map.containsValue()
// return set
map.keySet()
map.entrySet()
// return collection
map.values()
1
2
3
4
5
6
// provide value for new key which is absent 
map.put(key, map.getOrDefault(key, 0) + 1);
// if value is a collection object can use:
map.computeIfAbsent(key, k -> new ArrayList<Stone>()).add(new Stone(x,y));
// remove current key if it's value is val
map.remove(key, val)

Treemap/TreeSet (sorted map) perform all operation based on it’s default/custom comparator! if two key are equal in comparator, should be treated as equal in equals() method! 但如果没有一致，还是按照comparator去做. treemap/treeset.remove(object) 用的是comparator去比较相等！！

range query API:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// treemap
tm.ceilingKey(K key)
tm.ceilingEntry(K key)
tm.floorEntry(K key)
tm.floorKey(K key)

tm.firstKey()
tm.firstEntry()
tm.lastKey()
tm.lastEntry()

tm.pollFirstEntry()
tm.pollLastEntry()
// treeset
ts.ceiling(K key)
ts.floor(K key)

ts.first()
ts.last()
// 可以用来模拟pq
ts.pollFirst()
ts.pollLast()

如果要返回map中的任意一个key，比如key是string类型

1
return (String)map.keySet().iterator().next();

this is java syntax, I see it in leetcode https://stackoverflow.com/questions/1958636/what-is-double-brace-initialization-in-java

Exception Handling

1
throw new Exception("xxx");

Random Number Generation

1
2
3
4
5
6
import java.util.Random;
Random rand = new Random();
int randomNum = rand.nextInt((max - min) + 1) + min;
// simply can use this:
// return double, need to force convert to int maybe
Math.random(): [0.00,1.00)

Lambda Expression

for comparator and comparable, let’s see how to wirte it, this post

原来的方法，在constructor中定义comparator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Queue<Integer> que = new PriorityQueue<>(new Comparator<Integer>(){
      @Override
			public int compare(Integer n1, Integer n2) {
				return Integer.compare(n1, n2);
			} 
});

int[] arr = new int[]{5, 3, 56, 78, 4, 2, 5};
// anonymous class to implement comparator
Arrays.sort(arr, new Comparator<Integer>(){
  public int compare(Integer n1, Integer n2)
  {
    return Integer.compare(n1, n2);
  }
});
1
2
3
4
int[][] arr = {{5,1}, {2,3}};
// sort by the first element of one dimenstional array
Arrays.sort(arr, (int[] a, int[]b) -> a[0] - b[0]);
System.out.println("result= " + Arrays.deepToString(arr));

用lambda构造comparator 时可以用到外部的数据结构？ https://leetcode.com/problems/top-k-frequent-elements/solution/ 比如这个的官方solution

1
2
3
// init heap 'the less frequent element first'
    PriorityQueue<Integer> heap =
            new PriorityQueue<Integer>((n1, n2) -> count.get(n1) - count.get(n2))

其实这里可以使用Map.Entry<> 放入pq中。 count是一个外部定义的hashmap. 这个到底是怎么回事？

Java Memory Management

java heap space, java stack memory Memory Allocation in Java Stack Memory and Heap Space in Java

Java Garbage Collection

you can watch the operting system course video implemented by DFS with marked bit in each object, scan from stack

Why use Deque instead of stack

check this post https://leetcode.com/problems/flatten-nested-list-iterator/discuss/80147/Simple-Java-solution-using-a-stack-with-explanation/165585

I just recently interviewed with 16 different companies in the silicon valley (including FAANG except Netflix) for senior software engineering positions. Here’s my opinion, based on my experience:

Some interviewers will expect you to know why Deque is better than Stack.

Showing mastery of at least one programming language (in this case, Java) can, at worst, score you extra points in the interview, and at best get you the job and even help you get higher compensation or leveling. Getting the optimal solution is the basic requirement to pass an interview. Additionally, you are being benchmarked against other candidates being asked exactly the same question. Lastly, for those targeting senior level positions, the interviewer will also evaluate your seniority. This is one case where I think most interviewers will expect to see that you’ve mastered the Java programming language (if you chose to use it in your interview).

Here are a few reasons why Deque is better than Stack:

Object oriented design - Inheritance, abstraction, classes and interfaces: Stack is a class, Deque is an interface. Only one class can be extended, whereas any number of interfaces can be implemented by a single class in Java (multiple inheritance of type). Using the Deque interface removes the dependency on the concrete Stack class and its ancestors and gives you more flexibility, e.g. the freedom to extend a different class or swap out different implementations of Deque (like LinkedList, ArrayDeque).

Inconsistency: Stack extends the Vector class, which allows you to access element by index. This is inconsistent with what a Stack should actually do, which is why the Deque interface is preferred (it does not allow such operations)–its allowed operations are consistent with what a FIFO or LIFO data structure should allow.

Performance: The Vector class that Stack extends is basically the “thread-safe” version of an ArrayList. The synchronizations can potentially cause a significant performance hit to your application. Also, extending other classes with unneeded functionality (as mentioned in #2) bloat your objects, potentially costing a lot of extra memory and performance overhead.

Tries

string symbol table: specialized to string key. Faster than hashing, flexible then BST recall the structure of tries, very simple! put value in last node (character). put and search method for tries can be recursion implementations. 一般都用的这个。

3-way tries: 这里注意，当前char的值和node char比较，less then go left, larger then go right, then compare, if not match, miss hit. Using recursion to do put and search operation. TST is as fast as hashing (for string key) and space efficient. support in-order traverse (obey BST rule)

Implementation: prefix matching, wildcard match, longest prefix.

Algorithms

Tushar Roy youtube channel princeton algorithms，在youtube or coursera上都有

Time complexity: https://en.wikipedia.org/wiki/Time_complexity usually:

1
2
3
4
5
6
7
8
9
constant O(1)
logarithmic O(logn)
linear O(n)
quasilinear O(nlogn)
quadratic O(n^2), n to the power of 2
cubic O(n^3), n to the power of 3
polynomial O(n^x + n^y + ..)
exponential O(2^n)
factorial O(n!)

Tilde notation: ignore lower order terms, negligible best case, lower bound worst case, upper bound, Big O does this average case, cost for random input, expected cost when upper bound equals lower bound, we get optimal algorithms

tilde notation vs big-O

Prime

LC 886 https://leetcode.com/problems/prime-palindrome/ isPrime是如何检查的，函数记住, 并不是检查每个递增+1的除数是否整除！ 检查特殊的值就可以了 https://en.wikipedia.org/wiki/Primality_test

Monotonic Stack

LC 496 Next Greater Element I LC 503 Next Greater Element II 还有LC 31 next permutation 也是属于monotonic problem, 见这题我的note

Monotonic stack practice: https://medium.com/@vishnuvardhan623/monotonic-stack-e9dcc4fa8c3e

increasing monotonic stack: from stack top to stack bottom is increasing decreasing monotonoc stack: reverse order

General

bit and boolean can use XOR ^ operator!

Sliding Window

相关window问题的template and summary, good sliding window demo

basic sliding window problem leetcode 904 find the longest sequence with at most 2 integers

Quick select

Average O(n), worst case O(n^2), need to shuffle. if quick select Kth element, then in the range [0, K] is guarantee the K smallest elemets in unsorted array.

Summary of top k problem: https://leetcode.com/problems/k-closest-points-to-origin/discuss/220235/

how to decide the condition? lo < hi or lo <= hi? hi = mid - 1 or hi = mid? lo = mid + 1 or lo = mid?

when target exists, use

1
while (lo <= hi)

because it will finally concentrate. lo == hi will be the result: hi = mid - 1 or hi = mid? or lo = mid + 1 or lo = mid? does not matter. 对于可能不存在的也用lo <= hi，但要保证hi = mid - 1 和 lo = mid + 1

You use while (start <= end) if you are returning the match from inside the loop. You use while (start < end) if you want to exit out of the loop first, and then use the result of start or end to return the match.

Backtracking

Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, abandons those solutions that fail to satisfy the constraints of the problem at any point of time.

for example: SudoKo N Queens problem, smart at process diagonal row-col and row + col. think recursion as a tree, back and forth.

leetcode summary backtracking about Subsets, Permutations, and Combination Sum

Others

x^y how to describe: x to the power of y x^2: x squard x^3: x cubed

Find rectangle

p1[x,y], p2[x,y] if p1 and p2 are diagonal, check if other 2 points exist, can use hashmap or hashset

Toggle 1 and 0

use xor 1 to toggle 1 and 0

1
2
3
int a = 1
a ^= 1; // a is 0
a ^= 1; // a is 1

calculate power of 2:

1
2
3
Math.pow(2, n); // slow
// or can use shift
1 << n // fast

Union Find

for quick find, all sites in a component must have the same value in id[], directly check id[p] == id[q] for quick union, set the root of pool p to the root of q then improve quick union, compress the path when seach the root:

1
2
3
4
5
6
7
8
9
private int find(int[] uf, int i)
{
  while (uf[i] != i)
  {
    // path compression
    uf[i] = uf[uf[i]];
    i = uf[i];
  }
}

sort

in-place: bobble sort stable selection sort not stable insertion sort stable quick sort not stable heap sort not stable need space: merge sort stable

insertion sort对于partial sorted的数组排序很快。 merge sort O(nlogn) 很稳定，可以用merge sort的思路去divide and conquer解决其他问题 quick sort 最坏O(n^2)，比如排好序的数组，所以需要shuffle: Collections.shuffle(list)

radix sort不是通过comparison机制实现的, leetcode 164

sort one array based on another array

1
2
3
4
5
6
7
8
9
10
11
// sort a based on b
int[] a = new int[]{3,5,7,2,5,78,4,2};
int[] b = new int[]{7,45,2,4,7,78,2,4};

// pair[i][0] = a[i];
// pair[i][1] = b[i];
int[][] pair = new int[a.length][a.length];
Arrays.sort(pair, (a, b) -> a[1] - b[1]);

// or use map <b value: b index>
// the sort b, recreate a using the map mapping

0/1 knapsack

Binary Search Tree

need to know different traverse orders:

  • pre-order: current -> display -> left -> right
  • post-order: current -> left -> right -> display
  • in-order: current -> left -> display -> right, this will get ascending order if traverse a BST.
  • out-order: current -> right -> display -> left, this will get descending order if traverse a BST

pre order list can build BST uniquely. (post)pre order + in order can build BT uniquely

threaded binary search tree

LC 99: https://leetcode.com/problems/recover-binary-search-tree/submissions/ video: morris traversal inorder to binary tree: 不用递归的方式，实现constant space的一种traverse https://www.youtube.com/watch?v=wGXB9OWhPTg https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

Undirected graph

vertex and edge matters degree: num of edge connect to a vertex graph API design:

1
2
3
4
addEdge()
Iterable adjacent nodes
numEdge()
numVertex()

How to repesent vertex and it’s edge, here use adjacency list 如果发现graph的node是连续的，比如0 ~ n-1则用adjacency list比较好，否则用Map<Integer, List<Integer>>

1
2
3
4
5
6
7
8
9
10
// generic array
List<Integer>[] adj = (List<Integer>[]) new List[n];
// it seems we can do now:
List<Integer>[] adj =  new List[n];
TreeMap<Integer, Integer>[] tmap = new TreeMap[n];
// init
for (int i = 0; i < n; i++)
{
  adj[i] = new ArrayList<Integer>();
}

actually we can use list of list instead of this format, but array is faster. how to create an array of list

may contains: self-loop parallel edges

BFS

use queue to hold the vertices add all unmarked vertices to queue adjacent to v and mark them

1
2
3
boolean[] marked;
int[] edgeTo;
int[] distTo;

time complexity: O(E + V)

DFS

for example, find exit for maze graph mark vertex has visited recursive (or use stack )visit all unmarked vertices w adjancent to v

1
2
boolean[] marked;
int[] edgeTo;

time complexity: O(E + V)

Bridge

leetcode: 1192 这是一种找bridge的算法: Tarjan algorithm 可以看看这个频道的graph theory playlist: https://www.youtube.com/watch?v=aZXi1unBdJA https://www.youtube.com/watch?v=TyWtx7q2D7Y

Connected components

a connected component is a max pool of connected vertices answer the question: is v and w connected in contact time.

DFS? yes, run DFS for each unvisited vertex, verteice in same connected component has the same id (this can represent component number!), so, check vertex id will get result.

Directed graph

also called digraph outdegree, indegree directed cycle

DAG: directed acyclic graph

Unweighted

without weight on edge, the same for DFS and BFS we use adjacency list the same as undirected graph

1
List<Integer>[] adj;

topological sorting

for example, precedence scheduling at least one vertex has 0 indegree and should be directed acyclic graph (DAG)

BFS: 从indegree为0的node开始，压入队列中，每次下一个node的indegree减1，再把下一批indegree为0的node压入队列中，最后如果没有cycle，所有node都应该被explored.

DFS也可以，但要注意visited用2种记号表示, 0:没有访问，1:当前访问, 2:完全访问。如果在一次DFS中再次遇到了1，则说明有cycle.当完全访问后，再设置成2.

strongly connected component

Strongly connected: there is a path from v to w and w to v as well. skip this topic

Weighted

API design:

1
2
3
4
class DirectedEdge: weight, from, to
class EdgeWeightedDigraph: addEdge(new DirectedEdge(from, to, weight));
distTo(int w);
pathTo(int w);

we still use adjacency list representation:

1
2
3
List<DirectedEdge>[] adj = (List<DirectedEdge>[]) new List[n];
// new init array
List<DirectedEdge>[] adj = new List[n];

Dijkstra

non-negative weight SPT: shortest path tree exist in graph from the source vertex

remember: Use minium priority queue, to choose the next vertex cloest to the source vertex! Then update the path accordingly if it’s shorter than before (如何实现这个degrade呢?) implementation

有几点需要注意：

  1. 它没有实现degrade操作，只是又加入了新的元素在pq中，这样旧的就沉到底部了
  2. 有一个visited set去控制结束
  3. 注意comparator interface是怎么实现的，override了compare method，其实也用不着，在pq初始化的时候可以用lambda去实现。

time complexity of the construct computation: O(ElogV)

Bellman-Ford

no negative cycle

A*

A graph traversal and path search algorithm leetcode 1263

regular expression

leetcode 819 去掉所有非字典字母，然后split每个word组成数组:

1
String[] words = p.replaceAll("\\W+" , " ").toLowerCase().split("\\s+");
0%