Chapter 13 — LeetCode & Algorithms Interview Questions

This chapter is designed for Senior Software Engineer interviews.

For each problem, focus on:

  1. Understanding the pattern
  2. Explaining your approach
  3. Complexity analysis
  4. Writing clean code

Most companies do not expect only a working solution. They evaluate:

Examples use Python, because it is concise for algorithm interviews.

1. What is Big-O notation?

Interview Answer

Big-O notation describes how the runtime or memory usage of an algorithm grows as the input size increases.

It helps compare algorithm efficiency.

Common Complexities

O(1) — Constant Time

Execution time does not depend on input size.

Example:

value = array[0]

Whether the array has:

10 items

or:

10 million items

the operation takes the same time.

O(n) — Linear Time

Runtime grows proportionally with input size.

Example:

for item in array:

    print(item)

Array:

10 items → 10 operations

1000 items → 1000 operations

O(log n) — Logarithmic Time

Input is reduced by half each step.

Example:

Binary search.

1000 items

500

250

125

...

O(n²) — Quadratic Time

Usually nested loops.

Example:

for i in array:

    for j in array:

        print(i,j)

Complexity Table

Complexity

Example

O(1)

Hash lookup

O(log n)

Binary search

O(n)

Loop

O(n log n)

Merge sort

O(n²)

Nested loops

Senior Answer

Big-O describes how an algorithm scales as input grows. I use it to evaluate performance trade-offs between different solutions.

2. How do you analyze an algorithm?

Interview Answer

I analyze:

  1. Time complexity
  2. Space complexity
  3. Input constraints
  4. Possible optimizations

Example:

Find maximum number:

def find_max(nums):

    max_value = nums[0]

    for n in nums:

        if n > max_value:

            max_value = n

    return max_value

Time:

Loop runs:

n times

Therefore:

O(n)

Space:

Only one variable:

max_value

Therefore:

O(1)

Senior Answer

I first understand the constraints, then choose an appropriate data structure and evaluate both runtime and memory complexity.

3. How do you solve the Two Sum problem?

Problem

Given:

nums = [2,7,11,15]

target = 9

Return indexes of two numbers:

2 + 7 = 9

Output:

[0,1]

Brute Force Solution

Check every pair:

def two_sum(nums, target):

    for i in range(len(nums)):

        for j in range(i+1,len(nums)):

            if nums[i] + nums[j] == target:

                return [i,j]

Complexity:

Time:

O(n²)

Space:

O(1)

Optimized Solution Using Hash Map

Idea:

Store numbers we have already seen.

For each number:

needed = target - current

If needed exists:

we found the answer.

Code:

def two_sum(nums, target):

    seen = {}

    for i, value in enumerate(nums):

        complement = target - value

        if complement in seen:

            return [seen[complement], i]

        seen[value] = i

Example:

nums=[2,7,11,15]

target=9

Step 1:

value=2

needed=7

store:

{

2:0

}

Step 2:

value=7

needed=2

2 exists

return [0,1]

Complexity:

Time:

O(n)

Space:

O(n)

Senior Answer

I use a hash map to store previously visited numbers. This reduces the solution from quadratic time to linear time.

4. What is the difference between Array and Hash Table?

Interview Answer

They solve different problems.

Array

Stores elements sequentially.

Example:

numbers = [10,20,30]

Access:

numbers[1]

Complexity:

O(1)

Search:

O(n)

because we may scan every element.

Hash Table

Stores key-value pairs.

Example:

user = {

    "id":101,

    "name":"John"

}

Lookup:

user["id"]

Average:

O(1)

Comparison

Array

Hash Table

Access by index

Excellent

No

Lookup by key

Poor

Excellent

Order

Yes

Depends

Memory

Less

More

Senior Answer

Arrays provide fast indexed access, while hash tables provide fast lookup by key. I choose based on the access pattern required.

5. How does a Hash Table work internally?

Interview Answer

A hash table uses a hash function to convert a key into an array index.

Example:

Key:

"John"

Hash function:

hash("John")

Result:

index 5

Store:

Bucket[5] = John

Architecture:

Key

 |

Hash Function

 |

Array Index

 |

Bucket

Collision Problem

Two keys can generate the same index.

Example:

John → index 5

Mike → index 5

Solutions:

Python Dictionary

Python:

dictionary = {}

is implemented using a hash table.

Senior Answer

Hash tables use hashing to map keys to storage locations, providing average O(1) insertion and lookup. Collisions are handled using techniques such as chaining.

6. What is the difference between Stack and Queue?

Interview Answer

Both are linear data structures but follow different access rules.

Stack

LIFO:

Last In, First Out.

Example:

Stack of plates.

Top

Plate 3

Plate 2

Plate 1

Operations:

Push:

add item

Pop:

remove last item

Python:

stack=[]

stack.append(10)

stack.pop()

Uses:

Queue

FIFO:

First In, First Out.

Example:

People waiting in line.

First → Second → Third

Python:

from collections import deque

queue = deque()

queue.append(10)

queue.popleft()

Uses:

Senior Answer

A stack uses LIFO ordering and is useful for nested operations, while a queue uses FIFO ordering and is used for scheduling and breadth-first processing.

7. Solve Valid Parentheses

Problem

Given:

"()[]{}"

Return:

True

Invalid:

"(]"

Return:

False

Approach

Use a stack.

Opening brackets:

push

Closing brackets:

compare with top

Code:

def is_valid(s):

    stack = []

    pairs = {

        ')':'(',

        ']':'[',

        '}':'{'

    }

    for char in s:

        if char in pairs:

            if not stack or stack[-1] != pairs[char]:

                return False

            stack.pop()

        else:

            stack.append(char)

    return len(stack)==0

Example:

Input:

{[]}

Process:

