Coding Fundamentals and Problem Solving Questions

Focuses on algorithmic thinking, data structures, and the process of solving coding problems under time constraints. Topics include core data structures such as arrays, linked lists, hash tables, trees, and graphs, common algorithms for searching and sorting, basics of dynamic programming and graph traversal, complexity analysis for time and space, and standard coding patterns. Emphasis on a disciplined problem solving approach: understanding the problem, identifying edge cases, proposing solutions with trade offs, implementing clean and readable code, and testing or reasoning about correctness and performance. Includes debugging strategies, writing maintainable code, and practicing medium difficulty interview style problems.

MediumTechnical

37 practiced

Given a list of intervals represented as pairs [start, end], implement in Python a function merge(intervals) that merges all overlapping intervals and returns the merged list sorted by start time. Example: [[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]]. Aim for O(n log n) time due to sorting.

Sample Answer

To merge overlapping intervals, sort by start time, then iterate and merge consecutive intervals when the current interval's start <= last merged end. This yields O(n log n) due to sorting and O(n) for the single pass.

python

from typing import List

def merge(intervals: List[List[int]]) -> List[List[int]]:
    """
    Merge overlapping intervals and return sorted merged list.
    Time: O(n log n) due to sort. Space: O(n) for output (or O(1) extra if in-place).
    """
    if not intervals:
        return []
    
    # Sort intervals by start time
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    for curr in intervals[1:]:
        last = merged[-1]
        # Overlap if current start <= last end
        if curr[0] <= last[1]:
            # Merge by extending the end to the max end
            last[1] = max(last[1], curr[1])
        else:
            merged.append(curr)
    return merged

Key points:- Sorting ensures we only need a single linear pass to merge.- Use max to handle nested or partially overlapping intervals.Time complexity: O(n log n). Space complexity: O(n) for result (O(1) extra if modifying input).

Edge cases:- Empty list- Single interval- Intervals already non-overlapping- Intervals with same start or identical intervals

Alternative: If intervals arrive already sorted, skip sorting and achieve O(n).

HardTechnical

31 practiced

Given an n x n matrix where each row and column is sorted ascending, implement a Python function kthSmallest(matrix, k) to find the kth smallest element. Describe two approaches: using a min-heap merging rows with O(k log n) complexity and using binary search over value range with O(n log(range)) complexity; discuss tradeoffs and when one is preferable.

Sample Answer

Approach 1 — Min-Heap merging rows (O(k log n)):Idea: Treat each row as a sorted list. Push first element of each row into a min-heap (value, row, col). Pop the smallest k-1 times, and when you pop (r,c) push (r,c+1) if exists. After k-1 pops, the next pop is kth smallest.

python

import heapq

def kthSmallest_heap(matrix, k):
    n = len(matrix)
    if n == 0 or k < 1 or k > n * n:
        raise ValueError("Invalid input")
    heap = []
    # push first element of each row (value, row, col)
    for r in range(min(n, k)):  # no need to push more than k rows
        heapq.heappush(heap, (matrix[r][0], r, 0))
    # pop k-1 times
    for _ in range(k - 1):
        val, r, c = heapq.heappop(heap)
        if c + 1 < n:
            heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
    return heapq.heappop(heap)[0]

Approach 2 — Binary search on value range (O(n log(range))):Idea: Use value-range binary search between smallest and largest elements. For mid, count how many elements <= mid using row-wise binary search (or two-pointer from bottom-left in O(n)). If count < k move right, else move left. Continue until low is kth smallest.

python

import bisect

def kthSmallest_bs(matrix, k):
    n = len(matrix)
    if n == 0 or k < 1 or k > n * n:
        raise ValueError("Invalid input")
    low, high = matrix[0][0], matrix[-1][-1]
    while low < high:
        mid = (low + high) // 2
        # count <= mid using bisect on each row
        cnt = 0
        for row in matrix:
            cnt += bisect.bisect_right(row, mid)
        if cnt < k:
            low = mid + 1
        else:
            high = mid
    return low

Key points and trade-offs:- Heap: O(k log min(n,k)) time, O(min(n,k)) space. Simple, returns exact element by order. Good when k is small relative to n (e.g., k << n^2) or when matrix values range is huge/unknown.- Binary search: Each count is O(n log n) if using bisect per row, or O(n) with two-pointer, so total O(n log(range)) where range = max-min. Uses O(1) extra space. Prefer when n is moderate and k large (near n^2) or when matrix is large but value range is small or comparisons are cheap.- Binary search is faster when k is large or when range is small; heap is better when k is small or you need actual streaming/online retrieval of first k elements.Edge cases: empty matrix, k out of bounds, duplicate values (both handle correctly).

EasyTechnical

37 practiced

Implement iterative binary search in JavaScript. Given a sorted array of distinct integers nums and an integer target, write function function binarySearch(nums, target) that returns index of target or -1. Constraint: O(log n) time, O(1) space. Provide example: nums = [1,2,3,4,5], target = 3 -> 2. Explain invariants you maintain for left and right pointers.

Sample Answer

To implement iterative binary search, keep two pointers left and right that define a closed interval [left, right] where the target may reside. Repeatedly compute mid = left + Math.floor((right - left) / 2), compare nums[mid] with target, and move left or right to shrink the interval while maintaining the invariant that the target, if present, is always inside [left, right]. Stop when left > right and return -1.

javascript

function binarySearch(nums, target) {
  // nums: sorted array of distinct integers
  // returns index of target or -1
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    // prevent overflow and pick middle
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) return mid;
    if (nums[mid] < target) {
      // target must be in (mid, right]
      left = mid + 1;
    } else {
      // target must be in [left, mid)
      right = mid - 1;
    }
  }

  return -1;
}

// Example:
console.log(binarySearch([1,2,3,4,5], 3)); // 2

Key invariants:- Before each loop iteration, target ∈ [left, right] if it exists.- left and right are valid indices (left ∈ [0, n], right ∈ [-1, n-1]) and interval shrinks each loop.- Loop ends when left > right, meaning interval empty and target absent.

Complexity:- Time: O(log n)- Space: O(1)

Edge cases:- Empty array -> returns -1- Single-element arrays- Target at ends- Distinct integers assumption avoids equal-key ambiguity.

EasyTechnical

39 practiced

Explain how hash tables handle collisions. Compare separate chaining to open addressing (linear probing), describe how deletion is handled in each, define load factor, and discuss effects on performance and memory usage. Provide scenarios where one approach is preferable.

EasyTechnical

43 practiced

Given two sorted singly linked lists, implement a C++ function ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) that merges them into a single sorted list and returns its head. Do this in-place without allocating new nodes (reuse the existing nodes) and explain both iterative and recursive approaches and their space usage.

Sample Answer

To merge two sorted singly linked lists in-place, we splice nodes from l1 and l2 by adjusting next pointers rather than allocating new nodes. Both iterative and recursive approaches are simple and O(n) time; iterative uses O(1) extra space, recursive uses O(n) call stack.

Iterative approach (O(1) extra space):

cpp

// Definition
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

Recursive approach (uses call stack O(n) space worst-case):

cpp

ListNode* mergeTwoListsRecursive(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val <= l2->val) {
        l1->next = mergeTwoListsRecursive(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoListsRecursive(l1, l2->next);
        return l2;
    }
}

Key points:- Time complexity: O(n1 + n2).- Space: iterative O(1) extra, recursive O(n1 + n2) stack.- In-place: nodes reused; watch for null pointers and preserve next before reassigning in more complex variants.

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.