✅ DSA Interview Questions & Answers – Part 1 🧠💻

1️⃣ What is a Data Structure?
A: A way to store and organize data for efficient access and modification. Examples: Array, Linked List, Stack, Queue, Tree, Graph.

2️⃣ What is the difference between Array and Linked List?
A:
⦁ Array: Fixed size, contiguous memory, fast random access (O(1)), slow insertion/deletion (O(n)).
⦁ Linked List: Dynamic size, nodes in memory connected via pointers, slower access (O(n)), fast insertion/deletion (O(1)) at head or tail.

3️⃣ What is a Stack? Give an example.
A: Stack is a linear data structure following LIFO (Last In First Out).
⦁ Operations: push, pop, peek
⦁ Example: Browser history, Undo functionality in editors.

4️⃣ What is a Queue? Difference between Queue & Stack?
A: Queue is a linear data structure following FIFO (First In First Out).
⦁ Stack: LIFO → Last element added is first to remove.
⦁ Queue: FIFO → First element added is first to remove.
⦁ Example: Print job scheduling, Task scheduling.

5️⃣ What is a Linked List? Types?
A: Linked List is a collection of nodes where each node contains data and a pointer to the next node.
⦁ Types:
⦁ Singly Linked List
⦁ Doubly Linked List
⦁ Circular Linked List

6️⃣ What is the difference between Stack and Heap memory?
A:
⦁ Stack: Stores local variables, function calls; LIFO; automatically managed; faster access.
⦁ Heap: Stores dynamic memory; managed manually or via garbage collection; slower access; flexible size.

7️⃣ What is a Hash Table?
A: A data structure that maps keys to values using a hash function for O(1) average-time access.
⦁ Example: Python dict, Java HashMap.
⦁ Collision Handling: Chaining, Open addressing.

8️⃣ What is the difference between BFS and DFS?
A:
⦁ BFS (Breadth-First Search): Level-wise traversal; uses Queue; finds shortest path in unweighted graphs.
⦁ DFS (Depth-First Search): Deep traversal using Stack/Recursion; uses less memory for sparse graphs.

9️⃣ What is a Binary Search Tree (BST)?
A: A tree where each node:
⦁ Left child < Node < Right child
⦁ Allows O(log n) search, insertion, and deletion on average.
⦁ Not necessarily balanced → worst-case O(n).

🔟 What is Time Complexity?
A: Measure of the number of operations an algorithm takes relative to input size (n).
⦁ Examples:
⦁ O(1) → Constant
⦁ O(n) → Linear
⦁ O(log n) → Logarithmic
⦁ O(n²) → Quadratic

💬 Double Tap ❤️ if you found this helpful!

✅ DSA Interview Questions & Answers – Part 2 🧠💻

1️⃣ What is a Graph?
A: A non-linear data structure with nodes (vertices) connected by edges representing relationships.
⦁ Types: Directed (one-way edges, like Twitter follows), Undirected (bidirectional, like friendships), Weighted (edges with costs, e.g., distances), Unweighted.
⦁ Example: Social networks (users as nodes, connections as edges) or maps (cities and routes)—BFS/DFS traversal is key for shortest paths.

2️⃣ Difference between Tree and Graph?
A:
⦁ Tree: Acyclic (no loops), connected graph with exactly one path between nodes, hierarchical with a root and N-1 edges for N nodes—great for file systems.
⦁ Graph: Can have cycles, multiple paths, disconnected components, and more edges—more flexible but needs cycle detection algorithms like DFS.

3️⃣ What is a Heap?
A: A complete binary tree satisfying the heap property for fast min/max access.
⦁ Max Heap: Parent nodes ≥ children (root is maximum).
⦁ Min Heap: Parent ≤ children (root is minimum).
⦁ Uses: Priority queues (e.g., task scheduling), Heap Sort (O(n log n))—implemented via arrays for efficiency.

4️⃣ What is Recursion? Example?
A: A technique where a function solves a problem by calling itself on smaller inputs until a base case stops it, using implicit stack.
⦁ Example: Factorial: def fact(n): return 1 if n <= 1 else n * fact(n-1). Also Fibonacci or tree traversals—watch for stack overflow on deep calls.

5️⃣ Difference between Recursion and Iteration?
A:
⦁ Recursion: Self-calling with base case, elegant for tree/graph problems but uses call stack (risk of overflow), O(n) space.
⦁ Iteration: Uses loops (for/while), explicit control, lower memory, faster execution—convert recursion via tail optimization for interviews.

6️⃣ What is a Trie?
A: A prefix tree for storing strings in a tree where each node represents a character, enabling fast lookups and prefixes.
⦁ Use Case: Autocomplete (search engines), spell checkers, IP routing—O(m) time for m-length word, space-efficient for common prefixes.

7️⃣ Difference between Linear Search & Binary Search?
A:
⦁ Linear Search: Scans sequentially, O(n) time, works on unsorted data—simple but inefficient for large lists.
⦁ Binary Search: Divides sorted array in half repeatedly, O(log n) time—requires sorted input, ideal for databases or sorted arrays.

8️⃣ What is a Circular Queue?
A: A queue implementation where the rear connects back to front, reusing space to avoid linear queue's "wasted" slots after dequeues.
⦁ Efficient memory usage (no shifting), fixed size, handles wrap-around with modulo—common in buffering systems like OS task queues.

9️⃣ What is a Priority Queue?
A: An abstract data type where elements have priorities; dequeue removes highest/lowest priority first (not FIFO).
⦁ Implemented using: Heaps (binary for O(log n) insert/extract), also arrays or linked lists—used in Dijkstra's algorithm or job scheduling.

🔟 What is Dynamic Programming (DP)?
A: An optimization technique for problems with overlapping subproblems and optimal substructure, solving bottom-up or top-down with memoization to avoid recomputation.
⦁ Example: Fibonacci (store fib(n-1) + fib(n-2)), 0/1 Knapsack (max value without exceeding weight)—reduces exponential to polynomial time.

💬 Double Tap ❤️ if this helped you!