DSA Interview Notes
Short Theory + Python Coding Problems
Prepared for Fresher / Entry-Level roles (approx. 5-6 LPA)
This note covers the core Data Structures & Algorithms topics most commonly asked in fresher-level
technical interviews (service-based and product-based companies, 5-6 LPA range). Each topic has: a
short theory recap, a classic interview coding problem solved in Python, and its time/space complexity.
Use this as a quick revision sheet, not a first-time learning resource — solve each problem yourself before
checking the code.
Contents
1. Big-O / Time & Space Complexity
2. Arrays — Two Sum
3. Strings — Check Palindrome
4. Two Pointers — Pair with Given Sum (sorted array)
5. Sliding Window — Max Sum Subarray of Size K
6. Sorting — Merge Sort
7. Searching — Binary Search
8. Recursion — Fibonacci (basic)
9. Linked List — Reverse a Linked List
10. Stack — Valid Parentheses
11. Queue — Implement Queue using Two Stacks
12. Hashing — First Non-Repeating Character
13. Binary Tree — Inorder Traversal
14. Graph — BFS Traversal
15. Dynamic Programming — Climbing Stairs (memoization)
Foundations
1. Big-O / Time & Space Complexity
Big-O describes how runtime or memory grows as input size (n) grows. Common orders, fastest to
slowest: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic, O(2■) exponential.
Interviewers care about this because it tells them whether your solution will scale. Always state the
complexity of your solution out loud.
Code:
# Examples of common complexities
def constant(arr): # O(1)
return arr[0]
def linear(arr): # O(n)
total = 0
for x in arr:
total += x
return total
def quadratic(arr): # O(n^2)
for i in arr:
for j in arr:
print(i, j)
Know this table cold: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)
Arrays & Strings
2. Arrays — Two Sum
Given an array of integers and a target, return indices of the two numbers that add up to the target. Brute
force checks every pair (O(n²)). Optimal approach uses a hash map to store numbers seen so far,
checking the complement in O(1) per lookup.
Code:
def two_sum(nums, target):
seen = {} # value -> index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
Time: O(n) | Space: O(n)
3. Strings — Check Palindrome
A palindrome reads the same forwards and backwards. Use the two-pointer technique: one pointer from
the start, one from the end, moving toward the middle and comparing characters. Stop early on first
mismatch.
Code:
def is_palindrome(s):
s = [Link]()
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
print(is_palindrome("Madam")) # True
Time: O(n) | Space: O(1)
Two Pointers & Sliding Window
4. Two Pointers — Pair with Given Sum (sorted array)
For a SORTED array, find if a pair exists that sums to a target. Start with pointers at both ends: if the sum
is too small, move the left pointer right; if too large, move the right pointer left. Avoids the O(n²) brute-force
pair check.
Code:
def pair_with_sum(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current = arr[left] + arr[right]
if current == target:
return [arr[left], arr[right]]
elif current < target:
left += 1
else:
right -= 1
return []
print(pair_with_sum([1, 2, 3, 4, 6], 6)) # [2, 4]
Time: O(n) | Space: O(1) (array must be sorted first)
5. Sliding Window — Max Sum Subarray of Size K
To find the maximum sum of any contiguous subarray of fixed size k, avoid recomputing the sum from
scratch each time. Slide a window: subtract the element leaving the window and add the element entering
it.
Code:
def max_sum_subarray(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3)) # 9
Time: O(n) | Space: O(1)
Sorting & Searching
6. Sorting — Merge Sort
A divide-and-conquer sort: split the array into halves, recursively sort each half, then merge the two sorted
halves. Preferred over quicksort in interviews when stability or guaranteed O(n log n) worst case matters.
Code:
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
[Link](left[i]); i += 1
else:
[Link](right[j]); j += 1
[Link](left[i:])
[Link](right[j:])
return result
print(merge_sort([5, 2, 9, 1, 5, 6]))
Time: O(n log n) | Space: O(n)
7. Searching — Binary Search
Works only on SORTED arrays. Repeatedly halve the search range: compare the middle element to the
target, then discard the half that cannot contain it.
Code:
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
Time: O(log n) | Space: O(1)
Recursion
8. Recursion — Fibonacci (basic)
A function that calls itself to solve smaller sub-problems. Every recursive function needs a base case
(stopping condition) and a recursive case that moves toward it. Naive Fibonacci recomputes the same
sub-problems repeatedly — this is why it's often used to introduce memoization (see topic 15).
Code:
def fibonacci(n):
if n <= 1: # base case
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print([fibonacci(i) for i in range(8)])
# [0, 1, 1, 2, 3, 5, 8, 13]
Time: O(2^n) | Space: O(n) call stack (naive version)
Linked List, Stack & Queue
9. Linked List — Reverse a Linked List
A linked list is a chain of nodes, each pointing to the next. To reverse it, walk through the list and flip each
node's 'next' pointer to point backward, tracking the previous node as you go. A very common whiteboard
question.
Code:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
def reverse_list(head):
prev = None
current = head
while current:
next_node = [Link]
[Link] = prev
prev = current
current = next_node
return prev # new head
Time: O(n) | Space: O(1)
10. Stack — Valid Parentheses
A stack is LIFO (last in, first out). To check if brackets in a string are balanced: push opening brackets
onto a stack; on a closing bracket, pop and check it matches. String is valid only if the stack is empty at
the end.
Code:
def is_valid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in '([{':
[Link](ch)
elif ch in pairs:
if not stack or [Link]() != pairs[ch]:
return False
return not stack
print(is_valid("{[()]}")) # True
print(is_valid("{[(])}")) # False
Time: O(n) | Space: O(n)
11. Queue — Implement Queue using Two Stacks
A queue is FIFO (first in, first out). Using two stacks: push new elements onto stack 'in'. When you need to
dequeue, if 'out' is empty, pour everything from 'in' into 'out' (reversing order), then pop from 'out'.
Code:
class QueueUsingStacks:
def __init__(self):
self.stack_in = []
self.stack_out = []
def enqueue(self, x):
self.stack_in.append(x)
def dequeue(self):
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop() if self.stack_out else None
q = QueueUsingStacks()
[Link](1); [Link](2); [Link](3)
print([Link](), [Link]()) # 1 2
Time: O(1) amortized per op | Space: O(n)
Hashing, Trees & Graphs
12. Hashing — First Non-Repeating Character
A hash map (Python dict) gives O(1) average lookup/insert, making it ideal for frequency-counting
problems. Count occurrences of each character in one pass, then scan again to find the first with count 1.
Code:
def first_non_repeating(s):
freq = {}
for ch in s:
freq[ch] = [Link](ch, 0) + 1
for ch in s:
if freq[ch] == 1:
return ch
return None
print(first_non_repeating("swiss")) # 'w'
Time: O(n) | Space: O(k), k = distinct characters
13. Binary Tree — Inorder Traversal
A binary tree node has at most two children (left, right). Inorder traversal visits Left → Node → Right. On a
Binary Search Tree, inorder traversal visits nodes in sorted order — a fact interviewers like to probe.
Code:
class TreeNode:
def __init__(self, val):
[Link] = val
[Link] = None
[Link] = None
def inorder(root, result=None):
if result is None:
result = []
if root:
inorder([Link], result)
[Link]([Link])
inorder([Link], result)
return result
# Tree: 2
# / \
# 1 3
root = TreeNode(2)
[Link], [Link] = TreeNode(1), TreeNode(3)
print(inorder(root)) # [1, 2, 3]
Time: O(n) | Space: O(h), h = tree height (recursion stack)
14. Graph — BFS Traversal
Breadth-First Search explores a graph level by level using a queue. It's the standard approach for shortest
path in an unweighted graph and for problems like 'minimum steps to reach a node'. Track visited nodes to
avoid revisiting.
Code:
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = [Link]()
[Link](node)
for neighbor in graph[node]:
if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)
return order
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D']
Time: O(V + E) | Space: O(V)
Dynamic Programming
15. Dynamic Programming — Climbing Stairs (memoization)
DP = recursion + caching results of sub-problems to avoid recomputation. Classic problem: you can climb
1 or 2 steps at a time — how many distinct ways to reach step n? It follows the same recurrence as
Fibonacci: ways(n) = ways(n-1) + ways(n-2).
Code:
def climb_stairs(n, memo=None):
if memo is None:
memo = {}
if n <= 2:
return n
if n in memo:
return memo[n]
memo[n] = climb_stairs(n - 1, memo) + climb_stairs(n - 2, memo)
return memo[n]
print(climb_stairs(10)) # 89
Time: O(n) | Space: O(n) (vs O(2^n) without memoization)
Tip for interviews: always (1) clarify the problem and constraints, (2) state a brute-force approach and its
complexity first, (3) optimize, (4) code cleanly with meaningful names, (5) test with an example and an
edge case (empty input, single element, duplicates).