Title: Dsa Anki Deck — LearnCoachAssist

Q: What is a Data Structure?
A: A data structure is a particular way of organizing data in a computer so that it can be used effectively.

Q: What is an Algorithm?
A: An algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output.

Q: What is Big O Notation?
A: Big O notation describes the upper bound of the time complexity of an algorithm. It represents the worst-case scenario.

Q: What is Time Complexity?
A: Time complexity is a measure of the amount of time an algorithm takes to run as a function of the length of the input.

Q: What is Space Complexity?
A: Space complexity is a measure of the amount of working storage an algorithm needs.

Q: What is an Array?
A: An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together.

Q: What is a Linked List?
A: A linked list is a linear data structure where elements are not stored at contiguous memory locations. The elements are linked using pointers.

Q: What is the difference between Array and Linked List?
A: Arrays have fixed size and contiguous memory. Linked Lists have dynamic size and non-contiguous memory using pointers. Insertion/Deletion is easier in Linked Lists, while access is faster in Arrays.

Q: What is a Stack?
A: A stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out).

Q: What are the main operations on a Stack?
A: Push (add item), Pop (remove item), Peek/Top (view top item), isEmpty (check if empty).

Q: What is a Queue?
A: A queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).

Q: What are the main operations on a Queue?
A: Enqueue (add item), Dequeue (remove item), Front (get first item), Rear (get last item).

Q: What is a Binary Tree?
A: A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Q: What is a Binary Search Tree (BST)?
A: A BST is a binary tree where the left child contains only nodes with values less than the parent node, and the right child contains only nodes with values greater than the parent node.

Q: What is an AVL Tree?
A: An AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

Q: What is a Heap?
A: A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Common types are Min-Heap and Max-Heap.

Q: What is a Hash Table?
A: A Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value.

Q: What is Hashing?
A: Hashing is the process of converting a given key into another value, which is then used as an index to retrieve the value from the table.

Q: What is a Collision in Hashing?
A: Collision occurs when two different keys hash to the same index.

Q: How can collisions be resolved in Hashing?
A: Common methods include Chaining (using a linked list at the index) and Open Addressing (Linear Probing, Quadratic Probing, Double Hashing).

Q: What is a Graph?
A: A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.

Q: What is BFS (Breadth First Search)?
A: BFS is a traversing algorithm where you start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbor nodes (nodes which are directly connected to source node) first, before moving towards the next level neighbors.

Q: What is DFS (Depth First Search)?
A: DFS is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

Q: What is Recursion?
A: Recursion is a process in which a function calls itself as a subroutine.

Q: What is Dynamic Programming?
A: Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and storing the results of subproblems to avoid computing the same results again.

Q: What is the difference between Recursion and Iteration?
A: Recursion involves a function calling itself, while iteration involves a loop repeating a process. Recursion can be more memory intensive due to stack overhead.

Q: What is Memoization?
A: Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Q: What is Sorting?
A: Sorting is the process of arranging data in a particular format. Common sorting orders are numerical and lexicographical.

Q: What is Bubble Sort?
A: Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Q: What is Selection Sort?
A: Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

Q: What is Insertion Sort?
A: Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

Q: What is Merge Sort?
A: Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

Q: What is Quick Sort?
A: QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.

Q: What is the time complexity of Merge Sort?
A: O(n log n) in all 3 cases (worst, average and best).

Q: What is the worst case time complexity of Quick Sort?
A: O(n^2), usually when the array is already sorted or reverse sorted and the pivot is chosen poorly.

Q: What is Binary Search?
A: Binary Search is a searching algorithm for finding an element's position in a sorted array. It works by repeatedly dividing the search interval in half.

Q: What is the time complexity of Binary Search?
A: O(log n).

Q: What is a Trie?
A: A Trie (digital tree or prefix tree) is a type of search tree, a tree data structure used for locating specific keys from within a set.

Q: What is a Priority Queue?
A: A Priority Queue is an extension of queue with following properties: Every item has a priority associated with it. An element with high priority is dequeued before an element with low priority.

Q: What is Dijkstra's Algorithm?
A: Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph.

Q: What is Bellman-Ford Algorithm?
A: Bellman-Ford is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's but capable of handling graphs in which some of the edge weights are negative numbers.

Q: What is Floyd-Warshall Algorithm?
A: The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph.

