15 Algorithm Interview Questions and Answers

Algorithms form the backbone of computer science, enabling efficient problem-solving and optimization across various domains. Mastery of algorithms is crucial for developing robust software, optimizing performance, and tackling complex computational challenges. Understanding fundamental concepts such as sorting, searching, and graph traversal, as well as advanced techniques like dynamic programming and greedy algorithms, is essential for any aspiring software engineer.

This article offers a curated selection of algorithm-related questions and answers designed to help you prepare for technical interviews. By working through these examples, you will gain a deeper understanding of algorithmic principles and enhance your problem-solving skills, positioning yourself as a strong candidate in the competitive job market.

Algorithm Interview Questions and Answers

1. Implement binary search on a sorted array.

Binary search is an efficient algorithm for finding an item in a sorted list by repeatedly dividing the search interval in half. Here’s a concise implementation in Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# Example usage:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
print(binary_search(arr, target))  # Output: 4

2. Write a dynamic programming solution to generate the nth Fibonacci number.

Dynamic programming (DP) solves complex problems by breaking them into simpler subproblems. It is useful for optimization problems where solutions can be constructed from subproblem solutions. For generating the nth Fibonacci number, DP avoids redundant calculations by storing subproblem results.

def fibonacci(n):
    if n <= 1:
        return n

    fib = [0] * (n + 1)
    fib[1] = 1

    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]

    return fib[n]

# Example usage:
print(fibonacci(10))  # Output: 55

3. Implement Dijkstra’s algorithm to find the shortest path in a weighted graph.

Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph. It iteratively selects the node with the smallest known distance, updates distances to its neighbors, and marks the node as visited.

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

4. Solve the 0/1 knapsack problem using dynamic programming.

The 0/1 knapsack problem can be solved using dynamic programming by creating a 2D array where rows represent items and columns represent capacities. The value at each cell represents the maximum value achievable with the given capacity and items considered so far.

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

weights = [1, 2, 3, 4]
values = [10, 20, 30, 40]
capacity = 5
print(knapsack(weights, values, capacity))
# Output: 50

5. Implement Kruskal’s algorithm to find the minimum spanning tree of a graph.

Kruskal’s algorithm finds the minimum spanning tree (MST) of a graph by sorting all edges in non-decreasing order of their weight and adding them one by one to the MST, ensuring no cycles are formed. This is achieved using a union-find data structure.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst = []
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
    return mst

# Example usage:
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]
n = 4
print(kruskal(n, edges))
# Output: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

6. Write the Knuth-Morris-Pratt (KMP) algorithm for string matching.

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    lps = compute_lps(pattern)
    i = 0
    j = 0

    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == len(pattern):
            print(f"Found pattern at index {i - j}")
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

text = "abxabcabcaby"
pattern = "abcaby"
kmp_search(text, pattern)

7. Solve the N-Queens problem using backtracking.

The N-Queens problem can be solved using backtracking by placing queens one by one in different columns, starting from the leftmost column. When placing a queen, we check for clashes with already placed queens. If a clash is found, we backtrack and try the next position.

def is_safe(board, row, col, n):
    for i in range(col):
        if board[row][i] == 1:
            return False
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    for i, j in zip(range(row, n, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    return True

def solve_n_queens_util(board, col, n):
    if col >= n:
        return True
    for i in range(n):
        if is_safe(board, i, col, n):
            board[i][col] = 1
            if solve_n_queens_util(board, col + 1, n):
                return True
            board[i][col] = 0
    return False

def solve_n_queens(n):
    board = [[0 for _ in range(n)] for _ in range(n)]
    if not solve_n_queens_util(board, 0, n):
        return "Solution does not exist"
    return board

n = 4
solution = solve_n_queens(n)
for row in solution:
    print(row)

8. Implement the Bellman-Ford algorithm for finding shortest paths in a graph with negative weights.

The Bellman-Ford algorithm iteratively relaxes all edges in a graph. It repeats this process for a number of times equal to the number of vertices minus one. If a shorter path is found, it updates the shortest path estimate. After the main loop, it checks for negative weight cycles.

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []

    def add_edge(self, u, v, w):
        self.edges.append((u, v, w))

    def bellman_ford(self, src):
        dist = [float('inf')] * self.V
        dist[src] = 0

        for _ in range(self.V - 1):
            for u, v, w in self.edges:
                if dist[u] != float('inf') and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        for u, v, w in self.edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                print("Graph contains negative weight cycle")
                return

        return dist

g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)

distances = g.bellman_ford(0)
print(distances)

9. Construct a segment tree and perform range sum queries.

A segment tree is a binary tree used for storing intervals or segments. It allows querying which of the stored segments contain a given point efficiently. This data structure is useful for answering range queries and updating elements in logarithmic time.

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        self.build(data)

    def build(self, data):
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]

    def update(self, pos, value):
        pos += self.n
        self.tree[pos] = value
        while pos > 1:
            pos //= 2
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

    def range_sum(self, left, right):
        left += self.n
        right += self.n
        sum = 0
        while left < right:
            if left % 2:
                sum += self.tree[left]
                left += 1
            if right % 2:
                right -= 1
                sum += self.tree[right]
            left //= 2
            right //= 2
        return sum

