✅ Top DSA Interview Questions with Answers: Part-3 🧠

21. What is the Sliding Window technique? 
It’s an optimization method used to reduce time complexity in problems involving arrays or strings. You create a "window" over a subset of data and slide it as needed, updating results on the go. 
Example use case: Find the maximum sum of any k consecutive elements in an array.

22. Explain the Two-Pointer technique. 
This involves using two indices (pointers) to traverse a data structure, usually from opposite ends or the same direction. It's helpful for searching pairs or reversing sequences efficiently. 
Common problems: Two-sum, palindrome check, sorted array partitioning.

23. What is the Binary Search algorithm? 
It’s an efficient algorithm to find an element in a sorted array by repeatedly dividing the search range in half. 
Time Complexity: O(log n) 
Key idea: Compare the target with the middle element and eliminate half the array each step.

24. What is the Merge Sort algorithm? 
A divide-and-conquer sorting algorithm that splits the array into halves, sorts them recursively, and then merges them. 
Time Complexity: O(n log n) 
Stable? Yes 
Extra space? Yes, due to merging.

25. What is the Quick Sort algorithm?
It chooses a pivot, partitions the array so elements < pivot are left, and > pivot are right, then recursively sorts both sides. 
Time Complexity: Avg – O(n log n), Worst – O(n²) 
Fast in practice, but not stable.

26. Difference between Merge Sort and Quick Sort 
- Merge Sort is stable, consistent in performance (O(n log n)), but uses extra space. 
- Quick Sort is faster in practice and works in-place, but may degrade to O(n²) if pivot is poorly chosen.

27. What is Insertion Sort and how does it work? 
It builds the sorted list one item at a time by comparing and inserting items into their correct position. 
Time Complexity: O(n²) 
Best Case (nearly sorted): O(n) 
Stable? Yes 
Space: O(1)

28. What is Selection Sort? 
It finds the smallest element from the unsorted part and swaps it with the beginning. 
Time Complexity: O(n²) 
Space: O(1) 
Stable? No 
Rarely used due to inefficiency.

29. What is Bubble Sort and its drawbacks? 
It repeatedly compares and swaps adjacent elements if out of order. 
Time Complexity: O(n²) 
Space: O(1) 
Drawback: Extremely slow for large data. Educational, not practical.

30. What is the time and space complexity of common sorting algorithms?
- Bubble Sort → Time: O(n²), Space: O(1), Stable: Yes 
- Selection Sort → Time: O(n²), Space: O(1), Stable: No 
- Insertion Sort → Time: O(n²), Space: O(1), Stable: Yes 
- Merge Sort → Time: O(n log n), Space: O(n), Stable: Yes 
- Quick Sort → Avg Time: O(n log n), Worst: O(n²), Space: O(log n), Stable: No

Double Tap ♥️ For Part-4

✅ Top DSA Interview Questions with Answers: Part-4 📘⚙️

4️⃣1️⃣ What is Longest Common Subsequence (LCS)? 
LCS is the longest sequence that appears in the same order in both strings but not necessarily contiguously. 
Used in: diff tools, DNA sequencing. 
Approach: Dynamic Programming, O(n × m)

4️⃣2️⃣ What is Longest Increasing Subsequence (LIS)? 
It is the longest subsequence where each element is greater than the previous one. 
Approach: 
- DP: O(n²) 
- Binary Search: O(n log n)

4️⃣3️⃣ What is a Palindrome Substring problem? 
Find the longest or total number of substrings that are palindromes. 
Approach: 
- Expand Around Center (O(n²)) 
- DP Table 
- Manacher’s Algorithm (O(n))

4️⃣4️⃣ Difference between Greedy and Dynamic Programming? 
- Greedy: Makes the best local choice, may miss optimal global solution. 
- DP: Explores all choices with memoization, guarantees optimality. 
Example: 
- Greedy: Coin change (not always optimal) 
- DP: Coin change (optimal)

