🚀 Coding Interview Questions with Answers (Part 12)

1️⃣1️⃣1️⃣ What is Topological Sorting? 
Answer: 
Topological Sorting is a linear ordering of the vertices in a Directed Acyclic Graph (DAG) such that for every directed edge U → V, vertex U appears before V in the ordering.

Applications: 
• Task scheduling
• Course prerequisite planning
• Dependency resolution
• Build systems

Common Algorithms: 
• Kahn's Algorithm (BFS)
• DFS-based Topological Sort

Time Complexity: O(V + E)

1️⃣1️⃣2️⃣ What is Dijkstra's Algorithm? 
Answer: 
Dijkstra's Algorithm is a graph algorithm used to find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights.

Applications: 
• GPS navigation
• Network routing
• Flight route optimization

Time Complexity: 
• Using Priority Queue: O((V + E) log V)

Limitation: Cannot handle negative edge weights.

1️⃣1️⃣3️⃣ What is Bellman-Ford Algorithm? 
Answer: 
Bellman-Ford is a shortest-path algorithm that works even when a graph contains negative edge weights.

Advantages: 
• Detects negative weight cycles.
• Works with negative edge weights.

Time Complexity: O(V × E) 

Applications: 
• Network routing
• Currency exchange systems
• Graphs with negative weights

1️⃣1️⃣4️⃣ What is Floyd-Warshall Algorithm? 
Answer: 
Floyd-Warshall is an algorithm used to find the shortest paths between every pair of vertices in a weighted graph.

Applications: 
• Network analysis
• Route optimization
• Social network analysis

Time Complexity: O(V³) 

Advantage: Computes all-pairs shortest paths efficiently for smaller graphs.

1️⃣1️⃣5️⃣ What is Kruskal's Algorithm? 
Answer: 
Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted graph.

Steps: 
1. Sort all edges by weight.
2. Pick the smallest edge.
3. Add it if it doesn't create a cycle.
4. Repeat until the MST is complete.

Data Structure Used: Disjoint Set (Union-Find) 

Time Complexity: O(E log E)

1️⃣1️⃣6️⃣ What is Prim's Algorithm? 
Answer: 
Prim's Algorithm is another greedy algorithm used to find the Minimum Spanning Tree (MST).

Unlike Kruskal's algorithm, it starts from any vertex and repeatedly adds the smallest edge connecting the tree to a new vertex.

Time Complexity: 
• Using Priority Queue: O(E log V)

Applications: 
• Network design
• Road construction
• Cable layout

1️⃣1️⃣7️⃣ What is Kadane's Algorithm? 
Answer: 
Kadane's Algorithm efficiently finds the maximum sum of a contiguous subarray.

Idea: 
• Maintain the current maximum sum.
• Update the global maximum whenever a larger sum is found.

Time Complexity: O(n) 

Applications: 
• Stock profit analysis
• Financial data analysis
• Maximum subarray problems

1️⃣1️⃣8️⃣ What is KMP (Knuth-Morris-Pratt) Algorithm? 
Answer: 
KMP is a string-matching algorithm used to search for a pattern within a text efficiently.

It avoids unnecessary comparisons by using a Longest Prefix Suffix (LPS) array.

Time Complexity: O(n + m) 

Where: 
• n = Length of the text
• m = Length of the pattern

Applications: 
• Text editors
• Search engines
• DNA sequence matching

1️⃣1️⃣9️⃣ What is Rabin-Karp Algorithm? 
Answer: 
Rabin-Karp is a string-searching algorithm that uses hashing to find a pattern within a text.

Instead of comparing every character, it compares hash values first.

Time Complexity: 
• Average Case: O(n + m)
• Worst Case: O(n × m)

Applications: 
• Plagiarism detection
• Pattern matching
• Document searching

1️⃣2️⃣0️⃣ What is Huffman Coding? 
Answer: 
Huffman Coding is a lossless data compression algorithm that assigns shorter binary codes to frequently occurring characters and longer codes to less frequent characters.

Applications: 
• ZIP files
• File compression
• JPEG compression
• Data transmission

Advantages: 
• Reduces file size
• Preserves original data
• Efficient for text compression

🔥 Double Tap ❤️ For Part-13