Algorithm Interview Questions

Algorithm interview questions are a core component of programmer interviews, covering multiple dimensions including data structures, algorithm design, and complexity analysis. The following sections systematically organize the key examination points in algorithm interviews based on common questions.
Arrays and Strings

Question: How to efficiently determine if two strings are palindromes?
Answer: Use the two-pointer approach, moving from both ends of the string towards the center to compare characters. If all characters match, it is a palindrome.
Code Block
```
def is_palindrome(s):
    return s == s[::-1]
```

Sorting and Searching

Question: What is the average time complexity of Quick Sort?
Answer: The average time complexity of Quick Sort is O(n log n), which depends on the pivot selection strategy.
Code Block

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + [pivot] + quicksort(right)

Data Structures and Algorithm Design

Question: How to implement an LRU cache eviction algorithm?
Answer: Use a doubly linked list to maintain access order, combined with a hash table to record key-value pairs. When the capacity limit is reached, delete the least recently used element.
Code Block

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = None
        self.tail = None

Dynamic Programming and Greedy Algorithms

Question: How to optimize the recurrence relation for the Fibonacci sequence?
Answer: Use memoization or iteration to reduce repeated calculations.
Code Block
```
from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)
```

Graph Theory and Algorithms

Question: How to determine if a graph contains a cycle?
Answer: Use Depth First Search (DFS) to record the visited path. If a node is encountered multiple times, a cycle exists.
Code Block

def has_cycle(graph):
    visited = set()
    rec_stack = set()
    def dfs(node):
        if node in rec_stack:
            return True
        if node in visited:
            return False
        visited.add(node)
        rec_stack.add(node)
        for neighbor in graph.get(node, []):
            if dfs(neighbor):
                return True
        rec_stack.remove(node)
        return False
    return dfs(next(iter(graph)))

Algorithm Complexity Analysis

Question: What is the worst-case time complexity of the TSP problem?
Answer: The worst-case time complexity of the Traveling Salesperson Problem (TSP) is O(n^2 * 2^n), as the state space is n!.
Code Block

def tsp(n):
    memo = [[False] * n for _ in range(n)]
    for i in range(n):
        memo[i][i] = True
    for i in range(n):
        for j in range(i+1, n):
            memo[i][j] = True
    for k in range(n):
        for i in range(n):
            for j in range(i+1, n):
                memo[i][j] = memo[i][j] or memo[i][k] and memo[k][j]

Recursion and Backtracking

Question: How to solve the "Activity Selection Problem"?
Answer: Sort by end time, then greedily select the activity that ends earliest, and recursively determine if subsequent activities are feasible.
Code Block

def activity_selection(intervals):
    intervals.sort(key=lambda x: x[1])
    selected = []
    for start, end in intervals:
        if not selected or selected[-1][1] <= start:
            selected.append((start, end))
    return selected

Algorithm Optimization and Design

Question: How to optimize the performance of Bubble Sort?
Answer: Terminate early by setting a flag, or use an optimized version of Insertion Sort.
Code Block

def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr