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!