4️⃣5️⃣ What is Big-O Notation? 
It expresses time/space complexity in terms of input size n. 
Examples: 
- O(1): Constant 
- O(n): Linear 
- O(n²): Quadratic 
- O(log n): Binary Search

4️⃣6️⃣ Time vs Space Complexity? 
- Time Complexity: Time taken vs input size
- Space Complexity: Memory used 
Goal: Optimize both without sacrificing correctness.

4️⃣7️⃣ How to find time complexity of recursive function? 
Use Recurrence Relation 
Example: 
T(n) = T(n/2) + O(1) → O(log n) 
T(n) = 2T(n/2) + O(n) → O(n log n)

4️⃣8️⃣ What are Amortized Time Complexities? 
It’s the average time per operation over a sequence of operations. 
Example: Dynamic array resizing: 
- Most inserts: O(1) 
- Occasional resize: O(n) 
- Amortized: O(1)

4️⃣9️⃣ What is Tail Recursion? 
Recursive call is the last operation in the function. 
Benefit: Optimized by compilers to reduce stack usage. 
Example: 

def factorial(n, acc=1):
    if n == 0:
        return acc
    return factorial(n-1, acc*n)

5️⃣0️⃣ How to solve coding questions in interviews? 
- Understand the problem 
- Ask clarifying questions 
- Think out loud 
- Start with brute force 
- Optimize step-by-step 
- Test edge cases 
- Use clean, modular code

💬 Tap ❤️ for more!

Useful Algorithms for System Design Interviews

💻 Coding Interview Questions

1️⃣ What is the difference between an array and a linked list?
Answer: Arrays use contiguous memory and allow fast indexing. Linked lists use pointers and allow easy insert/delete.

2️⃣ What is time complexity?
Answer: It measures how runtime grows with input size (e.g., O(1), O(n), O(log n)).

3️⃣ What is a stack?
Answer: A data structure that follows LIFO (Last In, First Out).

4️⃣ What is a queue?
Answer: A data structure that follows FIFO (First In, First Out).

5️⃣ What is recursion?
Answer: A function calling itself until a base condition is met.

6️⃣ What is a hash table?
Answer: A data structure that stores key-value pairs for fast lookup.

7️⃣ Difference between == and === (or equivalent)?
Answer: == compares values, === compares value + type.

8️⃣ What is a variable?
Answer: A named storage location for data.

9️⃣ What is an infinite loop?
Answer: A loop that never stops because the exit condition is missing or false.

🔟 What is debugging?
Answer: The process of finding and fixing errors in code.

💻 Coding Interview Questions

1️⃣ What is an algorithm?
Answer: A step-by-step procedure to solve a problem.

2️⃣ What is Big-O notation?
Answer: It describes the worst-case time or space complexity of an algorithm.

3️⃣ What is a binary search?
Answer: A search algorithm that repeatedly divides a sorted array in half.

4️⃣ Linear search vs Binary search?
Answer: Linear search checks every element; binary search divides the search space (needs sorted data).

5️⃣ What is a function?
Answer: A reusable block of code that performs a specific task.

6️⃣ What is a compiler?
Answer: A program that translates source code into machine code.

7️⃣ What is an interpreter?
Answer: A program that executes code line by line.

8️⃣ What is a runtime error?
Answer: An error that occurs while the program is running.

9️⃣ What is memory leak?
Answer: When a program uses memory but fails to release it.

🔟 What is an exception?
Answer: An error that disrupts normal program execution and can be handled.

💻 Coding Interview Questions

1️⃣ What is an object?
Answer: An instance of a class containing data and methods.

2️⃣ What is a class?
Answer: A blueprint used to create objects.

3️⃣ What is OOP?
Answer: Object-Oriented Programming; it organizes code using objects and classes.

4️⃣ Name the four pillars of OOP.
Answer: Encapsulation, Inheritance, Polymorphism, Abstraction.

