🚀 Coding Interview Questions with Answers — Part 6

📊 Sorting, Searching & Dynamic Programming

🚀 51. How do you implement quicksort and mergesort? 
Both are divide-and-conquer sorting algorithms.

🔹 Quicksort 
🔹 Idea 
1. Pick pivot
2. Partition array
3. Recursively sort halves

🔹 Python Quicksort 

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr)//2]

    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quicksort(left) + middle + quicksort(right)

print(quicksort([5,2,8,1,3]))


🔹 Complexity 
Case: Best/Average → Complexity: O(n log n) 
Case: Worst → Complexity: O(n²) 

🔹 Mergesort 
🔹 Idea 
1. Split array
2. Sort recursively
3. Merge sorted halves

🔹 Python Mergesort 

def mergesort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr)//2

    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result


🔹 Complexity 
Case: All Cases → Complexity: O(n log n) 

🔹 Interview Tip 
Mergesort is stable. Quicksort is usually faster in practice.

🚀 52. How do you implement binary search in a rotated sorted array? 
Example: 
Target: 0[4][5][6][7][0][1][2] 

🔹 Key Idea 
One half is always sorted. 

🔹 Python Solution 

def search(nums, target):
    left, right = 0, len(nums)-1

    while left <= right:
        mid = (left + right)//2

        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1


🔹 Complexity 
Time: O(log n) 
Space: O(1) 

🔹 Interview Tip 
Very common medium-level interview problem.

🚀 53. How do you implement insertion sort and when is it useful? 
Insertion sort inserts elements into correct position.

🔹 Python Solution 

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1

        arr[j+1] = key

    return arr


🔹 Complexity 
Case: Best → Complexity: O(n) 
Case: Average/Worst → Complexity: O(n²) 

🔹 When Useful? 
✅ Small datasets 
✅ Nearly sorted arrays 
✅ Online sorting 

🔹 Interview Tip 
Simple but important for fundamentals.

🚀 54. How do you find the k-th largest element?

🔹 Efficient Approach 
Use: Min Heap OR Quickselect 

🔹 Heap Solution 

import heapq

def kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]

print(kth_largest([3,2,1,5,6,4], 2))


🔹 Output 
5 

🔹 Complexity 
Time: O(n log k) 
Space: O(k) 

🔹 Interview Tip 
Quickselect is often asked as optimization.

🚀 55. What is the difference between DFS and backtracking? 
Both use recursion, but purpose differs.

🔹 DFS 
Goal: Traverse/search graph or tree 

🔹 Backtracking 
Goal: Try all possibilities and undo choices 

🔹 Example Problems 
DFS: Tree traversal, Graph traversal 
Backtracking: N-Queens, Sudoku, Permutations 

🔹 Key Difference 
DFS: Traversal, No undo step 
Backtracking: Decision making, Includes undo step 

🔹 Interview Tip 
Backtracking = DFS + constraint checking + undoing choices.

🚀 56. How do you solve the “N-Queens” problem? 
Place N queens so none attack each other.

🔹 Backtracking Solution

def solve_n_queens(n):
    board = [-1] * n
    result = []