Algorithm Examples

English | Korean

This repository is an implementation of algorithms, data structures, and problem-solving. These are written in C++, Python, and Java, and each language uses the following test framework: Google Test(C++), pytest(Python), JUnit(Java). Run tests to perform methods/functions on the algorithmic logic. GitHub Actions workflows that build and test code run manually.

Project Environments

Each project is configured in specific environments, as described below:

• C++ project: C++20 / CMake build / GNU Scientific Library (GSL), Google Test, Google Benchmark, fmt packages / vcpkg package manager
• Python project: Python 3.11 / Poetry / NumPy, SciPy, NetworkX, pytest, pytest-benchmark packages
• Java project: Java 17 / Gradle build / JUnit, Java Microbenchmark Harness (JMH) libraries

Table of Contents

• Data structures
  • 🚋 Array
  • 📈 Graph
  • 🔑 Hash table
  • 🚀 Heap
  • 🖇️ Linked list
  • 🚶 Queue
  • 🍔 Stack
  • 🌳 Tree
• Topics
  • 🧩 Dynamic programming
  • 🕘 Greedy
  • 📐 Mathematics
  • 🔢 Primitive type
  • 🔍 Search
  • 🔤 Sort
  • 📄 String
• References

Data structures

🚋 Array

C++ declaration/methods

auto v = std::vector{1, 2, 3, 4, 5};
auto sub_v = std::vector<int>{v.begin(), v.end() - 1};
auto arr = std::array{1, 2, 3, 4, 5};
auto sub_arr = std::array{arr.begin(), arr.end() - 1};

// algorithm
std::ranges::any_of(v, [](auto x) { return x % 2 == 0; })
std::ranges::all_of(v, [](auto x) { return x % 2 == 0; })
std::ranges::none_of(v, [](auto x) { return x % 2 == 0; })
std::ranges::for_each(v, [](auto x) { std::cout << x << " "; }).fun
std::ranges::count(v, 42)
std::ranges::count_if(v, [](auto x) { return x % 2 == 0; })
std::ranges::reverse(v)
std::ranges::rotate(v, v.end() - k)
std::ranges::sort(v)
std::ranges::min_element(v)
std::ranges::max_element(v)
std::ranges::minmax_element(v)

Python declaration/functions

# list
number_list: list[int] = [1, 2, 3, 4, 5]
append(6), insert(3, 3), remove(4), pop(), pop(0), index(3), count(3), clear(), extend([6, 7, 8])
number_list.reverse()   # in-place
reversed(number_list)   # return an iterator
number_list.sort()      # in-place
sorted(number_list)     # return a new list(copy)
del(number_list[0])     # delete the first element
del(number_list[0:2])   # removes the slice
bisect.bisect_left(number_list, 3), bisect.bisect_right(number_list, 3), bisect.bisect(number_list, 3)
bisect.insort_left(number_list, 3), bisect.insort_right(number_list, 3), bisect.insort(number_list, 3)

# tuple
sample_tuple: tuple[int] = (1, 2, 3, 4, 5)
index(3), count(3)

### list comprehension
# single level of loop
even_list = [x for x in number_list if x % 2 == 0]
# two levels of loop
sample_list = [[1, 2, 3], [4, 5, 6]]
square_list = [[n ** 2 for n in row] for row in sample_list]
# multi levels of loop
list_a: list[int] = [1, 3, 5]
list_b: list[str] = ['a', 'b']
set_ab: set[tuple[int, str]] = {(a, b) for a in list_a for b in list_b}
# 2d array to 1d array
list_2d = [['a', 'b', 'c'], ['d', 'e', 'f']]
list_1d: list[str] = [ch for row in list_2d for ch in row]
# any/all
any(x % 2 == 0 for x in number_list)
all(x % 2 == 0 for x in number_list)

Java declaration/methods

var arr = new int[]{1, 2, 3, 4, 5};

// 2d array (m by n matrix)
var matrix = new int[m][n];

// Arrays
import java.util.Arrays;
binarySearch(arr, 3), equals(arr, another_arr), copyOf(arr, arr.length), copyOfRange(arr, from, to),
sort(arr), sort(arr, from, to), fill(arr, 42), fill(arr, from, to, 42),
// Arrays.stream()
anyMatch(x -> x % 2 == 0), allMatch(x -> x % 2 == 0), noneMatch(x -> x % 2 == 0),
count(), sum(), min(), max(), average(), map(x -> x * 2).toArray(), filter(x -> x % 2 == 0).count()

// Collections
import java.util.Collections;
sort(list), binarySearch(list, 3), min(list), max(list), swap(list, 0, 1), replaceAll(list, 1, 2),
frequency(list, 1), reverse(list), rotate(list, 1), shuffle(list), unmodifiableList(list)

// list
import java.util.Comparator;
import java.util.List;
var list = Arrays.asList(boxedArray);
Arrays.stream(arr).boxed().collect(Collectors.toList())
sort(), sort(Comparator.naturalOrder()), sort(Comparator.reverseOrder())

// string
String.join(", ", arr)                          // array to string
str.split(""), str.split(" "), str.split(", ")  // string to array
str.toCharArray()                               // string to char array
str.chars().toArray()                           // string to int array

// boxing
var v = Arrays.stream(arr).boxed().toArray(Integer[]::new);                     // int[] to Integer[]
var v = Arrays.stream(arr).mapToObj(String::valueOf).toArray(String[]::new);    // int[] to String[]
var v = Arrays.stream(arr).boxed().collect(Collectors.toList());                // int[] to List<Integer>

// integer sequence
var arr = IntStream.range(0, speeds.length).toArray();          // range to int array in [0, n)
var arr = IntStream.rangeClosed(1, speeds.length).toArray();    // range to int array in [1, n]
var list = IntStream.range(0, speeds.length).boxed().collect(Collectors.toList());  // range to list

var list = List.of(arr);        // array to list
var list = Arrays.asList(arr);  // array to list
var arr = strList.toArray(String[]::new);  // List<String> to String[]
var arr = intList.stream().mapToInt(Integer::intValue).toArray();  // List<Integer> to int[]
var list = Arrays.stream(arr).boxed().sorted().collect(Collectors.toCollection(ArrayList::new));    // array to sorted list

Examples