# Example usage:
data = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(data)
print(seg_tree.range_sum(1, 3))  # Output: 8
seg_tree.update(1, 10)
print(seg_tree.range_sum(1, 3))  # Output: 15

10. Implement a trie data structure and perform insert and search operations.

A trie, or prefix tree, is a specialized tree used to store associative data structures. A common application is storing a predictive text or autocomplete dictionary. Each node represents a single character, and the path from the root to a node represents a prefix of the stored strings.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

# Example usage:
trie = Trie()
trie.insert("hello")
print(trie.search("hello"))  # Output: True
print(trie.search("hell"))   # Output: False

11. Use Kadane’s algorithm to find the maximum subarray sum in an array.

Kadane’s algorithm finds the maximum subarray sum in an array by iterating through the array while keeping track of the maximum sum of the subarray ending at the current position.

def max_subarray_sum(arr):
    max_current = max_global = arr[0]
    
    for num in arr[1:]:
        max_current = max(num, max_current + num)
        if max_current > max_global:
            max_global = max_current
    
    return max_global

# Example usage:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr))  # Output: 6

12. Implement the Ford-Fulkerson algorithm to compute the maximum flow in a network.

The Ford-Fulkerson algorithm finds the maximum flow in a flow network by repeatedly finding augmenting paths in the residual graph and increasing the flow along these paths until no more augmenting paths can be found.

class Graph:
    def __init__(self, graph):
        self.graph = graph
        self.ROW = len(graph)

    def bfs(self, s, t, parent):
        visited = [False] * self.ROW
        queue = [s]
        visited[s] = True

        while queue:
            u = queue.pop(0)

            for ind, val in enumerate(self.graph[u]):
                if visited[ind] == False and val > 0:
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        return visited[t]

    def ford_fulkerson(self, source, sink):
        parent = [-1] * self.ROW
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            s = sink

            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

            max_flow += path_flow

        return max_flow

graph = [[0, 16, 13, 0, 0, 0],
         [0, 0, 10, 12, 0, 0],
         [0, 4, 0, 0, 14, 0],
         [0, 0, 9, 0, 0, 20],
         [0, 0, 0, 7, 0, 4],
         [0, 0, 0, 0, 0, 0]]

g = Graph(graph)
source = 0
sink = 5

print("The maximum possible flow is %d" % g.ford_fulkerson(source, sink))

13. Explain a greedy algorithm and provide an example problem it can solve efficiently.

A greedy algorithm solves problems by making the locally optimal choice at each stage with the hope of finding a global optimum. This method is effective for problems where choosing local optima leads to a global optimum. One example is the Activity Selection Problem, where the goal is to select the maximum number of non-overlapping activities.

def activity_selection(activities):
    activities.sort(key=lambda x: x[1])
    
    selected_activities = [activities[0]]
    last_end_time = activities[0][1]
    
    for i in range(1, len(activities)):
        if activities[i][0] >= last_end_time:
            selected_activities.append(activities[i])
            last_end_time = activities[i][1]
    
    return selected_activities

# Example usage
activities = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 7)]
print(activity_selection(activities))
# Output: [(1, 3), (4, 6), (6, 8)]

14. Explain the divide and conquer approach and give an example problem that uses this technique.

The divide and conquer approach consists of three steps: divide the problem into smaller subproblems, solve the subproblems recursively, and combine the solutions. A classic example is the Merge Sort algorithm, which divides the array into halves, recursively sorts each half, and merges the sorted halves.

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

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

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

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

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

    return sorted_array

# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)
# Output: [3, 9, 10, 27, 38, 43, 82]

15. Explain how to optimize a dynamic programming solution for space or time efficiency.

Dynamic programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. To optimize a DP solution, use techniques like memoization, tabulation, and space reduction. Memoization stores results of expensive function calls, tabulation solves subproblems iteratively, and space reduction stores only necessary values.

Example:

# Memoization
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Tabulation
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Space Reduction
def fib_space_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b