Coding Problems & Solutions¶

Common coding interview problems with solutions and explanations.

1. Print 1..N without a loop (Recursion)¶

View Solution

Problem

Print numbers from 1 to N using recursion instead of loops.

Approach 1: Recursive (Post-order)

static void printNos(int n) {
    if (n > 0) {
        printNos(n - 1);
        System.out.print(n + " ");
    }
}
// printNos(5);  → Output: 1 2 3 4 5

How it works: Recurse first, then print. This gives ascending order.

Approach 2: Recursive (Pre-order)

static void printNosPreOrder(int n) {
    if (n > 0) {
        System.out.print(n + " ");
        printNosPreOrder(n - 1);
    }
}
// printNosPreOrder(5);  → Output: 5 4 3 2 1

How it works: Print first, then recurse. This gives descending order.

Approach 3: Stream API

static void printNosStream(int n) {
    IntStream.rangeClosed(1, n).forEach(i -> System.out.print(i + " "));
}
// printNosStream(5);  → Output: 1 2 3 4 5

How it works: Functional approach using streams (no explicit recursion).

Complexity (All Approaches)

O(n) time, O(n) space (call stack for recursion)

Key Insight: Recursion Benefits

Natural for problems like palindromes, tree traversal
Can replace loops for linear processing
Trade-off: Space (call stack) for readability

📚 Learn more: Recursion & Algorithms

2. Check if a string is a palindrome¶

View Solution

Problem

Check if a string is a palindrome using recursion or functional approach.

Recursion Approach

public boolean isPalindromeRecursive(String text) {
    String clean = text.replaceAll("\\s+", "").toLowerCase();
    return recursivePalindrome(clean, 0, clean.length() - 1);
}

private boolean recursivePalindrome(String s, int fwd, int bwd) {
    if (fwd >= bwd) return true;  // Base case: reached middle
    if (s.charAt(fwd) != s.charAt(bwd)) return false;  // Mismatch
    return recursivePalindrome(s, fwd + 1, bwd - 1);  // Recurse
}

Approach

Clean: Remove spaces, convert to lowercase
Two pointers: fwd from start, bwd from end
Base case: fwd >= bwd (checked all pairs)
Mismatch: Return false if characters differ
Recurse: Move pointers inward

Complexity

O(n) time, O(n) space (call stack for recursion)

Stream API Approach

public boolean isPalindrome(String text) {
    String t = text.replaceAll("\\s+", "").toLowerCase();
    return IntStream.range(0, t.length() / 2)
        .noneMatch(i -> t.charAt(i) != t.charAt(t.length() - i - 1));
}

Approach

Range: Loop from 0 to length/2
noneMatch: Return true if NO index has mismatching characters
Concise functional style, no explicit recursion

Approach 3: Two-Pointer Iterative

public boolean isPalindromeIterative(String text) {
    String t = text.replaceAll("\\s+", "").toLowerCase();
    int left = 0, right = t.length() - 1;

    while (left < right) {
        if (t.charAt(left) != t.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}

How it works: Two pointers move inward, no recursion or streams.

Approach 4: StringBuilder Reverse

public boolean isPalindromeReverse(String text) {
    String clean = text.replaceAll("\\s+", "").toLowerCase();
    String reversed = new StringBuilder(clean).reverse().toString();
    return clean.equals(reversed);
}

How it works: Reverse the string and compare. Simple but uses extra space.

Complexity Comparison

Recursive: O(n) time, O(n) space (call stack)
Stream: O(n) time, O(1) space
Two-pointer: O(n) time, O(1) space
StringBuilder: O(n) time, O(n) space (new string)

Key Insight: Functional Approaches

Streams, lambdas reduce loops and improve readability
More declarative (what, not how)
Can be harder to debug but often more concise

📚 Learn more: Strings

3. Find maximum sum of a contiguous subarray (Kadane's Algorithm)¶

View Solution

Problem

Find maximum sum of a contiguous subarray.

Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (subarray: [4, -1, 2, 1])

Approach 1: Kadane's Algorithm (Optimal)

public static int maxSubArray(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    int curr = 0;

    for (int n : nums) {
        curr += n;                           // Include current element
        maxSum = Math.max(maxSum, curr);    // Track max so far
        if (curr < 0) curr = 0;            // Reset if cumulative sum negative
    }

    return maxSum;
}

Why it works: If cumulative sum becomes negative, start fresh. Dynamic programming: optimal substructure.

Approach 2: Brute Force (All Subarrays)

public static int maxSubArrayBruteForce(int[] nums) {
    int maxSum = Integer.MIN_VALUE;

    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            maxSum = Math.max(maxSum, sum);
        }
    }

    return maxSum;
}

How it works: Try all possible subarrays and track maximum. Simple but inefficient.

Approach 3: Divide and Conquer

public static int maxSubArrayDC(int[] nums, int left, int right) {
    if (left == right) return nums[left];

    int mid = left + (right - left) / 2;
    int leftMax = maxSubArrayDC(nums, left, mid);
    int rightMax = maxSubArrayDC(nums, mid + 1, right);
    int crossMax = maxCrossingSum(nums, left, mid, right);

    return Math.max(crossMax, Math.max(leftMax, rightMax));
}

private static int maxCrossingSum(int[] nums, int left, int mid, int right) {
    int leftSum = Integer.MIN_VALUE, sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }

    int rightSum = Integer.MIN_VALUE;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }

    return leftSum + rightSum;
}