• Advancing through an array, EPI#5.4: c++ | Advance through the array to the last index.
• Arbitrary precision operation - increment an arbitrary-precision integer, EPI#5.2: c++(PlusOne) | Add one to the number represented by the vector.
• Arbitrary precision operation - add two arbitrary-precision integers: c++((StringAddition)) | Add two numbers represented by strings.
• Arbitrary precision operation - multiply two arbitrary-precision integers, EPI#5.3: c++(Multiply) | Multiply two numbers represented by vectors.
• Delete duplicates from a sorted array, EPI#5.5: c++(DeleteDuplicates) | Delete duplicate elements in the array.
• Delete duplicates from a sorted array: c++(DeleteDuplicateElements) | Delete duplicate elements in the array.
• Delete specific elements from a sorted array: c++(DeleteSpecificElements) | Delete specific elements in the array.
• Dutch national flags problem, EPI#5.1: c++
• Enumerate prime numbers, EPI#5.9: c++ | Enumerate prime numbers in the range.
• Order elements in an array by even and odd: c++(EvenOdd) | Order even and odd numbers in the array.
• Order elements in an array by specified order, EPI#5.8: c++(Rearrange) | Rearrange arrays to have a specific order.
• Random data sampling - offline, EPI#5.12: c++(OfflineRandomSampling) | Randomly select k elements from the array.
• Random data sampling - compute permutation, EPI#5.14: c++(ComputeRandomPermutation) | Compute permutation of the array generated by random sampling.
• Replace elements - replace and remove: c++(ReplaceAndRemoveString1) | Replace element and remove element in the array. Keep the array size.
• Replace elements - replace and remove: c++(ReplaceAndRemoveString2) | Replace element and remove element in the array
• Replace elements - telex encoding: c++(TelexEncoding) | Telex encoding for punctuation marks.
• Stock trading - buy and sell a stock once, EPI#5.6: c++(BuyAndSellStockOnceBruteForce, BuyAndSellStockOnce)
• Stock trading - buy and sell a stock twice, EPI#5.7: c++(BuyAndSellStockTwice)

🔼 back to toc

📈 Graph

• Shortest path algorithm
  • Single-source: Bellman-Ford algorithm, Dijkstra's algorithm
  • Single-pair: A* search algorithm
  • All-pair: Floyd-Warshall algorithm, Johnson's algorithm
• Minimum spanning tree algorithm: Kruskal's algorithm, Prim's algorithm
• Maximum flow algorithm: Edmonds-Karp algorithm, Ford-Fulkerson algorithm, Push-relabel algorithm, Maximum bipartite matching

Graph algorithms

• A* search algorithm: A single-pair shortest path algorithm. This is a variant of Dijkstra's algorithm using heuristics to try to speed up the search.
• Bellman-Ford algorithm: c++, java | A single source shortest path algorithm that can handle negative edge weights. It finds the shortest path from a source vertex to all other vertices in a weighted graph.

algorithm BellmanFord(G, source):
    // Initialize single source
    for each u in G.V:
        u.distance = ∞
        u.parent = NIL
    source.distance = 0

    for i = 0 to |G.V| - 2:
        for each edge (u, v) in G.E:
            // Relaxation
            if v.distance > u.distance + w(u, v):
                v.distance = u.distance + w(u, v)
                v.parent = u

    for each edge (u, v) in G.E:
        if v.distance > u.distance + w(u, v):
            return false
    return true

• Breadth-first search (BFS), CCSP#4.3.1: c++, java, python(test) | A search algorithm that traverses a graph layer by layer. Check the shortest path and compute the distance from the source vertex to all other vertices.

algorithm BFS(G, source):
    for each u in G.V:
        u.color = WHITE
        u.distance = ∞
        u.parent = NIL
    source.color = GRAY
    source.distance = 0
    source.parent = NIL
    Queue = ∅
    Queue.enqueue(source)

    while Queue != ∅:
        u = Queue.dequeue()
        for each v in G.Adj[u]:
            if v.color == WHITE:
                v.color = GRAY
                v.distance = u.distance + 1
                v.parent = u
                Queue.enqueue(v)
        u.color = BLACK

• Depth-first search (DFS): c++, java | A search algorithm that traverses a graph by exploring as far as possible along each branch before backtracking. Check to exists cycle in a graph.

algorithm DFS(G):
    for each u in G.V:
        u.color = WHITE
        u.parent = NIL
    time = 0
    for each u in G.V:
        if u.color == WHITE:
            DFS-VISIT(G, u)

algorithm DFS-VISIT(G, u):
    time = time + 1               // discovered
    u.discovered = time
    u.color = GRAY
    for each v in G.Adj[u]:
        if v.color == WHITE:
            v.parent = u
            DFS-VISIT(G, v)
    u.color = BLACK
    time = time + 1               // finished
    u.finished = time

• Dijkstra's algorithm: c++, java | A single source shortest path algorithm that handle non-negative edge weights. It find the shortest path between two vertices in a graph.

algorithm Dijkstra(G, source):
    // Initialize single source
    for each u in G.V:
        u.distance = ∞
        u.parent = NIL
    source.distance = 0

    Set = ∅
    Queue = G.V
    while Queue != ∅:
        u = EXTRACT-MIN(Queue)
        Set = Set ∪ {u}
        for each v in G.Adj[u]:
            // Relaxation
            if v.distance > u.distance + w(u, v):
                v.distance = u.distance + w(u, v)
                v.parent = u

• Edmonds-Karp algorithm
• Floyd-Warshall algorithm: java | A all pairs shortest paths algorithm.

algorithm InitializeAdjacencyMatrix(G):
    d = matrix of size |G.V| × |G.V|
    for each u in G.V:
        for each v in G.V:
            if u == v:
                d[u][v] = 0
            else if (u, v) in G.E:
                d[u][v] = w(u, v)
            else:
                d[u][v] = ∞
    return d

algorithm FloydWarshall(G):
    d = InitializeAdjacencyMatrix(G)
    for k = 0 to |G.V| - 1:
        for i = 0 to |G.V| - 1:
            for j = 0 to |G.V| - 1:
                dᵏ[i, j] = MIN(dᵏ⁻¹[i, j], dᵏ⁻¹[i, k] + dᵏ⁻¹[k, j])
    return d

• Ford-Fulkerson algorithm
• Johnson's algorithm: A all pairs shortest paths algorithm. This is a combination of Dijkstra's algorithm and the Bellman-Ford algorithm. It may be faster than Floyd–Warshall on sparse graphs.
• Kruskal's algorithm: java | A minimum spanning tree algorithm. It finds a minimum spanning forest of an undirected edge-weighted graph. The algorithm uses path compression (FIND-SET) and union by rank (UNION) to improve the performance.

algorithm Kruskal(G, w):
    Set = ∅
    for each v in G.V:
        MAKE-SET(v)                                 // initialize vertice
    for each edge (u, v) in G.E ordered by w(u, v), increasing:
        if FIND-SET(u) != FIND-SET(v):
            Set = Set ∪ {(u, v)}
            UNION(u, v)                             // combine trees
    return Set

