Algorithm Examples

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

Project Environments

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

Language	Version	Build	Packages	Remarks
C++	C++20	CMake	GNU Scientific Library (GSL), Google Test, Google Benchmark, fmt	vcpkg
Python	3.12	Poetry	NumPy, SciPy, NetworkX, pytest, pytest-benchmark
Java	21	Gradle	Google Guava, JUnit, Java Microbenchmark Harness (JMH)
Go	1.22	Go	Testify

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])   # remove 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

int[] arr = new int[]{1, 2, 3, 4, 5};   // array
int[][] matrix = new int[m][n];         // 2d array (m by n matrix)

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
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
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 arr1 = Arrays.stream(arr).boxed().toArray(Integer[]::new);                     // int[] to Integer[]
var arr2 = Arrays.stream(arr).mapToObj(String::valueOf).toArray(String[]::new);    // int[] to String[]
var arr3 = Arrays.stream(arr).boxed().collect(Collectors.toList());                // int[] to List<Integer>

// integer sequence
var arr = IntStream.range(0, n).toArray();          // range to int array in [0, n)
var arr = IntStream.rangeClosed(1, n).toArray();    // range to int array in [1, n]
var list = IntStream.range(0, n).boxed().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

// guava
import com.google.common.collect.*;
List<String> list = Lists.newArrayList();
List<String> list = Lists.asList(boxedArray);

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.
- add two arbitrary-precision integers: c++(StringAddition) | Add two numbers represented by strings.
- 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, 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 $\textit{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, ReplaceAndRemoveString2) | Replace element and remove element in the array.
- telex encoding: c++(TelexEncoding) | Telex encoding for punctuation marks.
Stock trading
- buy and sell a stock once, EPI#5.6: c++(BuyAndSellStockOnceBruteForce, BuyAndSellStockOnce)
- buy and sell a stock twice, EPI#5.7: c++(BuyAndSellStockTwice)

Name		Name	Last commit message	Last commit date
Latest commit History 543 Commits
.config		.config
.github		.github
cpp-algorithm		cpp-algorithm
go-algorithm		go-algorithm
java-algorithm		java-algorithm
python-algorithm		python-algorithm
.gitignore		.gitignore
LICENSE		LICENSE
README.md		README.md
README_ko-KR.md		README_ko-KR.md

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

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)$

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)$	when the elements are distributed randomly in the array

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

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

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)$

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)$	when the input list is in jumbled order

License

codejsha/algorithm-examples

Folders and files

Latest commit

History

Repository files navigation

Algorithm Examples

Project Environments

Table of Contents

Data structures

🚋 Array

📈 Graph

🔑 Hash table

🚀 Heap

🖇️ Linked list

🚶 Queue

🍔 Stack

🌳 Tree

Topics

🧩 Dynamic programming (DP)

🕘 Greedy

📐 Mathematics

🔢 Primitive type

🔍 Search

🔤 Sort

📄 String

References

About

Topics

Resources

License

Stars

Watchers

Forks

Releases

Sponsor this project

Packages 0

Languages

Packages