All the reading

Data Structures

8 lessons, about 35 minutes. The check's questions come from these.

Choosing arrays and maps

1. Pick by cost first

5 min

Key point

One rule

Pick by cost first. Not by what looks familiar or what you used in the last LeetCode problem.

For interviews, your first job is to match the operations in the problem to the cheapest data structure that supports them.

Cost means operations

A data structure is useful because it makes some operations cheap and others costly. Arrays are good when you need index access. Hash maps are good when you need fast lookup by key. Queues are good when you process items in arrival order.

Before you code, list the operations the problem needs. Common ones are lookup, insert, delete, update, get min or max, and traverse all items.

Your to-do

Ask these first

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Name the main operation the problem repeats many times.
Check if order matters: original order, sorted order, or no order.
Check if duplicates matter.
Estimate input size from the question, if given.
Choose the structure with the best cost for repeated work.

0 of 5 done

Example

Small cost table

Add a note like this in your repo. It is simple enough to revise before interviews.

Do not memorise blindly. Use it to explain trade-offs.

Data structure | Fast at | Usually costs
Array/List | index access, append | lookup by value is O(n)
Hash map | lookup by key, count, last seen | extra space O(n)
Hash set | membership check, unique values | extra space O(n)
Stack | last-in-first-out problems | only top is easy
Queue | first-in-first-out problems | only front/back are easy
Heap | repeated min/max | not full sorted order
Tree/BST | ordered structure | balance matters
Graph | relationships and paths | traversal needs visited tracking

2. Arrays strings maps sets

4 min

Key point

One idea

Use the simplest structure that gives the operation cost you need. Arrays and strings are good for ordered scans. Maps and sets are good when fast lookup or frequency matters.

When to pick what

Pick an array when you need index access, sorting, prefix sums, two pointers, or a sliding window. In Python, use list. In JavaScript, use Array.

Pick a string when the input is text, but remember many strings are immutable. If you build many characters step by step, collect pieces in an array or list, then join.

Maps and sets

Pick a map when each key has a value: count, last seen index, parent, score, or group. Python uses dict. JavaScript uses Map or a plain object for simple string keys.

Pick a set when you only care whether something exists. Use it for duplicate checks, visited items, and membership tests.

Your to-do

Using stacks queues lists

3. Stacks queues linked lists

5 min

Key point

One idea

Stacks and queues are about order. Linked lists are about cheap pointer changes when you already have the node.

If you need random access by index, do not pick a linked list. Use an array or list instead.

When to use stack

Use a stack when the last item seen must be handled first. Think undo, browser back, valid brackets, next greater element, monotonic stack problems, DFS without recursion.

In most languages, use the built-in dynamic array as a stack. In Python, list append and pop at the end are fine.

When to use queue

Use a queue when the first item waiting must be handled first. Think ticket counters, BFS, level order traversal, task scheduling, and sliding windows.

In Python, do not use list.pop(0). It shifts items. Use collections.deque for O(1) append and popleft.

Trees heaps and graphs

4. Trees and BSTs

4 min

Key point

Core idea

A tree is for hierarchy. A BST is for ordered data where left is smaller and right is larger.

In interviews, first say what structure fits the shape of the data. Then say the cost for search, insert, delete, and traversal.

When trees fit

Use trees for folders, comments and replies, organisation charts, DOM-like UI, tournament brackets, and decision paths.

A binary tree node has up to two children. A general tree can have many children. A BST is a binary tree with an ordering rule.

BST costs

A balanced BST gives search, insert, and delete in O(log n). An inorder traversal gives sorted order in O(n).

A bad BST can become a linked list if values are inserted in sorted order. Then search becomes O(n). In interviews, mention this risk.

Explaining and shipping work

7. Explain choices like interviews

4 min

Key point

Say why, not just what

In interviews, picking the right data structure is only half the answer. You must explain why it fits the operations in the problem.

Use this pattern: operation needed, data structure chosen, cost, trade-off, edge case.

What interviewers listen for

They want to see that you can reason, not recite. If you choose a hash map, say it gives average O(1) lookup and update, but uses extra space.

If you choose a heap, say it helps when you repeatedly need the min or max item, not when you need sorted full output once.

Your to-do

Use a simple script

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

10 questions, 7 to pass.

Example

Worked choice

Problem: find if an array has any duplicate value.

Slow thought: compare every pair. That takes O(n²). Better thought: keep seen values in a set. Each membership check is usually O(1), so total time is O(n), with O(n) extra space.

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


def test_has_duplicate():
    assert has_duplicate([1, 2, 3, 2]) is True
    assert has_duplicate([1, 2, 3, 4]) is False
    assert has_duplicate([]) is False