{

stack=[{]

[

stack=[{,[ ]

]

remove [

}

remove {

Valid.

Complexity:

Time:

O(n)

Space:

O(n)

Senior Answer

This problem follows the stack pattern because brackets must be closed in reverse order of opening.

8. What is the Two Pointer technique?

Interview Answer

Two pointers use two indexes to efficiently process arrays, usually reducing nested loops.

Example:

Sorted array:

[1,2,3,4,6]

Find pair:

sum=7

Use:

left

right

L             R

1 2 3 4 6

If:

1+6 > 7

move right.

If:

1+6 ==7

found.

Code:

def two_sum_sorted(nums,target):

    left=0

    right=len(nums)-1

    while left < right:

        total=nums[left]+nums[right]

        if total==target:

            return [left,right]

        elif total < target:

            left+=1

        else:

            right-=1

Complexity:

Time:

O(n)

Space:

O(1)

Common Problems

Two pointers appear in:

9. What is the Sliding Window technique?

Interview Answer

Sliding window maintains a moving range of elements to avoid repeated calculations.

Example:

Find maximum sum of 3 consecutive numbers.

Array:

[2,1,5,1,3,2]

Window:

[2,1,5]

Move:

[1,5,1]

Instead of recalculating:

O(n*k)

we update:

remove old value

add new value

Code:

def max_sum(nums,k):

    window=sum(nums[:k])

    result=window

    for i in range(k,len(nums)):

        window += nums[i]

        window -= nums[i-k]

        result=max(result,window)

    return result

Complexity:

Time:

O(n)

Space:

O(1)

Common Problems

10. What is recursion?

Interview Answer

Recursion is when a function calls itself to solve smaller versions of the same problem.

Example:

Factorial:

5!

5 * 4 * 3 * 2 * 1

Recursive solution:

def factorial(n):

    if n==1:

        return 1

    return n * factorial(n-1)

Execution:

factorial(5)

5 * factorial(4)

5 * 4 * factorial(3)

...

Every recursion needs:

Base Case

Stopping condition.

Example:

if n==1:

Recursive Case

Smaller problem.

Example:

factorial(n-1)

Complexity:

Time:

O(n)

Space:

O(n)

because of call stack.

Senior Answer

Recursion solves problems by breaking them into smaller subproblems. I always define a clear base case to avoid infinite recursion.

End of Chapter 13 — LeetCode & Algorithms

Covered:

✅ Big-O
✅ Complexity Analysis
✅ Two Sum
✅ Arrays vs Hash Tables
✅ Hash Table Internals
✅ Stack
✅ Queue
✅ Valid Parentheses
✅ Two Pointers
✅ Sliding Window
✅ Recursion

11. What is a Linked List?

Interview Answer

A linked list is a linear data structure where elements (nodes) are connected using references instead of being stored in continuous memory locations.

Array vs Linked List

Array

[10][20][30][40]

Memory:

1000 1004 1008 1012

Elements are stored together.

Linked List

+------+      +------+      +------+

| 10 | ---> | 20 | ---> | 30 |

+------+      +------+      +------+

Each node contains:

Node Structure

Python example:

class Node:

    def __init__(self, value):

        self.value = value

        self.next = None

Advantages

Fast insertion/deletion

Adding a node:

Before:

10 → 20 → 30

Insert 15:

10 → 15 → 20 → 30

No shifting required.

Disadvantages

Slow access

To find item 30:

10 → 20 → 30

Need to traverse:

10

 |

20

 |

30

Complexity:

O(n)

Complexity

Operation

Array

Linked List

Access

O(1)

O(n)

Search

O(n)

O(n)

Insert beginning

O(n)

O(1)

Delete beginning

O(n)

O(1)

Senior Answer

Linked lists provide efficient insertion and deletion because nodes are connected through references, but they sacrifice fast random access compared with arrays.

12. How do you reverse a Linked List?

Problem

Given:

1 → 2 → 3 → 4 → NULL

Return:

4 → 3 → 2 → 1 → NULL

Approach

Use three pointers:

Before:

prev    current

NULL     1 → 2 → 3

Change direction:

prev ← current

Python Solution

def reverse_list(head):

    previous = None

    current = head

    while current:

        next_node = current.next

        current.next = previous

        previous = current

        current = next_node

    return previous

Complexity

Time:

O(n)

Space:

O(1)

Senior Answer

I reverse a linked list iteratively by changing each node's next reference while maintaining previous and current pointers. This provides O(n) time and O(1) memory.

13. How do you detect a cycle in a Linked List?

Problem

Example:

1 → 2 → 3 → 4

        ↑   |

        |___|

The list contains a loop.

Solution: Fast and Slow Pointers

Also called:

Floyd's Cycle Detection Algorithm

Use:

Slow pointer:

moves 1 step

Fast pointer:

moves 2 steps

Example:

1 → 2 → 3 → 4 → 5

    ↑             |

    |_____________|

Movement:

slow:

1 → 2 → 3

fast:

1 → 3 → 5 → 3

If they meet:

Cycle exists.

Python

def has_cycle(head):

    slow = head

    fast = head

    while fast and fast.next:

        slow = slow.next

        fast = fast.next.next

        if slow == fast:

            return True

    return False

Complexity

Time:

O(n)

Space:

O(1)

Senior Answer

Floyd's algorithm detects cycles using two pointers moving at different speeds. If a cycle exists, the fast pointer eventually catches the slow pointer.

14. What is Binary Search?

Interview Answer

Binary search finds an element in a sorted collection by repeatedly dividing the search space in half.

Example:

Array:

[1,3,5,7,9,11,13]

Find 9

Middle:

7

9 is greater:

Search right side:

[9,11,13]

Algorithm

  1. Find middle element
  2. Compare target
  3. Remove half of the search space
  4. Repeat

Python

def binary_search(nums, target):

    left = 0

    right = len(nums)-1

    while left <= right:

        middle = (left + right)//2

        if nums[middle] == target:

            return middle

        elif nums[middle] < target:

            left = middle + 1

        else:

            right = middle - 1

    return -1

Complexity

Time:

O(log n)

Space:

O(1)

Requirements

Binary search requires:

Senior Answer

Binary search is efficient because each comparison eliminates half of the remaining search space. It requires sorted input.

15. What is Merge Sort?

Interview Answer

Merge sort is a divide-and-conquer sorting algorithm.

It divides the array into smaller parts, sorts them, and merges them back.

Example:

[8,3,5,1]

Split:

[8,3] [5,1]

Split:

[8][3][5][1]

Merge:

[3,8][1,5]

Final:

[1,3,5,8]

Algorithm

Divide

Split array in half.

Conquer

Sort each half.

Merge

Combine sorted halves.

Python

def merge_sort(nums):

    if len(nums)<=1:

        return nums

    middle=len(nums)//2

    left=merge_sort(nums[:middle])

    right=merge_sort(nums[middle:])

    return merge(left,right)

def merge(left,right):

    result=[]

    while left and right:

        if left[0] < right[0]:

            result.append(left.pop(0))

        else:

            result.append(right.pop(0))

    return result + left + right

Complexity

Time:

O(n log n)

Space:

O(n)

Senior Answer

Merge sort provides predictable O(n log n) performance and is useful when stable sorting and predictable complexity are required.

16. What is a Binary Tree?

Interview Answer

A binary tree is a data structure where each node has at most two children:

Example:

         10

       /      \

      5        20

    /   \

   3     7

Node

class TreeNode:

    def __init__(self,value):

        self.value=value

        self.left=None

        self.right=None

Terminology

Root:

10

Leaf:

3,7,20

Height:

Longest path from root to leaf.

Uses

Senior Answer

A binary tree is a hierarchical structure where each node has up to two children. It is commonly used for searching, sorting, and representing hierarchical data.

17. Explain Binary Search Tree (BST).

Interview Answer

A Binary Search Tree is a binary tree with an ordering rule:

For every node:

Left subtree < Node < Right subtree

Example:

         8

       /     \

      3       10

    /  \        \

   1    6        14

Searching:

Find 6.

Start:

8

6 is smaller:

go left.

3

6 is larger:

go right.

6 found

Complexity

Balanced tree:

Search:

O(log n)

Worst case:

O(n)

Example:

1

 \

  2

   \

    3

Senior Answer

A BST maintains ordering between nodes, allowing efficient search, insertion, and deletion when the tree is balanced.

18. What are Tree Traversals?

Interview Answer

Tree traversal means visiting every node in a tree.

The main types are:

Depth First Search (DFS)

Goes deep before moving sideways.

Three variations:

Preorder

Order:

Root → Left → Right

Example:

     1

    /   \

   2     3

Output:

1 2 3

Inorder

Order:

Left → Root → Right

BST gives sorted output.

Output:

2 1 3

Postorder

Order:

Left → Right → Root

Output:

2 3 1

Python Example

def inorder(node):

    if node:

        inorder(node.left)

        print(node.value)

        inorder(node.right)

Senior Answer

Tree traversal algorithms allow processing hierarchical data. Inorder traversal of a BST is especially useful because it returns values in sorted order.

19. What is Breadth First Search (BFS)?

Interview Answer

BFS explores a tree or graph level by level using a queue.

Example:

         1

      /       \

     2         3

   /   \

  4     5

Traversal:

1 → 2 → 3 → 4 → 5

Algorithm

Use queue:

from collections import deque

def bfs(root):

    queue=deque([root])

    while queue:

        node=queue.popleft()

        print(node.value)

        if node.left:

            queue.append(node.left)

        if node.right:

            queue.append(node.right)

Complexity

Time:

O(n)

Space:

O(n)

Uses

Senior Answer

BFS processes nodes level by level using a queue. It is useful when we need the shortest path in an unweighted graph.

20. What is Depth First Search (DFS)?

Interview Answer

DFS explores as far as possible before backtracking.

It uses:

Example:

       A

      /   \

     B     C

    /

   D

DFS:

A → B → D → C

Recursive Example

def dfs(node):

    if not node:

        return

    print(node.value)

    dfs(node.left)

    dfs(node.right)

Complexity

Time:

O(n)

Space:

O(h)

where h is tree height.

DFS vs BFS

DFS

BFS

Uses stack

Uses queue

Goes deep

Goes wide

Less memory usually

More memory

Good for paths

Good for shortest path

Senior Answer

DFS explores depth-first using recursion or a stack. It is useful for tree traversal, graph exploration, and backtracking problems.

End of Chapter 13 — LeetCode & Algorithms

Covered:

✅ Linked Lists
✅ Reverse Linked List
✅ Cycle Detection
✅ Binary Search
✅ Merge Sort
✅ Binary Trees
✅ Binary Search Trees
✅ Tree Traversals
✅ BFS
✅ DFS

21. What is a Graph?

Interview Answer

A graph is a data structure consisting of:

Graphs represent relationships between objects.

Example:

Social network:

       Alice

       /     \

    Bob      John

      \

       Mike

Nodes:

People

Edges:

Friend relationships

Graph Types

1. Directed Graph

Edges have direction.

Example:

Twitter follow:

A → B

A follows B.

2. Undirected Graph

Edges have no direction.

Example:

Friendship:

A ---- B

3. Weighted Graph

Edges have values.

Example:

Road network:

Toronto ----100km---- Ottawa

Graph Representation

1. Adjacency List

Most common.

Example:

graph = {

    "A":["B","C"],

    "B":["A"],

    "C":["A"]

}

2. Adjacency Matrix

2D array:

   A B C

A   0 1 1

B   1 0 0

C   1 0 0

Senior Answer

A graph models relationships between entities using nodes and edges. I usually use adjacency lists because they provide efficient storage and traversal for most real-world problems.

22. How do you traverse a Graph?

Interview Answer

The two main graph traversal algorithms are:

Example:

      A

     /   \

    B     C

   /

  D

DFS

Go deep first:

A → B → D → C

Uses:

BFS

Go level by level:

A → B → C → D

Uses:

DFS Example

def dfs(graph, node, visited):

    if node in visited:

        return

    visited.add(node)

    print(node)

    for neighbor in graph[node]:

        dfs(graph, neighbor, visited)

Complexity

For graph:

Time:

O(V + E)

where:

Space:

O(V)

Senior Answer

Graph traversal requires tracking visited nodes to avoid infinite loops. BFS is preferred for shortest paths, while DFS is useful for exploration and backtracking.

23. What is Topological Sort?

Interview Answer

Topological sorting orders nodes in a directed acyclic graph (DAG) so that dependencies come before dependent tasks.

Example:

Software build dependencies:

Database

    ↓

Backend

    ↓

Frontend

Correct order:

Database → Backend → Frontend

Real Examples

Algorithm: Kahn's Algorithm

Uses:

Example:

A → C

B → C

Indegree:

A = 0

B = 0

C = 2

Start:

A,B

Remove:

C becomes 0

Python:

from collections import deque

def topological_sort(graph):

    indegree = {}

    for node in graph:

        indegree[node] = 0

    for node in graph:

        for neighbor in graph[node]:

            indegree[neighbor] += 1

    queue = deque(

        [n for n in indegree if indegree[n] == 0]

    )

    result=[]

    while queue:

        node=queue.popleft()

        result.append(node)

        for neighbor in graph[node]:

            indegree[neighbor]-=1

            if indegree[neighbor]==0:

                queue.append(neighbor)

    return result

Complexity:

Time:

O(V+E)

Space:

O(V)

Senior Answer

Topological sorting is used to order dependent tasks in a directed acyclic graph. It is common in build systems, scheduling, and deployment pipelines.

24. What is Dijkstra's Algorithm?

Interview Answer

Dijkstra's algorithm finds the shortest path from one node to all other nodes in a weighted graph with non-negative weights.

Example:

A ----5---- B

|           |

2           1

|           |

C ----3---- D

Find shortest path from A.

It calculates:

A → C = 2

A → B = 5

A → C → D = 5

Uses

Algorithm

Uses:

Priority Queue (Min Heap)

Steps:

  1. Start from source
  2. Pick closest unvisited node
  3. Update distances
  4. Repeat

Python:

import heapq

def dijkstra(graph, start):

    distances = {

        node: float('inf')

        for node in graph

    }

    distances[start]=0

    heap=[(0,start)]

    while heap:

        current_distance,node=heapq.heappop(heap)

        for neighbor,weight in graph[node]:

            distance=current_distance+weight

            if distance < distances[neighbor]:

                distances[neighbor]=distance

                heapq.heappush(

                    heap,

                    (distance,neighbor)

                )

    return distances

Complexity:

Using heap:

O((V+E) log V)

Senior Answer

Dijkstra uses a priority queue to repeatedly select the closest node and relax its edges. It is efficient for shortest-path problems with non-negative weights.

25. What is a Heap / Priority Queue?

Interview Answer

A heap is a tree-based data structure used to quickly retrieve the minimum or maximum element.

Types:

Min Heap

Smallest element at the top.

Example:

       1

      /   \

     3     5

Max Heap

Largest element at the top.

Example:

       10

      /    \

     7      5

Python

Python provides:

import heapq

Min heap:

heap=[]

heapq.heappush(heap,5)

heapq.heappush(heap,2)

heapq.heappop(heap)

Returns:

2

Applications

Complexity

Insert:

O(log n)

Remove:

O(log n)

Get minimum:

O(1)

Senior Answer

A heap provides efficient access to the highest or lowest priority element. I use it for scheduling, priority processing, and algorithms like Dijkstra.

26. How do you find the Kth Largest Element?

Problem

Input:

nums=[3,2,1,5,6,4]

k=2

Output:

5

because:

6,5,4,3,2,1

  ^

 second largest

Solution 1: Sorting

def kth_largest(nums,k):

    nums.sort(reverse=True)

    return nums[k-1]

Complexity:

Time:

O(n log n)

Better Solution: Min Heap

Keep only k elements.

import heapq

def kth_largest(nums,k):

    heap=[]

    for n in nums:

        heapq.heappush(heap,n)

        if len(heap)>k:

            heapq.heappop(heap)

    return heap[0]

Example:

k=2

Maintain:

largest two numbers

Complexity:

Time:

O(n log k)

Space:

O(k)

Senior Answer

For large datasets, I prefer a min heap because it avoids sorting the entire collection and maintains only the k largest elements.

27. What is an LRU Cache?

Interview Answer

LRU means:

Least Recently Used

It removes the item that has not been accessed for the longest time.

Example:

Cache size:

3

Operations:

Add A

Add B

Add C

Access A

Add D

Cache:

B C A

B is removed because it was least recently used.

Implementation

LRU requires:

  1. Hash Map

For O(1) lookup.

  1. Doubly Linked List

For O(1) insertion/removal.

Architecture:

Hash Map

    |

Node addresses

    |

Doubly Linked List

Python:

from collections import OrderedDict

class LRUCache:

    def __init__(self, capacity):

        self.cache=OrderedDict()

        self.capacity=capacity

    def get(self,key):

        if key not in self.cache:

            return -1

        value=self.cache.pop(key)

        self.cache[key]=value

        return value

    def put(self,key,value):

        if key in self.cache:

            self.cache.pop(key)

        self.cache[key]=value

        if len(self.cache)>self.capacity:

            self.cache.popitem(last=False)

Uses

Senior Answer

LRU Cache combines a hash map for fast lookup and a doubly linked list for tracking usage order, achieving O(1) get and put operations.

28. What is Backtracking?

Interview Answer

Backtracking is a technique where we build a solution step by step and undo choices when they lead to invalid results.

Pattern:

Choose

↓

Explore

↓

Undo

Example:

Generate permutations:

Input:

[1,2,3]

Output:

123

132

213

231

312

321

Algorithm:

def backtrack(path):

    if complete(path):

        result.append(path.copy())

        return

    for choice in choices:

        path.append(choice)

        backtrack(path)

        path.pop()

Applications

Senior Answer

Backtracking explores possible solutions recursively and removes invalid choices. It is useful for problems involving combinations, permutations, and constraint solving.

29. Generate Permutations

Problem

Input:

[1,2,3]

Return:

[

[1,2,3],

[1,3,2],

[2,1,3],

...

]

Solution:

def permutations(nums):

    result=[]

    def backtrack(path,used):

        if len(path)==len(nums):

            result.append(path.copy())

            return

        for i in range(len(nums)):

            if i in used:

                continue

            used.add(i)

            path.append(nums[i])

            backtrack(path,used)

            path.pop()

            used.remove(i)

    backtrack([],set())

    return result

Complexity:

Number of permutations:

n!

Time:

O(n!)

Space:

O(n)

Senior Answer

Permutations are a classic backtracking problem where each recursive call chooses an unused element and explores remaining possibilities.

30. What are common algorithm patterns?

Interview Answer

Most coding interview problems follow recognizable patterns.

Pattern 1: Hash Map

Use when:

Examples:

Pattern 2: Two Pointers

Use when:

Examples:

Pattern 3: Sliding Window

Use for:

Examples:

Pattern 4: Fast/Slow Pointer

Use for:

Examples:

Pattern 5: BFS/DFS

Use for:

Pattern 6: Dynamic Programming

Use when:

Senior Answer

I first identify the problem pattern before coding. Recognizing patterns such as hashing, sliding window, DFS, BFS, and dynamic programming allows me to create efficient solutions faster.

End of Chapter 13 — LeetCode & Algorithms

Covered:

✅ Graphs
✅ Graph Traversal
✅ Topological Sort
✅ Dijkstra
✅ Heap / Priority Queue
✅ Kth Largest Element
✅ LRU Cache
✅ Backtracking
✅ Permutations
✅ Algorithm Patterns

This section focuses on Dynamic Programming, Greedy Algorithms, and Interval Problems.

31. What is Dynamic Programming (DP)?

Interview Answer

Dynamic Programming is an optimization technique used when a problem has:

  1. Overlapping subproblems
  2. Optimal substructure

Instead of solving the same problem repeatedly, we store previous results.

Example: Fibonacci

Mathematical definition:

F(n) = F(n-1) + F(n-2)

Example:

F(5)

        F5

       /  \

     F4    F3

    / \    / \

  F3 F2  F2 F1

Notice:

F3

F2

are calculated multiple times.

Without DP

Recursive solution:

def fib(n):

    if n <= 1:

        return n

    return fib(n-1) + fib(n-2)

Complexity:

Time: O(2^n)

Space: O(n)

Very slow.

With Memoization

Store previous answers:

def fib(n, memo={}):

    if n in memo:

        return memo[n]

    if n <= 1:

        return n

    memo[n] = fib(n-1,memo) + fib(n-2,memo)

    return memo[n]

Complexity:

Time: O(n)

Space: O(n)

Two DP Approaches

1. Top-down

Recursion + cache.

Called:

Memoization

2. Bottom-up

Build answers iteratively.

Called:

Tabulation

Example:

0 1 1 2 3 5 8

Senior Answer

Dynamic programming improves performance by storing results of overlapping subproblems. I identify the state, recurrence relation, and base cases before implementing the solution.

32. How do you recognize a Dynamic Programming problem?

Interview Answer

I look for these characteristics:

1. Repeated Calculations

Example:

Fibonacci

The same values are calculated multiple times.

2. Choice Problems

Example:

"Maximum profit"

Choices:

Take item

Skip item

3. Optimization Questions

Common words:

Examples

Fibonacci

State:

dp[i] = Fibonacci number at i

Coin Change

State:

dp[amount] = minimum coins needed

Longest Common Subsequence

State:

dp[i][j]

=

answer using first i and j characters

Senior Answer

I identify DP problems by looking for overlapping subproblems and optimization decisions. The key step is defining the state and transition formula.

33. Solve Climbing Stairs Problem

Problem

You can climb:

1 or 2 steps

How many ways to reach step n?

Example:

n = 5

Answer:

8

Thinking

For step 5:

You can arrive from:

step 4 + 1

or

step 3 + 2

Therefore:

ways(n)=ways(n-1)+ways(n-2)

Solution

def climb_stairs(n):

    if n <= 2:

        return n

    prev2 = 1

    prev1 = 2

    for i in range(3,n+1):

        current = prev1 + prev2

        prev2 = prev1

        prev1 = current

    return prev1

Complexity:

Time: O(n)

Space: O(1)

Senior Answer

This is a Fibonacci-style DP problem. Each state depends only on the previous two states, allowing optimization from O(n) memory to O(1).

34. What is the 0/1 Knapsack problem?

Interview Answer

The Knapsack problem asks:

Given items with:

Choose items to maximize value without exceeding capacity.

Example:

Capacity:

10 kg

Items:

Item

Weight

Value

A

5

50

B

4

40

C

6

60

Choose the best combination.

Decision

For each item:

Two choices:

Take it

or

Skip it

DP State

dp[i][capacity]

means:

maximum value using first i items.

Formula

If item too heavy:

dp[i][w]=dp[i-1][w]

Otherwise:

max(

skip item,

take item

)

Complexity

Time: O(n * capacity)

Space: O(n * capacity)

Senior Answer

Knapsack is a classic DP problem where each item creates a decision: include or exclude. The solution stores the best result for each item and capacity combination.

35. What is Coin Change?

Problem

Given coins:

[1,2,5]

Amount:

11

Find minimum coins.

Answer:

3

5 + 5 + 1

DP Idea

State:

dp[x]

minimum coins needed for amount x

Example:

dp[0]=0

dp[1]=1

dp[2]=1

dp[5]=1

Python

def coin_change(coins, amount):

    dp=[float('inf')] * (amount+1)

    dp[0]=0

    for value in range(1,amount+1):

        for coin in coins:

            if value >= coin:

                dp[value]=min(

                    dp[value],

                    dp[value-coin]+1

                )

    return -1 if dp[amount]==float('inf') else dp[amount]

Complexity:

Time: O(amount * coins)

Space: O(amount)

Senior Answer

Coin Change uses bottom-up dynamic programming where each amount stores the minimum number of coins required to reach it.

36. What is the Longest Common Subsequence (LCS)?

Interview Answer

LCS finds the longest sequence that appears in two strings in the same order.

Characters do not need to be adjacent.

Example:

String 1:

"abcde"

String 2:

"ace"

Answer:

ace

DP State

dp[i][j]

means:

LCS length between:

first i characters

first j characters

Transition

If characters match:

dp[i][j]=dp[i-1][j-1]+1

Otherwise:

max(

dp[i-1][j],

dp[i][j-1]

)

Complexity

Time: O(m*n)

Space: O(m*n)

Applications

Senior Answer

LCS is a two-dimensional DP problem where the state represents the best solution for prefixes of two sequences.

37. What is the Longest Increasing Subsequence (LIS)?

Problem

Find the longest increasing sequence.

Example:

[10,9,2,5,3,7,101]

Answer:

[2,3,7,101]

Length:

4

DP Idea

Define:

dp[i]

as:

length of LIS ending at index i

Example:

For:

[2,5,3]

At 5:

2 → 5

length=2

At 3:

2 → 3

length=2

Complexity

Basic DP:

O(n²)

Optimized:

O(n log n)

using binary search.

Senior Answer

LIS can be solved using dynamic programming by tracking the best increasing subsequence ending at each position. An optimized approach uses binary search.

38. What are Interval Problems?

Interview Answer

Interval problems involve ranges:

[start, end]

Examples:

Meetings

Reservations

Time schedules

Example:

[1,3]

[5,8]

[10,12]

Common techniques:

  1. Sort intervals
  2. Compare neighbors
  3. Merge or detect conflicts

Typical Problems

Senior Answer

Interval problems are usually solved by sorting ranges by their start value and then processing overlapping intervals sequentially.

39. Solve Merge Intervals

Problem

Input:

[

[1,3],

[2,6],

[8,10],

[15,18]

]

Output:

[

[1,6],

[8,10],

[15,18]

]

Approach

Sort:

[1,3]

[2,6]

[8,10]

Compare:

Current:

1-3

Next:

2-6

They overlap:

merge

Python

def merge(intervals):

    intervals.sort()

    result=[]

    for interval in intervals:

        if not result or result[-1][1] < interval[0]:

            result.append(interval)

        else:

            result[-1][1] = max(

                result[-1][1],

                interval[1]

            )

    return result

Complexity:

Time: O(n log n)

Space: O(n)

Senior Answer

For interval merging, I sort intervals by start time and merge whenever the current interval overlaps with the previous result.

40. What is a Greedy Algorithm?

Interview Answer

A greedy algorithm makes the best local choice at each step hoping it leads to the global optimum.

Example:

Making change:

Amount:

£37

Coins:

£20 £10 £5 £2 £1

Greedy approach:

Take largest possible coin first:

20 + 10 + 5 + 2

Greedy Works When:

The problem has:

Examples

Activity Selection

Choose maximum non-overlapping meetings.

Huffman Coding

Compression algorithm.

Dijkstra

For non-negative weights.

When Greedy Fails

Example:

Coins:

[1,3,4]

Amount:

6

Greedy:

4+1+1

3 coins.

Optimal:

3+3

2 coins.

Senior Answer

Greedy algorithms make locally optimal decisions. They are efficient but require proof that local choices lead to the global optimum.

End of Chapter 13 — LeetCode & Algorithms

Covered:

✅ Dynamic Programming
✅ Memoization
✅ Tabulation
✅ Fibonacci Pattern
✅ Climbing Stairs
✅ Knapsack
✅ Coin Change
✅ LCS
✅ LIS
✅ Interval Problems
✅ Merge Intervals
✅ Greedy Algorithms

41. What is Prefix Sum?

Interview Answer

Prefix Sum is a technique where we preprocess an array so that range sum calculations can be performed efficiently.

Example:

Original array:

[2,4,6,8,10]

Create prefix array:

[0,2,6,12,20,30]

Meaning:

prefix[i] = sum of elements before i

Finding Range Sum

Question:

Find sum from index 1 to 3.

Original:

[2,4,6,8,10]

Need:

4+6+8 = 18

Using prefix:

prefix[4] - prefix[1]

20 - 2 = 18

Python

def build_prefix(nums):

    prefix=[0]

    for n in nums:

        prefix.append(prefix[-1]+n)

    return prefix

Complexity:

Building:

O(n)

Query:

O(1)

Applications

Senior Answer

Prefix sums trade memory for speed. By preprocessing cumulative values, we can answer range queries in constant time.

42. Solve Subarray Sum Equals K

Problem

Given:

nums=[1,2,3]

k=3

Find number of continuous subarrays whose sum equals k.

Answer:

2

Because:

[1,2]

[3]

Brute Force

Check every subarray.

Complexity:

O(n²)

Optimized Solution

Use:

Idea:

If:

current_sum - previous_sum = k

then:

previous_sum = current_sum - k

Store previous sums.

Python

def subarray_sum(nums,k):

    count=0

    current=0

    sums={0:1}

    for n in nums:

        current += n

        if current-k in sums:

            count += sums[current-k]

        sums[current]=sums.get(current,0)+1

    return count

Complexity:

Time:

O(n)

Space:

O(n)

Senior Answer

I use prefix sums with a hash map to avoid checking every possible subarray. This reduces the solution from quadratic to linear time.

43. Explain Kadane's Algorithm

Interview Answer

Kadane's algorithm finds the maximum sum contiguous subarray.

Problem:

[-2,1,-3,4,-1,2,1,-5,4]

Answer:

6

Because:

[4,-1,2,1]

Idea

At every position:

Choose:

  1. Start new subarray
  2. Continue previous subarray

Formula:

current =

max(

number,

current + number

)

Python

def max_sub_array(nums):

    current=nums[0]

    best=nums[0]

    for n in nums[1:]:

        current=max(

            n,

            current+n

        )

        best=max(

            best,

            current

        )

    return best

Complexity:

Time:

O(n)

Space:

O(1)

Applications

Senior Answer

Kadane's algorithm solves maximum subarray problems by maintaining the best possible sum ending at each position.

44. Solve Product of Array Except Self

Problem

Input:

[1,2,3,4]

Output:

[24,12,8,6]

Because:

24 = 2*3*4

12 = 1*3*4

Important Constraint

Do not use division.

Approach

Calculate:

  1. Product of elements on the left
  2. Product of elements on the right

Example:

Left:

[1,1,2,6]

Right:

[24,12,4,1]

Multiply:

[24,12,8,6]

Python

def product_except_self(nums):

    result=[1]*len(nums)

    prefix=1

    for i in range(len(nums)):

        result[i]=prefix

        prefix*=nums[i]

    suffix=1

    for i in range(len(nums)-1,-1,-1):

        result[i]*=suffix

        suffix*=nums[i]

    return result

Complexity:

Time:

O(n)

Space:

O(1)

(excluding output array)

Senior Answer

I solve this using prefix and suffix products, avoiding division and maintaining linear time complexity.

45. Solve Trapping Rain Water

Problem

Given heights:

0,1,0,2,1,0,1,3,2,1,2,1

Calculate trapped water.

Answer:

6

Idea

Water depends on:

min(left maximum, right maximum) - height

Example:

Left wall       Right wall

     |

     |

  |  | |

  |~~~~|

__|____|__

Two Pointer Solution

Maintain:

Python

def trap(height):

    left=0

    right=len(height)-1

    left_max=0

    right_max=0

    water=0

    while left < right:

        if height[left] < height[right]:

            if height[left]>=left_max:

                left_max=height[left]

            else:

                water += left_max-height[left]

            left+=1

        else:

            if height[right]>=right_max:

                right_max=height[right]

            else:

                water += right_max-height[right]

            right-=1

    return water

Complexity:

Time:

O(n)

Space:

O(1)

Senior Answer

The two-pointer approach works because the smaller side determines the maximum possible trapped water.

46. What is a Trie?

Interview Answer

A Trie is a tree structure used for storing strings efficiently.

It is also called:

Prefix Tree

Example:

Words:

cat

car

can

Stored as:

       c

        |

        a

      / | \

     t  r  n

Uses

Complexity

Searching:

O(length of word)

Insertion:

O(length of word)

Python Structure

class TrieNode:

    def __init__(self):

        self.children={}

        self.end=False

Senior Answer

A Trie stores strings by characters and provides fast prefix-based searching. It is commonly used for autocomplete and dictionary applications.

47. What is Backtracking vs Dynamic Programming?

Interview Answer

Both solve complex problems recursively, but they solve different types of problems.

Backtracking

Goal:

Find all possible solutions.

Example:

Generate all permutations

Pattern:

Choose

Explore

Undo

Dynamic Programming

Goal:

Find optimal solution.

Example:

Minimum coins

Maximum profit

Pattern:

Store previous results

Comparison:

Backtracking

DP

Goal

Explore possibilities

Optimize

Stores results

Usually no

Yes

Examples

Sudoku

Coin Change

Speed

Often exponential

Usually faster

Senior Answer

Backtracking explores possible solutions, while dynamic programming avoids repeated calculations by storing optimal results of subproblems.

48. Explain Bit Manipulation.

Interview Answer

Bit manipulation works directly with binary representations of numbers.

Common operators:

Operator

Meaning

&

AND

|

OR

^

XOR

<<

Shift left

>>

Shift right

Example: XOR

Property:

a ^ a = 0

a ^ 0 = a

Single Number Problem

Input:

[4,1,2,1,2]

Output:

4

Because duplicate numbers cancel.

Solution:

def single_number(nums):

    result=0

    for n in nums:

        result ^= n

    return result

Complexity:

Time:

O(n)

Space:

O(1)

Applications

Senior Answer

Bit manipulation allows efficient operations at the binary level. XOR is especially useful for problems involving duplicates because equal values cancel each other.

49. What is a Monotonic Stack?

Interview Answer

A monotonic stack maintains elements in increasing or decreasing order.

It is useful for finding:

Example:

Daily temperatures:

73,74,75,71,69,72,76,73

Find days until warmer temperature.

Idea

Keep indexes whose answer is not found yet.

When a warmer temperature appears:

Resolve previous items.

Python

def daily_temperatures(temp):

    stack=[]

    result=[0]*len(temp)

    for i,t in enumerate(temp):

        while stack and t > temp[stack[-1]]:

            index=stack.pop()

            result[index]=i-index

        stack.append(i)

    return result

Complexity:

Time:

O(n)

Space:

O(n)

Senior Answer

A monotonic stack maintains ordered elements and allows solving next greater or smaller element problems efficiently in linear time.

50. What are the most important LeetCode patterns for interviews?

Interview Answer

I focus on recognizing patterns rather than memorizing solutions.

Pattern Checklist

Arrays

Problems:

Techniques:

Strings

Problems:

Techniques:

Linked Lists

Problems:

Techniques:

Trees

Problems:

Techniques:

Graphs

Problems:

Techniques:

Optimization

Problems:

Technique:

Senior Answer

In interviews, I first identify the underlying pattern. Knowing common techniques like hashing, sliding window, DFS, BFS, dynamic programming, and greedy algorithms allows me to solve unfamiliar problems efficiently.

End of Chapter 13 — LeetCode & Algorithms

Covered:

✅ Prefix Sum
✅ Subarray Sum
✅ Kadane Algorithm
✅ Product Except Self
✅ Trapping Rain Water
✅ Trie
✅ Backtracking vs DP
✅ Bit Manipulation
✅ Monotonic Stack
✅ Interview Pattern Recognition

Chapter 13 — LeetCode & Algorithms Interview Questions

This final section covers senior-level algorithm design questions that are often asked after basic LeetCode problems.

51. How do you choose the right data structure?

Interview Answer

I choose a data structure based on:

  1. How data is accessed
  2. Required operations
  3. Performance requirements

Common Choices

Array / List

Use when:

Example:

numbers[5]

Complexity:

Access: O(1)

Search: O(n)

Hash Map

Use when:

Example:

users["john"]

Complexity:

Average lookup: O(1)

Stack

Use when:

Examples:

Queue

Use when:

Examples:

Heap

Use when:

Examples:

Tree

Use when:

Examples:

Graph

Use when:

Examples:

Senior Answer

I select data structures based on the operations that are most important. For example, I use hash maps for fast lookup, heaps for priority processing, and graphs for relationship-based problems.

52. Explain Sorting Algorithms and Their Differences

Interview Answer

Sorting algorithms differ in:

Bubble Sort

Repeatedly swaps adjacent elements.

Example:

5 3 2

swap

3 5 2

swap

3 2 5

Complexity:

O(n²)

Rarely used.

Selection Sort

Find smallest element and place it correctly.

Complexity:

O(n²)

Insertion Sort

Builds sorted section gradually.

Good for:

Complexity:

O(n²)

Merge Sort

Divide and conquer.

Complexity:

O(n log n)

Memory:

O(n)

Quick Sort

Choose pivot and partition.

Average:

O(n log n)

Worst:

O(n²)

Heap Sort

Uses heap.

Complexity:

O(n log n)

Comparison

Algorithm

Average

Memory

Stable

Bubble

O(n²)

O(1)

Yes

Insertion

O(n²)

O(1)

Yes

Merge

O(n log n)

O(n)

Yes

Quick

O(n log n)

O(log n)

No

Heap

O(n log n)

O(1)

No

Senior Answer

In production applications I usually rely on optimized library sorting implementations, but understanding algorithms helps choose the right approach when constraints are unusual.

53. What is Quick Sort?

Interview Answer

Quick Sort is a divide-and-conquer sorting algorithm.

It works by:

  1. Choosing a pivot
  2. Partitioning elements around pivot
  3. Recursively sorting partitions

Example:

Array:

[7,2,9,1,5]

Choose pivot:

5

Partition:

[2,1] 5 [7,9]

Sort sides:

[1,2,5,7,9]

Complexity

Average:

O(n log n)

Worst:

O(n²)

Example:

Already sorted array with bad pivot choice.

Senior Answer

Quick Sort is efficient because partitioning reduces the problem size recursively. In practice, randomized pivots avoid worst-case behavior.

54. What is Binary Search Tree validation?

Problem

Determine whether a tree is a valid BST.

Example:

Valid:

      5

    /     \

   3       8

Invalid:

      5

    /     \

   7       8

Approach

Each node must satisfy:

left < node < right

Python:

def validate(node, low=float("-inf"), high=float("inf")):

    if not node:

        return True

    if node.value <= low or node.value >= high:

        return False

    return (

        validate(node.left, low, node.value)

        and

        validate(node.right, node.value, high)

    )

Complexity:

Time:

O(n)

Space:

O(h)

Senior Answer

BST validation requires maintaining valid value ranges while traversing the tree recursively.

55. What is Lowest Common Ancestor (LCA)?

Interview Answer

The Lowest Common Ancestor is the deepest node that contains two given nodes in its subtree.

Example:

            6

          /     \

         2       8

       /  \

      0    4

LCA of:

0 and 4

is:

2

Recursive Solution

def lowest_common_ancestor(root,p,q):

    if not root or root == p or root == q:

        return root

    left = lowest_common_ancestor(

        root.left,p,q

    )

    right = lowest_common_ancestor(

        root.right,p,q

    )

    if left and right:

        return root

    return left or right

Complexity:

Time:

O(n)

Space:

O(h)

Senior Answer

LCA can be solved recursively by searching both subtrees. If both sides contain the target nodes, the current node is the ancestor.

56. Explain Rate Limiting Algorithm

Interview Answer

A rate limiter controls how many requests a client can make during a period.

Example:

API rule:

100 requests per minute

Common Algorithms

Token Bucket

Tokens are added over time.

Example:

Bucket capacity: 100 tokens

Each request consumes 1 token

If no tokens:

Request rejected

Sliding Window

Track requests in time window.

Example:

10:00:01

10:00:05

10:00:10

Fixed Window

Simple counter:

10:00-10:01

count requests

Enterprise Example

API Gateway:

Client

 |

Rate Limiter

 |

Backend Service

Senior Answer

Rate limiting protects services from overload. Common approaches include token bucket, fixed window, and sliding window algorithms.

57. Explain Producer-Consumer Pattern

Interview Answer

Producer-consumer is a concurrency pattern where:

A queue connects them.

Architecture:

Producer

   |

 Queue

   |

Consumer

Example:

Order processing:

Producer:

Customer places order

Queue:

RabbitMQ / Kafka

Consumer:

Payment service

Python example:

from queue import Queue

queue = Queue()

# Producer

queue.put("Order1")

# Consumer

order = queue.get()

Benefits

Senior Answer

Producer-consumer separates data creation from processing. Message queues allow systems to scale independently and handle spikes.

58. How do you design a Cache?

Interview Answer

A cache stores frequently accessed data closer to the application to improve performance.

Architecture:

User

 |

Application

 |

Cache

 |

Database

Cache Strategies

Cache Aside

Application checks cache first.

Flow:

Request

 |

Cache?

 |

Yes → Return

 |

No

 |

Database

 |

Store Cache

Write Through

Write to:

Cache + Database

Write Behind

Write cache first.

Database updated later.

Cache Considerations

Examples

Senior Answer

A cache improves performance by reducing expensive database calls. The main design challenges are cache invalidation, expiration policies, and consistency.

59. Explain Thread Safety in Algorithms

Interview Answer

Thread safety means multiple threads can access shared data without causing incorrect results.

Problem:

Two threads:

Counter = 0

Thread A:

Counter++

Thread B:

Counter++

Expected:

2

Possible result:

1

because operations overlap.

Solutions

Locks

Only one thread modifies data.

Atomic Operations

CPU guarantees operation completion.

Immutable Objects

Cannot change after creation.

Concurrent Collections

Examples:

.NET:

ConcurrentDictionary<TKey,TValue>

Senior Answer

Thread safety requires protecting shared state through synchronization mechanisms such as locks, atomic operations, immutable objects, or concurrent collections.

60. How do you approach a coding interview problem?

Interview Answer

My approach:

Step 1 — Understand the Problem

Clarify:

Step 2 — Identify Pattern

Ask:

Is this:

Step 3 — Explain Solution

Before coding:

Example:

I will use a hash map because I need constant-time lookup.

Step 4 — Implement Clean Code

Focus on:

Step 5 — Analyze Complexity

Always explain:

Time Complexity: O(n)

Space Complexity: O(n)

Step 6 — Test

Check:

Senior Answer

I first understand constraints, identify the appropriate algorithm pattern, explain the trade-offs, implement clean code, and validate complexity and edge cases.

Chapter 13 — LeetCode & Algorithms Completed ✅

Total:

60 Interview Questions

Covered:

Fundamentals

✅ Big-O
✅ Complexity Analysis
✅ Data Structures

Arrays

✅ Two Sum
✅ Sliding Window
✅ Prefix Sum
✅ Kadane Algorithm
✅ Product Except Self

Linked Lists

✅ Reverse List
✅ Cycle Detection

Trees

✅ DFS
✅ BFS
✅ BST
✅ LCA

Graphs

✅ Traversal
✅ Topological Sort
✅ Dijkstra

Advanced

✅ Heap
✅ LRU Cache
✅ Trie
✅ Backtracking
✅ Dynamic Programming
✅ Greedy Algorithms
✅ Bit Manipulation
✅ Rate Limiting
✅ Concurrency Patterns