All the reading

Algorithms

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

Complexity and search basics

1. Big-O without fear

4 min

Why Big-O matters

In placement rounds, the interviewer is not only checking if your code works. They are checking if it still works when the input becomes large.

Big-O is the short way to say how your time or memory grows as input size grows. It helps you choose a better approach before you waste time coding.

Key point

One idea

Big-O ignores exact seconds and focuses on growth. Ask: if n doubles, does my work stay almost same, double, or become much worse?

For interviews and your repo, mention both time complexity and space complexity for each solution.

Common growth rates

Use these as a placement cheat sheet. O(1) is constant work. O(log n) cuts the search area. O(n) scans once. O(n log n) is common in efficient sorting. O(n²) checks pairs. O(2ⁿ) often appears in brute force subsets.

You do not need a proof in most interviews. You need a clear reason linked to loops, recursion, data structures, or sorting.

Example

Loop reading

Read code like a cost meter. Count how many times the main operation runs as n grows.

This example compares one scan with a pair check.

def has_zero(nums):
    for x in nums:
        if x == 0:
            return True
    return False
# Time: O(n), because in the worst case we scan every number.
# Space: O(1), because we use no extra data structure.


def has_pair_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False
# Time: O(n^2), because we check many pairs.
# Space: O(1).

2. Sorting and searching basics

4 min

Key point

Core idea

Sorting changes the shape of a problem. Searching uses that shape to avoid checking every item.

Before coding, ask: can sorted order remove choices, reveal duplicates, or make yes/no decisions monotonic?

When sorting helps

In placement rounds, sorting is often the first move when order does not matter in the final answer. It helps with duplicates, intervals, pairing, closest values, and ranking.

Sorting costs time, usually O(n log n). That is fine if it makes the rest of the solution simple and correct.

Your to-do

Sort-first checklist

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.

Check if the original order is important. If yes, do not sort blindly.
Sort numbers, strings, or pairs using the natural key you need.
Scan once after sorting to find duplicates, gaps, pairs, or merged ranges.
Write the complexity as O(n log n) for sorting plus O(n) for the scan.
Add a small sample run so your repo proves the code works.

0 of 5 done

Windows recursion and choices

3. Two pointers and windows

5 min

Key point

One idea

Two pointers and sliding windows avoid checking every pair or every subarray again and again.

Move only the pointer that can still improve the answer. This is why these patterns are usually linear after sorting, or linear on the original array.

When to use

Use two pointers when the problem has a sorted array, a pair condition, or two ends of a sequence. Common examples: pair sum in a sorted array, remove duplicates, reverse vowels, container with most water.

Use sliding window when the answer is a contiguous part. Common examples: maximum sum of k elements, longest substring without repeating characters, smallest subarray with sum at least target.

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.

Graphs explanation and repo

6. Graph traversal for placements

4 min

Why graphs matter

Placement graph questions often hide inside simple stories: cities and roads, friends, courses, islands, servers, or college clubs.

Your job is usually not to invent a complex algorithm. First build the graph. Then traverse it safely.

Key point

One idea

Graph traversal is controlled exploration. Keep a visited set, then use a queue for BFS or a stack/recursion for DFS.

BFS is best when you need the minimum number of edges in an unweighted graph. DFS is handy for components, cycles, and reachability.

Your to-do

Build the graph

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.

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 local folder named placement-dsa-practice if you have not started your repo yet.
Add a notes file called complexity-notes.txt or README draft.
Write the common Big-O list in your own words.
Pick any old array problem you solved and add time and space complexity comments.
Commit the note with a message like add big-o notes.

0 of 5 done

mkdir placement-dsa-practice
cd placement-dsa-practice
git init
printf "Big-O notes\n" > complexity-notes.txt
git add complexity-notes.txt
git commit -m "add big-o notes"

Example

Example: lower bound

Lower bound finds the first index where arr[index] is greater than or equal to target. It is useful for insert position, counts, and range queries.