5️⃣ What is encapsulation?
Answer: Binding data and methods together and restricting direct access.

6️⃣ What is inheritance?
Answer: When a class derives properties and methods from another class.

7️⃣ What is polymorphism?
Answer: One interface, multiple implementations.

8️⃣ What is abstraction?
Answer: Hiding implementation details and showing only essentials.

9️⃣ What is an interface?
Answer: A contract that defines methods without implementation.

🔟 What is method overloading?
Answer: Multiple methods with the same name but different parameters.

PostgreSQL Architecture

💻 Coding Interview Questions

1️⃣ What is a database?
Answer: An organized collection of data for efficient storage and retrieval.

2️⃣ What is SQL?
Answer: Structured Query Language used to manage relational databases.

3️⃣ What is a primary key?
Answer: A unique identifier for each record in a table.

4️⃣ What is a foreign key?
Answer: A key that links one table to another.

5️⃣ What is normalization?
Answer: Organizing data to reduce redundancy.

6️⃣ What is an index in a database?
Answer: A structure that improves data retrieval speed.

7️⃣ What is a JOIN?
Answer: Combines rows from multiple tables based on a condition.

8️⃣ INNER JOIN vs LEFT JOIN?
Answer: INNER returns matching rows; LEFT returns all left-table rows.

9️⃣ What is ACID?
Answer: Atomicity, Consistency, Isolation, Durability.

🔟 What is a transaction?
Answer: A sequence of database operations executed as a single unit.

Program vs Process vs Thread

The “I’ve Never Seen This Before” Moment

🗯Scenario: The interviewer finishes explaining the problem and you realize you have never practiced anything like it.

👉 Do this: Shift into discovery mode. Ask about constraints, input size, and edge cases. Then propose a naive solution first and improve it. This shows structured thinking and calm problem solving, which often scores higher than instantly jumping to an optimal answer.

❔Interviewer:

Explain the difference between horizontal and vertical scaling.

✅ Answer:

Vertical scaling means increasing the resources of a single machine, such as adding more CPU or memory. It is simpler to implement but has hardware limits and can become a single point of failure.

Horizontal scaling means adding more machines and distributing the load across them. It provides better fault tolerance and scalability but introduces additional complexity such as load balancing, data consistency, and distributed coordination.

Modern high scale systems typically favor horizontal scaling because it supports elastic growth and higher availability.

The Memory Usage Question

🗯 Scenario: After solving the problem, the interviewer asks about space complexity and you did not track it.

👉 Do this: Always mention both time and space when presenting a solution. Count auxiliary data structures and recursion stack if present. Technically, many candidates forget that recursion adds implicit space. Calling this out makes you look much more thorough.

💻 Coding Interview Questions

1️⃣ What is a pointer?
Answer: A variable that stores the memory address of another variable.

2️⃣ What is memory allocation?
Answer: The process of reserving memory for program execution.

3️⃣ Stack vs Heap memory?
Answer: Stack is fast and automatic; heap is dynamic and manually managed.

4️⃣ What is garbage collection?
Answer: Automatic memory cleanup of unused objects.

5️⃣ What is a deadlock?
Answer: When processes wait forever for resources held by each other.

6️⃣ What is multithreading?
Answer: Running multiple threads concurrently within a process.

7️⃣ What is synchronization?
Answer: Controlling access to shared resources in concurrent programs.

8️⃣ What is a race condition?
Answer: When multiple threads access shared data unsafely.

9️⃣ What is a process?
Answer: An independent program in execution.

🔟 What is a thread?
Answer: The smallest unit of execution within a process.

The Final Question Trap

🗯 Scenario: The interviewer smiles and says,

Do you have any questions for us?

👉 Do this: Always have one thoughtful question ready. Ask about the team’s biggest technical challenge or what success looks like in the first six months. Sharp questions make you memorable long after the coding part ends.