• Maximum bipartite matching
• Prim's algorithm: java | A minimum spanning tree algorithm. It is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.

algorithm Prim(G, root):
    for each u in G.V:
        u.key = ∞
        u.parent = NIL
    root.key = 0
    Queue = G.V                                       // queue is a min priority queue
    while Queue != ∅:
        u = EXTRACT-MIN(Queue)
        for each v in G.Adj[u]:
            if v in Queue and w(u, v) < v.key:
                v.parent = u
                v.key = w(u, v)

• Push-relabel algorithm
• Viterbi algorithm: A shortest stochastic path algorithm. It solves with additional probabilistic weights on each node.

Examples

• Maze problem: java | A maze problem is that find a path from the start to the goal. The maze is represented by a graph. The start and the goal are represented by vertices. The path is represented by a sequence of vertices.
• Minimum spanning tree (Kruskal, Prim, Boruvka), CCSP#4.4.2: python(test) | Find the minimum spanning tree of a graph.

🔼 back to toc

🔑 Hash table

C++ declaration/methods

// map
auto map = std::unordered_map<std::string, int>{{"a", 1}, {"b", 2}};
insert({"c", 3}), emplace("d", 4), find("b"), end(), erase("a"), size(), empty()

// set
auto set = std::unordered_set{1, 2, 3, 4, 5};
insert(42), emplace(42), find(42), end(), erase(42), size(), empty()

// tuple
auto t1 = std::tuple{-1, -1};
auto t2 = std::make_tuple(-1, -1);
auto [x, y] = t1;

// transform
std::ranges::transform(nums, std::inserter(map, map.end()),
    [i = 0](auto num) mutable { return std::pair{num, i++}; });

Python declaration/functions

# set
number_set: set[int] = set()
add(1), update([2, 3, 4])

# dictionary
sample_dict: dict[str, int] = {'a': 1, 'b': 2, 'c': 3}

# defaultdict
sample_dict: collections.defaultdict[str, int] = collections.defaultdict(int)
sample_dict['a'] = 1
sample_dict.update({'b': 2, 'c': 3})

# counter
sample_counter: collections.Counter = collections.Counter()
sample_counter.update([1, 1, 2, 2, 3])

Java declaration/methods

// map
import java.util.HashMap;
var map = new HashMap<String, Integer>();
put("a", 1), putIfAbsent("b", 2), get("a"), getOrDefault("f", 6), remove("a"), size(), isEmpty(),
keySet(), values(), entrySet(), containsKey("a"), containsValue(1), replace("a", 2), clear()
var keys = map.keySet().toArray(String[]::new);
var values = map.values().toArray(Integer[]::new);

// set
import java.util.HashSet;
var set = new HashSet<Integer>();
add(1), remove(1), size(), isEmpty(), contains(1), clear(), iterator()
var arr = set.toArray(Integer[]::new);

// unmodifiable
import java.util.Collections;
Collections.unmodifiableMap(map);
Collections.unmodifiableSet(set);
Collections.unmodifiableSortedMap(map);
Collections.unmodifiableSortedSet(set);

// stream
int[] result = map.entrySet().stream()
        .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
        .map(Map.Entry::getKey)
        .mapToInt(Integer::parseInt)
        .toArray();

Examples

• Anonymous letter constructible, EPI#12.2: c++(IsLetterConstructibleFromMagazine) | Check if a letter can be written using the characters in a magazine.
• Anonymous words constructible: c++(IsWordConstructibleFromMagazine) | Check if a letter can be written using the words in a magazine.
• Collatz conjecture, EPI#12.11: c++(FindNumbersSatisfyingCollatzConjecture) | Find the numbers satisfying the Collatz conjecture.
• Find anagrams: c++(FindAnagramMappings) | Given an array of strings, group anagrams together.
• Find smallest subarray covering all values, EPI#12.6: c++(FindSmallestSubarrayCoveringSubset) | Find the smallest subarray that covers all the elements in a set.
• Find smallest subarray sequentially covering all values, EPI#12.7: c++(FindSmallestSubarraySequentiallyCoveringSubset) | Find the smallest subarray that sequentially covers all the elements in a set.
• ISBN cache, EPI#12.3: c++ | Implement a LRU (Least Recently Used) cache for ISBN lookups.
• Nearest repeated entry, EPI#12.5: c++(FindNearestRepeatedEntry) | Find the nearest repeated entry in an array of strings.
• Optimized lowest common ancestor, EPI#12.4: c++(FindOptimizedLowestCommonAncestor) | Find the lowest common ancestor of two nodes in a binary tree using a hash table. This traverses together until node1 and node2 meet.
• Palindromic permutation, EPI#12.1: c++(IsPalindromePermutation) | Given a string, determine if a permutation of the string could form a palindrome.

🔼 back to toc

🚀 Heap

A min-heap/max-heap is ideal for maintaining a collection of elements when we need to add arbitrary values and extract the smallest/largest element.

C++ declaration/methods

auto queue = std::priority_queue<int>{};    // max heap
auto queue = std::priority_queue<int, std::vector<int>, std::greater<int>>{};   // min heap
push(1), emplace(2), pop(), top(), size(), empty()

Python declaration/functions

number_list: list[int] = [5, 4, 3, 2, 1]
heapq.heapify(number_list)
heapq.nlargest(3, number_list), heapq.nsmallest(3, number_list)
heapq.heappush(number_list, 6), heapq.heappop(number_list), heapq.heapreplace(number_list, 0)

Java declaration/methods

import java.util.PriorityQueue;
var queue = new PriorityQueue<Integer>();
var queue = new PriorityQueue<Integer>(Collections.reverseOrder());
add(1), peek(), poll(), remove(), size(), isEmpty(),
contains(1), clear(), iterator()

Heap algorithms

• Fibonacci heap

Examples

• Compute the k closest stars: c++(FindClosestStar) | Find the $k$ closest stars to the earth. The stars are represented by a sequence of points(coordinates).
• Compute the median of a sequence of numbers: c++(FindMedian) | Find the median of a sequence of numbers. The median is the number separating the higher half of a data sample from the lower half.
• Merge sorted arrays: c++(MergeSortedArray) | Merge k sorted arrays into one heap.
• Sort an increasing-decreasing array: c++(SortIncreasingDecreasingArray) | Sort an array that is repeatedly increasing then decreasing.

🔼 back to toc

🖇️ Linked list

In Python, there is no built-in type or library for LinkedList.

C++ declaration/methods

auto list = std::list{1, 2, 3};   // doubly linked list
push_front(4), emplace_front(5), push_back(6), emplace_back(7),
pop_front(), pop_back(), reverse(), sort(), insert(list.begin(), 11),
emplace(list.end(), 12), splice(list.end(), std::list{8, 9, 10})

