Algorithmic Problem Solving Fundamentals Questions

Core foundation for solving entry level algorithmic problems. Focuses on arrays, strings, basic mathematics and number theory problems, simple bit manipulation, basic linked list and tree operations, stacks and queues, basic sorting and searching algorithms, simple recursion, and use of hash based data structures for counting and lookup. Emphasizes understanding asymptotic time and space complexity, selecting appropriate data structures for a task, and clear step by step problem solving including writing a brute force solution and analyzing correctness.

EasyTechnical

53 practiced

Implement a function in Python that determines whether a 32-bit signed integer is a power of two (positive powers only). Solve it using bit manipulation without loops. Discuss edge cases (e.g., zero, negative inputs) and time/space complexity.

Sample Answer

Approach: A positive integer is a power of two iff it has exactly one '1' bit in binary. For n>0 this is equivalent to (n & (n-1)) == 0. We'll also validate 32-bit signed integer bounds and rule out non-positive values.

python

def is_power_of_two_32(n):
    """
    Return True if n is a positive power of two within 32-bit signed integer range.
    Uses bit manipulation (no loops).
    """
    # Validate integer type and 32-bit signed range
    if not isinstance(n, int):
        return False
    if n <= 0:
        return False
    if n > 2**31 - 1:  # exceed 32-bit signed max
        return False
    # Bit trick: powers of two have a single 1-bit
    return (n & (n - 1)) == 0

# Examples:
# is_power_of_two_32(1) -> True
# is_power_of_two_32(16) -> True
# is_power_of_two_32(0) -> False
# is_power_of_two_32(-2) -> False
# is_power_of_two_32(3) -> False

Key points:- Edge cases: 0 and negatives -> False; non-int -> False; values > 2^31-1 -> False per 32-bit signed constraint.- Time complexity: O(1) constant-time bit ops.- Space complexity: O(1).- Alternative: could skip explicit 32-bit bound if environment guarantees integers fit, but for strict 32-bit validation keep the check.

EasyTechnical

46 practiced

Given an unsorted array of integers and a target integer, implement in Python a function that returns indices (i, j) of any two numbers that add up to the target. Aim for O(n) expected time and O(n) extra space. Describe how your algorithm handles duplicate numbers and multiple valid pairs, and provide a brief correctness argument.

Sample Answer

Approach: Use a hash map (value -> index) and scan the array once. For each element x at index i, check if target - x exists in the map; if so return (map[complement], i). This yields expected O(n) time and O(n) extra space.

python

def two_sum(nums, target):
    """
    Return a tuple (i, j) of indices such that nums[i] + nums[j] == target.
    If no pair exists, return None.
    """
    seen = {}  # value -> index
    for i, x in enumerate(nums):
        comp = target - x
        if comp in seen:
            return (seen[comp], i)
        # store current value's index (keeps first occurrence)
        if x not in seen:
            seen[x] = i
    return None

Handling duplicates and multiple pairs:- Duplicates: If two identical numbers sum to target (e.g., target=6 and two 3s), the first 3 is stored in seen; when we encounter the second 3, comp=3 is found and returns their indices.- Multiple valid pairs: This implementation returns the first valid pair discovered (deterministic based on left-to-right scan). To collect all pairs, iterate fully and store pairs, taking care to avoid reusing indices.

Correctness argument:- For any pair (i,j) with i<j, when scanning index j we will have seen nums[i] in the map, so the algorithm will detect and return a valid pair. Thus any existing pair is discoverable; the check guarantees nums[i]+nums[j]==target.

Time complexity: O(n) expected (hash lookups/insertions O(1)).Space complexity: O(n) for the hash map.

EasyTechnical

57 practiced

Describe and implement in Python a single-pass algorithm to find both the minimum and maximum elements in an array. Explain how to reduce the number of comparisons compared to doing separate passes, and present the final comparison count in terms of n.

Sample Answer

We can reduce comparisons by processing the array in pairs. Instead of updating min and max separately for each element (which costs about 2 comparisons per element, ~2n − 2 total), compare elements in pairs, first between themselves (1 comparison), then compare the smaller to current min and the larger to current max (2 more comparisons). That’s 3 comparisons per pair → about 1.5 comparisons per element.

Algorithm (pairwise single pass):- Handle n = 0/1 as special cases.- If n is even, initialize min and max from first pair; if odd, initialize both to first element.- Iterate over remaining elements two at a time: - Compare the pair to decide local smaller/larger (1 comp) - Compare local smaller with global min (1 comp) - Compare local larger with global max (1 comp)

Python implementation:

python

