APIs To Learn Flashcards
1
Q
vLeast Integer
A
Integer.MIN_VALUE
2
Q
Greatest Integer
A
Integer.MAX_VALUE
3
Q
Greater of two numbers
A
Math.max(double, double)
4
Q
add collection to other collection
A
::addAll(Collection c)
5
Q
char[] from String
A
String::toCharArray
6
Q
check if char is numeric
A
Character.isDigit(char)
7
Q
Eulerian Path on Undirected Graph
A
Either every vertex has even degree
-or-
exactly two vertices have odd degree
8
Q
Eulerian Circuit on Undirected Graph
A
Every vertex has an even degree
9
Q
Eulerian circuit on directed graph
A
Every vertex has an equal in degree and out degree
10
Q
Eulerian Path on Directed Graph
A
At most 1 vertex with one more out degree than in degree
- and -
at most 1 vertex with one more in degree than out degree
- and -
all other vertices have equal in and out degrees
11
Q
number of chars in string
A
String::length()
12
Q
get “bcde” from “abcde”
A
“abcde”.substring(1) // NOTE ALL LOWER CASE
13
Q
get “bcd” from “abcde”
A
“abcde”.substring(1,4) // begin index is inclusive, end index is not inclusive NOTE ALL LOWER CASE
14
Q
insert element into Set
A
Set.add(element)
15
Q
Get any element from Set
A
Set::iterator::next
16
Q
concrete implementation of stack
A
Stack
17
Q
Boxed Object for char
A
Character
18
Q
number of elements in list
A
List::size
19
Q
sort int[] (and complexity)
A
Arrays.sort(int[] a), O(n log(n))
20
Q
copy an int[]
A
Arrays.copyOf(int[] original, int newLength)
21
Q
sort int[] range (and complexity)
A
Arrays.sort(int[] a, int fromIndex, int toIndex) O(n log(n)), fromIndex is inclusive, toIndex is exclusive
22
Q
parse int value from char
A
Character.getNumericValue(c)
23
Q
check if map has any key value mappings
A
Map::isEmpty
24
Q
remove key value mapping from map
A
Map.remove(Object key)
25
put element in set
Set.add(Object o)
26
increment a maybe null map key with default
int count = m.getOrDefault(k, d);
m.put(k, count + 1);
or
m.compute(k, (k, count) -> count == null ? 1 : count+1);
27
int to String
String.valueOf(int n) or specific implementation Integer.toString(int n)
28
Data Structure that maintains unique elements with order
TreeSet
29
least element in TreeSet
treeSet::first
30
greatest element in TreeSet
treeSet::last
31
TreeSet least element strictly greater than the given element (or null if not exist)
treeSet.higher(E e)
32
TreeSet greatest element strictly less than the given element, or null if there is no such element.
treeSet.lower(E e)
33
Queue that maintains order based on Comparator
new PriorityQueue(Comparator comparator)
34
Comparator Signature
```
int compare(T o1, T o2)
Returns: a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
```
35
Look at top of Stack without removing
Stack::peek
36
square root
Math.sqrt(double a)
37
raise to power
Math.pow(double a, double b)
38
Integer Comparator
Integer::compare
39
Array Literal
new int[]{-1, -1}
40
get int[][] from List
list.toArray(new int[0][]); using new int[0][] is strangely much faster than a sized array: https://shipilev.net/blog/2016/arrays-wisdom-ancients/#_conclusion
41
Disjoint Set
```
Node class with Union and Find operations, can track tree number with external variable
Union / Find may be linear with a naïve implementation, but with union by rank and path compression are effectively constant
```
42
Disjoint Set: union by rank
every node starts with rank 1.
Whenever nodes are unioned, if their rank is equal increment the root rank and add the other under it.
In all other cases, just add the lesser under the greater.
43
Disjoint Set Path Compression
in find operator, if the node's parent is a root node, return that parent. Otherwise, return the assignment:
return this.parent = this.parent.find();
44
Create comparator for object property
Comparator.comparing(Function keyExtractor)
45
Reverse a comparator
comparator.reversed()
46
combine comparators
comparator.thenComparing(Comparator other)
47
What happens when Map::get missing key
return null
48
max signed int in scientific notation
2*10^9
49
max signed long in scientific notation
9*10^18
50
Map implementation that maintains order of keys (and time costs)
TreeMap log(n) time cost for the containsKey, get, put and remove
51
TreeMap least key greater than or equal to the given key
treeMap.higherKey(K key) (or null if not exist) (also higherEntry)
52
TreeMap greatest key less than or equal to the given key
treeMap.lowerKey(K key) (or not exist) (also lowerEntry)
53
Breadth First Search
Iterate with Queue, check for visited with HashSet (or visited property)
time complexity O(v+e)
space complexity O(v)
can optimize with dual start (but same time complexity)
54
Queue concrete implementation
LinkedList
55
Depth First Search
iterate with recursion (or stack), check for visited with HashSet (or visited property)
time complexity O(v+e)
space complexity O(v) but in practice can be less than BFS (e.g. tree is log(v))
56
Topological Sort
Kahn's Algorithm
repeatedly remove nodes with 0 indegree from graph, add them to the ordering, and enqueue children with newly 0 indegree to queue for subsequent removal
57
count of leafs in perfect binary tree (or number at level) where height at root is 0
2^height
58
count of nodes in perfect binary tree where height at root is 0
2^(height + 1) - 1
59
binary search
select a left and right window
while left <= right, select middle pivot
bring left or right in depending on which side of pivot
60
find Eulerian Path / Circuit
Hierholzer's algorithm
start from valid starting node (for path, outdegree greater)
dfs (with recursion) until run out of outgoing edges (mark visited)
backtrack up the recursion stacks adding edges to solution until find an unvisited outgoing edge, then replay from there
61
Minimum Spanning Tree
Kruskal’s Minimum Spanning Tree Algorithm
Sort the edges by weight
iterate through smallest edge. Check if it forms a cycle with the spanning tree formed so far (union find). If roots are unique, include this edge. Else, discard it.
repeat until v-1 edges
62
Closed form for sum of numbers from 0 to n
Gauss' Formula: n(n+1)/2
63
find entrance to cycle in linked list
Floyd's Tortoise and Hare:
start two pointers at head, jump the hare 2x as fast
if there is a cycle, they will meet
if they meet, reset one index and then increment both at 1x speed
the index of the second meeting is the entrance to the cycle
64
Triangle Number
n (n+1) / 2
65
Java map key type with 2 instead of 1 input
Pair<>
66
how to create hashmap that doesn't get rehashed and why
new HashMap( (int) maxCapacity / 0.75), because 0.75 is the default load factor and rehash happens at capacity * load factor
67
initialize int array with size
new int[size]
68
check if character is alphabetic
Character.isLetter(char c)
69
check if character is upper case
Character.isUpperCase(char c)
70
check if character is lower case
Character.isLowerCase(char c)
71
change character to upper case
Character.toUpperCase(char c)
72
lower case version of character
Character.toLowerCase(char c)
73
remove last character from StringBuffer
StringBuffer.deleteCharAt(sb.length()-1)
74
create list from int[]
Arrays.stream(nums).boxed().collect(Collectors.toList())
75
swap elements in list
Collections.swap(List list, int i, int j)
76
count of elements in triangle number for n
n (n+1) / 2
77
remove last element of (java standard library) LinkedList
LinkedList::removeLast
78
formula for number of sub-combinations of size r from set with size n
n! / r! (n-r)! recursively multiply the options * options-1 up to set size but also divide by orderings
79
formula for number of permutations of size r from n distinct objects
n! / (n-r)! recursively multiply the options * options-1 up to set size
80
formula for ways to arrange n objects
n!
81
formula for number of subsets in a set with size n
2^n for every element, you either include it or you don't
82
number of chars in stringbuffer
StringBuffer::length
83
delete string range from StringBuffer
StringBuffer.delete(int start, int end)
84
get element from array that occurs more than length / 2 times
Boyer-Moore Voting Algorithm
maintain a candidate and a count
for each elemenet, increment the count if equal else decrement the count
if count hits 0, reset with next candidate
run second time to check full count (could be less than 1/2)
85
copy range from java array to new array
Arrays.copyOfRange(int[] array, int from, int to) where to is exclusive
86
Merge Sort Algorithm
if length is 1, return self
else split into halves
recursively merge sort both halves
combine the halves
87
Quick Sort Algorithm
if list size is 1, return list
else pick an element as pivot (right most is convenient)
rearrange the list such that everything greater than pivot is to the right of pivot (swapping and shifting pivot)
recursively call quick sort on left side and right side (if exist)
87
Quick Sort Algorithm
if list size is 1, return list
else pick an element as pivot (right most is convenient)
rearrange the list such that everything greater than pivot is to the right of pivot (swapping and shifting pivot)
recursively call quick sort on left side and right side (if exist)
88
get entries from hashmap
HashMap::entrySet
89
empty out a set
Set::clear
90
get subarray of array
Arrays.copyOfRange(T[] array, int beg, int end)
91
first n elements from stream
Stream<>.limit(int n)
92
sort a stream
Stream<>.sorted(Comparator)
93
Stream to int[]
stream.mapToInt(i -> i).toArray();
94
retain only unique elements in stream
Stream::distinct