auto list = std::forward_list{1, 2, 3};   // singly linked list
push_front(4), emplace_front(5), pop_front(), reverse(), sort()

Java declaration/methods

// doubly linked list
import java.util.LinkedList;
var list = new LinkedList<Integer>();
add(1), addAll(List.of(2, 3, 4, 5)),
remove(0), removeFirst(), removeLast(), removeIf(x -> x % 2 == 0), subList(1, 3),
get(0), getFirst(), getLast(), size(), isEmpty(), contains(1), containsAll(List.of(1, 2, 3)),
iterator(), listIterator()

// dynamically resized array
import java.util.ArrayList;
var list = new ArrayList<Integer>();
add(1), addAll(List.of(2, 3, 4, 5)), remove(0), subList(1, 3),
get(0), size(), isEmpty(), contains(3), containsAll(List.of(3, 4)),
iterator(), listIterator()

Examples

• Add list-based integers, EPI#7.13: c++(AddTwoNumbers) | Add two numbers represented by linked list.
• Delete a node from linked list, EPI#7.6: c++(DeleteNodeFromList) | Delete a node from a linked list.
• Delete duplicate nodes from sorted linked list, EPI#7.8: c++(DeleteDuplicateNode) | Delete duplicate nodes from a sorted linked list.
• Delete the k-th last node from linked list, EPI#7.7: c++(DeleteNodeKthLast) | Delete the $k$-th last node from a linked list.
• Implement cyclic right shift for a singly linked list, EPI#7.9: c++(CyclicallyRightShiftList) | Implement cyclic right shift for a singly linked list.
• Linked list has a cycle, EPI#7.3: c++(HasCycle1, HasCycle2, HasCycle3) | Determine that a linked list has a cycle.
• List pivoting, EPI#7.12: c++(ListPivoting) | Rearrange nodes smaller than pivot to the left and larger than pivot to the right.
• Merge even and odd nodes in linked list, EPI#7.10: c++(MergeEvenOddLinkedList) | Merge even and odd nodes in a singly linked list.
• Merge two sorted linked lists, EPI#7.1: c++(MergeTwoSortedLinkedList) | Merge two sorted linked lists. In worst-case, this task has $O(n + m)$ time complexity, where $n$ and $m$ are the length of the lists.
• Palindrome list, EPI#7.11: c++(IsListPalindrome) | Determine that a linked list is a palindrome.
• Reverse a single sublist, EPI#7.2: c++(ReverseSubList) | Reverse a single sublist of a linked list.
• Two linked lists overlap, EPI#7.4: c++(OverlappingNoCycleList) | Determine that two linked lists without cycle overlap.
• Two linked lists with cycles overlap, EPI#7.5 c++(OverlappingCycleList) | Determine that two linked lists with cycle overlap.

🔼 back to toc

🚶 Queue

C++ declaration/methods

auto container = std::queue<int>{};
push(1), emplace(2), pop(), front(), back(), size(), empty()

auto container = std::deque<int>{};
push_back(1), emplace_back(2), push_front(3), emplace_front(4),
pop_back(), pop_front(), front(), back(), size(), empty()

Python declaration/functions

deque: collections.deque = collections.deque([1, 2, 3, 4, 5])
deque[0], deque[-1]
append(6), appendleft(7), pop(), popleft()

Java declaration/methods

import java.util.ArrayDeque;
var deque = new ArrayDeque<Integer>();
add(1), remove(), pop(), size(), isEmpty(), contains(1), clear(),
offerFirst(6), offerLast(7), pollFirst(), pollLast(), peekFirst(), peekLast(),
addFirst(8), addLast(9), removeFirst(), removeLast(), getFirst(), getLast(),
iterator(), descendingIterator()

var array = deque.toArray(Integer[]::new);  // deque to array
var list = new ArrayList<>(deque);          // deque to list

Examples

🔼 back to toc

🍔 Stack

C++ declaration/methods

auto stack = std::stack<int>{};
push(1), emplace(2), pop(), top(), size(), empty()

Python declaration/functions

# use list type
stack: list[int] = [1, 2, 3]
stack[-1], len(stack)
append(4), pop()

Java declaration/methods

import java.util.Stack;
var stack = new Stack<Integer>();
push(1), add(1, 2), addAll(anotherList), pop(), peek(), size(), isEmpty(),
contains(1), search(1), size(),
remove(1), removeIf(x -> x == 1), clear(),
iterator(), listIterator()

var array = stack.toArray(Integer[]::new);  // stack to array
var list = new ArrayList<>(stack);          // stack to list

Examples

• Pair of bracket (CheckPairOfBracket): c++ | Checks if the input string contains bracket pairs and is well-formed.
• Print linked list in reverse order (PrintLinkedListInReverseOrder): c++ | Print the linked list in reverse order using stack.
• Max stack element: c++ | Implement stack that caches max value.

🔼 back to toc

🌳 Tree

The tree is a specific type of graph. A tree is an undirected graph in which any two vertices are connected by exactly one path. It is connected without cycles.

C++ declaration/methods (binary search tree based)

// map
auto map = std::map<std::string, int>{{"a", 1}, {"b", 2}};
insert({"c", 3}), emplace("d", 4), erase("a"), find("b"), size(), empty(), equal_range("c")

// set
auto set = std::set{1, 2, 3, 4, 5};
insert(42), emplace(42), erase(42), find(42), size(), equal_range(3)

Python declaration/functions (binary search tree based)

