Coding Interview Resources

🚀 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 = []

❤1

1.13K views11:00