DSA Basics Interview Questions

A data structure organizes data so the operations you need are cheap: an array reads by index in O(1), a hash table finds a key in O(1) on average. An algorithm is a finite sequence of steps from input to output, such as binary search. You choose them together: finding duplicates pair by pair is O(n²), with a set it is O(n).

In a linear structure the elements form a sequence, each with at most one predecessor and one successor: arrays, linked lists, stacks, queues. In a non-linear one an element connects to several others: trees, heaps, graphs, tries. Linear ones are walked in one pass; non-linear ones need DFS or BFS.

An array stores elements in one contiguous block, so a[i] is O(1) but inserting in the middle is O(n). A linked list stores each element in a node pointing to the next, so inserting after a node you hold is O(1), but reaching the i-th element is O(n). Arrays win most benchmarks because of CPU caching. See a linked list step by step.

A stack is LIFO (last in, first out): push and pop at the same end. A queue is FIFO (first in, first out): add at the back, remove from the front. In Python use a list as a stack and deque as a queue, since list.pop(0) is O(n) (see the deque docs).

from collections import deque

stack = []
for x in [1, 2, 3]:
    stack.append(x)
print("stack pops:", stack.pop(), stack.pop())

queue = deque()
for x in [1, 2, 3]:
    queue.append(x)
print("queue pops:", queue.popleft(), queue.popleft())

Watch a stack in action.

Recursion is a function calling itself on a smaller input. The base case is an input small enough to answer directly; without one, the calls never stop.

import sys

def factorial(n):
    if n <= 1:                   # base case
        return 1
    return n * factorial(n - 1)  # smaller input

print(factorial(5))
print(sys.getrecursionlimit())

Each pending call holds a stack frame, so recursion uses O(depth) memory; CPython raises RecursionError at a depth of about 1000 by default. See the call stack grow and unwind.

f(4) expands to 4 + 3 + 2 + 1 + f(0), and the base case returns 0, so it prints 10. Reading it as factorial (24) is the common slip; the operator is +. It takes O(n) time and O(n) stack.

A slice with step -1 builds a new, reversed string, yddoc. Strings are immutable, so s is still coddy.

Follow-up: reverse it by hand? Copy the string into a list and swap from both ends with two pointers.

Compare characters from both ends moving inward; any mismatch means it is not a palindrome. That is O(n) time and O(1) space; s == s[::-1] is also O(n) but builds a reversed copy.

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

for word in ["racecar", "level", "coddy", ""]:
    print(repr(word), is_palindrome(word))

Follow-up: ignore case and punctuation? Skip characters that fail isalnum() inside the same loop and compare lowercased characters, without building a cleaned copy.

Keep first and second. A value above first pushes the old first down to second; a value above second that is not equal to first becomes second. One pass, O(1) space; sorting costs O(n log 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([12, 35, 1, 10, 34, 1]))
print(second_largest([10, 10, 10]))

Raise duplicates yourself: [10, 10, 10] has no second largest, so this returns None, not 10.

Subtract the array's sum from n * (n + 1) // 2, the sum of 0 to n. O(n) time, O(1) space. XORing every index and every value gives the same answer and avoids overflow in languages with fixed-size integers.

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

def missing_xor(nums):
    result = len(nums)
    for i, x in enumerate(nums):
        result ^= i ^ x
    return result

nums = [3, 0, 1, 5, 2]
print(missing_sum(nums), missing_xor(nums))

Both print 4.

Match the structure to the operation the feature does most: two stacks for undo and redo, a queue for a printer queue, a trie for autocomplete, a heap for a leaderboard's top k, a hash map for a phone book, and a graph for routes on a map. Say the operation out loud: "we mostly look up by key, so a hash map".

Clarify, work an example, state the brute force, remove its bottleneck, then code and test:

1. Ask about input size, duplicates, negatives and empty input.
2. Work a small example by hand.
3. State the brute force and its complexity.
4. Remove the bottleneck: a hash map for lookups, two pointers on sorted data, a heap for top k.
5. Code it and trace your example.

Around 10^5 elements means O(n log n) or better.