# sortedcontainers
sort_list = SortedList([1, 2, 3, 4, 5])
sort_set = SortedSet([1, 2, 3, 4, 5])
sort_dict = SortedDict({'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5})

Java declaration/methods (binary search tree based)

// TreeMap (based on red-black tree)
import java.util.TreeMap;
var map = new TreeMap<Integer, Integer>();
var map = new TreeMap<Integer, Integer>(Collections.reverseOrder());
var map = new TreeMap<String, Integer>(Map.of("a", 1, "b", 2, "c", 3));
put("a", 1), putIfAbsent("b", 2), get("a"), getOrDefault("f", 6), remove("a"), size(), isEmpty(),
keySet(), values(), entrySet(), containsKey("a"), containsValue(1), replace("a", 2), clear()
firstKey(), lastKey(), lowerKey("b"), higherKey("b"), floorKey("b"), ceilingKey("b"),pollFirstEntry(), pollLastEntry(),
headMap("c"), tailMap("c"), subMap("a", "c"), descendingMap(), descendingKeySet()

// treeSet (based on red-black tree)
import java.util.TreeSet;
var set = new TreeSet<Integer>();
var set = new TreeSet<Integer>(Collections.reverseOrder());
var set = new TreeSet<Integer>(List.of(1, 2, 3, 4, 5));
add(1), remove(1), size(), isEmpty(), contains(1), clear(), iterator(), descendingIterator(),
first(), last(), lower(3), higher(3), floor(3), ceiling(3), pollFirst(), pollLast(),
headSet(3), tailSet(3), subSet(2, 4), descendingSet()

Properties of Trees

• A tree with $n$ vertices has $n-1$ edges.
• A full $m$-ary tree with $i$ internal vertices contains $n = mi + 1$ vertices. (cf. vertices $n$ = internal vertices $i$ + leaves $l$)
• A full $m$-ary tree with
  • $(i)$ $n$ vertices has $i = (n - 1)∕m$ internal vertices and $l = [(m - 1)n + 1]∕m$ leaves,
  • $(ii)$ $i$ internal vertices has $n = mi + 1$ vertices and $l = (m - 1)i + 1$ leaves,
  • $(iii)$ $l$ leaves has $n = (ml - 1)∕(m - 1)$ vertices and $i = (l - 1)∕(m - 1)$ internal vertices.
• There are at most $m^h$ leaves in an $m$-ary tree of height $h$. $(l = m^h)$
  • If an $m$-ary tree of height $h$ has $l$ leaves, then $h \geq \lceil \log_{m}{l} \rceil$.
  • If the $m$-ary tree is full and balanced, then $h = \lceil \log_{m}{l} \rceil$.

Balanced binary tree

• Depending on the balance: complete binary tree, full binary tree, perfect binary tree
• Balanced binary tree: Red-black tree, AVL tree (from Adelson-Velsky and Landis)

Tree traversal in binary tree

• Preorder traversal (root, left, right): best choice for applications where internal vertices must be explored before leaves.
• Inorder traversal (left, root, right): best choice for applications where internal vertices must be explored in-order.
• Postorder traversal (left, right, root): best choice for applications where leaves need to be explored before internal vertices.

Tree algorithms

• AVL tree
• B-tree: c++ | B-tree is a self-balancing data structure which can have many child nodes. It is commonly used in auxiliary storage devices and database system. B-tree has the following properties: 1) Nodes have lower and upper bounds on the number of keys they can contain. (represent using degree $t$) 2) Every node other than the root must have at least $t-1$ keys. 3) Every node may contain at most $2t-1$ keys.
• Binary search tree: c++ | In binary search tree, all internal nodes are stored in ordered state. If $y$ is a child of $x$ and $y$ is a node in the left subtree, then $y.key \leq x.key$, and if $y$ is a node in the right subtree, then $y.key \geq x.key$.
• Red-black tree
• Trie
• van Emde Boas tree (vEB tree)

Examples

• Balanced tree status: c++ | Whether the binary tree is balanced or not.
• Binary tree exterior: c++(CreateExteriorNodeList) | Create a vector of exterior nodes in a binary tree.
• Construct binary tree from preorder and inorder traversal: c++(ConstructTreeFromPreorderInorder) | Construct a binary search tree from preorder and inorder traversal. This task has $O(n)$ time complexity.
• Construct binary tree from preorder with marker: c++(ConstructTreeFromMarkerPreorder) | Construct a binary search tree from preorder traversal with marker. This task has $O(n)$ time complexity.
• Leaf node list: c++(CreateLeafNodeList) | Create a vector of leaf nodes in a binary tree.
• Lowest common ancestor: c++(FindLowestCommonAncestor) | Find the lowest common ancestor of two nodes in a binary tree.
• Lowest common ancestor with parent pointer: c++(FindLowestCommonAncestor2) | Find the lowest common ancestor of two nodes in a binary tree. The nodes have parent pointers.
• Populate right sibling: c++(PopulateRightSibling) | Populate the right sibling of a binary tree.
• Root to leaf path corresponding to the given sum: c++(HasKeySum) | Whether the tree has a root-leaf path equal to the given sum.
• Sum of root to leaf: c++(SumRootToLeafDecimal, SumRootToLeafBinary) | Sum of all root to leaf paths in a binary tree (decimal and binary representation).
• Tree symmetric: c++ | Whether the binary tree is symmetric or not.

🔼 back to toc

Topics

🧩 Dynamic programming

Examples

• Fibonacci number: c++ | Fibonacci sequence is a sequence of numbers where each number is the sum of the two preceding numbers. Fibonacci number is $n$th number in the sequence. The Fibonacci sequence is defined as follows:
  • $F_0 = 0$
  • $F_1 = 1$
  • $F_n = F_{n-1} + F_{n-2}$ (for $n > 1$)
• Interval subset sum (SubsetSum1, SubsetSum2, DivideAndConquerSubsetSum, DynamicProgrammingSubsetSum): c++ | Interval subset sum problem is that finds the maximum sum of a subset of intervals.
• Longest common subsequence: c++
• Rod cutting: c++ | Rod cutting is a problem of cutting a rod into pieces of a given length to determine the maximum profit.

🔼 back to toc

🕘 Greedy

Examples

• Activity selection: c++ | Activity selection problem using greedy algorithm or recursive approach. This is similar to the Interval scheduling problem.
• Cashier's change: python | Cashier's change problem is that finds the minimum number of coins required to make change for a given amount of money.
• Huffman code: c++ | Huffman code constructs optimal prefix codes. This is always represented by a full binary tree.
• Interval scheduling: python | Interval scheduling problem is that finds the minimum number of intervals required to schedule a set of activities(lectures).

🔼 back to toc

📐 Mathematics

C++ declaration/methods

std::numeric_limits<int>::min(), std::numeric_limits<float>::max(), std::numeric_limits<double>::infinity()
std::abs(-34), std::fabs(-3.14), std::ceil(2.17), std::floor(3.14), std::min(x, -4), std::max(3.14, y), pow(2.17, 3.14), log(7.12), sqrt(225) // cmath

Python declaration/functions

float('inf'), float('-inf'), math.inf, -math.inf
math.fabs(-34.5), math.ceil(2.17), math.floor(3.14), math.max(x, -3), math.min(x, 3.14), math.pow(2.71, 3.15), math.round(3.14), math.sqrt(225) # math

Java declaration/methods

Integer.MIN_VALUE, Float.MAX_VALUE, Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY, Boolean.TRUE
Math.abs(-34.5), Math.ceil(2.17), Math.floor(3.14), Math.max(x, -3), Math.min(x, 3.14), Math.pow(2.71, 3.15), Math.round(3.14), Math.sqrt(225) // math