Notice the loop keeps the answer inside left. No special case is needed after the loop.

def lower_bound(arr, target):
    left, right = 0, len(arr)

    while left < right:
        mid = (left + right) // 2

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left

nums = [2, 4, 4, 7, 9]
print(lower_bound(nums, 4))   # 1
print(lower_bound(nums, 5))   # 3
print(lower_bound(nums, 10))  # 5

Example

Example solution

Problem: Given a sorted array and a target, return whether any two numbers add to target.

This is a good repo problem because the brute force is easy to explain, and the pointer improvement is clear.

def has_pair_sum(nums, target):
    left = 0
    right = len(nums) - 1

    while left < right:
        current = nums[left] + nums[right]

        if current == target:
            return True
        if current < target:
            left += 1
        else:
            right -= 1

    return False


print(has_pair_sum([1, 2, 4, 6, 9], 10))  # True: 1 + 9 or 4 + 6
print(has_pair_sum([1, 2, 4, 6, 9], 20))  # False

Example

Window example

Problem: Maximum sum of any k consecutive elements. This is a fixed-size sliding window.

First build the first window. Then slide by adding the new item and removing the item that left.

def max_sum_k(nums, k):
    if k <= 0 or k > len(nums):
        return None

    window_sum = sum(nums[:k])
    best = window_sum

    for right in range(k, len(nums)):
        window_sum += nums[right]
        window_sum -= nums[right - k]
        best = max(best, window_sum)

    return best


print(max_sum_k([2, 1, 5, 1, 3, 2], 3))  # 9, from [5, 1, 3]

Tip

Write the explanation

In your README, write why each pointer moves. This is what an interviewer checks when you talk through the solution.

Use AI to draft the explanation if you want. Then check that it states the invariant, the movement rule, and the time complexity correctly.

Problem: Pair sum in sorted array
Pattern: Two pointers
Idea: Keep left at the smallest value and right at the largest value.
Move left when the sum is too small. Move right when the sum is too large.
Why it works: The array is sorted, so these moves are the only ones that can fix the sum.
Time: O(n)
Space: O(1)

4. Recursion and backtracking

4 min

Key point

One idea

Recursion solves a problem by calling the same function on a smaller problem. Backtracking is recursion where you try a choice, explore it, then undo it before trying the next choice.

When to use it

Use recursion when the problem naturally breaks into smaller copies. Common placement examples are subsets, permutations, combination sum, N-Queens, maze paths, and tree traversal.

The shape is usually: stop at a base case, loop over choices, make one choice, recurse, then undo the choice.

Your to-do

Build the template

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.

Define what your recursive function means in one sentence.
Write the base case first, including what you return or save.
List the choices available at the current step.
Make one choice and move to the smaller problem.
Undo the choice if you changed shared state.
Check the time complexity from the recursion tree.

0 of 6 done

Example

Subsets example

This is a clean first backtracking problem. For each number, you either include it or skip it.

Create a file like recursion_backtracking/subsets.py and add this code.

def subsets(nums):
    ans = []
    path = []

    def backtrack(i):
        if i == len(nums):
            ans.append(path.copy())
            return

        # choice 1: include nums[i]
        path.append(nums[i])
        backtrack(i + 1)
        path.pop()  # undo

        # choice 2: skip nums[i]
        backtrack(i + 1)

    backtrack(0)
    return ans

if __name__ == "__main__":
    print(subsets([1, 2, 3]))
    # Expected: 8 subsets, including [] and [1, 2, 3]

Common mistake

Copying too late

A common bug is appending path directly to ans. That stores the same list reference many times, so later pop calls change saved answers too.

Use path.copy() when saving a current answer. Use path.pop() right after the recursive call that used path.append().

Tip

Explain complexity simply

For subsets, each item has two choices: include or skip. That gives 2^n leaves, and each saved subset can take up to n to copy.

So you can write: Time O(n * 2^n), space O(n) recursion depth, excluding output storage. This is enough for a README explanation.

