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

60 practiced

Given a string s, return the index of the first non-repeating character in it. If it does not exist, return -1. Implement in Python or Java in O(n) time and discuss space trade-offs. Examples: 'leetcode' -> 0, 'loveleetcode' -> 2. Also describe a streaming variant where characters arrive one by one.

Sample Answer

Approach: Do a single pass to count frequencies, then a second pass to find first char with count 1. This is O(n) time. Space is O(k) where k is number of distinct characters (often constant 26 for lowercase letters).

python

def first_unique_char(s: str) -> int:
    # Count frequencies in one pass
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1

    # Second pass to find first char with freq == 1
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return i
    return -1

# Examples
# first_unique_char("leetcode") -> 0
# first_unique_char("loveleetcode") -> 2

Key points:- Time complexity: O(n) (two linear passes).- Space complexity: O(k) for frequency map. If input limited to lowercase letters, k ≤ 26 ⇒ O(1) auxiliary space.

Edge cases:- Empty string -> return -1- All repeating chars -> return -1- Unicode input -> freq map size grows with distinct code points

Streaming variant:- Maintain a counts map and a queue of characters seen (or indices if you need positions).- For each incoming char c: - Increment counts[c]. - Append c to queue. - While queue not empty and counts[queue[0]] > 1: pop left. - The first non-repeating is queue[0] (or none if queue empty).- Complexity: amortized O(1) per arriving char (each char enters and leaves queue once). Space: O(k + q) but queue size limited by distinct chars that are currently candidates; for bounded alphabet it's O(1).

EasyTechnical

54 practiced

Given the head of a singly linked list, reverse the list and return the new head. Implement an iterative solution in your preferred language and explain invariants during iteration. Example: 1->2->3->4->NULL becomes 4->3->2->1->NULL. Achieve O(n) time and O(1) extra space and analyze complexity.

Sample Answer

Approach: Iteratively walk the list and reverse links one node at a time using three pointers: prev, curr, next. Maintain invariant that before each iteration, prev points to the head of the already-reversed prefix (or None for empty prefix), and curr points to the first node of the remaining unreversed suffix. Each step reverses curr.next to point to prev, then advances prev and curr.

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head: ListNode) -> ListNode:
    """
    Reverse a singly linked list iteratively.
    Time: O(n), Space: O(1)
    """
    prev = None       # reversed prefix head
    curr = head       # head of remaining suffix

    while curr:
        nxt = curr.next    # save next node (invariant: curr -> nxt -> ...)
        curr.next = prev   # reverse link (now curr is new head of reversed prefix)
        prev = curr        # extend reversed prefix
        curr = nxt         # move to next node in original order

    return prev  # prev is new head (original tail)

Key invariants:- At loop start: prev is head of reversed prefix (could be None), curr is head of unreversed suffix.- After reversing curr.next -> prev, the combined list is: (reversed prefix starting at curr) followed by the remaining suffix starting at nxt.- No node is lost because nxt stores the remaining suffix before changing links.

Time complexity: O(n) — single pass. Space complexity: O(1) extra — only three pointers. Edge cases: empty list (head is None), single-node list, and lists with cycles (function assumes acyclic list).

EasyTechnical

56 practiced

You are given two sorted integer arrays nums1 and nums2, where nums1 has a length of m + n with the first m elements valid and the last n elements set to 0 as placeholders. Merge nums2 into nums1 in-place to produce one sorted array. Implement in C++ or Python, achieve O(m+n) time and O(1) extra space, and explain your pointer strategy.

Sample Answer

Approach:Use three pointers and fill nums1 from the end to avoid overwriting. p1 points to last valid element in nums1 (m-1), p2 to last element in nums2 (n-1), and p points to last position in nums1 (m+n-1). Compare nums1[p1] and nums2[p2], place the larger at nums1[p], and decrement pointers. When one array is exhausted, remaining elements (if any) from nums2 are copied into nums1.

python

def merge(nums1, m, nums2, n):
    """
    Merge nums2 into nums1 in-place.
    nums1 has length m + n, first m are valid, last n are zeros.
    Time: O(m + n), Space: O(1)
    """
    p1 = m - 1          # last valid in nums1
    p2 = n - 1          # last in nums2
    p = m + n - 1       # last position in nums1 (fill from end)

    while p2 >= 0:      # only need to ensure nums2 is consumed
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

