Classic Number & String Programs — Interview Questions

How to use this lesson

In a fresher coding round, a working solution is only half the score. The other half is explaining the complexity and handling edge cases (empty input, negatives, overflow). Each question below gives an interview-ready solution, then the points that earn extra credit.

Q1. Reverse a string without using built-in reverse functions.

Short answer: Use two pointers, one at each end, swapping characters as they move towards the middle. O(n) time, O(n) extra space for the character array (strings are immutable, so a copy is unavoidable).

static String reverse(String input) {
    if (input == null) return null;
    char[] chars = input.toCharArray();
    for (int left = 0, right = chars.length - 1; left < right; left++, right--) {
        char tmp = chars[left];
        chars[left] = chars[right];
        chars[right] = tmp;
    }
    return new String(chars);
}

Key points to cover:

• In production code, write new StringBuilder(s).reverse().toString(). It's also correct for surrogate pairs (emoji, some scripts), which the simple char swap would break apart.
• A recursive version (reverse(s.substring(1)) + s.charAt(0)) is O(n²) and can overflow the stack. Mention it only as the thing not to do.

Learn it in depth → Two Pointers

Q2. Swap two numbers without a third variable.

Short answer: Use arithmetic (a = a + b; b = a - b; a = a - b;) or XOR (a ^= b; b ^= a; a ^= b;).

int a = 7, b = 3;
a = a + b;   // 10
b = a - b;   // 7
a = a - b;   // 3

a ^= b; b ^= a; a ^= b;     // the XOR version: no overflow concerns at all

Key points to cover:

• The arithmetic version works even if a + b overflows, because int arithmetic wraps around consistently in two's complement. But it's confusing to reason about, so XOR is the cleaner trick.
• The XOR trick fails if both "variables" are the same memory location (for example arr[i] and arr[j] with i == j), because it zeroes the value.
• Java passes arguments by value. A swap(int a, int b) method can't swap the caller's variables. Do the swap inline, or swap elements inside an array.
• In real code, just use a temporary variable. It's clearer, and the JIT makes it just as fast.

Q3. Check whether a number is prime, efficiently.

Short answer: Handle the small cases, rule out multiples of 2 and 3, then test only candidates of the form 6k ± 1 up to √n. That's O(√n) time.

static boolean isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; (long) i * i <= n; i += 6) {        // long avoids overflow of i*i near Integer.MAX_VALUE
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

Key points to cover:

• Why √n? If n = a × b with a ≤ b, then a ≤ √n, so any factor pair has a member at most √n.
• Why 6k ± 1? Every integer is 6k + r with r in 0..5. Those with r = 0, 2, 3, 4 are divisible by 2 or 3, so only 6k ± 1 can be prime.
• To find all primes up to N, use the Sieve of Eratosthenes, which is O(N log log N).

Common trap: writing i * i <= n with int i. For n close to Integer.MAX_VALUE, i * i overflows to a negative number, and the loop misbehaves. Use long, or write i <= n / i.

Q4. Check whether a string or a number is a palindrome.

Short answer: For strings, compare characters from both ends moving inwards: O(n) time, O(1) space. For numbers, reverse half the digits and compare, with no string conversion.

static boolean isPalindrome(String s) {
    for (int l = 0, r = s.length() - 1; l < r; l++, r--) {
        if (s.charAt(l) != s.charAt(r)) return false;
    }
    return true;
}

static boolean isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;   // negatives, and numbers ending in 0 (except 0 itself)
    int reversedHalf = 0;
    while (x > reversedHalf) {
        reversedHalf = reversedHalf * 10 + x % 10;
        x /= 10;
    }
    return x == reversedHalf || x == reversedHalf / 10;   // even and odd digit counts
}

Key points to cover:

• Interviewers often extend the string version with "ignore case and non-alphanumeric characters" ("A man, a plan…"). Skip characters where Character.isLetterOrDigit is false, and compare with Character.toLowerCase.
• Reversing only half the number avoids overflow when the reversed number would exceed int.

Learn it in depth → Valid Palindrome