Example

README note

Add a short note near this problem in your repo README. Recruiters should see your thinking, not only code.

### Recursion and backtracking: Subsets

Problem: Generate all subsets of a list of distinct integers.

Approach:
I use backtracking. At each index, I make two choices: include the number or skip it. When I reach the end, I save a copy of the current path.

Base case:
When index == len(nums), save path.copy().

Complexity:
Time: O(n * 2^n), because there are 2^n subsets and copying each subset can take O(n).
Space: O(n) recursion depth, excluding the output list.

Sample run:
Input: [1, 2, 3]
Output count: 8

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 folder named recursion_backtracking in your placement-dsa-practice repo.
Add subsets.py with the working backtracking solution.
Run it once and confirm [1, 2, 3] gives 8 subsets.
Add the README note with approach, base case, and complexity.
Commit with the message: add recursion backtracking subsets.

0 of 5 done

5. Greedy versus dynamic programming

4 min

Key point

Main choice

Greedy makes the best-looking choice now and never goes back. Dynamic programming stores answers to smaller states because the same subproblems come back again.

Use greedy only when you can explain why the local choice is safe. Use DP when you need to try choices and keep the best result.

Greedy signals

Greedy problems often ask for minimum coins, maximum activities, intervals, jumps, or scheduling. But the topic name can trick you in placements.

Ask: after I pick this option, can any better full answer require me to undo it? If yes, greedy is unsafe.

DP signals

DP fits when you see words like count ways, maximum profit, minimum cost, subsequence, partition, or choose or skip. You usually have an index, remaining capacity, previous choice, or amount as state.

A DP solution needs three things: state, transition, and base case. Then add memoization or build a table.

Common mistake

Common trap

Do not choose greedy just because it passes the sample tests. Samples are small and friendly.

For Indian coin values, greedy works for many everyday amounts. But for a custom set like [1, 3, 4], amount 6, greedy picks 4+1+1 as 3 coins. DP finds 3+3 as 2 coins.

Example

DP coin change

This is a good repo problem because it clearly shows why DP is needed. Save it as dp/coin_change.py or similar.

The state is amount x. dp[x] means the minimum coins needed to make x.

def min_coins(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for x in range(1, amount + 1):
        for coin in coins:
            if coin <= x:
                dp[x] = min(dp[x], 1 + dp[x - coin])

    return -1 if dp[amount] == INF else dp[amount]

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

Your to-do

Pick the approach

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.

Write the brute-force choice first in one sentence: choose, skip, take next, or stop.
Check if the best local choice can be proved safe for every input.
Use greedy if one sorted order plus one pass solves it safely.
Use DP if the same state appears again, like index and remaining amount.
Write time and space complexity before you move to the next problem.

0 of 5 done

Tip

Use AI carefully

You can ask ChatGPT, Gemini, or Claude: “Is this problem greedy or DP? Give the state or greedy proof, but do not write code first.”

Check the answer yourself. For greedy, demand a short proof or counterexample. For DP, check that the state contains enough information to make future decisions.

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 two folders in your repo: greedy and dp.
Add one greedy problem, such as activity selection or merge intervals, with a short proof in comments.
Add the coin change DP problem with the two sample runs shown above.
Update your README with approach, time complexity, and space complexity for both.
Run the files and commit with a clear message like add greedy and dp patterns.

0 of 5 done

Example

BFS shortest path

This is the pattern for minimum buses, minimum roads, or minimum friend links when every edge has equal cost.

Save this as graphs/bfs_shortest_path.py in your repo.

from collections import deque

def shortest_path(n, edges, start, target):
    graph = [[] for _ in range(n)]

    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)  # remove this line for a directed graph

    dist = [-1] * n
    dist[start] = 0
    q = deque([start])

    while q:
        node = q.popleft()
        if node == target:
            return dist[node]

        for nei in graph[node]:
            if dist[nei] == -1:
                dist[nei] = dist[node] + 1
                q.append(nei)

    return -1

