Data Structures & Algorithms — Interview Crash Course

DodaTech Updated 2026-06-21 7 min read

In this tutorial, you'll learn about Data Structures & Algorithms. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Data structures and algorithms form the foundation of coding interviews — arrays, trees, graphs, sorting, searching, and Dynamic Programming appear in nearly every technical screen. This crash course covers the essential data structures, their time complexities, common algorithms, and interview patterns. DodaTech engineers apply these fundamentals daily in Doda Browser's rendering engine and Durga Antivirus Pro's pattern-matching algorithms.

DSA Quick Reference

flowchart TD
  A[DSA Review] --> B[Linear: Arrays, Linked Lists, Stacks, Queues]
  A --> C[Hierarchical: Trees, Heaps, Graphs]
  A --> D[Lookup: Hash Tables, Sets]
  A --> E[Algorithms: Sort, Search, DP]
  style A fill:#f90,color:#fff

Time Complexity Cheatsheet

Data Structure	Access	Search	Insert	Delete
Array	O(1)	O(n)	O(n)	O(n)
Stack	O(n)	O(n)	O(1)	O(1)
Queue	O(n)	O(n)	O(1)	O(1)
Singly Linked List	O(n)	O(n)	O(1)	O(1)
Doubly Linked List	O(n)	O(n)	O(1)	O(1)
Hash Table	O(1)*	O(1)*	O(1)*	O(1)*
Binary Search Tree	O(log n)*	O(log n)*	O(log n)*	O(log n)*
Heap	O(1)	O(n)	O(log n)	O(log n)

*Average case. Worst case can be O(n).

Arrays

The most fundamental data structure. Fixed-size contiguous memory blocks.

# Array operations
arr = [10, 20, 30, 40, 50]

# Access — O(1)
print(f"Third element: {arr[2]}")

# Insert at end — O(1) amortized
arr.append(60)

# Insert at beginning — O(n)
arr.insert(0, 5)

# Delete — O(n)
removed = arr.pop(2)

# Find — O(n)
index = arr.index(40) if 40 in arr else -1

print(f"Array: {arr}")
print(f"Found 40 at index: {index}")
print(f"Removed element: {removed}")

Expected output:

Third element: 30
Array: [5, 10, 20, 40, 50, 60]
Found 40 at index: 3
Removed element: 30

Linked Lists

Nodes connected by pointers. Good for frequent insertions/deletions.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def reverse_linked_list(head):
    """Reverse a linked list in place."""
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

def list_to_ll(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

def ll_to_list(head):
    result = []
    while head:
        result.append(head.value)
        head = head.next
    return result

original = list_to_ll([1, 2, 3, 4, 5])
reversed_head = reverse_linked_list(original)
print(f"Reversed: {ll_to_list(reversed_head)}")

Expected output:

Reversed: [5, 4, 3, 2, 1]

Hash Tables

Key-value storage with O(1) average lookups. HashMap, Dictionary, Object.

# Hash table operations
user_scores = {}

# Insert — O(1) average
user_scores["alice"] = 95
user_scores["bob"] = 87
user_scores["charlie"] = 92

# Lookup — O(1) average
print(f"Alice's score: {user_scores.get('alice', 'Not found')}")

# Check existence
print(f"David in scores: {'david' in user_scores}")

# Group by pattern: find duplicates
def find_duplicates(nums):
    seen = {}
    for num in nums:
        if num in seen:
            return num
        seen[num] = True
    return -1

print(f"First duplicate: {find_duplicates([3, 1, 4, 2, 5, 3, 6])}")

Expected output:

Alice's score: 95
David in scores: False
First duplicate: 3

Trees

Binary Tree Traversal

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

def inorder_traversal(root):
    """In-order: left, root, right (sorted in BST)."""
    result = []
    def traverse(node):
        if not node:
            return
        traverse(node.left)
        result.append(node.value)
        traverse(node.right)
    traverse(root)
    return result

def max_depth(root):
    """Find maximum depth of binary tree."""
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# Build a BST:      5
#                  / \
#                 3   8
#                / \   \
#               2   4   10
root = TreeNode(5,
    TreeNode(3, TreeNode(2), TreeNode(4)),
    TreeNode(8, None, TreeNode(10))
)

print(f"In-order: {inorder_traversal(root)}")
print(f"Max depth: {max_depth(root)}")

Expected output:

In-order: [2, 3, 4, 5, 8, 10]
Max depth: 3

Sorting Algorithms

Algorithm	Best	Average	Worst	Space
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)

