✅
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!