Q5. Print the Fibonacci series using recursion.

Short answer: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1. The plain recursive version is O(2ⁿ), because it recomputes the same values again and again. Memoise it (O(n)), or compute it iteratively (O(n) time, O(1) space).

static long fibRecursive(int n) {                  // what was asked, but exponential
    return n <= 1 ? n : fibRecursive(n - 1) + fibRecursive(n - 2);
}

static long fibMemo(int n, long[] memo) {          // top-down DP: O(n)
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

static void printSeries(int count) {               // iterative: O(n) time, O(1) space
    long a = 0, b = 1;
    for (int i = 0; i < count; i++) {
        System.out.print(a + " ");
        long next = a + b; a = b; b = next;
    }
}

Key points to cover:

• fib(92) is the largest value that fits in a long. Beyond that, use BigInteger.
• This is the classic introduction to dynamic programming: overlapping subproblems solved once.

Learn it in depth → Dynamic Programming Introduction

Q6. Check whether a number is an Armstrong number.

Short answer: An Armstrong (narcissistic) number equals the sum of its digits, each raised to the power of the number of digits. For example, 153 = 1³ + 5³ + 3³, and 9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴.

static boolean isArmstrong(int n) {
    if (n < 0) return false;
    int digits = String.valueOf(n).length();
    long sum = 0;
    for (int x = n; x > 0; x /= 10) {
        sum += intPow(x % 10, digits);
    }
    return sum == n;
}
static long intPow(int base, int exp) {
    long result = 1;
    for (int i = 0; i < exp; i++) result *= base;
    return result;
}

Common trap: using Math.pow, which returns a double. Adding up doubles and comparing the total with an int works for small numbers, but it invites rounding surprises. Integer exponentiation is exact.

Q7. Repeatedly add the digits of a number until one digit remains.

Short answer: Loop: sum the digits, and repeat while the sum is 10 or more. Or use the O(1) digital root formula: n == 0 ? 0 : 1 + (n - 1) % 9.

static int addDigits(int num) {
    while (num >= 10) {
        int sum = 0;
        for (int x = num; x > 0; x /= 10) sum += x % 10;
        num = sum;
    }
    return num;
}
static int addDigitsO1(int num) { return num == 0 ? 0 : 1 + (num - 1) % 9; }   // 38 → 2

Key points to cover:

• Why the formula works: a number and the sum of its digits leave the same remainder modulo 9, because 10 ≡ 1 (mod 9).

Q8. Check whether an integer is a power of two.

Short answer: A power of two has exactly one bit set. n & (n - 1) clears the lowest set bit, so the result is 0 only for powers of two. Check n > 0 first.

static boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;        // 8 = 1000, 7 = 0111 → 1000 & 0111 = 0
}
// Alternative: Integer.bitCount(n) == 1 (for n > 0)

Key points to cover:

• Without the n > 0 check, 0 and Integer.MIN_VALUE (binary 1000…0) would wrongly pass.

Learn it in depth → Number of 1 Bits

Follow-up questions this topic invites — and their answers

Q: How would you count the vowels in a string? A: Loop over the characters and test each one against "aeiouAEIOU".indexOf(c) >= 0, or use a boolean[128] lookup table. Stream version: s.chars().filter(c -> "aeiouAEIOU".indexOf(c) >= 0).count().

Q: How do you compute a factorial, and what are the limits? A: Iteratively multiply 1..n. 20! is the largest factorial that fits in a long, so use BigInteger beyond that. Recursion works too, but deep recursion risks a StackOverflowError.

Q: How do you reverse the words in a sentence? A: Split on whitespace into a list, reverse it, and join:

List<String> words = new ArrayList<>(Arrays.asList(s.trim().split("\\s+")));
Collections.reverse(words);          // or words.reversed() on Java 21+
String result = String.join(" ", words);

Or walk the string backwards, appending words to a StringBuilder.

Q: What's the time complexity of checking all numbers up to N for primality one by one? A: O(N√N) with trial division. The Sieve of Eratosthenes brings it down to O(N log log N), using O(N) memory.