Mathematical algorithms

• Combination: c++(GenerateCombination) | Find the number of ways to choose $k$ items from $n$ items.
• Fast Fourier transform: Fast Fourier transform is a mathematical algorithm that finds the discrete Fourier transform of a set of real numbers.
• Greatest common divisor (GCD): python, java | Find the greatest common divisor of two numbers.
• Integer factorization: c++, java | Integer factorization is the process of determining which prime numbers divide a given positive integer.
• Least common multiple (LCM): python, java | Find the least common multiple of two numbers.
• Miller-Rabin primality test: c++ | Miller-Rabin primality test is a mathematical algorithm that finds whether a given number is prime.
• Permutation: c++(Permutation) | Find the permutation of a set of items.
• Permutation, EPI#5.10: c++(ApplyPermutationWithAdditionalSpace, ApplyPermutationBySwap) | Permute the elements of an array
• Permutation: c++(InversePermutation)
• Permutation, EPI#5.11: c++(NextPermutation/PreviousPermutation) | Compute the next/previous permutation.
• Permutation, EPI#5.11: c++(KthPermutation) | Compute the $k$-th permutation.
• Prime number: java(isPrime) | Check whether a given number is prime.
• Simplex algorithm: Simplex algorithm is a mathematical algorithm that finds the optimal solution to a linear programming problem.
• System of linear equations: System of linear equations is a mathematical algorithm that finds the solution to a system of linear equations.

Examples

• Base expansion (base $b$ expansion of $n$): python | Constructing the base $b$ expansion of an integer $n$. Such as binary, octal, decimal, hexadecimal expansion, etc.
• Binary operation: python(addition)
• Inverse of matrix: Inverse of matrix is a mathematical algorithm that finds the inverse of a matrix.
• Matrix multiplication: python | This is the product of two matrices.

🔼 back to toc

🔢 Primitive type

C++ declaration/methods

std::to_string(42), std::swap(x, y)
std::numeric_limits<int>::min(), std::numeric_limits<float>::max(), std::numeric_limits<double>::infinity()
std::abs(-34), std::fabs(-3.14), std::ceil(2.17), std::floor(3.14), std::min(x, -4), std::max(3.14, y), pow(2.17, 3.14), log(7.12), sqrt(225) // cmath
std::stoi("42"), std::stod("3.14"), std::stoi("42", nullptr, 16), std::stoi("1000010", nullptr, 2) // string -> int/double/hex/binary
std::bitset<8>(42), std::bitset<8>(3.14), std::bitset<8>(0x42), std::bitset<8>(0b1000010) // int/double/hex/binary -> bitset
std::uniform_int_distribution<int> distribution(1, 6), std::uniform_real_distribution<double> distribution(0.0, 1.0) // random

// random values
std::random_device rd;
std::mt19937 generator(rd());
std::uniform_int_distribution distribution(1, 10);  // integer in [1, 10]
const auto i = distribution(generator);
const auto d = std::generate_canonical<double, 10>(generator);  // floating point number in [0, 1)

Python declaration/functions

float('inf'), float('-inf'), math.inf, -math.inf
math.fabs(-34.5), math.ceil(2.17), math.floor(3.14), math.max(x, -3), math.min(x, 3.14), math.pow(2.71, 3.15), math.round(3.14), math.sqrt(225) # math
abs(-34), min(number_list), max(number_list), sum(number_list), sorted(number_list)
len(sample_string), len(number_list), len(sample_dict)  # length
str(42), str(3.14), str(True)           # int/float/bool -> string
int("42"), float("3.14"), bool("true")  # string -> int/float/bool
int("1000010", 2), int("52", 8), int("2a", 16)  # string -> binary/octal/hex
bin(42), oct(42), hex(42)       # int -> binary/octal/hex
ascii('a'), chr(97), ord('a')   # unicode <-> ascii code

### copy
copy.deepcopy(number_list) # deep copy
copy.copy(number_list)     # shallow copy

### random
random.randrange(28)       # [0, 28)
random.randrange(1, 100)   # [1, 100)
random.randrange(8, 16)    # [8, 16)
random.randrange(8, 16, 2) # [8, 16) with step 2
random.shuffle(number_list)
random.choice(number_list)

Java declaration/methods

Integer.MIN_VALUE, Float.MAX_VALUE, Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY, Boolean.TRUE
Math.abs(-34.5), Math.ceil(2.17), Math.floor(3.14), Math.max(x, -3), Math.min(x, 3.14), Math.pow(2.71, 3.15), Math.round(3.14), Math.sqrt(225) // math
Integer.valueOf("1"), Double.valueOf("3.14"), Boolean.valueOf("true"), Float.toString(3.14f)  // reference type
Integer.parseInt("42"), Double.parseDouble("3.14")  // primitive type
Double.compare(x, 1.23) == 0, Integer.compare(x, 2) == 0  // comparing values

// bitwise operation
Integer.parseInt("1000010", 2), Integer.parseInt("52", 8), Integer.parseInt("2a", 16) // string -> binary/octal/hex
Integer.toBinaryString(42), Integer.toHexString(42), Integer.toOctalString(42)      // int -> binary/hex/octal string
Integer.toString(num, base)     // int -> string with base
Integer.bitCount(42)            // number of 1-bits
Long.parseLong("1000010", 2), Long.parseLong("52", 8), Long.parseLong("2a", 16) // string -> binary/octal/hex
Long.toBinaryString(42), Long.toHexString(42), Long.toOctalString(42)       // long -> binary/hex/octal string
Long.toString(num, base)    // long -> string with base
Long.bitCount(42)           // number of 1-bits

// bitset
import java.util.BitSet;
new BitSet(16), set(0), set(0, 8), set(0, 8, true)

// random values
import java.util.Random;
var random = new Random();
var randomInt = random.nextInt(100);      // [0, 100)
var randomLong = random.nextLong();       // [0, 2^48)
var randomDouble = random.nextDouble();   // [0.0, 1.0)
var randomBoolean = random.nextBoolean(); // true/false

Primitive type algorithms

• Arithmetic operation, EPI#4.5, EPI#4.6: c++(Multiply/Divide) | Calculate the product/fraction of two numbers without using arithmetic operators.
• Power operation, EPI#4.7: c++ | Compute repeated squaring $x^y$.

Examples