Example

Example file

Add one clean problem to your kit today: first non-repeating character. It shows why a map is better than scanning the string again and again.

# arrays_strings_maps_sets/first_non_repeating.py

def first_non_repeating(s: str) -> str:
    freq = {}

    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1

    for ch in s:
        if freq[ch] == 1:
            return ch

    return ""


def test_first_non_repeating():
    assert first_non_repeating("aabbcdd") == "c"
    assert first_non_repeating("leetcode") == "l"
    assert first_non_repeating("aabb") == ""
    assert first_non_repeating("") == ""

Example

Stack example

Put this in your repo as code/python/valid_parentheses.py. It shows the real stack pattern and has no extra classes.

def is_valid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []

    for ch in s:
        if ch in pairs.values():
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            return False

    return len(stack) == 0


def test_is_valid():
    assert is_valid("()[]{}") is True
    assert is_valid("([{}])") is True
    assert is_valid("(]") is False
    assert is_valid("((") is False

Example

Queue example

For queues, prefer deque in Python. This small BFS shape will repeat later when you reach trees and graphs.

from collections import deque

def time_to_process(tasks):
    q = deque(tasks)
    order = []

    while q:
        order.append(q.popleft())

    return order


def test_time_to_process():
    assert time_to_process(["A", "B", "C"]) == ["A", "B", "C"]

Tip

Write comparison notes

Your kit should not just dump solutions. Add short notes that explain why this structure fits.

A good note says: access pattern, main operations, costs, and why you rejected another option.

# notes/stacks-queues-linked-lists.md

Problem: Valid parentheses
Pick: Stack
Why: Need to match the latest unmatched opening bracket first.
Cost: O(n) time, O(n) space in the worst case.
Rejected: Queue, because oldest bracket first does not match nesting.

Problem: Process tasks in arrival order
Pick: Queue using deque
Why: First task should be processed first.
Cost: O(n) time, O(n) space.
Rejected: Python list with pop(0), because removing from the front shifts items.

Problem: Detect linked list cycle
Pick: Slow and fast pointers
Why: We only move through next links. No index access is needed.
Cost: O(n) time, O(1) space.
Rejected: Array copy, because it uses extra space and changes the problem shape.

Example

BST search code

Add this small Python file to your kit. Keep it boring and testable.

It shows the rule clearly: go left for smaller values, right for larger values.

# trees/bst_search.py

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


def search(root, target):
    cur = root
    while cur:
        if cur.val == target:
            return True
        if target < cur.val:
            cur = cur.left
        else:
            cur = cur.right
    return False


def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

Example

Test the rule

Your repo should prove code works. Add one test for search and one for sorted inorder traversal.

If you use pytest, this can go in tests/test_bst_search.py.

from trees.bst_search import Node, search, inorder


def sample_tree():
    return Node(
        8,
        Node(3, Node(1), Node(6)),
        Node(10, None, Node(14))
    )


def test_search_finds_existing_value():
    assert search(sample_tree(), 6) is True


def test_search_rejects_missing_value():
    assert search(sample_tree(), 7) is False


def test_inorder_is_sorted_for_bst():
    assert inorder(sample_tree()) == [1, 3, 6, 8, 10, 14]

5. Heaps for priority

4 min

Key point

One idea

A heap is for priority. Use it when the problem repeatedly asks for the smallest, largest, earliest, or highest-priority item while data changes.

If you only need one final sorted list, sort. If you need the next best item many times, use a heap.

Where heaps fit

A heap gives fast access to one extreme: min or max. In Python, heapq is a min-heap. In Java, PriorityQueue is a min-heap by default.

Common interview clues: kth largest, top K frequent, merge K sorted lists, meeting rooms, running median, shortest path later in graphs. The word priority may not appear.

Cost check

Heap push and pop cost O(log n). Peeking at the top costs O(1). Building a heap from an existing list costs O(n).

For top K, a heap of size K often beats sorting the full array. Sorting n items is O(n log n). A size K heap across n items is O(n log K).

Your to-do

Pick the heap

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Ask what must be returned first: smallest, largest, earliest, or most frequent.
Check if items change while solving: insert, remove, or update priority.
Use a min-heap directly for smallest values.
Store negative numbers when you need a max-heap in Python.
Keep heap size limited to K when the problem asks for top K.

0 of 5 done

Common mistake

Do not use a heap just because the problem says top or kth. If input is tiny in an interview dry run, many solutions work. You must explain cost.

Also remember: a heap is not sorted. Only heap[0] is guaranteed to be the current best item. Do not print the heap list as sorted output.