Q: What is Prim's Algorithm?
A: Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.

Q: What is Kruskal's Algorithm?
A: Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.

Q: What is a Greedy Algorithm?
A: A greedy algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.

Q: What is Divide and Conquer?
A: Divide and Conquer is an algorithmic paradigm. A typical Divide and Conquer algorithm solves a problem using following three steps: Divide, Conquer, Combine.

Q: What is Backtracking?
A: Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time.

Q: What is a Red-Black Tree?
A: A Red-Black tree is a binary search tree which has the following red-black properties: 1. Every node is either red or black. 2. The root is black. 3. Every leaf (NULL) is black. 4. If a node is red, then both its children are black. 5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Q: What is a B-Tree?
A: B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It is a generalization of a binary search tree in that a node can have more than two children.

Q: What is the best case time complexity of Bubble Sort?
A: O(n) when the array is already sorted.

Q: What is Linear Search?
A: Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one.

Q: What is the time complexity of Linear Search?
A: O(n).

Q: What is an Adjacency Matrix?
A: An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

Q: What is an Adjacency List?
A: An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.

Q: What is Topological Sorting?
A: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering.

Q: What is a Circular Linked List?
A: A circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end.

Q: What is a Doubly Linked List?
A: A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

Q: What is Inorder Traversal?
A: In a binary tree: Left, Root, Right.

Q: What is Preorder Traversal?
A: In a binary tree: Root, Left, Right.

Q: What is Postorder Traversal?
A: In a binary tree: Left, Right, Root.

Q: What is Level Order Traversal?
A: Breadth-first traversal of a tree.

Q: What is a Spanning Tree?
A: A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.

Q: What is a Minimum Spanning Tree (MST)?
A: A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Q: What is Bit Manipulation?
A: Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word.

Q: What are the bitwise operators?
A: AND (&), OR (|), XOR (^), NOT (~), Left Shift (<<), Right Shift (>>).

Q: What is the Two Pointers technique?
A: Two pointers is a pattern where two pointers iterate through the data structure in tandem until one or both of the pointers hit a certain condition.

Q: What is the Sliding Window technique?
A: The Sliding Window technique is used to perform an operation on a specific window size of a given array or linked list, such as finding the longest subarray containing all 1s.

Q: What is Cycle Detection in a Linked List?
A: Floyd’s Cycle-Finding Algorithm (Tortoise and Hare algorithm) is used to detect if a linked list contains a cycle.

Q: What is Knapsack Problem?
A: The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Q: What is Longest Common Subsequence (LCS)?
A: The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences).

Q: What is Huffman Coding?
A: Huffman coding is a popular algorithm used for lossless data compression. It uses variable-length encoding where variable-length codes are assigned to input characters based on their frequencies.

Q: What is Union-Find Data Structure?
A: Union-Find (or Disjoint Set Union - DSU) is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

Q: What are the operations of Union-Find?
A: Find: Determine which subset a particular element is in. Union: Join two subsets into a single subset.

Q: What is Shell Sort?
A: ShellSort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shellSort is to allow exchange of far items.

Q: What is Counting Sort?
A: Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing).

Q: What is Radix Sort?
A: Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step.

Q: What is Bucket Sort?
A: Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the following problem. Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range.

Q: What is Interpolation Search?
A: Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched.

Q: What is Exponential Search?
A: Exponential search allows for searching in a sorted, unbounded list. The algorithm consists of two stages: determining a range where the search key resides and performing a binary search within that range.

Q: What is a B+ Tree?
A: A B+ tree is an N-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.

Q: What is a Segment Tree?
A: A Segment Tree is a data structure used for storing information about intervals or segments. It allows querying which of the stored segments contain a given point.

Q: What is a Fenwick Tree (Binary Indexed Tree)?
A: A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

Q: What is a Quadtree?
A: A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.

Q: What is an Octree?
A: An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional space by recursively subdividing it into eight octants.

Q: What is Topological Sort (Kahn's Algorithm)?
A: Kahn's algorithm is a topological sorting method for Directed Acyclic Graphs (DAGs). It works by repeatedly removing nodes with zero in-degree and updating the in-degrees of their neighbors.

Q: What is Tarjan's Algorithm?
A: Tarjan's algorithm is an algorithm for finding the strongly connected components of a directed graph. It uses depth-first search (DFS) and maintains two arrays, discovery time and low-link value, to identify SCCs.

Q: What is Kosaraju's Algorithm?
A: Kosaraju's algorithm is another linear time algorithm to find Strongly Connected Components of a directed graph. It involves two passes of DFS.

Q: What is Ford-Fulkerson Algorithm?
A: The Ford-Fulkerson algorithm computes the maximum flow in a flow network. It uses DFS or BFS to find augmenting paths in the residual graph.

Q: What is A* Search?
A: A* Search algorithm is a graph traversal and path search algorithm, which is often used in computer science due to its completeness, optimality, and optimal efficiency. It uses a heuristic function to estimate the cost to reach the goal.

Q: What is KMP Algorithm?
A: The Knuth-Morris-Pratt (KMP) string searching algorithm searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin.

Q: What is Rabin-Karp Algorithm?
A: Rabin-Karp algorithm is a string-searching algorithm that uses hashing to find any one of a set of pattern strings in a text. For text of length n and p patterns of combined length m, its average and best case running time is O(n+m) in space O(p), but its worst-case time is O(nm).

Q: What is a Suffix Tree?
A: A Suffix Tree is a compressed trie of all suffixes of the given text. It is a powerful data structure used for solving many string problems like pattern matching, finding the longest repeated substring, etc.

Q: What is a Suffix Array?
A: A suffix array is a sorted array of all suffixes of a string. It is a space-efficient alternative to a suffix tree.

Q: What is the Master Theorem?
A: The Master Theorem provides a solution for recurrence relations of the form T(n) = aT(n/b) + f(n), which often arise in the analysis of divide-and-conquer algorithms.

Q: What is Amortized Analysis?
A: Amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. It considers the average cost of an operation over a sequence of operations, rather than the worst-case cost of a single operation.

Q: What is the Sieve of Eratosthenes?
A: The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

Q: What is the Euclidean Algorithm?
A: The Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers.

Q: What is Modular Exponentiation?
A: Modular exponentiation is a type of exponentiation performed over a modulus. It is useful in computer science, especially in public-key cryptography.

Q: What is the Iterator Pattern?
A: The Iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container's elements. It decouples the traversal algorithm from the container.

Q: What is a Bloom Filter?
A: A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not.

Q: What is a Skip List?
A: A skip list is a probabilistic data structure that allows O(log n) search complexity as well as O(log n) insertion complexity within an ordered sequence of elements.

Q: What is a Disjoint Set?
A: A disjoint-set data structure is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations (bounded by the inverse Ackermann function) to add new sets, to merge existing sets, and to determine whether elements are in the same set.

Q: What is the Travelling Salesman Problem (TSP)?
A: The Travelling Salesman Problem asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

Q: What is P Complexity Class?
A: P is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

Q: What is NP Complexity Class?
A: NP is the complexity class of problems that can be verified in polynomial time. It stands for "Nondeterministic Polynomial time".

Q: What is NP-Complete?
A: A problem is NP-Complete if it is in NP and every problem in NP is reducible to it in polynomial time. These are the hardest problems in NP.

Q: What is NP-Hard?
A: A problem is NP-Hard if every problem in NP can be reduced to it in polynomial time. NP-Hard problems are at least as hard as the hardest problems in NP, but they don't necessarily have to be in NP themselves.

Q: What is Dynamic Array?
A: A dynamic array is a variable-size list data structure that allows elements to be added or removed. It is supplied with standard libraries in many modern programming languages.

Q: What is Threaded Binary Tree?
A: A threaded binary tree is a binary tree variant that allows fast traversal: given a pointer to a node, it is possible to find the next node in the in-order traversal (or other traversals) without recursion or a stack.

Q: What is Expression Tree?
A: An expression tree is a binary tree used to represent expressions. The leaves of the binary tree are operands, such as constants or variable names, and the other nodes contain operators.

Q: What is Cartesian Tree?
A: A Cartesian tree is a binary tree derived from a sequence of numbers — it can be uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the sequence itself.

Q: What is Decomposition in Graphs?
A: Decomposition is the process of breaking a graph into subgraphs to simplify the analysis or solution of graph problems. Examples include decomposition into connected components, biconnected components, or strongly connected components.

Q: What is Maximum Bipartite Matching?
A: Maximum Bipartite Matching is a problem of finding the maximum number of edges in a matching of a bipartite graph. A matching is a set of edges without common vertices.

Q: What is Stable Marriage Problem?
A: The stable marriage problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element.

Q: What is Convex Hull?
A: The convex hull of a set of points is the smallest convex polygon that contains all the points.

Q: What is Graham Scan?
A: Graham scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n).

