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.
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 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 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 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 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 interval trees.
A data structure that holds intervals and allows efficiently querying all intervals that overlap with any given interval or point.
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.
Define a dense graph.
A graph where the number of edges is close to the maximum number of edges possible.
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 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 Dijkstra's algorithm.
An algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
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 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.
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 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 graph vertex.
A fundamental part of a graph, representing a node or a point in the graph where edges are connected.
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 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.
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 priority queue.
A type of queue where each element has a priority associated with it, and elements are dequeined in order of their priority.
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.
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 trie (prefix tree).
A tree-like data structure that stores a dynamic set of strings, where the keys are usually strings.
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.