def quick_sort(arr):
    """Quick sort using last element as pivot."""
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

def merge_sort(arr):
    """Merge sort — divide and conquer."""
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

data = [38, 27, 43, 3, 9, 82, 10]
print(f"Quick sort: {quick_sort(data)}")
print(f"Merge sort: {merge_sort(data)}")

Expected output:

Quick sort: [3, 9, 10, 27, 38, 43, 82]
Merge sort: [3, 9, 10, 27, 38, 43, 82]

Dynamic Programming

DP solves problems by breaking them into overlapping subproblems and storing results to avoid recomputation.

def fibonacci(n):
    """Fibonacci with DP (bottom-up)."""
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

def coin_change(coins, amount):
    """Minimum coins needed to make amount."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount] if dp[amount] != float('inf') else -1

print(f"Fibonacci(10): {fibonacci(10)}")
print(f"Coin change for 11 with [1,2,5]: {coin_change([1, 2, 5], 11)}")

Expected output:

Fibonacci(10): 55
Coin change for 11 with [1,2,5]: 3

Common Mistakes

Not analyzing time/space complexity — Every interview expects you to discuss Big O. Always state your complexity before coding.
Choosing wrong data structure — Need fast lookups? Hash table. Need ordered data? Array. Need frequent insertions? Linked list.
Forgetting edge cases — Empty arrays, single elements, null inputs, negative numbers. Test these before running.
Overflow and off-by-one — Array indexing, binary search boundaries, loop conditions. Use left + (right-left)//2 to avoid overflow.
Modifying input without considering — Can you mutate the input? Ask before modifying.
Mixing BFS and DFS — BFS uses a queue (shortest path), DFS uses a stack/recursion (all paths).
Not optimizing brute force — If you start with brute force, acknowledge it and work toward optimization.

Practice Questions

1. What's the time complexity of accessing an element in a hash table? O(1) average, O(n) worst case (hash collisions). Good hash functions and load factor management keep it O(1).

2. When would you use a linked list over an array? When you need frequent insertions/deletions at arbitrary positions, or when you don't need random access.

3. What's the difference between DFS and BFS? DFS goes deep first (uses stack/recursion, good for path-finding). BFS goes level-by-level (uses queue, finds shortest path in unweighted graphs).

4. How do you identify a DP problem? Optimal substructure + overlapping subproblems. Keywords: minimum, maximum, number of ways, longest, shortest.

5. Challenge: Write a function that detects a cycle in a linked list using Floyd's Tortoise and Hare algorithm (two pointers, one slow one fast). Test it with a list that has a cycle and one that doesn't.

Real-World Task

Take a slow algorithm you've written in the past and optimize it using data structures from this guide. Profile both versions and document the performance improvement with before/after metrics.

FAQ

Which data structure appears most in interviews?

Arrays and hash tables appear in nearly every interview. Trees and graphs are the next most common, especially for senior roles. Master these four first.

How do I practice DSA effectively?

Focus on patterns, not problems. Solve problems by category (arrays, trees, DP) and learn to recognize the pattern before coding. Use LeetCode's "Explore" feature for structured learning.

Is it better to write iterative or recursive solutions?

Iterative is usually safer (no stack overflow) and often expected for production code. Recursive is sometimes more readable. Know both. For tree problems, recursive is typically fine with proper depth management.

← Previous Coding Challenges Practice — Structured Problem-Solving for Technical Interviews Next → Array & String Coding Problems — Interview Guide with Solutions

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Interview Prep