if __name__ == "__main__":
    n = 6
    edges = [(0, 1), (0, 2), (1, 3), (2, 4), (4, 5)]
    print(shortest_path(n, edges, 0, 5))  # 3

Example

README note

For every graph solution, write what the nodes and edges mean. A recruiter should not guess your model.

Add a small complexity note beside the code file.

### Graph traversal: shortest path in unweighted graph

File: graphs/bfs_shortest_path.py

Approach:
- Build an adjacency list from the edge list.
- Run BFS from the start node.
- Store distance in edges from the start.
- Return -1 if the target is not reachable.

Complexity:
- Time: O(V + E), because each node and edge is processed at most once.
- Space: O(V + E), for the graph, queue, and distance array.

7. Talk through your solution

5 min

Key point

One thing to remember

A good solution is not only accepted by the judge. You must be able to explain why it works, what it costs, and where it can fail.

Why this matters

In a placement interview, the interviewer is checking your thinking process. They may care more about your reasoning than the final code.

Your repo should show the same skill. Each solved problem needs a short explanation that sounds like you can talk through it on a call.

Your to-do

Use this 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.

Restate the problem in one line using your own words.
Name the pattern you are using, such as two pointers, BFS, DP, or greedy.
Explain the core idea before talking about code.
Give the time and space complexity.
Mention one or two edge cases you handled.

0 of 5 done

Example

Explanation template

Create a small explanation beside each solution, or add it inside your README under that problem. Keep it short. Recruiters will scan it.

Problem: Two Sum

Goal:
Find two indices whose values add up to the target.

Pattern:
Hash map lookup.

Approach:
Scan the array once. For each number x, check if target - x was seen before.
If yes, return both indices. If no, store x with its index.

Why it works:
For every element, the only possible partner is target - x.
The map tells us if that partner appeared earlier.
So the first valid pair found is correct.

Complexity:
Time: O(n), because each element is visited once.
Space: O(n), because the map can store up to n elements.

Edge cases:
- Negative numbers
- Duplicate values
- No valid pair, if the platform allows that case

Tip

Practise out loud

Before you commit a problem, explain it in 60 to 90 seconds without reading the code. If you get stuck, your explanation file is not clear enough yet.

You can ask ChatGPT or Gemini: “Act as an interviewer. Ask me follow-up questions on this solution.” Check that the AI does not change your algorithm or invent constraints.

Common mistake

Common weak explanation

Do not say only, “I used DP” or “I used BFS.” That names the tool, not the reasoning.

Also avoid fake certainty. If there is an edge case you have not tested, test it before writing that it works.

Example

Speak it simply

Here is a short spoken version for a graph traversal problem. Notice the order: goal, method, safety check, cost.

I need to find whether all rooms can be visited.
I model rooms as nodes and keys as directed edges.
I start from room 0 and run DFS.
Whenever I enter a room, I mark it visited so I do not loop forever.
At the end, if the number of visited rooms equals n, the answer is true.
The time is O(V + E), because I visit rooms and keys once.
The space is O(V), for the visited set and recursion stack.

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.

Pick one solved problem from your repo.
Add a short explanation using the template above.
Say the explanation out loud once without looking at the code.
Add two edge cases to your sample run or test file.
Commit the solution and explanation with a clear message.

0 of 5 done

git add .
git commit -m "Add explanation and edge cases for two sum"

8. Ship your DSA proof repo

5 min

Key point

Proof beats claims

A recruiter cannot inspect your confidence. They can inspect a repo that runs, has clear solutions, and explains trade-offs.

Your repo is not a dump of code files. It is evidence that you can solve, communicate, and keep work organised.

What to ship

Name the repo something clear, like placement-dsa-practice. Keep it public unless your college has a rule against public code for a specific assignment.

Cover each pattern from this track: sorting/searching, two pointers/windows, recursion/backtracking, greedy/DP, and graph traversal. Add one short explanation per problem.