How it works: Divide array in half, find max in left, right, and crossing subarrays.

Complexity Comparison

Kadane's: O(n) time, O(1) space ⭐ Best
Brute Force: O(n²) time, O(1) space
Divide & Conquer: O(n log n) time, O(log n) space (recursion stack)

Key Insight: Algorithm Efficiency

Kadane's algorithm: O(n) instead of brute force O(n²)
Key optimization: Can we reduce passes? Can we use state efficiently?
Dynamic programming: Optimal substructure - best solution built from smaller subproblems

📚 Learn more: Dynamic Programming

4. Remove duplicates from a list¶

View Solution

Problem

How would you remove duplicates from a list while maintaining order?

Approach 1: Stream + HashSet Filter

List<Integer> list = Arrays.asList(1, 2, 2, 3, 3, 3);
Set<Integer> seen = new HashSet<>();
List<Integer> result = list.stream().filter(seen::add).collect(Collectors.toList());
// Result: [1, 2, 3]

Key insight: seen.add() returns false if element already exists, so filter() keeps only new elements.

Approach 2: LinkedHashSet (Maintains Order)

List<Integer> list = Arrays.asList(1, 2, 2, 3, 3, 3);
List<Integer> result = new ArrayList<>(new LinkedHashSet<>(list));
// Result: [1, 2, 3]

How it works: LinkedHashSet maintains insertion order while removing duplicates. Simplest approach.

Approach 3: Stream + toSet (No Order Guarantee)

List<Integer> list = Arrays.asList(1, 2, 2, 3, 3, 3);
Set<Integer> result = list.stream().collect(Collectors.toSet());
// Result: {1, 2, 3} - order not guaranteed

How it works: Use Collectors.toSet() if order doesn't matter (faster).

Approach 4: Manual Iteration with Set

List<Integer> list = Arrays.asList(1, 2, 2, 3, 3, 3);
Set<Integer> seen = new HashSet<>();
List<Integer> result = new ArrayList<>();

for (Integer num : list) {
    if (seen.add(num)) {
        result.add(num);
    }
}
// Result: [1, 2, 3]

How it works: Explicit loop, no streams. More verbose but easier to debug.

Complexity (All Approaches)

Time: O(n) for all approaches
Space: O(n) for all approaches (storing unique elements)

When to Use

LinkedHashSet: Simplest, maintains insertion order ⭐ Recommended
Stream + filter: Functional style, maintains order
Manual iteration: Most explicit, easiest to debug
Collectors.toSet(): Only if order doesn't matter

📚 Learn more: Collections Framework

5. Find duplicate number from a linked list¶

View Solution

Problem

Detect if a linked list contains a duplicate value.

Approach

Use Floyd's cycle detection (tortoise & hare) if duplicate implies cycle, or use HashSet to track visited values. Time: O(n), Space: O(1) for cycle detection or O(n) for HashSet

HashSet Approach

Set<Integer> seen = new HashSet<>();
while (head != null) {
    if (!seen.add(head.val)) return head.val;
    head = head.next;
}

Two-pointer Approach (Cycle Detection)

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;  // Cycle detected
}
return false;

📚 Learn more: Data Structures

6. Trace the output of a given Java program¶

View Solution

Problem

Predict the output of a given Java code snippet.

Approach

Trace execution step-by-step:

Variable initialization and scope
Method calls and return values
Control flow (loops, conditionals)
Side effects (mutations, I/O)
Type coercion and operator precedence

Example

int x = 5;
int y = ++x + x++ + x;  // ?
System.out.println(x + " " + y);

Trace

++x: x becomes 6 (pre-increment), used value is 6
x++: x becomes 7 (post-increment), used value is 6
x: x is 7
y = 6 + 6 + 7 = 19
Output: 7 19

Tips

Pay attention to ++/-- (pre vs post-increment)
Watch for operator precedence
Test with actual compilation if unsure

📚 Learn more: Java Basics

Backlog¶

See DSA Backlog for additional problems: - Sort students by mark + rank assignment - List ↔ Array ↔ Stream conversions - Integer ↔ String conversions - Bitwise operations & tricks