Heapsort is a sorting algorithm that first reorganizes an input array into a
heap, then repeatedly removes the largest node from that heap, placing it at
the end of the array.
The k-way merge algorithm is a sequence merge algorithm that takes in k sorted
lists, typically greater than two, and merges them into a single sorted list.
It can be efficiently solved in O(nlog k) time using a heap, where n is the
total number of elements for all k lists.
The kth smallest (or largest) problem can be efficiently solved using a
max-heap (or min-heap). Maintaining a heap of size k, the kth smallest value is
always the root of the max-heap. To retrieve all k smallest elements, simply
return the sorted heap.
Levenshtein distance is a string metric for measuring the difference between
two sequences. The Levenshtein distance between two words is the minimum number
of single-character edits (insertions, deletions, or substitutions) required to
change one word into the other.
The longest common subsequence is the longest subsequence that is common to two
or more sequences. It can be found using a dynamic programming approach.
The longest increasing subsequence is the longest sequence of numbers from an
array where each number is greater than the previous one. It can be found using
a dynamic programming approach.
Manacher's Algorithm was discovered by Glenn K. Manacher in 1975 and can be
used to find the longest palindromic substring of a string and all palindromic
substrings of a string in linear time.
The maximum subarray problem is the task of finding a contiguous subarray with
the largest sum, within a given one-dimensional array A[1...n] of numbers. It
can be solved in O(n) time and O(1) space.
Merge sort is the quintessential divide-and-conquer sorting algorithm. It
follows the premise that an array of one element is considered sorted.
Furthermore, it is trivial to sort two sorted arrays.
Quickselect (also known as Hoare's selection algorithm) is a selection
algorithm to find the kth smallest (or largest) element in an unordered list of
n elements.
Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot'
element from the array and partitioning the other elements into two sub-arrays,
according to whether they are less than or greater than the pivot. The
sub-arrays are then sorted recursively.
Three-way partition, also known as the Dutch national flag problem, is an
algorithm for partitioning three types of elements (those less than a given
key, those equal to a given key, and those greater than a given key). Three-way
partitioning can be done in linear time.
Common tree operations involve searching, inserting, and deleting nodes in the
tree. For binary trees, these operations require simple pointer manipulation.
For binary search trees, however, the invariant-the key of each internal node
must be greater than all the keys in the node's left subtree and less than all
the keys in the node's right subtree-must be maintained, making the operations
slightly more involved.
Tree traversal is the process of visiting each node in a tree exactly once.
Such traversals are classified by the order in which the nodes are visited.
There are two main tree traversals: depth-first and breadth-first search.
Additionally, depth-first search can be done pre-order, post-order, and
in-order.