Beginner DSA Interview Questions and Answers

Big O describes how an algorithm's running time (or memory) grows as the input size n grows, ignoring constants and smaller terms. It lets you compare algorithms independently of hardware. For example, finding the maximum of a list is O(n); checking every pair is O(n²). See Big O Notation.

Use an array when you index a lot; a linked list when you insert and remove in the middle through references you already hold.

A stack is last in, first out (undo, back button, recursion, bracket matching). A queue is first in, first out (task scheduling, BFS). In Python, use a list for a stack (append, pop) and collections.deque for a queue (append, popleft).

from collections import deque

stack, queue = [1, 2, 3], deque([1, 2, 3])
print(stack.pop(), queue.popleft())

3 1

A hash function turns each key into an index into an array of buckets, so a lookup jumps straight to one bucket instead of scanning. Collisions (two keys in one bucket) are handled by chaining or open addressing, and the table resizes as it fills so buckets stay short. That makes lookups O(1) on average; the worst case is O(n) if many keys collide. See Hash Tables.

It needs sorted data (or a yes/no condition that flips only once). Each step compares with the middle and discards half, so it costs O(log n). A million items need at most 20 comparisons.

A function that calls itself on a smaller input, with a base case that stops it. Problems: a missing or unreachable base case gives infinite recursion (RecursionError in Python), deep recursion uses O(depth) stack memory, and branching recursion can repeat work exponentially unless you memoize.

Simple sorts (bubble, selection, insertion) compare many pairs: O(n²). Merge sort, heap sort and (on average) quick sort divide the work in halves: O(n log n). For 100,000 items, n² is 10 billion while n log₂ n is about 1.7 million. Python's sorted() is O(n log n).

def reverse(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

print(reverse("interview"), reverse(""))

weivretni

Strings are immutable in Python, so convert to a list, swap from both ends, and join: O(n).

def second_largest(nums):
    first = second = None
    for x in nums:
        if first is None or x > first:
            first, second = x, first
        elif x != first and (second is None or x > second):
            second = x
    return second

print(second_largest([4, 9, 2, 9, 7]))
print(second_largest([5, 5]))

7
None

O(n) time, O(1) space. Duplicates of the maximum do not count as the second largest; with only one distinct value there is none.

def has_duplicates(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

print(has_duplicates([1, 2, 3, 1]), has_duplicates([1, 2, 3]))

True False

O(n) time with a set, versus O(n²) comparing every pair. Mention the alternative: sorting first and checking neighbours is O(n log n) with O(1) extra space.

A list holds n distinct numbers from 0 to n, with one missing. The expected total is n(n + 1)/2; the difference is the missing number:

def missing_number(nums):
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)

print(missing_number([3, 0, 1]), missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]))

2 8

O(n) time, O(1) space. (XOR-ing all indexes and values also works and cannot overflow in fixed-size integer languages.)

def move_zeros(nums):
    write = 0
    for x in nums:
        if x != 0:
            nums[write] = x
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0
    return nums

print(move_zeros([0, 1, 0, 3, 12]))

[1, 3, 12, 0, 0]

The read/write pointer pattern from Two Pointers: O(n) time, in place.

from collections import Counter

def is_anagram(a, b):
    return len(a) == len(b) and Counter(a) == Counter(b)

print(is_anagram("listen", "silent"), is_anagram("hello", "world"))

True False

Counting characters is O(n); comparing sorted strings is O(n log n). Ask whether case and spaces matter.

def valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

print(valid("()[]{}"), valid("(]"), valid("([)]"), valid("{[]}"))

True False False True

A stack holds the open brackets; each closer must match the most recent opener. O(n).