Define a union by rank and path compression in disjoint-set data structures.
Techniques used to optimize disjoint-set data structures, where union by rank ensures the shorter tree is merged under the taller tree, and path compression flattens the structure of the tree whenever find is used.
Define the concept of a persistent data structure.
Data structures that preserve their previous versions when modified, allowing access to any version of the data structure at any time.
Define a complete binary tree.
A binary tree in which all the levels are completely filled except possibly the last level, which is filled from left to right.
Define a hash function in the context of hash tables.
A function that computes a location from an input key where the data associated with the key is stored.
Define a quadtree.
A tree data structure in which each internal node has exactly four children, used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
Define a graph vertex.
A fundamental part of a graph, representing a node or a point in the graph where edges are connected.
Explain the A* search algorithm.
A pathfinding and graph traversal algorithm that is used to find the most cost-effective path between nodes, using heuristics to improve performance over Dijkstra's algorithm.
Define the Boyer-Moore algorithm.
An efficient string searching algorithm that skips sections of the text to be searched by pre-processing the pattern being searched for.
Explain dynamic programming in relation to data structures.
A method of solving complex problems by breaking them down into simpler subproblems, storing the solution to each subproblem to avoid redundant calculations.
Define amortized analysis in the context of algorithm complexity.
An analysis technique for averaging the worst-case cost of operations in a data structure over a sequence of operations.
Define linear probing in the context of open addressing.
A method where, upon a collision, the table is searched sequentially to find the next empty slot.
Define AVL tree.
A self-balancing binary search tree where the height difference between left and right subtrees (the balance factor) is at most one for every node.
Define a priority queue.
A type of queue where each element has a priority associated with it, and elements are dequeined in order of their priority.
Define a dense graph.
A graph where the number of edges is close to the maximum number of edges possible.
Define a k-d tree (k-dimensional tree).
A space-partitioning data structure for organizing points in a k-dimensional space, used in various applications such as searches involving a multidimensional search key.
Define interval trees.
A data structure that holds intervals and allows efficiently querying all intervals that overlap with any given interval or point.
Differentiate between a directed and undirected graph.
In a directed graph, edges have a direction from one vertex to another, while in an undirected graph, edges do not have a direction.
Define a doubly linked list.
A linked list where each node has two links: one to the next node and another to the previous node.
Explain Breadth-first search (BFS) in tree traversal.
A traversal method where one starts at the tree root and explores all neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Define the concept of an exponential tree.
A variation of a binary search tree with nodes that have variable-sized subtrees, designed to optimize for operations performed on consecutive elements.
Define Dijkstra's algorithm.
An algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
Define a weighted graph.
A graph where each edge is assigned a weight or cost, representing the cost of moving from one vertex to another.
Define a segment tree.
A tree data structure used for storing information about intervals or segments. It allows querying which segments contain a given point.
Define a trie (prefix tree).
A tree-like data structure that stores a dynamic set of strings, where the keys are usually strings.
Differentiate between adjacency list and adjacency matrix representations of a graph.
An adjacency list represents a graph as an array of lists, where each list describes the neighbors of a vertex; an adjacency matrix uses a two-dimensional array to represent the presence or absence of edges between vertices.