Oct 13, 2024

Classic Computer Algorithms

Computer algorithms have been around for decades, and if you've ever sat through a software engineering interview, you know companies love testing how well you understand them. Here's a rundown of the most important ones you'll encounter.

Array Algorithms

  1. Merge Sort: This algorithm splits the array in half, sorts each half, then combines them back together. It's a classic example of divide-and-conquer.

  2. Quick Sort: Another divide-and-conquer approach. You pick a pivot element, rearrange the array so everything smaller is on one side and everything larger is on the other, then repeat the process for each side.

  3. Two-Pointer Technique: This technique comes in handy when you're working with sorted arrays or linked lists. You use two pointers moving at different speeds or directions to find pairs, subarrays, or other patterns.

    Common interview questions:

    • Find two numbers in a sorted array that add up to a specific target.
    • Check if a subarray with a given sum exists in an unsorted array.

  4. Kadane's Algorithm: This is the go-to solution for finding the maximum sum of a contiguous subarray. You walk through the array while keeping track of your running sum. If that sum ever drops below zero, you reset it to zero because a negative sum would only make things worse for any subarray that follows. You also keep track of the highest sum you've seen so far. The algorithm runs in O(n) time, which makes it efficient even for large datasets.

    Common interview questions:

    • What's the maximum sum of a contiguous subarray in the given array?
    • How would you modify Kadane's Algorithm to also return the start and end indices of that subarray?

  5. Sliding Window Technique: This method involves keeping a "window" that slides across your data, adjusting the elements inside as you go. It's useful when you need to find subarrays that meet certain conditions.

    Common interview questions:

    • Find the maximum sum of a subarray with a fixed length.
    • What's the smallest subarray length with a sum greater than or equal to a given value?

  6. Prefix Sum: You precompute an array where each element is the sum of all elements before it. This lets you answer range sum queries in constant time after the initial O(n) setup.

    Common interview questions:

    • Given an array of integers, find the length of the longest subarray with a sum equal to zero.
    • You have a list of non-negative integers and a target S. How many ways can you assign plus and minus signs to make the sum equal to S?
    • Given an array of integers, find the maximum product of a subarray.
    • Can the string be segmented into a space-separated sequence of dictionary words?
    • Find the length of the longest substring without repeating characters.

Search Algorithms

  1. Binary Search: This is what you use when you need to find something in a sorted array quickly. You keep splitting the search range in half until you find your target.

    Common interview questions:

    • Find the square root of a number with precision up to 6 decimal places.
    • Search for a target value in a rotated sorted array.
    • Find the smallest element in a sorted array that's greater than a given target.
    • Locate the first and last position of a target value in a sorted array.

  2. Depth-First Search (DFS): You start at the root and explore as far as possible along each branch before backtracking. It's useful for traversing trees and graphs.

    Common interview questions:

    • Given a binary tree, return all root-to-leaf paths.
    • Find all connected components in an undirected graph.
    • Does a path exist between two nodes in a directed graph?
    • Generate all possible permutations of a given list of numbers.
    • Solve a maze represented by a 2D grid, where 0s are paths and 1s are walls.

  3. Breadth-First Search (BFS): You start at the root and explore all neighbors at the present depth before moving on to the next level. This is the algorithm you want when you need the shortest path in an unweighted graph.

    Common interview questions:

    • Given a binary tree, return the level order traversal of its nodes' values.
    • Find the shortest path in an unweighted graph from a starting node to a target node.
    • What's the minimum number of moves to transform one word into another using a given set of transformations?
    • Given a 2D grid of '1's (land) and '0's (water), count the number of islands.
    • Find the minimum number of steps to reach the end of a maze from a starting point.

Graph Algorithms

  1. Dijkstra's Algorithm: This finds the shortest path between nodes in a graph. It's commonly used for routing and navigation problems.

    Common interview questions:

    • Given a graph with weighted edges, find the shortest path from a starting node to all other nodes.
    • You have a map of cities connected by roads with travel times. What's the quickest route from one city to another?
    • In a computer network, what's the minimum time to send a message from one computer to all others?
    • Given a grid where each cell has a cost, find the path from top-left to bottom-right with minimum cost.
    • You have a list of flights with durations. What's the shortest travel time from a starting airport to a destination?

  2. A Search Algorithm*: This is a pathfinding algorithm often used in games and maps. Like Dijkstra's, it finds the shortest path, but it uses a heuristic to prioritize paths that look promising. This makes it faster than Dijkstra's in many situations because it doesn't waste time exploring obviously bad routes.

  3. Kruskal's Algorithm: This finds a minimum spanning tree by adding edges in order of weight, making sure you don't create cycles.

  4. Prim's Algorithm: Another minimum spanning tree algorithm, but it works differently. You start with one vertex and grow the tree one edge at a time, always picking the cheapest connection to a new vertex.

  5. Bellman-Ford Algorithm: This computes shortest paths from a single source to all other vertices. Unlike Dijkstra's, it handles negative edge weights, which makes it more versatile in certain situations.

Optimization and Problem Solving

  1. Dynamic Programming: This technique breaks complex problems into smaller subproblems and stores the results so you don't have to recalculate them. It's all about avoiding redundant work.

  2. Backtracking: This is a systematic way to search through all possible solutions to a problem. You build solutions piece by piece and abandon (backtrack from) choices that don't work.

  3. Greedy Algorithms: These make the best choice at each step, hoping that local最优 choices lead to a global optimum. They don't always work, but when they do, they're efficient and straightforward.

  4. Divide and Conquer: This approach breaks a problem into smaller subproblems of the same type, solves them recursively, and combines the results. Many sorting and searching algorithms fall into this category.

String Algorithms

You won't see these as often in interviews as the others, but knowing them can definitely score you extra points.

  1. Knuth-Morris-Pratt (KMP) Algorithm: This searches for occurrences of a pattern within a larger text. It preprocesses the pattern to skip unnecessary comparisons, making it faster than a naive approach.

  2. Rabin-Karp Algorithm: Another string searching algorithm that uses hashing to find pattern matches. It's particularly useful when you're searching for multiple patterns at once.