Q: What is Line Intersection?
A: Line intersection is the problem of finding the intersection point(s) of lines or line segments.

Q: What is Memoization vs Tabulation?
A: Memoization is a top-down approach where we cache the results of function calls. Tabulation is a bottom-up approach where we solve the problem by filling up a table.

Q: What is the Longest Increasing Subsequence (LIS)?
A: The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Q: What is Matrix Chain Multiplication?
A: Matrix Chain Multiplication is an optimization problem regarding the most efficient way to multiply a given sequence of matrices. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.

Q: What is Edit Distance (Levenshtein Distance)?
A: The edit distance between two strings is the minimum number of operations (insertions, deletions, and substitutions) required to transform one string into the other.

Q: What is 0/1 Knapsack vs Fractional Knapsack?
A: In 0/1 Knapsack, items cannot be broken which means we should take the whole item or leave it. In Fractional Knapsack, we can break items for maximizing the total value of knapsack.

Q: What is Branch and Bound?
A: Branch and bound is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. It systematically enumerates candidate solutions by means of state space search.

Q: What is Johnson's Algorithm?
A: Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist.

Q: What are Articulation Points (Cut Vertices)?
A: An articulation point in a graph is a vertex that, if removed (along with edges incident to it), makes the graph disconnected (or increases the number of connected components).

Q: What is a Bridge in a Graph?
A: A bridge in a graph is an edge that, if removed, increases the number of connected components of the graph.

Q: What is the Hopcroft-Karp Algorithm?
A: The Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output. It runs in O(E sqrt(V)) time.

Q: What is an Eulerian Path?
A: An Eulerian path is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices).

Q: What is a Hamiltonian Path?
A: A Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once.

Q: What is Graph Coloring?
A: Graph coloring is the assignment of labels (colors) to elements of a graph subject to certain constraints. The most common form is vertex coloring, where no two adjacent vertices share the same color.

Q: What is the Chromatic Number?
A: The chromatic number of a graph is the smallest number of colors needed to color the vertices of the graph so that no two adjacent vertices share the same color.

Q: What is a Splay Tree?
A: A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. Operations perform a "splaying" step which moves the accessed element to the root.

Q: What is a Treap?
A: A Treap is a data structure that combines a Binary Search Tree and a Heap. Each node has a key (BST property) and a priority (Heap property), often assigned randomly.

Q: What is a Rope (Data Structure)?
A: A Rope is a tree-based data structure that is used to store or manipulate very long strings, where operations like concatenation are more efficient than standard strings.

Q: What is a k-d Tree?
A: A k-d tree (k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. It is a binary search tree with other constraints.

Q: What is a Van Emde Boas Tree?
A: A Van Emde Boas tree is a tree data structure which implements an associative array with integer keys. It performs all operations in O(log log M) time, where M is the maximum number of elements in the universe.

Q: What is TimSort?
A: TimSort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It is the standard sort in Python and Java.

Q: What is IntroSort (Introspective Sort)?
A: IntroSort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort, switches to heapsort when the recursion depth exceeds a level, and uses insertion sort for small subarrays.

Q: What is Cycle Sort?
A: Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array.

Q: What is QuickSelect?
A: QuickSelect is a selection algorithm to find the kth smallest element in an unordered list. It is related to Quicksort and has an average time complexity of O(n).

Q: What is Ternary Search?
A: Ternary search is a divide and conquer algorithm used to find the maximum or minimum of a unimodal function. It divides the search space into three parts.

Q: What is the Z-Algorithm?
A: The Z-Algorithm is a linear time string matching algorithm that finds all occurrences of a pattern in a text. It constructs a Z-array where Z[i] is the length of the longest common prefix between the string and its suffix starting at i.

Q: What is Aho-Corasick Algorithm?
A: Aho-Corasick is a string-searching algorithm that constructs a finite state machine from a set of pattern strings. It locates all occurrences of any of the patterns in a text.

Q: What is Manacher's Algorithm?
A: Manacher's algorithm is an algorithm that finds the longest palindromic substring in a string in linear time O(n).

Q: What is Boyer-Moore Algorithm?
A: The Boyer-Moore string-search algorithm is an efficient string-searching algorithm that skips sections of the text to be searched. It uses two heuristics: the bad character rule and the good suffix rule.

Q: What is Consistent Hashing?
A: Consistent hashing is a hashing technique that minimizes the number of keys that need to be remapped when a hash table is resized (e.g., a server is added or removed in a distributed system).

Q: What is LRU Cache?
A: LRU (Least Recently Used) is a cache replacement policy where the least recently used items are discarded first when the cache is full.

Q: What is LFU Cache?
A: LFU (Least Frequently Used) is a cache replacement policy where the least frequently used items are discarded first. It counts how often an item is needed.

Q: Can Bloom Filters have false negatives?
A: No, Bloom filters can have false positives, but they never have false negatives. If the filter says an element is not in the set, it definitely is not.

Q: What is Geohashing?
A: Geohashing is a public domain geocode system which encodes a geographic location into a short string of letters and digits. It is a hierarchical spatial data structure.

Q: What is Minimax Algorithm?
A: Minimax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario.

Q: What is Alpha-Beta Pruning?
A: Alpha-beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree.

Q: What is Fast Fourier Transform (FFT)?
A: The Fast Fourier Transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). It reduces the complexity from O(n^2) to O(n log n).

