10 Essential Mathematical Basics for DSA Interview (With Answers)

Mathematical Basics for DSA

Mathematics is the backbone of Data Structures and Algorithms (DSA). Many interview problems revolve around mathematical concepts like number theory, combinatorics, probability, and bit manipulation. Below is a curated list of 10 essential mathematical problems commonly asked in DSA interviews and their solutions.

1. Prime Number Check

Problem: Given a numbern, determine if it is a prime number. Solution: Check divisibility from 2 to sqrt(n).

import math
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

2. GCD (Greatest Common Divisor)

Problem: Find the GCD of two numbers a and b. Solution: Use the Euclidean algorithm.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

3. LCM (Least Common Multiple)

Problem: Find the LCM of two numbers a and b. Solution: Use the relation LCM(a, b) = (a * b) / GCD(a, b).

def lcm(a, b):
    return (a * b) // gcd(a, b)

4. Sieve of Eratosthenes