🚀 Coding Interview Questions with Answers (Part 7)

6️⃣1️⃣ What is Graph Traversal?
Answer:
Graph traversal is the process of visiting every vertex (node) in a graph in a systematic way.
The two most common graph traversal algorithms are:
• Breadth-First Search (BFS)
• Depth-First Search (DFS)

Applications:
• Finding paths in a graph
• Network routing
• Social network analysis
• Web crawling

6️⃣2️⃣ What is the Difference Between BFS and DFS?
Answer:
Breadth-First Search (BFS)
• Visits nodes level by level.
• Uses a Queue data structure.
• Finds the shortest path in an unweighted graph.
• Requires more memory for large graphs.

Depth-First Search (DFS)
• Explores one path completely before backtracking.
• Uses a Stack (or recursion).
• Does not always find the shortest path.
• Typically uses less memory than BFS.

6️⃣3️⃣ What is a Trie?
Answer:
A Trie (Prefix Tree) is a tree-like data structure used to store and search strings efficiently.
Applications:
• Autocomplete
• Spell checking
• Dictionary lookup
• Search engines
Time Complexity:
• Search: O(L)
• Insert: O(L)
Where L is the length of the word.

6️⃣4️⃣ What is a Segment Tree?
Answer:
A Segment Tree is a binary tree used to perform efficient range queries and updates on an array.
Applications:
• Range Sum Query
• Minimum/Maximum Query
• Competitive Programming
Time Complexity:
• Build: O(n)
• Query: O(log n)
• Update: O(log n)

6️⃣5️⃣ What is a Fenwick Tree (Binary Indexed Tree)?
Answer:
A Fenwick Tree is a data structure used to efficiently calculate prefix sums and update elements in an array.
Advantages:
• Less memory than Segment Tree
• Easier implementation
• Fast updates and queries
Time Complexity:
• Update: O(log n)
• Query: O(log n)

6️⃣6️⃣ What is a Disjoint Set (Union-Find)?
Answer:
A Disjoint Set, also known as Union-Find, is a data structure used to maintain a collection of non-overlapping sets.
It supports two operations:
• Find: Determines which set an element belongs to.
• Union: Merges two sets into one.
Applications:
• Kruskal's Minimum Spanning Tree Algorithm
• Cycle Detection
• Network Connectivity

6️⃣7️⃣ What is an Adjacency Matrix?
Answer:
An Adjacency Matrix is a 2D array used to represent a graph.
• Rows and columns represent vertices.
• A value of 1 (or the edge weight) indicates a connection.
• A value of 0 indicates no connection.
Advantages: Fast edge lookup (O(1))
Disadvantages: Uses O(V²) memory, making it inefficient for sparse graphs.

6️⃣8️⃣ What is an Adjacency List?
Answer:
An Adjacency List represents a graph by storing a list of neighboring vertices for each vertex.
Advantages: Requires O(V + E) memory. Efficient for sparse graphs.
Disadvantages: Edge lookup is slower than an adjacency matrix.

6️⃣9️⃣ What is a Circular Linked List?
Answer:
A Circular Linked List is a linked list in which the last node points back to the first node instead of pointing to "NULL".
Applications:
• CPU Scheduling
• Multiplayer Games
• Circular Buffers
• Music Playlists
Benefit: Traversal can continue indefinitely without restarting.

7️⃣0️⃣ What is a Doubly Linked List?
Answer:
A Doubly Linked List is a linked list where each node contains:
• Data
• Pointer to the next node
• Pointer to the previous node
Advantages: Supports forward and backward traversal. Easier insertion and deletion compared to a singly linked list.
Disadvantages: Requires extra memory for the previous pointer. Slightly more complex to implement.

🔥 Double Tap ❤️ For Part-8