Q: What are Catalan Numbers?
A: Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects (e.g., valid parenthesis sequences, full binary trees).

Q: What is Brent's Algorithm?
A: Brent's algorithm is a cycle detection algorithm that is generally faster than Floyd's Tortoise and Hare algorithm, although the worst-case time complexity is the same.

Q: What is Vertex Cover Problem?
A: The vertex cover problem is a classic optimization problem used in computer science to find a minimum size set of vertices such that each edge of the graph is incident to at least one vertex in the set. It is NP-complete.

Q: What is Set Cover Problem?
A: The set cover problem asks: given a set of elements (universe) and a collection of sets whose union equals the universe, what is the smallest sub-collection of sets whose union equals the universe?

Q: What is the Clique Problem?
A: The clique problem refers to finding a clique (a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent) of a given size in a graph. The maximum clique problem is NP-hard.

Q: What is Difference Array?
A: A difference array is an array used to perform range update queries in O(1) time. The actual array can be obtained by taking the prefix sum of the difference array.

Q: What is Mo's Algorithm?
A: Mo's algorithm is a technique to solve range query problems on arrays (and trees) offline. It involves sorting queries in a specific order to minimize the movement of the left and right pointers.

Q: What is Heavy-Light Decomposition (HLD)?
A: Heavy-light decomposition is a technique for decomposing a rooted tree into a set of paths (chains) to allow efficient traversal and path queries (e.g., O(log^2 n)).

Q: What is Centroid Decomposition?
A: Centroid decomposition is a technique for decomposing a tree by recursively finding the centroid (a node that splits the tree into subtrees of size at most n/2). It produces a tree of height O(log n).

Q: What is Lowest Common Ancestor (LCA)?
A: The LCA of two nodes v and w in a tree is the lowest (deepest) node that has both v and w as descendants.

Q: What is Binary Lifting?
A: Binary Lifting is a dynamic programming approach used to find the K-th ancestor of a node in a tree or to compute LCA efficiently in O(log n) time.

Q: What is Square Root Decomposition?
A: Square Root Decomposition is a technique used to answer range queries. It divides the array into blocks of size sqrt(n) to reduce query time complexity to O(sqrt(n)).

Q: What is a Persistence Data Structure?
A: A persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable.

Q: What is a Judy Array?
A: A Judy array is a complex but very fast associative array data structure that stores integers or strings. It is designed to minimize cache-line fills.

Q: What is a Cuckoo Filter?
A: A Cuckoo filter is a probabilistic data structure that is used to test whether an element is a member of a set. It supports adding and removing items dynamically and achieves higher space efficiency than Bloom filters.

Q: What is 2-SAT (2-Satisfiability)?
A: 2-SAT is a restriction of the SAT problem where each clause has exactly two literals. It can be solved in linear time using strong connected components.

