What DSA is

The idea in real life

Why it exists

1. Real programs work with a lot of data: millions of orders, messages or search results.
2. The same task can take milliseconds or hours, depending only on how the data is stored and how your code works through it.
3. Small test inputs hide slow code. Real inputs expose it as frozen screens, timeouts and large server bills.
4. Data structures and algorithms are the shared toolkit programmers use to store data well and process it fast.

How it works

What a data structure is

How you arrange data decides which actions are cheap and which are expensive.

A data structure is a way of arranging data in memory so that some actions on it are fast. The structure you pick decides which actions are fast and which are slow.

Take a plain array. It keeps items side by side in one block of memory, and each slot has a number called an index, starting at 0. The computer knows where the array starts and how big each item is, so getting item 5 (numbers[5]) is instant: it works out the address with one calculation and reads the value.

But putting a new item at the front (numbers[0]) means moving every existing item one slot to the right to make room. With one million items, that one insert costs one million moves. Every data structure is a trade: fast at some actions, slow at others. Later chapters show structures that make different trades, such as linked lists (chapter 20), hash tables (chapter 17) and balanced trees (chapter 26).

What an algorithm is

An exact recipe that always stops and always gives the right answer.

An algorithm is a list of exact steps that solves a problem. To count as an algorithm, it must work for every valid input, leave no step open to guessing, stop after a finite number of steps, and give the correct answer every time.

Suppose you want to find whether a target number exists inside an array. The simplest approach is linear search: you start at index 0 and inspect every item one by one until you find the target or reach the end. This algorithm works on any array, even if the elements are completely scrambled, but in the worst case it must check every single item.

If the array is already sorted, you can use binary search instead. You check the middle element first. If the middle element is your target, you stop. If your target is smaller than the middle element, you know the target cannot possibly live in the right half of the array, so you discard the entire right half. If your target is larger, you discard the left half. Each check cuts the remaining part in half, so binary search needs far fewer checks than linear search.

Counting steps, not seconds

Machines differ, but the number of steps an algorithm takes does not.

Timing two algorithms with a stopwatch, for example with System.currentTimeMillis(), misleads you. A new laptop is faster than an old phone, a busy machine is slower than an idle one, and the Java Virtual Machine (JVM) speeds code up while it runs. A stopwatch measures the machine, not the algorithm.

So we compare algorithms by counting basic steps (comparisons, assignments, array reads) and asking how that count grows as the input size n grows.

Suppose you have a sorted array of 1,000,000 items (n = 1_000_000). If you search for the very last item using linear search, your program must perform 1,000,000 checks. If you search for that same item using binary search, each check halves the remaining items: from 1,000,000 to 500,000, then 250,000, and so on. Binary search reaches the last item in at most 20 checks. Chapter 06 makes this precise with Big-O notation: linear search is O(n), binary search is O(log n).

The following program creates a sorted array of 1,000,000 integers and counts the exact number of checks each search makes to find the last item. In this program:

• n is the total number of elements in the array (1,000,000).
• numbers is the array containing numbers from 0 to n - 1.
• target is the value to find, set to n - 1 (999,999) to force the worst-case scenario.
• linearChecks accumulates the number of element comparisons made during linear search.
• binaryChecks accumulates the number of midpoint checks made during binary search.
• left and right mark the lower and upper bounds of the current search window.
• mid is the middle index, computed as left + (right - left) / 2 to prevent integer overflow.

public class Main {
    public static void main(String[] args) {
        int n = 1_000_000;
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = i;
        }

        int target = n - 1;

        // Linear search: inspect each item from the start
        int linearChecks = 0;
        for (int i = 0; i < n; i++) {
            linearChecks++;
            if (numbers[i] == target) {
                break;
            }
        }

        // Binary search: halve the remaining range each step
        int binaryChecks = 0;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            binaryChecks++;
            int mid = left + (right - left) / 2;
            if (numbers[mid] == target) {
                break;
            } else if (numbers[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println("Items in array: " + n);
        System.out.println("Linear search checks: " + linearChecks);
        System.out.println("Binary search checks: " + binaryChecks);
    }
}

Items in array: 1000000
Linear search checks: 1000000
Binary search checks: 20

The map of this course

Nine parts, from your first Java program to clearing the interview.

The course has nine parts. Each part builds on the ones before it.

Going deeper

What a DSA interview round looks like

A conversation that turns a loosely stated problem into working, tested code.

Rounds differ from company to company, but most follow the same four phases:

1. The problem: the interviewer describes a problem. It is often stated briefly or loosely on purpose, to see whether you ask before you assume.
2. Questions and approach: you ask about edge cases, input sizes and data types. Then you talk through solutions out loud, starting with a simple brute-force idea and improving it, before writing any code.
3. Code: once you agree on an approach, you write clean, correct code, usually in a shared online editor with little or no autocomplete.
4. Test and analyse: you walk through your code with an example, check edge cases such as an empty input or a single item, and state the time and space cost.

What the interviewer is scoring

A correct answer is only part of the score.

Many people think a round is pass or fail on the final answer. In practice, interviewers look at five things:

1. Problem comprehension: Did you listen carefully, clarify ambiguous requirements, identify hidden edge conditions, and verify your understanding with sample inputs?
2. Algorithmic reasoning: Did you explain trade-offs between different approaches, select appropriate data structures, and justify why your chosen algorithm is optimal?
3. Code quality and fluency: Is your code well-structured, easy to read, idiomatic, and logically sound, with meaningful variable names and zero syntax confusion?
4. Testing and verification: Did you proactively test your implementation against corner cases, spot your own bugs, and fix them systematically without needing the interviewer to point them out?
5. Communication and collaboration: Did you think out loud throughout the session, explain your reasoning clearly, and incorporate feedback constructively like a collaborative teammate?

Patterns beat memorising

A memorised answer breaks when the problem changes; a pattern does not.

LeetCode and GeeksforGeeks have thousands of problems, far too many to memorise. And a memorised answer stops working the moment the interviewer changes a limit, adds negative numbers or asks you to do it in place.

The good news: most interview problems are built on a few dozen patterns. For example:

• Processing pairs from opposite ends of a sorted array uses Two Pointers (chapter 13).
• Finding the longest or shortest contiguous subarray satisfying a condition uses Sliding Window (chapter 14).
• Finding the shortest path in an unweighted grid uses Breadth-First Search (chapter 30).
• Solving problems with overlapping subproblems and optimal substructure uses Dynamic Programming (chapters 37 to 43).

Once you know a pattern well, you learn the signs in a problem that point to it. Then you can solve problems you have never seen, instead of hoping you have seen this exact one before.

Reading the constraints

The input limits tell you how fast your solution must be.

Every problem states its constraints: how big the input can be and what values it can hold. They are not background details. They tell you how fast your solution has to be.

A common rule of thumb is that a judge runs roughly 10^7 to 10^8 simple steps per second. If a problem states that an array has at most 20 elements (n <= 20), an exponential O(2^n) backtracking algorithm will easily finish within time. If n <= 1_000, an O(n^2) nested loop approach is viable. However, if n = 100_000 (n = 10^5), an O(n^2) algorithm needs about 10^10 steps, far too many, and it fails with Time Limit Exceeded. In that scenario, the constraints tell you immediately that your solution must run in O(n) or O(n log n) time. Chapter 06 provides a complete guide to reading constraints.

Under the hood

Why companies use DSA rounds

One shared test lets companies compare very different candidates.

Companies hire from people with very different degrees, colleges and jobs behind them. A DSA round gives them the same test for everyone, built on fundamentals every programmer should know.

It is used as a signal for skills that real engineering work needs:

1. Abstract problem solving: How systematically you break down a complex, unfamiliar problem into manageable logical pieces.
2. Working under ambiguity: How calmly you ask questions, navigate incomplete information, and make sound engineering decisions under time constraints.
3. Execution correctness: Whether you can translate conceptual ideas into clean, functioning code without relying on an IDE, compiler warnings, or automated assistance.

The round has limits. Solving one problem against the clock says little about designing large systems, writing maintainable code or working in a team. That is why companies add system design and behavioural rounds, especially for experienced roles.

How expectations change with experience

Freshers are judged on reaching a correct solution; seniors also on judgement.

What counts as a strong round changes with experience:

• Freshers and junior engineers are judged mostly on reaching a correct, efficient solution, choosing sensible data structures and stating its cost.
• Experienced engineers are expected to get there faster and to lead the conversation: raise edge cases and trade-offs themselves, compare alternatives, and explain why their choice fits, without being prompted.

Why Java for this course

Accepted everywhere, with the structures you need already built in.

Java is one of the most common interview languages and is accepted by almost every company and coding platform.

It has three advantages for interview preparation:

1. A rich standard library: the Collections Framework (chapter 04) already has growable arrays (ArrayList), hash tables (HashMap), double-ended queues (ArrayDeque), heaps (PriorityQueue) and balanced trees (TreeMap).
2. Strict types: the compiler catches many mistakes before the code runs, and it makes you think clearly about what each variable holds.
3. Useful at work too: Java is widely used for backend services, so what you learn here about memory, objects and performance carries over to real jobs.

Java also has its own traps, such as integer overflow, comparing objects with == instead of equals(), and the hidden cost of autoboxing. The Java chapters teach them, and later chapters point them out wherever they bite.

In Java

This program solves the same task both ways on a sorted array and reports, for each search, where it found the target and how many checks it made.

In this program:

• SearchResult is a helper class that bundles index (the position of the target, or -1 if absent) and steps (the number of comparisons made).
• linearSearch(nums, target) inspects nums one item at a time from start to finish.
• binarySearch(nums, target) halves the active search interval in nums at each step.
• numbers is the input array containing 9 sorted integers {11, 22, 33, 44, 55, 66, 77, 88, 99}.
• target is the number 77 to search for.
• linear holds the result returned by linearSearch.
• binary holds the result returned by binarySearch.

public class Main {
    static class SearchResult {
        int index;
        int steps;