• Computing parity of word: c++(CountBits) | Count the number of bits that are set to 1.
• Computing parity of word, EPI#4.1: c++(Parity) | Compute parity of word.
• Computing parity of word, EPI#4.1: c++(ParityDropLowestBits) | Compute parity by dropping the lowest set bit.
• Computing parity of word, EPI#4.1: c++(ParityLookupTable) | Compute parity by caching the results.
• Generate random number, EPI#4.10: c++ | Generate a random number in a range with equal probability.
• Integer palindrome, EPI#4.9: c++ | Check if a number is a palindrome.
• Rectangle intersection, EPI#4.11: c++ | Check if two rectangles intersect.
• Reverse digits, EPI#4.8: c++ | Reverse the digits of a given integer.
• Swap bit, EPI#4.2: c++ | Swap the bits at indices $i$ and $j$.

🔼 back to toc

🔍 Search

C++ declaration/methods

// map
auto map = std::map<std::string, int>{{"a", 1}, {"b", 2}};
insert({"c", 3}), emplace("d", 4), erase("a"), find("b"), size(), empty(), equal_range("c")

// set
auto set = std::set{1, 2, 3, 4, 5};
insert(42), emplace(42), erase(42), find(42), size(), equal_range(3)

// algorithm
std::ranges::find(v, 42)
std::ranges::find(v, 42)
std::ranges::find_if(v, [](auto x) { return x % 2 == 0; })
std::ranges::find_end(v, sub_v).begin() // cf. result - v.begin()
std::ranges::binary_search(v, 42)
std::ranges::lower_bound(v, 42)
std::ranges::upper_bound(v, 42)

Python declaration/functions

bisect.bisect_left(number_list, 3), bisect.bisect_right(number_list, 3), bisect.bisect(number_list, 3)

Java declaration/methods

import java.util.*;
var array = new int[]{1, 2, 3, 4, 5};
var arrayList = new ArrayList<Integer>(List.of(1, 2, 3, 4, 5));
var linkedList = new LinkedList<Integer>(List.of(1, 2, 3, 4, 5));
var hashSet = new HashSet<Integer>(List.of(1, 2, 3, 4, 5));
var linkedHashSet = new LinkedHashSet<Integer>(List.of(1, 2, 3, 4, 5));
var treeSet = new TreeSet<Integer>(List.of(1, 2, 3, 4, 5));

// binary search
import java.util.Arrays;
import java.util.Collections;
Arrays.binarySearch(array, 3)             // for array
Collections.binarySearch(arrayList, 3);   // for list

Search algorithms

• Binary search: python | Binary search is a search algorithm that finds the position of a target value within a sorted array.
• Integer square root, EPI#11.4: c++(ComputeIntegerSquareRoot) | Compute the integer square root of a given integer. This function returns the largest integer whose square is less than or equal to the given integer.
• Linear search: python | Linear search is a search algorithm that compares x successively with each term of the list until a match is found.
• Quick select algorithm: c++(QuickSelectAlgorithm) | QuickSelect is an algorithm used to select the k-th smallest (or largest) element in an unordered list of elements.

Examples

• Find k-th smallest/largest element in an array, EPI#11.8: c++(FindKthSmallestElement/FindKthLargestElement) | Find the k-th smallest/largest element in an array using the quickselect algorithm (QuickSelectAlgorithm).
• Find the minimum and maximum elements in an array, EPI#11.7: c++(FindMinMax)
• Search a codon(combinations of three nucleotides) in a gene, CCSP#2.1: python(linear_contains, binary_contains) | Search a codon(combinations of three nucleotides) in a gene using linear search and binary search.
• Search an element in generic list, CCSP#2.1: python(generic_linear_contains, generic_linear_contains) | Search an element in generic list using linear search and binary search.
• Search a sorted array for entry equal to its index, EPI#11.2: c++(SearchEntryEqualToItsIndex)
• Search a sorted array for the first greater than a key: c++(SearchFirstGreaterThanKey)
• Search a sorted array for the first occurrence of a key, EPI#11.1: c++(SearchFirstOfKey)
• Search a cyclically sorted array for the smallest element, EPI#11.3: c++(SearchSmallestElementInCyclicallySortedArray)
• Search in a 2D sorted array(matrix), EPI#11.6: c++(SearchSortedMatrix) | Search in a 2D sorted array(matrix) for a given element.

🔼 back to toc

🔤 Sort

C++ declaration/methods

std::ranges::sort(v);         // introsort (quick sort + heap sort + insertion sort)
std::ranges::stable_sort(v);  // merge sort

Python declaration/functions

number_list: list[int] = [1, 2, 3, 4, 5]
number_list.sort()              # in-place
result = sorted(number_list)    # return a new list(copy)

Java declaration/methods

Arrays.sort() and Collections.sort() sort the array and list in ascending order in-place.

import java.util.Arrays;
Arrays.sort(arr);           // dual pivot quick sort (primitive types)
                            // timsort (insertion sort + merge sort) (reference types)
Arrays.sort(arr, Comparator.comparingInt(String::length));
Arrays.sort(arr, Comparator.comparingInt(String::length).reversed());

import java.util.Collections;
Collections.sort(list);     // timsort (insertion sort + merge sort)
list.sort(Comparator.naturalOrder());
list.sort(Comparator.reverseOrder());
list.sort(Comparator.comparingInt(String::length));

Sorting algorithms

• Bubble sort: java | Bubble sort is a sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items, and swaps them if needed.
  (n is the number of elements)

Case	Time complexity	Remarks
Best	$O(n)$	when the input list is already sorted in the desired order
Worst	$O(n^2)$	when the input list is already sorted in the reverse order of the desired sorting order
Average	$O(n^2)$

• Bucket sort: java | Bucket sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket contains a range of values and the elements are sorted within these buckets using any of the suitable sorting algorithms (such as insertion sort, merge sort, selection sort).
  (n is the number of elements and k is the number of buckets)

Case	Time complexity	Remarks
Best	$O(n + k)$	when input elements are uniformly distributed and each bucket contains roughly the same number of elements
Worst	$O(n^2)$	when all elements are placed into a single bucket
Average	$O(n)$

• Counting sort: java | Counting sort is a non-comparative sorting algorithm that sorts the elements of an array by counting the occurrences of each element in the array. The count is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array. It is used as a subroutine in radix sort.
  (n is the number of elements and k is the range of input values)

Case	Time complexity	Remarks
Best	$O(n + k)$	when the input elements have a small range of values
Worst	$O(n + k)$	when the input elements have a large range of values
Average	$O(n + k)$

• Heap sort: java | Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort an array. It is used for the implementation of priority queue.
  (n is the number of elements)

Case	Time complexity	Remarks
Best	$O(n log n)$
Worst	$O(n log n)$
Average	$O(n log n)$

• Insertion sort: c++, java | Insertion sort is a comparison-based sorting algorithm that builds the final sorted array one element at a time. One of the fastest algorithms for sorting very small arrays (around 10 elements).
  (n is the number of elements)