Q: What is Meet-in-the-middle?
A: Meet-in-the-middle is a search technique that divides the search space into two roughly equal parts, searches each part separately, and then combines the results. It is often used to reduce complexity from O(2^n) to O(2^(n/2)).

Q: What is Convex Hull Trick?
A: Convex Hull Trick is a geometry-based optimization technique used to optimize DP transitions that involve linear functions, typically reducing complexity from O(n^2) to O(n log n) or O(n).

Q: What is Gaussian Elimination?
A: Gaussian elimination is an algorithm for solving systems of linear equations. It is also used to find the rank of a matrix, the determinant of a matrix, and the inverse of an invertible square matrix.

Q: What is Reservoir Sampling?
A: Reservoir sampling is a family of randomized algorithms for choosing a simple random sample, without replacement, of k items from a population of unknown size n in a single pass over the items.

Q: What is Boyer-Moore Majority Vote Algorithm?
A: This algorithm finds a majority element (an element that appears more than n/2 times) in an array in O(n) time and O(1) space.

Q: What is Kadane's Algorithm?
A: Kadane's algorithm is used to find the maximum sum contiguous subarray within a one-dimensional array of numbers.

Q: What is Flood Fill Algorithm?
A: Flood fill is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs.

Q: What is Lee Algorithm?
A: The Lee algorithm is a possible solution for maze routing problems. It always gives an optimal solution, if one exists, but is slow and memory intensive.

Q: What is Sparse Table?
A: A sparse table is a data structure that allows answering range queries (like Range Minimum Query) on a static array in O(1) time after O(n log n) preprocessing.

Q: What is Dinic's Algorithm?
A: Dinic's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network. It improves on Edmonds-Karp by using a level graph and finding blocking flows.

Q: What is SPFA (Shortest Path Faster Algorithm)?
A: SPFA is an improvement of the Bellman-Ford algorithm which computes single-source shortest paths in a weighted directed graph. It works well on random sparse graphs but has a worst-case exponential time complexity.

Q: What is a DAG?
A: A Directed Acyclic Graph (DAG) is a directed graph with no directed cycles. It is the basic structure used in topological sorting.

Q: What is a Forest?
A: A forest is an undirected graph in which any two vertices are connected by at most one path. Equivalently, a forest is a disjoint union of trees.

Q: What is a Multigraph?
A: A multigraph is a graph which is permitted to have multiple edges (also called parallel edges), that is, edges that have the same end nodes.

Q: What is a Hypergraph?
A: A hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

Q: What is a Planar Graph?
A: A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that no edges cross each other.

Q: What is Euler's Formula (Graphs)?
A: For a connected planar graph with v vertices, e edges, and f faces, v - e + f = 2.

Q: What is the Maximum Flow Min-Cut Theorem?
A: The Max-Flow Min-Cut theorem states that in a flow network, the maximum amount of flow possible from source to sink is equal to the capacity of the minimum cut.

Q: What is Push-Relabel Algorithm?
A: The push-relabel algorithm is an algorithm for computing maximum flows in a flow network. It is generally more efficient than the Ford-Fulkerson algorithm.

Q: What is Edmonds-Karp Algorithm?
A: The Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network in O(V E^2) time. It uses BFS to find augmenting paths.

Q: What is the Simplex Algorithm?
A: The Simplex algorithm is a popular algorithm for linear programming. It moves along the edges of the feasible region (polytope) to find the optimal solution.

Q: What is a Randomized Algorithm (Monte Carlo)?
A: A Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Running it more times reduces the error probability.

Q: What is a Randomized Algorithm (Las Vegas)?
A: A Las Vegas algorithm is a randomized algorithm that always produces the correct result, but its running time is a random variable (it might take longer sometimes).

Q: What is a UUID/GUID in DSA context?
A: Universally Unique Identifier (UUID) or Globally Unique Identifier (GUID) is a 128-bit label. In DSA, they are often used as keys where collision probability must be negligible without central coordination.

Q: What is the difference between B-Tree and B+ Tree?
A: In a B-Tree, keys and data are stored in both internal and leaf nodes. In a B+ Tree, all data is stored in the leaf nodes, and internal nodes only contain keys for indexing. B+ Trees usually have linked leaves for fast sequential access.

Q: What is an XOR Linked List?
A: An XOR linked list is a space-efficient implementation of a doubly linked list. Instead of storing two pointers (prev, next), it stores the XOR of the two pointers.