        SearchResult(int index, int steps) {
            this.index = index;
            this.steps = steps;
        }
    }

    // Searches nums sequentially and returns the found index and steps taken.
    static SearchResult linearSearch(int[] nums, int target) {
        int steps = 0;
        for (int i = 0; i < nums.length; i++) {
            steps++;
            if (nums[i] == target) {
                return new SearchResult(i, steps);
            }
        }
        return new SearchResult(-1, steps);
    }

    // Searches sorted nums by halving the range and returns the found index and steps taken.
    static SearchResult binarySearch(int[] nums, int target) {
        int steps = 0;
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            steps++;
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return new SearchResult(mid, steps);
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return new SearchResult(-1, steps);
    }

    public static void main(String[] args) {
        int[] numbers = {11, 22, 33, 44, 55, 66, 77, 88, 99};
        int target = 77;

        SearchResult linear = linearSearch(numbers, target);
        SearchResult binary = binarySearch(numbers, target);

        System.out.println("Linear search: index " + linear.index + ", steps " + linear.steps);
        System.out.println("Binary search: index " + binary.index + ", steps " + binary.steps);
    }
}

Linear search: index 6, steps 7
Binary search: index 6, steps 2

The cost of each operation

n is the number of items in the array.

Traps

1. Memorising solutions instead of mastering patterns

   If you memorize specific problem code, your approach falls apart when the interviewer tweaks a minor constraint or dresses the question in a new scenario. Learn the underlying pattern and trigger conditions so you can solve novel variations.

2. Jumping straight into code before clarifying the problem

   Writing code before confirming assumptions wastes valuable interview time on the wrong problem. Always ask clarifying questions about edge cases, null inputs, and size limits before writing a single line.

3. Ignoring the input constraints

   Skipping the problem constraints means guessing the required performance blind. The value of n tells you whether an O(n^2) approach is acceptable or if you must design an O(n) or O(n log n) solution.

4. Skipping Java fundamentals and language-specific traps

   Strong algorithmic intuition cannot save an interview if basic syntax fails or if you fall into classic Java pitfalls, such as integer overflow in calculations or using == to compare object references.

5. Staying silent while thinking

   An interview is a collaborative technical dialogue, not a silent written exam. If you go quiet for minutes, the interviewer cannot evaluate your thought process or give hints when you stray off course.

6. Testing only the happy path

   Passing one simple example does not mean the code works. Always trace edge cases: an empty input, a single item, duplicates and very large or negative values.

7. Leaving complexity analysis as an afterthought

   If the interviewer has to ask you for the cost, you lose points. State the time and extra space as soon as you propose an approach, and again when the code is done.