12 DSA Problems Every Fresher Should Be Able to Solve (With Python Code)

The coding round in most fresher interviews is not about rare tricks. It checks whether you can use the basic tools: a hash map, two pointers, a stack, a queue, recursion and a little dynamic programming. The 12 problems below cover those tools. Each one comes with the idea in plain words, a tested Python solution, and its time and space complexity.

Read the idea, close the page, and write the code yourself before you look at the solution. A solution you only read is forgotten by the next day.

Arrays and strings

1. Two Sum

Problem. Given a list of numbers and a target, return the positions of the two numbers that add up to the target. Exactly one answer exists.

Idea. For each number, the partner you need is target − number. Keep a dictionary of the numbers seen so far and their positions; if the partner is already in it, you are done. This turns an O(n²) double loop into a single pass.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Complexity. O(n) time, O(n) space.

2. Best time to buy and sell a stock

Problem. prices[i] is a share's price on day i. Buy on one day and sell on a later day. What is the most profit you can make? Return 0 if no trade makes money.

Idea. Walk through the days once and remember the lowest price so far. On each day, selling today would earn price − lowest, so keep the best of those.

def max_profit(prices):
    lowest = float("inf")
    best = 0
    for p in prices:
        lowest = min(lowest, p)
        best = max(best, p - lowest)
    return best

print(max_profit([7, 1, 5, 3, 6, 4]))  # 5  (buy at 1, sell at 6)

Complexity. O(n) time, O(1) space.

3. Maximum subarray sum (Kadane's algorithm)

Problem. Find the largest sum of any contiguous part of a list. The list may contain negative numbers.

Idea. At each position, the best subarray ending here either continues the previous one or starts fresh at this number, whichever is larger. Track the best value seen anywhere.

def max_subarray(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6  ([4, -1, 2, 1])

Complexity. O(n) time, O(1) space. Starting from nums[0] instead of 0 makes it correct when every number is negative; that is the usual follow-up question.

4. Longest substring without repeating characters

Problem. Find the length of the longest stretch of a string in which no character repeats.

Idea. Keep a window [start, i] with no repeats (a sliding window). Remember where each character was last seen. When the current character already appears inside the window, move start just past its last position.

def longest_unique(s):
    last = {}          # char -> last index seen
    start = best = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1
        last[ch] = i
        best = max(best, i - start + 1)
    return best

print(longest_unique("abcabcbb"))  # 3  ("abc")
print(longest_unique("pwwkew"))    # 3  ("wke")

Complexity. O(n) time, and space for one entry per distinct character.

5. Binary search

Problem. Find the position of a target in a sorted list, or return −1.

Idea. Compare with the middle element and throw away the half that cannot contain the target. Each step halves the range.

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3

Complexity. O(log n) time, O(1) space. Off-by-one mistakes are the classic failure, so be ready to say why the loop is lo <= hi and why the updates are mid + 1 and mid - 1. In Java or C++, write mid = lo + (hi - lo) / 2 so that lo + hi cannot overflow.

Stacks and linked lists

6. Valid parentheses

Problem. Given a string of ()[]{}, decide whether every bracket is closed in the right order.

Idea. Push each opening bracket onto a stack. A closing bracket must match the bracket on top of the stack. At the end, the stack must be empty.

def is_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(is_valid("{[()]}"))  # True
print(is_valid("([)]"))    # False

Complexity. O(n) time, O(n) space.

7. Reverse a linked list

Problem. Reverse a singly linked list and return the new head.

Idea. Walk the list once with three pointers: prev, cur, and the next node (saved before you change the link). Point each node back at prev.

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

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

Complexity. O(n) time, O(1) space. Draw three boxes and the arrows on paper while you explain this one; interviewers want to see that you do not lose the rest of the list.

8. Detect a cycle in a linked list

Problem. Decide whether a linked list loops back on itself.

Idea. This is Floyd's "tortoise and hare". Move one pointer one step at a time and another two steps at a time. If there is a loop, the fast pointer eventually catches up with the slow one; if not, it reaches the end.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Complexity. O(n) time, O(1) space. A set of visited nodes also works, but uses O(n) space; mention both and say why you chose this one.

9. Merge two sorted linked lists

Problem. Merge two sorted linked lists into one sorted list.

Idea. Start from a dummy node and repeatedly attach the smaller of the two front nodes. When one list runs out, attach the rest of the other.

def merge(a, b):
    dummy = tail = Node(0)
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

Complexity. O(n + m) time, O(1) extra space, because the existing nodes are reused. The dummy node saves you from writing a special case for the first node.

Trees, graphs and dynamic programming

10. Level-order traversal of a binary tree

Problem. Return the values of a binary tree level by level, top to bottom.

Idea. This is breadth-first search. Use a queue and process it one level at a time: the queue's length at the start of a level is the number of nodes on that level.

from collections import deque

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

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

tree = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(level_order(tree))  # [[3], [9, 20], [15, 7]]

Complexity. O(n) time, and O(n) space for the queue. Use deque: list.pop(0) is O(n) per call.

11. Number of islands

Problem. A grid has "1" for land and "0" for water. Count the islands, where an island is land connected up, down, left or right.

Idea. Scan the grid. Each time you find land you have not visited, that is a new island: count it and mark every connected land cell as visited, using a depth-first search with an explicit stack.

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                count += 1
                stack = [(r, c)]
                seen.add((r, c))
                while stack:
                    i, j = stack.pop()
                    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        ni, nj = i + di, j + dj
                        if 0 <= ni < rows and 0 <= nj < cols \
                                and grid[ni][nj] == "1" and (ni, nj) not in seen:
                            seen.add((ni, nj))
                            stack.append((ni, nj))
    return count

grid = [
    ["1", "1", "0", "0"],
    ["1", "0", "0", "1"],
    ["0", "0", "1", "1"],
]
print(num_islands(grid))  # 2

Complexity. O(rows × cols) time and space. A recursive DFS is shorter, but Python's recursion limit (about 1,000 calls) can break it on a large grid, which is a good point to raise yourself.

12. Climbing stairs

Problem. You can climb 1 or 2 steps at a time. In how many different ways can you climb n steps?

Idea. To reach step n, your last move came from step n − 1 or step n − 2, so ways(n) = ways(n − 1) + ways(n − 2), the Fibonacci pattern. Build the answer up from the bottom and keep only the last two values.

def climb_stairs(n):
    a, b = 1, 1        # ways to reach step 0 and step 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

print(climb_stairs(5))  # 8

Complexity. O(n) time, O(1) space. Plain recursion recalculates the same steps over and over and takes exponential time. Explaining that, and then fixing it, is exactly the dynamic-programming step the interviewer wants to hear.

How to use these 12 in an interview

1. Say the brute force first, with its complexity, before you optimise. It shows you understand the problem and gives you a fallback.
2. Ask about edge cases out loud: an empty input, a single element, duplicates, negative numbers, a very large n.
3. Run your code by hand on a small example before you say "done". Most bugs show up in the first two or three steps.
4. State the time and space complexity without being asked.

To practise writing and running solutions, use the coding problems. To practise explaining them out loud, which is the part most people find harder, try a mock technical interview.

FAQ