Example

Top K largest

This version keeps only K numbers in the heap. That is the interview point: do not store more than needed.

Add this to your repo as code/heaps/top_k_largest.py or similar.

import heapq

def top_k_largest(nums, k):
    if k <= 0:
        return []

    heap = []

    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)

    return sorted(heap, reverse=True)


def test_top_k_largest():
    assert top_k_largest([3, 1, 5, 12, 2, 11], 3) == [12, 11, 5]
    assert top_k_largest([5, 5, 5], 2) == [5, 5]
    assert top_k_largest([9, 1], 0) == []

if __name__ == "__main__":
    test_top_k_largest()
    print("ok")

Tip

Use AI carefully

You can ask ChatGPT or Gemini: “Give me three interview problems where a heap beats sorting, with time complexity and one edge case each.”

Check the answer. It should mention O(log n) push or pop, O(1) peek, and why the heap size may stay K. If it says the heap is sorted, fix that note.

Your to-do

Do this now

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Create a heaps folder in your dsa-interview-kit repo.
Add top_k_largest code with at least three tests.
Write a short note comparing sorting O(n log n) with heap O(n log K).
Add one more heap problem idea: merge K sorted lists or meeting rooms.
Commit with a clear message like add heap priority examples.

0 of 5 done

6. Graphs without fear

5 min

Key point

One idea

A graph is just nodes plus edges. Most interview graph problems ask one of three things: can I reach it, what is the shortest unweighted path, or what order is valid.

When it is a graph

Use a graph when items connect to other items in no fixed parent-child shape. Think friends in a college app, cities connected by trains, courses with prerequisites, or UPI transactions between accounts.

If each item has at most one parent, it may be a tree. If each item can connect to many others both ways or one way, think graph.

Your to-do

Pick the pattern

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Use an adjacency list for most interview problems because it stores only real edges.
Use BFS when all edges have equal cost and you need the fewest steps.
Use DFS when you need to explore a full component, detect a cycle, or mark visited nodes.
Use topological sort when tasks have prerequisites and you need a valid order.
Use Dijkstra only when edges have different positive costs. Do not use it for simple unweighted shortest path.

0 of 5 done

Common mistake

Beginners often forget the visited set. Then code loops forever on cycles like A to B and B to A.

Another mistake is using an adjacency matrix for sparse graphs. A matrix is easy to see, but it costs n squared space. For interviews, adjacency lists are usually the safer default.

Example

BFS shortest path

This finds the fewest edges from a start node to a target node in an unweighted graph. Add a file like graphs/bfs_shortest_path.py to your repo.

Notice the queue and visited set. The distance increases by 1 each time you move across an edge.

from collections import deque

def shortest_path_edges(graph, start, target):
    if start == target:
        return 0

    q = deque([(start, 0)])
    visited = {start}

    while q:
        node, dist = q.popleft()

        for nei in graph.get(node, []):
            if nei in visited:
                continue
            if nei == target:
                return dist + 1
            visited.add(nei)
            q.append((nei, dist + 1))

    return -1


def test_shortest_path_edges():
    graph = {
        "hostel": ["canteen", "library"],
        "canteen": ["hostel", "lab"],
        "library": ["hostel", "lab"],
        "lab": ["canteen", "library", "gate"],
        "gate": ["lab"]
    }

    assert shortest_path_edges(graph, "hostel", "gate") == 3
    assert shortest_path_edges(graph, "hostel", "hostel") == 0
    assert shortest_path_edges(graph, "gate", "unknown") == -1

Tip

Write interview notes

For every graph file, add a short note beside the code. Keep it practical: representation, algorithm, time cost, space cost, and why you did not pick another option.

Example note: adjacency list because the graph is sparse. BFS because edges are unweighted and we need minimum number of hops. Time O(V + E). Space O(V).

Directed or undirected

Ask this early. A follow relation, course prerequisite, or payment flow is directed. A friendship, road with both-way travel, or cable connection is often undirected.

In code, directed means add one edge: a to b. Undirected means add both: a to b and b to a.

Your to-do

Do this now

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Create a graphs folder in your dsa-interview-kit repo.
Add the BFS shortest path code with the three tests shown above.
Add one DFS file for counting connected components or detecting a cycle.
Write a notes file comparing adjacency list and adjacency matrix.
Commit with the message add graph patterns.

0 of 5 done

Example

Repo note example

Add notes like this beside your solution files. Keep them short enough that someone can read them before opening the code.

Problem: First non-repeating character in a string

Choice:
Use a hash map to count characters, then scan the string again.

Why:
We need fast frequency lookup for each character.
A hash map gives average O(1) update and lookup.