Case	Time complexity	Remarks
Best	$O(n)$	if the list is already sorted. this case has linear running time
Worst	$O(n^2)$	if the list is sorted in reverse order. this case has quadratic running time
Average	$O(n^2)$	this case has quadratic running time

• Merge sort: java | divide and conquer algorithm

Case	Time complexity	Remarks
Best	$O(n log n)$	running time of sorting for input length $n$ is $T(n)$. $T(n) = 2T(n/2) + O(n) \approx O(n log n)$
Worst	$O(n log n)$
Average	$O(n log n)$

• Quick sort: java | divide and conquer algorithm

Case	Time complexity	Remarks
Best	$O(n log n)$
Worst	$O(n^2)$
Average	$O(n log n)$

• Selection sort: c++, java

Case	Time complexity	Remarks
Best	$O(n^2)$	if the list is already sorted
Worst	$O(n^2)$	when sorted in ascending order, if you want to sort in descending order (vice versa)
Average	$O(n^2)$

Examples

• H-Index, EPI#13.3: c++(HIndex) | Compute the researcher's h-index given a citation count array. The h-index is the largest number h such that h articles have at least h citations each.
• Intersection of two sorted arrays, EPI#13.1: c++(IntersectTwoSortedArray) | Compute the intersection of two sorted array. The input arrays may have duplicate entries, but the output should be free of duplicates.
• Merge intervals, EPI#13.7, LeetCode#merge-intervals: c++(MergeIntervals) | Given a collection of intervals, merge all overlapping intervals.
• Merge two sorted arrays, EPI#13.2, LeetCode#merge-sorted-array: c++(MergeTwoSortedArray) | Merge two sorted array. Merge the second array into the first array.
• Partitioning and sorting an array with many repeated entries, EPI#13.9: java(GroupByAge) | Given an array of objects with an age field, reorder the array so that objects of equal age appear together. They should be sorted in ascending order of age, and the order of objects with the same age is not important.
• Remove first-name duplicates, EPI#13.4: c++(EliminateFirstNameDuplicate) | Given an array of names, remove the duplicates of the first name.
• Salary threadhold, EPI#13.12: java(SalaryThreshold) | Given an array of salaries and a budget, compute the salary cap so that the total salaries equal the budget.
• Team photo day, EPI#13.10: java(SortPlayerByHeight) | Given two arrays of numbers, for team photos, players are arranged in front and back rows and then photographed. The players in the back row must necessarily be taller than those in the front row. Additionally, all players in a row should belong to the same team.
• Union of intervals, EPI#13.8: c++(UnionOfIntervals) | Given a set of intervals, compute their union.

🔼 back to toc

📄 String

C++ declaration/methods

auto str = std::string{"hello"};
append("_world"), push_back('!'), pop_back(), insert(5, "_world"), substr(0, 5), compare("hello_world")

// string stream
std::stringstream ss(str);
good(), bad(), fail(), eof(), clear(), operator<<(), operator>>()

Python declaration/functions

hello_world: str = 'hello world'
len(hello_world), count('l'), find('world'), rfind('world'), index('world'), rindex('world'),
strip(), split(' '), replace(' ', ''), startswith('hello'), endswith('world'),
lower(), upper(), capitalize(), title(), swapcase()

# string concatenation
s = s[6:]
s += 'abc'

Java declaration/methods

var str = "Hello World";
length(), charAt(0), substring(0, 5), indexOf("Java"), lastIndexOf("Java"),
contains("Java"), startsWith("Hello"), endsWith("World"),
compareTo("Hello Java"), compareToIgnoreCase("hello world"),
concat("!"), replace("World", "Java"), toUpperCase(), toLowerCase(), trim(),
toCharArray(), chars()

// static methods
String.format("%s %s", "Hello", "World")
String.join(" ", "Hello", "World")
String.valueOf(123)

// string builder
var sb = new StringBuilder();
append("!"), insert(0, "Hello"), delete(0, 5), deleteCharAt(0),
length(), charAt(0), indexOf("Java"), lastIndexOf("Java"),
reverse(), replace(0, 5, "World"), substring(0, 5), toString(),
subSequence(0, 5), chars()

// character
var ch = new Character('a');
Character.isDigit('0'), Character.isLetter('a'), Character.isLetterOrDigit('a'), Character.isAlphabetic('a'),
Character.isLowerCase('a'), Character.isUpperCase('A'), Character.toLowerCase('A'), Character.toUpperCase('a'),
Character.isWhitespace(' ')

// list/stack/deque to string
var str = collection.stream()
    .map(String::valueOf)
    .collect(StringBuilder::new, StringBuilder::append, StringBuilder::append);

String algorithms

• Finite automata
• Knuth-Morris-Pratt algorithm (KMP)
• Naive string matching: c++, python | Find all occurrences of a pattern in a string.
• Rabin-Karp algorithm, EPI#6.12: c++ | Use the hash function to find all occurrences of a pattern in a string. It has $\theta(\text{pattern-size})$ preprocessing time and $\theta((\text{text-size} - \text{pattern-size} + 1) \text{pattern-size})$ time complexity.

Examples

• Convert string, EPI#6.1: c++(IntToString, StringToInt) | Convert integer to string and vice versa.
• IP address validation, EPI#6.9: c++ | Validate IPv4 address that is in the form of x.x.x.x where x is a number between 0 and 255.
• Look and say problem, EPI#6.7: c++
• Palindrome, EPI#6.5: c++ | Check if a string is palindromic.
• Print sine wave pattern string, EPI#6.10: c++(SineWaveString and PrintSineWaveString) | Print a string in sine wave pattern.
• Roman number, EPI#6.8: c++(VerifyRomanString) | Verify if a string is a valid roman number.
• Roman number, EPI#6.8: c++(RomanStringToInteger) | Convert a roman number to integer.
• Run-length encoding (RLE), EPI#6.11: c++ | Run-length encoding is a simple form of data compression in which runs of data are stored as a single data value and count.
• Spreadsheet column decoding/encoding, EPI#6.3: c++(DecodingSheetColumnId/EncodingSheetColumnId) | Convert a spreadsheet column id to integer and vice versa.

🔼 back to toc

References

• Introduction to Algorithms, 3rd Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (CLRS)
• Discrete Mathematics and Its Applications, 8th Edition, by Kenneth H. Rosen
• Cracking the Coding Interview, 6th Edition, by Gayle Laakmann McDowell | CTCI
• Elements of Programming Interviews, 2nd Edition, by Adnan Aziz, Tsung-Hsien Lee and Amit Prakash | EPI
• Classic Computer Science Problems in Python, by David Kopec | CCSP

🔼 back to toc