Algorithms Answers

Basic Algorithms Answers

#	Question	Answer	Examples
1	What is an Algorithm?	A step-by-step set of instructions to solve a problem or perform a task	Sorting, searching, finding the shortest path
2	What is Sorting?	Arranging elements in a specific order (e.g., ascending, descending)	Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort
3	What is Searching?	Finding a specific element within a collection of data	Linear Search, Binary Search
4	What is Linear Search?	Checks each element sequentially until the target is found	O(n) time complexity
5	What is Binary Search?	Repeatedly divides the search interval in half	O(log n) time complexity (requires sorted data)
6	What is Bubble Sort?	Repeatedly compares adjacent elements and swaps them if they are in the wrong order	O(n^2) time complexity
7	What is Selection Sort?	Selects the minimum element from the unsorted part and puts it at the beginning	O(n^2) time complexity
8	What is Insertion Sort?	Builds the sorted array one element at a time	O(n^2) time complexity (but efficient for nearly sorted arrays)
9	What is Merge Sort?	Divides the array into two halves, sorts them recursively, and merges them	O(n log n) time complexity
10	What is Quick Sort?	Partitions the array around a pivot element and recursively sorts sub-arrays	Average O(n log n) time complexity, worst-case O(n^2)
11	What is Recursion?	A function that calls itself to solve smaller subproblems	Calculating factorial (n! = n * factorial(n-1))
12	What is a Base Case in Recursion?	The condition that stops the recursion	if (n == 0) return 1; for factorial
13	What is the Recursive Step in Recursion?	The part where the function calls itself with a modified input	return n * factorial(n-1); for factorial
14	What is Iteration?	Repeating a block of code using loops (for, while)	Iterating through an array using a for loop
15	What is a Palindrome?	A sequence that reads the same forwards and backward	"level", "racecar", "Madam"

Intermediate Algorithms Answers

#	Question	Answer	Examples
1	What is Dynamic Programming?	Solving problems by breaking them down into smaller, overlapping subproblems and storing the results	Fibonacci sequence, Knapsack problem, Longest Common Subsequence.
2	What is Memoization?	Storing the results of expensive function calls and returning the cached result when encountered again	Storing computed Fibonacci numbers in a cache/map.
3	What is Tabulation (Bottom-Up DP)?	Building up the solution from smaller subproblems to larger ones	Filling a table with results of subproblems, starting from base cases.
4	What is a Greedy Algorithm?	Making locally optimal choices at each step with the hope of finding a globally optimal solution	Dijkstra's algorithm, Prim's algorithm, Kruskal's algorithm.
5	What is Backtracking?	Exploring all possible solutions by building candidates incrementally, abandoning branches that don't lead to a solution	N-Queens problem, Sudoku solver.
6	What is Breadth-First Search (BFS)?	A graph/tree traversal algorithm that explores neighbor nodes at the present depth prior to moving to nodes at the next depth level	Uses a queue; explores all nodes at one level before moving to the next.
7	What is Depth-First Search (DFS)?	A graph/tree traversal algorithm that explores as far as possible along each branch before backtracking	Uses a stack (or recursion); explores one branch fully before trying another.
8	What is a Sliding Window Technique?	An algorithmic technique for solving problems involving a "window" of a fixed size that slides over data	Finding the maximum sum of a subarray of size k.
9	What is the Two Pointers Technique?	An algorithmic technique using two pointers (indices) to traverse a data structure	Finding pairs in a sorted array that sum to a target value.
10	What is a Hash Table (Dictionary/Map)?	A data structure that uses a hash function to map keys to indices in an array	Stores key-value pairs; provides fast lookups, insertions, and deletions.
11	What is a Hash Collision?	When two different keys map to the same index in a hash table	Solutions include Separate Chaining or Open Adressing (Linear Probing, Quadratic Probing).
12	What is a Priority Queue?	A queue where elements are served based on their priority (not just FIFO)	Often implemented using a Heap (Min-Heap or Max-Heap).
13	What is a Heap?	A specialized tree-based data structure that satisfies the heap property (parent-child relationship)	Min-Heap (parent <= children), Max-Heap (parent >= children).
14	What is a Trie (Prefix Tree)?	A tree-like data structure used for efficient retrieval of keys in a dataset	Used for autocomplete, spell checking, dictionary implementations.
15	What is a Balanced BST (e.g., AVL, Red-Black)?	A BST that automatically adjusts itself to maintain balance, ensuring efficient operations	Prevents skewed trees, guaranteeing O(log n) time complexity for operations.

Advanced Algorithms Answers

#	Question	Answer	Examples
1	What is Dijkstra's Algorithm?	Finds the shortest paths from a source node to all other nodes in a graph with non-negative edge weights	Uses a priority queue to explore nodes in increasing order of distance from the source.
2	What is the Floyd-Warshall Algorithm?	Finds the shortest paths between all pairs of vertices in a graph	Uses dynamic programming; works with negative edge weights (but no negative cycles).
3	What is Prim's Algorithm?	Finds a Minimum Spanning Tree (MST) for a connected, undirected, weighted graph	Uses a greedy approach with a priority queue.
4	What is Kruskal's Algorithm?	Finds a Minimum Spanning Tree (MST) for a connected, undirected, weighted graph	Uses a greedy approach, sorting edges by weight and adding them if they don't form a cycle (often with Union-Find).
5	What is a Disjoint Set Union (Union-Find)?	A data structure that keeps track of a partition of a set of elements	Used for finding minimum spanning trees (Kruskal's algorithm), detecting cycles in graphs.
6	What is Topological Sort?	A linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge from vertex u to vertex v, u comes before v in the ordering	Used for scheduling tasks, resolving dependencies.
7	What is Maximum Flow?	The maximum amount of flow that can pass from a source node to a sink node in a network	Ford-Fulkerson algorithm, Edmonds-Karp algorithm.
8	What is Minimum Cut?	A set of edges whose removal disconnects the source from the sink in a network	Max-Flow Min-Cut Theorem states that the maximum flow equals the capacity of the minimum cut.
9	What is the Longest Common Subsequence (LCS)?	Finding the longest subsequence that is common to two or more sequences	Often solved using dynamic programming.
10	What is the Knapsack Problem?	Selecting a subset of items with weights and values to maximize the total value within a given weight capacity	Often solved using dynamic programming or greedy approaches.
11	What is the Traveling Salesperson Problem (TSP)?	Finding the shortest possible route that visits each city exactly once and returns to the origin city	NP-hard problem; often solved using dynamic programming (for small instances) or approximation algorithms.
12	What is P vs. NP?	The question of whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time	A fundamental open problem in computer science.
13	What is NP-Complete?	Class of problems that are at least as hard as the hardest problem in NP	Examples include TSP, Clique, Vertex Cover.
14	What is an Approximation Algorithm?	An algorithm that finds a solution that is close, but not necessarily optimal, in polynomial time	Used for NP-hard problems where finding the exact optimal solution is computationally expensive.
15	What is a Randomized Algorithm?	An algorithm that uses randomness as part of its logic	Quick Sort (random pivot selection), randomized primality testing.