Q: What is an Unrolled Linked List?
A: An Unrolled Linked List is a variation of the linked list where each node stores an array of elements instead of just one. It improves cache locality.

Q: What is a Shadow Paging?
A: Shadow paging is a technique used in database systems to provide atomicity and durability. It maintains two page tables: current and shadow. Updates are made to new pages, and the shadow table is switched to current on commit.

Q: What is Write-Ahead Logging (WAL)?
A: WAL is a family of techniques for providing atomicity and durability in database systems. The key concept is that modifications are written to a log file before they are applied to the main database files.

Q: What is the CAP Theorem?
A: The CAP theorem states that a distributed data store can only provide two of the following three guarantees: Consistency, Availability, and Partition Tolerance.

Q: What is HyperLogLog?
A: HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset. It uses very little memory.

Q: What is Count-Min Sketch?
A: Count-Min Sketch is a probabilistic data structure that serves as a frequency table of events in a stream of data. It uses hash functions to map events to frequencies, but can overestimate counts.

Q: What is MinHash?
A: MinHash is a technique for quickly estimating how similar two sets are. It is often used to estimate the Jaccard similarity coefficient.

Q: What is Geohash vs Quadtree?
A: Geohash encodes a 2D location into a string, effectively linearizing the grid. A Quadtree is a tree structure partitioning space. Geohashes are often implemented using Z-order curves (related to Quadtrees).

Q: What is an R-Tree?
A: R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.

Q: What is Burrows-Wheeler Transform (BWT)?
A: BWT is a block-sorting compression algorithm that rearranges a character string into runs of similar characters. It is useful for compression (like bzip2).

Q: What is Run-Length Encoding (RLE)?
A: RLE is a simple form of lossless data compression in which runs of data (sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count.

Q: What is Huffman Coding vs Arithmetic Coding?
A: Huffman coding assigns variable-length codes to input characters. Arithmetic coding encodes the entire message into a single number n where 0.0 <= n < 1.0. Arithmetic coding is generally more efficient but more complex.

Q: What is Levenshtein vs Hamming Distance?
A: Levenshtein distance measures difference between two sequences allowing insertions, deletions, and substitutions. Hamming distance only allows substitutions and requires strings of equal length.

Q: What is Jaccard Similarity?
A: Jaccard similarity measures the similarity between two sets. It is defined as the size of the intersection divided by the size of the union of the sample sets.

Q: What is Cosine Similarity?
A: Cosine similarity is a measure of similarity between two non-zero vectors of an inner product space. It is defined to be the cosine of the angle between them.

Q: What is Euclidean vs Manhattan Distance?
A: Euclidean distance is the straight-line distance between two points. Manhattan distance is the distance between two points measured along axes at right angles (grid-like).

Q: What is Little-Endian vs Big-Endian?
A: Endianness refers to the order of bytes in a word. Big-endian stores the most significant byte at the smallest memory address. Little-endian stores the least significant byte at the smallest address.

Q: What is Garbage Collection (Mark and Sweep)?
A: Mark and Sweep is a garbage collection algorithm. It has two phases: Mark (traverse all reachable objects and mark them) and Sweep (scan memory and reclaim unmarked objects).

Q: What is a Race Condition?
A: A race condition occurs when two or more threads can access shared data and they try to change it at the same time. The result depends on the order of execution.

Q: What is a Deadlock?
A: Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.

Q: What is a Livelock?
A: Livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing.

Q: What is a Mutex vs Semaphore?
A: A Mutex (Mutual Exclusion) is a locking mechanism used to synchronize access to a resource (only one owner). A Semaphore is a signaling mechanism (can allow N accesses).

Q: What is CAS (Compare And Swap)?
A: CAS is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents to a new given value.

Q: What is the ABA Problem?
A: The ABA problem occurs in lock-free programming when a location reads 'A', then changes to 'B', then back to 'A'. A thread may incorrectly assume the state hasn't changed.

Q: What is False Sharing?
A: False sharing is a performance-degrading usage pattern that can arise in systems with distributed cache. It occurs when threads on different processors modify variables that reside on the same cache line.

Q: What is Branch Prediction?
A: Branch prediction is a strategy used in CPU design to guess which way a branch (e.g., an if-then-else structure) will go before this is known for sure, to improve flow in the instruction pipeline.