Your to-do

Set up 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 GitHub repository named placement-dsa-practice.
Group problems by pattern, not by random date.
Add a README at the root with your goal, folder map, run commands, and progress table.
Add tests if your language setup is ready; otherwise add sample input-output runs.
Commit after each solved problem with a clear message.

0 of 5 done

Example

Simple repo map

Use boring names. They help someone find your work in 30 seconds.

placement-dsa-practice/
  README.md
  sorting-searching/
    binary_search.py
    binary_search_test.py
  two-pointers-windows/
    longest_substring.py
    sample_runs.md
  recursion-backtracking/
    subsets.py
  greedy-dp/
    coin_change.py
  graphs/
    bfs_shortest_path.py
  notes/
    patterns.md

Example

README starter

Your README should answer three questions fast: what did you solve, how do I run it, and why does the approach work.

# placement-dsa-practice

DSA practice repo for internship and placement rounds.
Each solution includes the pattern used, approach, complexity, and a test or sample run.

## Patterns covered

| Pattern | Problem | File | Time | Space | Status |
|---|---|---|---|---|---|
| Sorting/Search | Binary Search | sorting-searching/binary_search.py | O(log n) | O(1) | Done |
| Two Pointers | Longest unique substring | two-pointers-windows/longest_substring.py | O(n) | O(k) | Done |
| Graphs | BFS shortest path | graphs/bfs_shortest_path.py | O(V + E) | O(V) | Done |

## How to run

python sorting-searching/binary_search.py
python -m pytest

## My solution format

1. State the pattern.
2. Explain the idea in 4 to 6 lines.
3. Add time and space complexity.
4. Add tests or sample runs.

Tip

Use AI carefully

You can ask ChatGPT, Gemini, or Claude to review your README and explanations. Ask for missing edge cases, unclear complexity, and better folder names.

Do not paste AI output blindly. Check every complexity claim, run every command, and remove phrases that sound generic.

Prompt:
Review this DSA repo README for an internship recruiter.
Find unclear explanations, missing run steps, and wrong complexity claims.
Do not rewrite everything. Give a checklist.

Common mistake

Avoid repo smells

Do not upload only screenshots, zipped code, or files named final_final.py. Do not leave broken imports or empty README sections.

A small repo with 8 working, explained problems is stronger than 40 copied files that nobody can run.

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 the public GitHub repo with the exact name placement-dsa-practice or a close clear name.
Add folders for the five track patterns and move your solved files into them.
Write the root README using the starter table and run commands.
Run at least one test or sample run per pattern and save the result.
Push your final commit and submit the repo link on HackIndia.

0 of 5 done

Algorithms

1. Big-O without fear

Why Big-O matters

One idea

Common growth rates

Loop reading

2. Sorting and searching basics

Core idea

When sorting helps

Sort-first checklist

3. Two pointers and windows

One idea

When to use

Pick the pattern

6. Graph traversal for placements

Why graphs matter

One idea

Build the graph

How to estimate

Do not average casually

Use AI carefully

Do this now

Common mistake

When search helps

Example: lower bound

Use AI carefully

Do this now

Common mistake

Example solution

Window example

Write the explanation

Do this now

4. Recursion and backtracking

One idea

When to use it

Build the template

Subsets example

Copying too late

Explain complexity simply

README note

Do this now

5. Greedy versus dynamic programming

Main choice

Greedy signals

DP signals

Common trap

DP coin change

Pick the approach

Use AI carefully

Do this now

BFS shortest path

Use AI carefully

Common bug

README note

Do this now

7. Talk through your solution

One thing to remember

Why this matters

Use this structure

Explanation template

Practise out loud

Common weak explanation

Speak it simply

Do this now

8. Ship your DSA proof repo

Proof beats claims

What to ship

Set up structure

Simple repo map

README starter

Use AI carefully

Avoid repo smells

Do this now