Key points:- Filling from the end avoids shifting elements and keeps O(1) extra space.- Pointer strategy: compare tails and write largest to tail of destination.Time complexity: O(m + n). Space complexity: O(1).

Edge cases:- m == 0 (nums1 empty of valid elements): loop copies all nums2.- n == 0: no changes.- Duplicates and negative numbers handled correctly.

Alternative:- Merge forward using extra array (simpler) but uses O(m + n) extra space; not acceptable here.

HardTechnical

56 practiced

Design serialize and deserialize functions for a Binary Search Tree that produce a compact representation smaller than naive null-marked BFS strings. Implement serialization using preorder traversal without storing null markers, and reconstruct the BST during deserialization using bound constraints. Provide Python code and explain correctness and compactness.

Sample Answer

Approach — use preorder traversal (root,left,right) to serialize values only (no null markers). A BST's preorder uniquely determines structure because left subtree values < root < right subtree values. During deserialization, consume the preorder list in order and rebuild recursively using (min, max) bounds so each value is placed in the correct subtree. This avoids storing explicit nulls and yields a compact string: only node values.

python

# Python implementation: serialize/deserialize BST using preorder without null markers.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root):
    """Return compact string of preorder values (space-separated)."""
    vals = []
    def preorder(node):
        if not node:
            return
        vals.append(str(node.val))
        preorder(node.left)
        preorder(node.right)
    preorder(root)
    return " ".join(vals)  # empty string for empty tree

def deserialize(data):
    """Reconstruct BST from preorder values using bounds."""
    if not data:
        return None
    vals = list(map(int, data.split()))
    idx = 0
    def build(lower, upper):
        nonlocal idx
        if idx >= len(vals):
            return None
        val = vals[idx]
        if not (lower < val < upper):   # must fit BST bounds
            return None
        idx += 1
        node = TreeNode(val)
        node.left = build(lower, val)
        node.right = build(val, upper)
        return node
    return build(float("-inf"), float("inf"))

Correctness:- Preorder of BST contains root then values for left subtree (< root) then right subtree (> root). Using increasing bounds ensures each consumed value belongs to the current subtree; recursion reconstructs the original shape.- Works when BST has unique values. If duplicates are allowed, define a consistent tie-break (e.g., <= goes left) and adjust bounds check accordingly.

Compactness:- Serialized form stores only n values (space-separated integers). A naive BFS with null markers stores n values plus up to n+1 null tokens — roughly doubles size for sparse trees. This preorder format is thus significantly smaller, especially when tree is unbalanced or sparse.

Complexity:- Time: O(n) to serialize and O(n) to deserialize (each value consumed once).- Space: O(n) for output string and recursion stack (O(h) auxiliary during operations, h = tree height).

Edge cases:- Empty tree -> empty string; deserializes to None.- Very large trees might need iterative conversion to avoid recursion limits.

EasyTechnical

41 practiced

Given a string containing parentheses characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if brackets are closed in the correct order and match types. Implement in Java or Python and analyze time/space complexity. Examples: '()[]{}' -> true, '(]' -> false.

Sample Answer

A clean way is to use a stack: push opening brackets, and for each closing bracket check the stack top matches the corresponding opening bracket. If mismatch or stack empty, return false. At end the stack must be empty.

python

def is_valid(s: str) -> bool:
    """
    Return True if s contains valid matching parentheses.
    """
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs.values():        # opening bracket
            stack.append(ch)
        elif ch in pairs:               # closing bracket
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            # If other characters are allowed, decide policy. Here we treat them invalid.
            return False
    return not stack

Key points:- Use a hash map for matching closing->opening for O(1) checks.- Maintain LIFO order with a stack to enforce correct nesting.

Time complexity: O(n) — one pass over the string.Space complexity: O(n) in worst case (all openings on stack).

Edge cases:- Empty string -> True.- Starts with closing bracket -> False.- Unequal counts or wrong nesting like "([)]" -> False.Alternative: For restricted inputs you can use string replacement loop (replace "()", "[]", "{}" until no change), but that is less efficient (O(n^2) worst-case) and not recommended for large inputs.

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.