def find_min_max(arr):
    """
    Return (min, max) in a single pass with reduced comparisons.
    Time: O(n), Space: O(1)
    """
    n = len(arr)
    if n == 0:
        raise ValueError("Array must be non-empty")
    if n == 1:
        return arr[0], arr[0]

    # Initialize
    if n % 2 == 0:
        # start from first pair
        if arr[0] < arr[1]:
            current_min, current_max = arr[0], arr[1]
        else:
            current_min, current_max = arr[1], arr[0]
        i = 2
    else:
        current_min = current_max = arr[0]
        i = 1

    # Process pairs
    while i < n:
        a, b = arr[i], arr[i+1]
        if a < b:
            small, large = a, b
        else:
            small, large = b, a
        if small < current_min:
            current_min = small
        if large > current_max:
            current_max = large
        i += 2

    return current_min, current_max

Comparison counts:- Even n: 3n/2 − 2 comparisons.- Odd n: 3(n−1)/2 comparisons = 3n/2 − 3/2 (equivalently floor(3n/2) comparisons).This improves over separate passes (~2n − 2), saving roughly n/2 comparisons. Edge cases: empty array (error), single element (min=max).

HardTechnical

45 practiced

Given bar heights in a histogram (array of non-negative integers), compute the largest rectangular area that can be formed. Implement the O(n) monotonic stack-based solution in Python, explain what the stack stores and why sentinels simplify boundary handling.

Sample Answer

We can solve this in O(n) using a monotonic (increasing) stack of indices. The stack stores indices of bars in strictly increasing height order; when a lower bar arrives we pop taller bars and compute areas where the popped bar is the smallest in that span. Adding sentinel zeros at both ends (height 0) simplifies boundary handling by forcing all bars to be popped and avoiding empty-stack checks.

python

def largestRectangleArea(heights):
    """
    Monotonic-stack O(n) solution.
    heights: list[int] non-negative
    Returns max rectangle area in histogram.
    """
    # add sentinels to avoid boundary checks
    h = [0] + heights + [0]
    stack = [0]  # store indices; h[stack] is increasing
    max_area = 0

    for i in range(1, len(h)):
        # while current height breaks the increasing order
        while h[i] < h[stack[-1]]:
            height = h[stack.pop()]
            left = stack[-1]  # index of previous smaller
            width = i - left - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

Key points:- Stack stores indices whose heights are strictly increasing; using indices lets us compute widths precisely.- When popping index j, the rectangle where height=h[j] spans (stack[-1]+1) .. (i-1).- Sentinels (0 at both ends) guarantee every real bar is popped by a lower sentinel, removing special-case logic for end-of-array and empty stack checks.

Time complexity: O(n) — each index pushed/popped at most once.Space complexity: O(n) for the stack.Edge cases: empty input -> 0; all equal heights -> handled efficiently. Alternative: divide-and-conquer gives O(n log n) average or O(n^2) worst-case.

EasyTechnical

45 practiced

You're given an array of categorical values (e.g., user event types from logs). Implement in Python a function that returns a frequency mapping of each distinct value. Provide an implementation that works in one pass, and then explain how you'd adapt it for a streaming input where the dataset doesn't fit in memory.

Sample Answer

To compute frequencies in one pass, use a single dictionary (hashmap) and iterate once over the array, updating counts. This is O(n) time and O(k) space where k is number of distinct categories.

python

from collections import defaultdict
from typing import Iterable, Dict

def freq_map(events: Iterable[str]) -> Dict[str, int]:
    """
    One-pass frequency mapping of categorical values.
    Accepts any iterable (list, generator) of event strings.
    """
    counts = defaultdict(int)
    for e in events:
        if e is None:
            key = "<NULL>"           # handle missing values explicitly
        else:
            key = str(e).strip()     # normalize strings minimally
        if key:                     # skip empty strings if desired
            counts[key] += 1
    return dict(counts)

Key points:- Works in one pass and is memory-efficient relative to input size (but stores one entry per distinct category).- Time: O(n). Space: O(k).

Adapting for streaming / data too large for memory:- If k fits memory, feed a streaming iterator to the same function; it never loads all items at once.- If distinct categories are too many, use approximate counters like Count–Min Sketch to bound memory and get probabilistic counts, or use hashing + HyperLogLog for cardinality estimation.- For distributed streams, use a streaming framework (Kafka + Spark Streaming/Flink) to maintain per-key state or use map-reduce aggregation: compute local counts, then merge reducers.- Also consider periodic checkpointing, TTL for low-frequency keys, or sampling if exact counts aren’t required.

Edge cases: nulls, trailing spaces, case sensitivity, extremely high-cardinality IDs (use approximate structures).

Unlock Full Question Bank

Get access to hundreds of Algorithmic Problem Solving Fundamentals interview questions and detailed answers.

Join thousands of developers preparing for their dream job.