Cost:
Time: O(n), because we scan the string twice.
Space: O(k), where k is the number of distinct characters.

Trade-off:
An array of size 26 works for lowercase English letters.
A hash map is safer if input can include uppercase, digits, or symbols.

Edge case:
If no non-repeating character exists, return -1.

Example

Spoken answer template

Practise saying this in 30 to 45 seconds. It works for most college internship interviews.

I need to find pairs that sum to target.
The repeated operation is checking whether target - current exists.
I will use a hash set because lookup is average O(1).
I scan the array once, check the complement, then add the current number.
Time is O(n). Space is O(n) in the worst case.
I am not using two pointers because the array is not sorted.
If sorting were allowed, two pointers would use less extra space but change the cost to O(n log n).

8. Ship the public repo

4 min

Key point

The repo is proof

Your final project is not a folder of random solutions. It is proof that you can choose a data structure, explain the cost, write working code, and test it.

A recruiter or peer should understand your thinking in two minutes without running everything.

Your to-do

Create the structure

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Create a public GitHub repo named dsa-interview-kit or a similar clear name.
Keep one folder per topic: arrays, maps, stacks, queues, linked-lists, trees, heaps, graphs.
Add code files, matching test files, and a short note for each topic.
Use one language if possible, like Python, Java, C++, or JavaScript.
Commit often with messages that say what changed.

0 of 5 done

Example

Simple repo layout

Use names that make review easy. Do not make someone hunt through screenshots or zip files.

dsa-interview-kit/
  README.md
  arrays/
    two_sum.py
    test_two_sum.py
    notes.md
  stacks/
    valid_parentheses.py
    test_valid_parentheses.py
    notes.md
  heaps/
    top_k_frequent.py
    test_top_k_frequent.py
    notes.md
  graphs/
    bfs_shortest_path.py
    test_bfs_shortest_path.py
    notes.md
  run_tests.md

What README must say

Your README is the front door. Keep it short and useful.

Include what the repo covers, how to run tests, and how each note compares choices by time, space, and trade-offs.

Example

README starter

Copy this, then edit it for your language and files.

# DSA Interview Kit

A small interview prep repo with working code, tests, and notes for common data structure choices.

## Topics
- Arrays, strings, maps, sets
- Stacks, queues, linked lists
- Trees and BSTs
- Heaps
- Graphs

## How to run tests
Python:
python -m pytest

JavaScript:
npm test

## What each note explains
- Problem pattern
- Data structure used
- Time complexity
- Space complexity
- Why this choice is better than at least one alternative

Tip

Use AI carefully

You can ask ChatGPT, Gemini, or Claude to review your README and notes. Ask for missing edge cases, unclear cost claims, and weak explanations.

Do not paste AI output blindly. Check every complexity claim, run every test, and remove fake links or invented problem names.

Common mistake

Avoid weak proof

A repo with only solved code is not enough for this track. The skill is choosing the right data structure, not only passing sample input.

Also avoid private repos, broken test commands, huge copied files, and notes that say only 'used map because fast'.

Your to-do

Do this now

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Open GitHub and create a public repo named dsa-interview-kit.
Add a README with topics, test command, and what your notes explain.
Push at least three solved problems with code, tests, and notes.
Run the tests locally and fix failures before submitting.
Submit the public repo link as your HackIndia project.

0 of 5 done

Data Structures

1. Pick by cost first

One rule

Cost means operations

Ask these first

Small cost table

2. Arrays strings maps sets

One idea

When to pick what

Maps and sets

3. Stacks queues linked lists

One idea

When to use stack

When to use queue

4. Trees and BSTs

Core idea

When trees fit

BST costs

7. Explain choices like interviews

Say why, not just what

What interviewers listen for

Use a simple script

Worked choice

Common mistake

Use AI carefully

Do this now

Interview pattern check

Example file

Common mistake

Use AI well

Do this now

Linked list trap

Stack example

Queue example

Write comparison notes

Do this now

Common mistake

BST search code

Test the rule

Interview phrasing

Do this now

5. Heaps for priority

One idea

Where heaps fit

Cost check

Pick the heap

Common mistake

Top K largest

Use AI carefully

Do this now

6. Graphs without fear

One idea

When it is a graph

Pick the pattern

Common mistake

BFS shortest path

Write interview notes

Directed or undirected

Do this now

Repo note example

Compare one rejected choice

Do not overclaim

Spoken answer template

Do this now

8. Ship the public repo

The repo is proof

Create the structure

Simple repo layout

What README must say

README starter

Use AI carefully

Avoid weak proof

Do this now