QA-Specific Coding Questions¶

Companion to 01_DSA_Patterns.md. That file covers algorithmic patterns (FAANG SDET tier). This file covers what actually gets asked in non-FAANG QA / SDET interviews at Bangalore companies — Razorpay, PhonePe, Swiggy, Zomato, CRED, Postman, BrowserStack, Atlassian, Adobe, Salesforce, Walmart, Flipkart, ServiceNow, ThoughtWorks, plus services companies (TCS, Infosys, Wipro).

Every problem has: Java solution + Python solution + how to think about it + common follow-ups. Languages picked because Java + REST Assured is your strongest stack, Python is your data-validation stack.

What's covered¶

Section	Topic	Questions
1	String manipulation (#1 most asked)	20
2	Array basics	15
3	Number problems	12
4	HashMap basics	10
5	Recursion basics	8
6	OOP design (LLD)	8
7	Validators (the SDET favourite)	10
8	SQL coding (separate round, full coverage)	15
9	Concurrency basics (SDET-2)	6
10	Pattern printing	6
11	Test-data generators / parsers	7
12	Linked lists basics	5
13	Mini cheat-sheet — what to remember	—

1. STRING MANIPULATION (the #1 category)¶

1.1 Reverse a string¶

Problem¶

Reverse a string. (Asked in 80%+ of QA phone screens.)

Java¶

public String reverse(String s) {
    return new StringBuilder(s).reverse().toString();
}

// Without library
public String reverseManual(String s) {
    char[] chars = s.toCharArray();
    int l = 0, r = chars.length - 1;
    while (l < r) {
        char tmp = chars[l];
        chars[l++] = chars[r];
        chars[r--] = tmp;
    }
    return new String(chars);
}

Python¶

def reverse(s: str) -> str:
    return s[::-1]

def reverse_manual(s: str) -> str:
    chars = list(s)
    l, r = 0, len(chars) - 1
    while l < r:
        chars[l], chars[r] = chars[r], chars[l]
        l, r = l + 1, r - 1
    return ''.join(chars)

Follow-ups they'll ask¶

"Without library?" — show the two-pointer version
"In place?" — Java strings are immutable, so explain you'd convert to char[] first
"Reverse only words?" — see Q1.2

1.2 Reverse words in a sentence¶

Problem¶

Input: "the quick brown fox" → Output: "fox brown quick the"

Java¶

public String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        sb.append(words[i]);
        if (i > 0) sb.append(" ");
    }
    return sb.toString();
}

Python¶

def reverse_words(s: str) -> str:
    return ' '.join(s.split()[::-1])

Follow-ups¶

Preserve original spacing? Use split(' ') (no regex) and reverse
Reverse each word's characters in place? Different problem entirely

1.3 Check palindrome¶

Problem¶

Is "racecar" a palindrome? Yes. Is "hello" a palindrome? No.

Java¶

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

// Case-insensitive, alphanumeric only
public boolean isPalindromeRelaxed(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
        while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
        if (Character.toLowerCase(s.charAt(l++)) !=
            Character.toLowerCase(s.charAt(r--))) return false;
    }
    return true;
}

Python¶

def is_palindrome(s: str) -> bool:
    return s == s[::-1]

# Case-insensitive, alphanumeric only
def is_palindrome_relaxed(s: str) -> bool:
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

1.4 Check anagram¶

Problem¶

Are "listen" and "silent" anagrams? Yes.

Java¶

// Sort both
public boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false;
    char[] x = a.toCharArray(), y = b.toCharArray();
    Arrays.sort(x); Arrays.sort(y);
    return Arrays.equals(x, y);
}

// Count chars (O(N) better)
public boolean isAnagramFast(String a, String b) {
    if (a.length() != b.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < a.length(); i++) {
        count[a.charAt(i) - 'a']++;
        count[b.charAt(i) - 'a']--;
    }
    for (int c : count) if (c != 0) return false;
    return true;
}

Python¶

def is_anagram(a: str, b: str) -> bool:
    return sorted(a) == sorted(b)

# O(N) version
from collections import Counter
def is_anagram_fast(a: str, b: str) -> bool:
    return Counter(a) == Counter(b)

1.5 Count vowels and consonants¶

Java¶

public int[] countVowelsConsonants(String s) {
    int v = 0, c = 0;
    for (char ch : s.toLowerCase().toCharArray()) {
        if (ch >= 'a' && ch <= 'z') {
            if ("aeiou".indexOf(ch) >= 0) v++;
            else c++;
        }
    }
    return new int[]{v, c};
}

Python¶

def count_vc(s: str) -> tuple[int, int]:
    vowels = set('aeiou')
    v = sum(1 for c in s.lower() if c in vowels)
    c = sum(1 for c in s.lower() if c.isalpha() and c not in vowels)
    return v, c

1.6 First non-repeating character¶

Problem¶

"swiss" → 'w'

Java¶

public Character firstUnique(String s) {
    LinkedHashMap<Character, Integer> freq = new LinkedHashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
    for (var entry : freq.entrySet())
        if (entry.getValue() == 1) return entry.getKey();
    return null;
}

Python¶

from collections import Counter

def first_unique(s: str):
    freq = Counter(s)
    for c in s:
        if freq[c] == 1:
            return c
    return None

1.7 Remove duplicate characters¶

Problem¶

"programming" → "progamin" (preserve first occurrence order)

Java¶

public String removeDuplicates(String s) {
    Set<Character> seen = new LinkedHashSet<>();
    for (char c : s.toCharArray()) seen.add(c);
    StringBuilder sb = new StringBuilder();
    for (char c : seen) sb.append(c);
    return sb.toString();
}

Python¶

def remove_dups(s: str) -> str:
    seen = set()
    out = []
    for c in s:
        if c not in seen:
            seen.add(c)
            out.append(c)
    return ''.join(out)

# Python 3.7+ dict preserves order — one-liner:
def remove_dups_short(s: str) -> str:
    return ''.join(dict.fromkeys(s))

1.8 Check if one string is rotation of another¶

Problem¶

isRotation("abcd", "cdab") → true

Java¶

public boolean isRotation(String a, String b) {
    if (a.length() != b.length()) return false;
    return (a + a).contains(b);
}

Python¶

def is_rotation(a: str, b: str) -> bool:
    return len(a) == len(b) and b in a + a

The trick: any rotation of a is a substring of a+a. Beautiful single-line solution.

1.9 Longest substring without repeating characters¶

Java (sliding window)¶

public int longestUnique(String s) {
    Map<Character, Integer> seen = new HashMap<>();
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        if (seen.containsKey(c) && seen.get(c) >= l) {
            l = seen.get(c) + 1;
        }
        seen.put(c, r);
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Python¶

def longest_unique(s: str) -> int:
    seen = {}
    l = best = 0
    for r, c in enumerate(s):
        if c in seen and seen[c] >= l:
            l = seen[c] + 1
        seen[c] = r
        best = max(best, r - l + 1)
    return best

1.10 String compression¶

Problem¶

"aaabbc" → "a3b2c1". Return original if compressed is longer.

Java¶

public String compress(String s) {
    StringBuilder sb = new StringBuilder();
    int count = 1;
    for (int i = 1; i <= s.length(); i++) {
        if (i < s.length() && s.charAt(i) == s.charAt(i - 1)) {
            count++;
        } else {
            sb.append(s.charAt(i - 1)).append(count);
            count = 1;
        }
    }
    return sb.length() < s.length() ? sb.toString() : s;
}

Python¶

def compress(s: str) -> str:
    if not s: return s
    out = []
    count = 1
    for i in range(1, len(s) + 1):
        if i < len(s) and s[i] == s[i - 1]:
            count += 1
        else:
            out.append(s[i - 1] + str(count))
            count = 1
    result = ''.join(out)
    return result if len(result) < len(s) else s

1.11 Capitalize first letter of each word¶

Java¶

public String titleCase(String s) {
    StringBuilder sb = new StringBuilder();
    boolean capitalize = true;
    for (char c : s.toCharArray()) {
        if (Character.isWhitespace(c)) {
            capitalize = true;
            sb.append(c);
        } else if (capitalize) {
            sb.append(Character.toUpperCase(c));
            capitalize = false;
        } else {
            sb.append(Character.toLowerCase(c));
        }
    }
    return sb.toString();
}

Python¶

def title_case(s: str) -> str:
    return s.title()      # built-in

# Manual
def title_case_manual(s: str) -> str:
    return ' '.join(w.capitalize() for w in s.split(' '))

1.12 Count occurrences of a character¶

Java¶

public int countChar(String s, char c) {
    int count = 0;
    for (char ch : s.toCharArray()) if (ch == c) count++;
    return count;
}

Python¶

def count_char(s: str, c: str) -> int:
    return s.count(c)

1.13 Find all duplicate characters¶

Java¶

public List<Character> duplicates(String s) {
    Map<Character, Integer> freq = new LinkedHashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
    List<Character> out = new ArrayList<>();
    for (var e : freq.entrySet())
        if (e.getValue() > 1) out.add(e.getKey());
    return out;
}

Python¶

from collections import Counter
def duplicates(s: str) -> list:
    return [c for c, count in Counter(s).items() if count > 1]

1.14 Check if two strings are equal ignoring case¶

Java¶

public boolean equalsIgnoreCase(String a, String b) {
    return a.equalsIgnoreCase(b);
}

Python¶

def equals_ignore_case(a: str, b: str) -> bool:
    return a.casefold() == b.casefold()    # better than .lower() for unicode

1.15 Group anagrams¶

Java¶

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

Python¶

from collections import defaultdict
def group_anagrams(strs: list) -> list:
    groups = defaultdict(list)
    for s in strs:
        groups[''.join(sorted(s))].append(s)
    return list(groups.values())

1.16 Reverse only vowels in a string¶

Problem¶

"hello" → "holle"

Java¶

public String reverseVowels(String s) {
    char[] chars = s.toCharArray();
    Set<Character> vowels = Set.of('a','e','i','o','u','A','E','I','O','U');
    int l = 0, r = chars.length - 1;
    while (l < r) {
        while (l < r && !vowels.contains(chars[l])) l++;
        while (l < r && !vowels.contains(chars[r])) r--;
        char tmp = chars[l]; chars[l++] = chars[r]; chars[r--] = tmp;
    }
    return new String(chars);
}

Python¶

def reverse_vowels(s: str) -> str:
    vowels = set('aeiouAEIOU')
    chars = list(s)
    l, r = 0, len(chars) - 1
    while l < r:
        while l < r and chars[l] not in vowels: l += 1
        while l < r and chars[r] not in vowels: r -= 1
        chars[l], chars[r] = chars[r], chars[l]
        l, r = l + 1, r - 1
    return ''.join(chars)

1.17 Longest common prefix¶

Java¶

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

Python¶

import os
def lcp(strs: list) -> str:
    return os.path.commonprefix(strs)   # built-in!

def lcp_manual(strs: list) -> str:
    if not strs: return ""
    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix: return ""
    return prefix

1.18 Check if string contains only digits¶

Java¶

public boolean isNumeric(String s) {
    return s != null && !s.isEmpty() && s.chars().allMatch(Character::isDigit);
}

Python¶

def is_numeric(s: str) -> bool:
    return s.isdigit() if s else False

1.19 Swap case of every character¶

Java¶

public String swapCase(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (Character.isUpperCase(c)) sb.append(Character.toLowerCase(c));
        else if (Character.isLowerCase(c)) sb.append(Character.toUpperCase(c));
        else sb.append(c);
    }
    return sb.toString();
}

Python¶

def swap_case(s: str) -> str:
    return s.swapcase()

1.20 Find the longest palindromic substring¶

Problem¶

"babad" → "bab" or "aba"

Java¶

public String longestPalindrome(String s) {
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expand(s, i, i);      // odd-length palindrome
        int len2 = expand(s, i, i + 1);   // even-length palindrome
        int len = Math.max(len1, len2);
        if (len > maxLen) {
            start = i - (len - 1) / 2;
            maxLen = len;
        }
    }
    return s.substring(start, start + maxLen);
}

private int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--; r++;
    }
    return r - l - 1;
}

Python¶

def longest_palindrome(s: str) -> str:
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l, r = l - 1, r + 1
        return s[l + 1:r]

    best = ""
    for i in range(len(s)):
        odd = expand(i, i)
        even = expand(i, i + 1)
        best = max(best, odd, even, key=len)
    return best

2. ARRAY BASICS¶

2.1 Find max and min¶

Java¶

public int[] maxMin(int[] arr) {
    int max = arr[0], min = arr[0];
    for (int n : arr) {
        if (n > max) max = n;
        if (n < min) min = n;
    }
    return new int[]{max, min};
}

Python¶

def max_min(arr): return max(arr), min(arr)

2.2 Find second largest¶

Problem¶

[5, 2, 9, 1, 9, 6] → 6 (distinct second-largest)

Java¶

public int secondLargest(int[] arr) {
    int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE;
    for (int n : arr) {
        if (n > first) {
            second = first;
            first = n;
        } else if (n > second && n != first) {
            second = n;
        }
    }
    return second;
}

Python¶

def second_largest(arr):
    first = second = float('-inf')
    for n in arr:
        if n > first:
            first, second = n, first
        elif n > second and n != first:
            second = n
    return second

2.3 Find missing number in 1..N¶

Problem¶

[1, 2, 4, 5] (N=5) → 3

Java¶

public int missingNumber(int[] arr, int n) {
    int expectedSum = n * (n + 1) / 2;
    int actualSum = 0;
    for (int x : arr) actualSum += x;
    return expectedSum - actualSum;
}

Python¶

def missing_number(arr, n):
    return n * (n + 1) // 2 - sum(arr)

2.4 Remove duplicates in-place from sorted array¶

Java¶

public int removeDuplicates(int[] arr) {
    if (arr.length == 0) return 0;
    int k = 1;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != arr[i - 1]) {
            arr[k++] = arr[i];
        }
    }
    return k;   // new length
}

Python¶

def remove_duplicates(arr):
    if not arr: return 0
    k = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[k] = arr[i]
            k += 1
    return k

2.5 Move zeros to the end (preserve order)¶

Java¶

public void moveZeros(int[] arr) {
    int k = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != 0) arr[k++] = arr[i];
    }
    while (k < arr.length) arr[k++] = 0;
}

Python¶

def move_zeros(arr):
    k = 0
    for n in arr:
        if n != 0:
            arr[k] = n
            k += 1
    for i in range(k, len(arr)):
        arr[i] = 0

2.6 Rotate array by K positions¶

Java¶

public void rotate(int[] arr, int k) {
    int n = arr.length;
    k %= n;
    reverse(arr, 0, n - 1);
    reverse(arr, 0, k - 1);
    reverse(arr, k, n - 1);
}

private void reverse(int[] arr, int l, int r) {
    while (l < r) {
        int tmp = arr[l]; arr[l++] = arr[r]; arr[r--] = tmp;
    }
}

Python¶

def rotate(arr, k):
    n = len(arr)
    k %= n
    arr[:] = arr[-k:] + arr[:-k]

2.7 Find all pairs with given sum¶

Java¶

public List<int[]> pairsWithSum(int[] arr, int target) {
    Set<Integer> seen = new HashSet<>();
    List<int[]> pairs = new ArrayList<>();
    for (int n : arr) {
        if (seen.contains(target - n)) {
            pairs.add(new int[]{target - n, n});
        }
        seen.add(n);
    }
    return pairs;
}

Python¶

def pairs_with_sum(arr, target):
    seen, pairs = set(), []
    for n in arr:
        if target - n in seen:
            pairs.append((target - n, n))
        seen.add(n)
    return pairs

2.8 Find majority element (appears > N/2)¶

Boyer-Moore voting algorithm¶

Java¶

public Integer majority(int[] arr) {
    int candidate = 0, count = 0;
    for (int n : arr) {
        if (count == 0) candidate = n;
        count += (n == candidate) ? 1 : -1;
    }
    // Verify (Boyer-Moore doesn't guarantee — check)
    count = 0;
    for (int n : arr) if (n == candidate) count++;
    return count > arr.length / 2 ? candidate : null;
}

Python¶

def majority(arr):
    candidate, count = 0, 0
    for n in arr:
        if count == 0:
            candidate = n
        count += 1 if n == candidate else -1
    return candidate if arr.count(candidate) > len(arr) // 2 else None

2.9 Find common elements in two arrays¶

Java¶

public List<Integer> intersection(int[] a, int[] b) {
    Set<Integer> setA = new HashSet<>();
    for (int n : a) setA.add(n);
    List<Integer> result = new ArrayList<>();
    Set<Integer> added = new HashSet<>();
    for (int n : b) {
        if (setA.contains(n) && added.add(n)) {
            result.add(n);
        }
    }
    return result;
}

Python¶

def intersection(a, b):
    return list(set(a) & set(b))

2.10 Check if array is sorted¶

Java¶

public boolean isSorted(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) return false;
    }
    return true;
}

Python¶

def is_sorted(arr):
    return all(arr[i] >= arr[i - 1] for i in range(1, len(arr)))

2.11 Find the only number that appears once (rest twice)¶

Trick: XOR¶

Java¶

public int singleNumber(int[] arr) {
    int result = 0;
    for (int n : arr) result ^= n;
    return result;
}

Python¶

from functools import reduce
def single_number(arr):
    return reduce(lambda a, b: a ^ b, arr)

2.12 Sum of subarray (range sum)¶

Java¶

public int rangeSum(int[] arr, int l, int r) {
    int sum = 0;
    for (int i = l; i <= r; i++) sum += arr[i];
    return sum;
}

Python¶

def range_sum(arr, l, r):
    return sum(arr[l:r + 1])

For repeated queries — use prefix sum (see file 01 pattern #4).

2.13 Find pair with maximum sum¶

Java¶

public int[] maxSumPair(int[] arr) {
    int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE;
    for (int n : arr) {
        if (n > max1) { max2 = max1; max1 = n; }
        else if (n > max2) max2 = n;
    }
    return new int[]{max1, max2};
}

Python¶

import heapq
def max_sum_pair(arr):
    return heapq.nlargest(2, arr)

2.14 Frequency of each element¶

Java¶

public Map<Integer, Integer> frequencies(int[] arr) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : arr) freq.merge(n, 1, Integer::sum);
    return freq;
}

Python¶

from collections import Counter
def frequencies(arr):
    return Counter(arr)

2.15 Largest sum of contiguous subarray (Kadane)¶

Java¶

public int maxSubArraySum(int[] arr) {
    int curSum = arr[0], maxSum = arr[0];
    for (int i = 1; i < arr.length; i++) {
        curSum = Math.max(arr[i], curSum + arr[i]);
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}

Python¶

def max_subarray_sum(arr):
    cur = best = arr[0]
    for n in arr[1:]:
        cur = max(n, cur + n)
        best = max(best, cur)
    return best

3. NUMBER PROBLEMS¶

3.1 Check if prime¶

Java¶

public boolean isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

Python¶

def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    return all(n % i for i in range(3, int(n ** 0.5) + 1, 2))

3.2 Sieve of Eratosthenes (all primes up to N)¶

Java¶

public boolean[] sieve(int n) {
    boolean[] prime = new boolean[n + 1];
    Arrays.fill(prime, 2, n + 1, true);
    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }
    return prime;
}

Python¶

def sieve(n):
    prime = [False, False] + [True] * (n - 1)
    for i in range(2, int(n ** 0.5) + 1):
        if prime[i]:
            for j in range(i * i, n + 1, i):
                prime[j] = False
    return [i for i, p in enumerate(prime) if p]

3.3 Factorial (iterative and recursive)¶

Java¶

public long factorial(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

public long factorialRec(int n) {
    return n <= 1 ? 1 : n * factorialRec(n - 1);
}

Python¶

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def factorial_rec(n):
    return 1 if n <= 1 else n * factorial_rec(n - 1)

3.4 Fibonacci (iterative)¶

Java¶

public long fib(int n) {
    if (n < 2) return n;
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long c = a + b;
        a = b; b = c;
    }
    return b;
}

Python¶

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

3.5 Reverse a number¶

Problem¶

12345 → 54321. Handle negatives.

Java¶

public int reverse(int n) {
    int sign = n < 0 ? -1 : 1;
    n = Math.abs(n);
    int result = 0;
    while (n > 0) {
        result = result * 10 + n % 10;
        n /= 10;
    }
    return sign * result;
}

Python¶

def reverse_num(n):
    sign = -1 if n < 0 else 1
    n = abs(n)
    result = 0
    while n > 0:
        result = result * 10 + n % 10
        n //= 10
    return sign * result

# One-liner
def reverse_short(n):
    sign = -1 if n < 0 else 1
    return sign * int(str(abs(n))[::-1])

3.6 Sum of digits¶

Java¶

public int sumDigits(int n) {
    n = Math.abs(n);
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

Python¶

def sum_digits(n):
    return sum(int(c) for c in str(abs(n)))

3.7 Armstrong number¶

Problem¶

153 → 1^3 + 5^3 + 3^3 = 153 → Armstrong

Java¶

public boolean isArmstrong(int n) {
    int original = n, digits = String.valueOf(n).length(), sum = 0;
    while (n > 0) {
        sum += (int) Math.pow(n % 10, digits);
        n /= 10;
    }
    return sum == original;
}

Python¶

def is_armstrong(n):
    s = str(n)
    return sum(int(c) ** len(s) for c in s) == n

3.8 Check palindrome number¶

Java¶

public boolean isPalindromeNum(int n) {
    if (n < 0) return false;
    int original = n, reversed = 0;
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return original == reversed;
}

Python¶

def is_palindrome_num(n):
    return n >= 0 and str(n) == str(n)[::-1]

3.9 GCD (Euclidean)¶

Java¶

public int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

Python¶

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Or use built-in
from math import gcd

3.10 LCM¶

Java¶

public int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

Python¶

def lcm(a, b):
    from math import gcd
    return a * b // gcd(a, b)

3.11 Power of 2 check¶

Java¶

public boolean isPowerOf2(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Python¶

def is_power_of_2(n):
    return n > 0 and (n & (n - 1)) == 0

Why this works: powers of 2 have exactly one bit set. n - 1 flips that bit and sets all lower bits. AND with n = 0.

3.12 Count digits¶

Java¶

public int countDigits(int n) {
    if (n == 0) return 1;
    int count = 0;
    n = Math.abs(n);
    while (n > 0) { count++; n /= 10; }
    return count;
}

Python¶

def count_digits(n):
    return len(str(abs(n))) if n != 0 else 1

4. HASHMAP BASICS¶

4.1 Word frequency in a sentence¶

Java¶

public Map<String, Integer> wordFreq(String s) {
    Map<String, Integer> freq = new HashMap<>();
    for (String w : s.toLowerCase().split("\\s+")) {
        freq.merge(w, 1, Integer::sum);
    }
    return freq;
}

Python¶

from collections import Counter
def word_freq(s):
    return Counter(s.lower().split())

4.2 Top K frequent words¶

Java¶

public List<String> topKFrequent(String s, int k) {
    Map<String, Integer> freq = wordFreq(s);
    PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>(
        Comparator.comparingInt(Map.Entry::getValue)
    );
    for (var entry : freq.entrySet()) {
        heap.offer(entry);
        if (heap.size() > k) heap.poll();
    }
    List<String> result = new ArrayList<>();
    while (!heap.isEmpty()) result.add(0, heap.poll().getKey());
    return result;
}

Python¶

from collections import Counter
def top_k(s, k):
    return [w for w, _ in Counter(s.lower().split()).most_common(k)]

4.3 Two Sum¶

Java¶

public int[] twoSum(int[] arr, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < arr.length; i++) {
        if (seen.containsKey(target - arr[i])) {
            return new int[]{seen.get(target - arr[i]), i};
        }
        seen.put(arr[i], i);
    }
    return new int[]{};
}

Python¶

def two_sum(arr, target):
    seen = {}
    for i, n in enumerate(arr):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i

4.4 Group strings by length¶

Java¶

public Map<Integer, List<String>> groupByLength(List<String> strs) {
    return strs.stream().collect(Collectors.groupingBy(String::length));
}

Python¶

from collections import defaultdict
def group_by_length(strs):
    groups = defaultdict(list)
    for s in strs:
        groups[len(s)].append(s)
    return dict(groups)

4.5 Find longest substring with exactly K distinct characters¶

Java (sliding window)¶

public int longestKDistinct(String s, int k) {
    Map<Character, Integer> count = new HashMap<>();
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        count.merge(s.charAt(r), 1, Integer::sum);
        while (count.size() > k) {
            char lc = s.charAt(l);
            count.merge(lc, -1, Integer::sum);
            if (count.get(lc) == 0) count.remove(lc);
            l++;
        }
        if (count.size() == k) best = Math.max(best, r - l + 1);
    }
    return best;
}

Python¶

from collections import defaultdict
def longest_k_distinct(s, k):
    count = defaultdict(int)
    l = best = 0
    for r, c in enumerate(s):
        count[c] += 1
        while len(count) > k:
            count[s[l]] -= 1
            if count[s[l]] == 0:
                del count[s[l]]
            l += 1
        if len(count) == k:
            best = max(best, r - l + 1)
    return best

4.6 Find duplicate elements in array¶

Java¶

public Set<Integer> findDuplicates(int[] arr) {
    Set<Integer> seen = new HashSet<>();
    Set<Integer> dups = new HashSet<>();
    for (int n : arr) {
        if (!seen.add(n)) dups.add(n);
    }
    return dups;
}

Python¶

def find_duplicates(arr):
    seen, dups = set(), set()
    for n in arr:
        if n in seen:
            dups.add(n)
        seen.add(n)
    return dups

4.7 Subarray sum equals K (count subarrays)¶

Java¶

public int subarraySumK(int[] arr, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);
    int curSum = 0, count = 0;
    for (int n : arr) {
        curSum += n;
        count += prefixCount.getOrDefault(curSum - k, 0);
        prefixCount.merge(curSum, 1, Integer::sum);
    }
    return count;
}

Python¶

from collections import defaultdict
def subarray_sum_k(arr, k):
    prefix = defaultdict(int)
    prefix[0] = 1
    cur = count = 0
    for n in arr:
        cur += n
        count += prefix[cur - k]
        prefix[cur] += 1
    return count

4.8 Find missing number using HashMap¶

Java¶

public int missing(int[] arr, int n) {
    Set<Integer> seen = new HashSet<>();
    for (int x : arr) seen.add(x);
    for (int i = 1; i <= n; i++) {
        if (!seen.contains(i)) return i;
    }
    return -1;
}

Python¶

def missing(arr, n):
    seen = set(arr)
    return next(i for i in range(1, n + 1) if i not in seen)

4.9 Longest consecutive sequence¶

Java¶

public int longestConsecutive(int[] arr) {
    Set<Integer> set = new HashSet<>();
    for (int n : arr) set.add(n);
    int best = 0;
    for (int n : set) {
        if (!set.contains(n - 1)) {       // only start at sequence head
            int current = n, length = 1;
            while (set.contains(current + 1)) { current++; length++; }
            best = Math.max(best, length);
        }
    }
    return best;
}

Python¶

def longest_consecutive(arr):
    nums = set(arr)
    best = 0
    for n in nums:
        if n - 1 not in nums:
            length = 1
            while n + length in nums: length += 1
            best = max(best, length)
    return best

4.10 LRU Cache (HashMap + Doubly Linked List)¶

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

5. RECURSION BASICS¶

5.1 Print N to 1¶

Java¶

public void printNto1(int n) {
    if (n < 1) return;
    System.out.println(n);
    printNto1(n - 1);
}

Python¶

def print_n_to_1(n):
    if n < 1: return
    print(n)
    print_n_to_1(n - 1)

5.2 Sum of 1..N recursively¶

Java¶

public int sumToN(int n) {
    return n <= 0 ? 0 : n + sumToN(n - 1);
}

Python¶

def sum_to_n(n):
    return 0 if n <= 0 else n + sum_to_n(n - 1)

5.3 Power of a number (recursive)¶

Problem¶

power(2, 10) → 1024. Faster than N multiplications.

Java¶

public long power(int base, int exp) {
    if (exp == 0) return 1;
    if (exp % 2 == 0) {
        long half = power(base, exp / 2);
        return half * half;
    }
    return base * power(base, exp - 1);
}

Python¶

def power(base, exp):
    if exp == 0: return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half
    return base * power(base, exp - 1)

Why this is O(log N): halving the exponent.

5.4 Reverse a string recursively¶

Java¶

public String reverse(String s) {
    if (s.isEmpty()) return s;
    return reverse(s.substring(1)) + s.charAt(0);
}

Python¶

def reverse(s):
    return s if not s else reverse(s[1:]) + s[0]

5.5 Tower of Hanoi¶

Java¶

public void hanoi(int n, char from, char via, char to) {
    if (n == 1) {
        System.out.println("Move disk 1 from " + from + " to " + to);
        return;
    }
    hanoi(n - 1, from, to, via);
    System.out.println("Move disk " + n + " from " + from + " to " + to);
    hanoi(n - 1, via, from, to);
}

Python¶

def hanoi(n, src, via, dst):
    if n == 1:
        print(f"Move disk 1 from {src} to {dst}")
        return
    hanoi(n - 1, src, dst, via)
    print(f"Move disk {n} from {src} to {dst}")
    hanoi(n - 1, via, src, dst)

5.6 Generate all permutations of a string¶

Java¶

public List<String> permutations(String s) {
    List<String> result = new ArrayList<>();
    permute(s.toCharArray(), 0, result);
    return result;
}

private void permute(char[] chars, int start, List<String> result) {
    if (start == chars.length) {
        result.add(new String(chars));
        return;
    }
    for (int i = start; i < chars.length; i++) {
        swap(chars, start, i);
        permute(chars, start + 1, result);
        swap(chars, start, i);
    }
}

Python¶

from itertools import permutations
def perms(s):
    return [''.join(p) for p in permutations(s)]

# Manual
def perms_manual(s):
    if len(s) <= 1: return [s]
    result = []
    for i, c in enumerate(s):
        for p in perms_manual(s[:i] + s[i+1:]):
            result.append(c + p)
    return result

5.7 Find all subsets of a string¶

Java¶

public List<String> subsets(String s) {
    List<String> result = new ArrayList<>();
    subsetsHelper(s, 0, "", result);
    return result;
}

private void subsetsHelper(String s, int i, String current, List<String> result) {
    if (i == s.length()) { result.add(current); return; }
    subsetsHelper(s, i + 1, current, result);             // exclude
    subsetsHelper(s, i + 1, current + s.charAt(i), result); // include
}

Python¶

def subsets(s):
    if not s: return [""]
    rest = subsets(s[1:])
    return rest + [s[0] + r for r in rest]

5.8 Check if string is palindrome (recursive)¶

Java¶

public boolean isPalindrome(String s) {
    return isPalindrome(s, 0, s.length() - 1);
}

private boolean isPalindrome(String s, int l, int r) {
    if (l >= r) return true;
    if (s.charAt(l) != s.charAt(r)) return false;
    return isPalindrome(s, l + 1, r - 1);
}

Python¶

def is_palindrome(s):
    if len(s) <= 1: return True
    if s[0] != s[-1]: return False
    return is_palindrome(s[1:-1])

6. OOP DESIGN (LLD — Low-Level Design)¶

6.1 Implement a Stack¶

Java¶

public class MyStack<T> {
    private List<T> data = new ArrayList<>();

    public void push(T item) { data.add(item); }
    public T pop() {
        if (data.isEmpty()) throw new RuntimeException("Empty");
        return data.remove(data.size() - 1);
    }
    public T peek() {
        if (data.isEmpty()) throw new RuntimeException("Empty");
        return data.get(data.size() - 1);
    }
    public boolean isEmpty() { return data.isEmpty(); }
    public int size() { return data.size(); }
}

Python¶

class MyStack:
    def __init__(self):
        self.data = []

    def push(self, item): self.data.append(item)
    def pop(self): return self.data.pop() if self.data else None
    def peek(self): return self.data[-1] if self.data else None
    def is_empty(self): return not self.data
    def size(self): return len(self.data)

6.2 Implement a Queue using two stacks¶

Java¶

public class MyQueue<T> {
    private Stack<T> in = new Stack<>(), out = new Stack<>();

    public void enqueue(T item) { in.push(item); }
    public T dequeue() {
        shift();
        return out.isEmpty() ? null : out.pop();
    }
    public T peek() {
        shift();
        return out.isEmpty() ? null : out.peek();
    }
    private void shift() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.push(in.pop());
        }
    }
}

Python¶

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def enqueue(self, item):
        self.in_stack.append(item)

    def dequeue(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop() if self.out_stack else None

6.3 Min Stack (push/pop/getMin all O(1))¶

Java¶

public class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) minStack.push(x);
    }
    public void pop() {
        int top = stack.pop();
        if (top == minStack.peek()) minStack.pop();
    }
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

6.4 Parking Lot (classic OOP design)¶

Java skeleton (this is the kind of design they want you to talk through)¶

enum VehicleType { CAR, MOTORCYCLE, BUS }

abstract class Vehicle {
    protected String licensePlate;
    protected VehicleType type;
    abstract int spotsNeeded();
}

class Car extends Vehicle {
    int spotsNeeded() { return 1; }
}

class Bus extends Vehicle {
    int spotsNeeded() { return 5; }
}

class ParkingSpot {
    int id;
    VehicleType compatibleType;
    Vehicle occupant;
    boolean isFree() { return occupant == null; }
}

class ParkingLot {
    private List<ParkingSpot> spots;
    private Map<String, List<ParkingSpot>> activeTickets = new HashMap<>();

    public boolean park(Vehicle v) {
        List<ParkingSpot> chosen = findContiguousSpots(v);
        if (chosen == null) return false;
        chosen.forEach(s -> s.occupant = v);
        activeTickets.put(v.licensePlate, chosen);
        return true;
    }

    public boolean unpark(String licensePlate) {
        List<ParkingSpot> spots = activeTickets.remove(licensePlate);
        if (spots == null) return false;
        spots.forEach(s -> s.occupant = null);
        return true;
    }

    private List<ParkingSpot> findContiguousSpots(Vehicle v) {
        // logic to find N contiguous compatible spots
        return null; // skeleton
    }
}

How to talk about it in interview¶

"Three layers. Vehicle hierarchy with spotsNeeded() polymorphism — cars need 1, buses need 5. ParkingSpot with compatibility type. ParkingLot owns the spots, parks via findContiguousSpots, tracks active tickets by license plate. For senior probing, I'd add: pricing strategy (interface for different pricing models), payment processor (interface), multi-level lot (decoration on ParkingLot), thread-safety on park/unpark (synchronized or ReentrantLock)."

6.5 Library Management System¶

Skeleton¶

class Book {
    String isbn, title;
    List<String> authors;
}

class BookCopy {
    Book book;
    String barcode;
    BookCopyStatus status;   // AVAILABLE, BORROWED, RESERVED
}

class Member {
    String memberId;
    List<Loan> currentLoans = new ArrayList<>();
}

class Loan {
    BookCopy copy;
    Member member;
    LocalDate dueDate;
    boolean isOverdue() { return LocalDate.now().isAfter(dueDate); }
}

class Library {
    Map<String, List<BookCopy>> catalog = new HashMap<>();
    Map<String, Member> members = new HashMap<>();

    public Loan borrow(String memberId, String isbn) {
        // 1. Find available copy
        // 2. Check member's loan limit
        // 3. Create loan, update copy status
        // 4. Return loan
    }

    public void returnBook(String barcode) {
        // 1. Find loan
        // 2. Mark copy AVAILABLE
        // 3. Calculate fine if overdue
    }
}

6.6 ATM (state machine)¶

Key states¶

IDLE → CARD_INSERTED → PIN_ENTERED → OPTION_CHOSEN → TRANSACTION_COMPLETE → back to IDLE

interface ATMState {
    void insertCard(ATM atm);
    void enterPin(ATM atm, String pin);
    void selectOption(ATM atm, Option option);
    void dispenseCash(ATM atm, int amount);
}

class IdleState implements ATMState {
    public void insertCard(ATM atm) { atm.setState(new CardInsertedState()); }
    // other methods throw IllegalState
}

State pattern keeps each state's allowed transitions isolated.

6.7 URL Shortener (basic)¶

Java¶

public class UrlShortener {
    private Map<String, String> codeToUrl = new HashMap<>();
    private Map<String, String> urlToCode = new HashMap<>();
    private static final String BASE_URL = "https://short.ly/";
    private static final String CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

    public String encode(String longUrl) {
        if (urlToCode.containsKey(longUrl)) {
            return BASE_URL + urlToCode.get(longUrl);
        }
        String code = generateCode();
        codeToUrl.put(code, longUrl);
        urlToCode.put(longUrl, code);
        return BASE_URL + code;
    }

    public String decode(String shortUrl) {
        String code = shortUrl.replace(BASE_URL, "");
        return codeToUrl.get(code);
    }

    private String generateCode() {
        StringBuilder sb;
        do {
            sb = new StringBuilder();
            for (int i = 0; i < 6; i++) {
                sb.append(CHARS.charAt((int)(Math.random() * CHARS.length())));
            }
        } while (codeToUrl.containsKey(sb.toString()));
        return sb.toString();
    }
}

Talking points¶

Idempotency — same URL returns same code
Collision check — regenerate on collision (alternative: use auto-incrementing ID + base62)
Scale — for production, you'd use distributed ID generation (Snowflake) + cache

6.8 Rate Limiter (Token Bucket)¶

Java¶

public class TokenBucket {
    private final int capacity;
    private final double refillRate;     // tokens per second
    private double availableTokens;
    private long lastRefillTimestamp;

    public TokenBucket(int capacity, double refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.availableTokens = capacity;
        this.lastRefillTimestamp = System.nanoTime();
    }

    public synchronized boolean tryAcquire() {
        refill();
        if (availableTokens >= 1) {
            availableTokens--;
            return true;
        }
        return false;
    }

    private void refill() {
        long now = System.nanoTime();
        double elapsed = (now - lastRefillTimestamp) / 1_000_000_000.0;
        availableTokens = Math.min(capacity, availableTokens + elapsed * refillRate);
        lastRefillTimestamp = now;
    }
}

Why this design wins: O(1) per request, lazy refill (no background thread), thread-safe via synchronized.

7. VALIDATORS (THE SDET FAVOURITE)¶

7.1 Email validation¶

Java (RFC-5322 simplified)¶

public boolean isValidEmail(String email) {
    if (email == null) return false;
    String regex = "^[A-Za-z0-9+_.-]+@[A-Za-z0-9.-]+\\.[A-Za-z]{2,}$";
    return email.matches(regex);
}

Python¶

import re
def is_valid_email(email):
    return bool(re.match(r'^[A-Za-z0-9+_.-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,}$', email or ''))

Follow-ups¶

"Are you handling all RFC-5322 cases?" → No — production regex is much longer. For testing, simplified version is fine.
"What about IDN (internationalized domain names)?" → Punycode-convert first

7.2 Phone number (Indian)¶

Java¶

public boolean isValidIndianPhone(String phone) {
    if (phone == null) return false;
    return phone.matches("^(\\+91[\\-\\s]?)?[6-9]\\d{9}$");
}

Python¶

import re
def is_valid_indian_phone(phone):
    return bool(re.match(r'^(\+91[\-\s]?)?[6-9]\d{9}$', phone or ''))

The rules: starts with 6, 7, 8, or 9 (mobile prefixes), 10 digits total, optional +91 prefix.

7.3 Credit card validation (Luhn algorithm)¶

Java¶

public boolean isValidLuhn(String cardNumber) {
    if (cardNumber == null) return false;
    cardNumber = cardNumber.replaceAll("\\s+", "");
    if (!cardNumber.matches("\\d{13,19}")) return false;

    int sum = 0;
    boolean alternate = false;
    for (int i = cardNumber.length() - 1; i >= 0; i--) {
        int n = cardNumber.charAt(i) - '0';
        if (alternate) {
            n *= 2;
            if (n > 9) n -= 9;
        }
        sum += n;
        alternate = !alternate;
    }
    return sum % 10 == 0;
}

Python¶

def is_valid_luhn(card_number):
    s = (card_number or '').replace(' ', '')
    if not s.isdigit() or not (13 <= len(s) <= 19):
        return False
    total = 0
    for i, c in enumerate(reversed(s)):
        n = int(c)
        if i % 2 == 1:
            n *= 2
            if n > 9: n -= 9
        total += n
    return total % 10 == 0

Explain the algorithm: "Double every second digit from the right, subtract 9 if > 9, sum all digits, divisible by 10 = valid."

7.4 IP address (IPv4)¶

Java¶

public boolean isValidIPv4(String ip) {
    if (ip == null) return false;
    String[] parts = ip.split("\\.");
    if (parts.length != 4) return false;
    for (String part : parts) {
        if (!part.matches("\\d+")) return false;
        int n = Integer.parseInt(part);
        if (n < 0 || n > 255) return false;
        if (part.length() > 1 && part.startsWith("0")) return false;   // no leading zeros
    }
    return true;
}

Python¶

def is_valid_ipv4(ip):
    parts = (ip or '').split('.')
    if len(parts) != 4: return False
    for p in parts:
        if not p.isdigit() or not 0 <= int(p) <= 255:
            return False
        if len(p) > 1 and p[0] == '0':
            return False
    return True

7.5 Password policy¶

Rules¶

8-32 chars, at least 1 uppercase, 1 lowercase, 1 digit, 1 special

Java¶

public boolean isValidPassword(String pwd) {
    if (pwd == null || pwd.length() < 8 || pwd.length() > 32) return false;
    return pwd.matches(".*[A-Z].*") &&
           pwd.matches(".*[a-z].*") &&
           pwd.matches(".*\\d.*") &&
           pwd.matches(".*[!@#$%^&*()_+\\-=].*");
}

Python¶

import re
def is_valid_password(pwd):
    if not pwd or not 8 <= len(pwd) <= 32: return False
    if not re.search(r'[A-Z]', pwd): return False
    if not re.search(r'[a-z]', pwd): return False
    if not re.search(r'\d', pwd): return False
    if not re.search(r'[!@#$%^&*()_+\-=]', pwd): return False
    return True

7.6 PAN card (Indian)¶

Format¶

5 uppercase letters + 4 digits + 1 uppercase letter, total 10.

Java¶

public boolean isValidPAN(String pan) {
    return pan != null && pan.matches("^[A-Z]{5}\\d{4}[A-Z]$");
}

Python¶

import re
def is_valid_pan(pan):
    return bool(re.match(r'^[A-Z]{5}\d{4}[A-Z]$', pan or ''))

7.7 Aadhaar (Indian, 12 digits, Verhoeff check optional)¶

Java (format only)¶

public boolean isValidAadhaarFormat(String aadhaar) {
    return aadhaar != null && aadhaar.matches("^\\d{12}$");
}

Python¶

def is_valid_aadhaar_format(aadhaar):
    return bool(aadhaar and len(aadhaar) == 12 and aadhaar.isdigit())

Full validation uses the Verhoeff algorithm — UIDAI's checksum scheme. Mention you know about it; don't usually need to implement.

7.8 Date format validation¶

Java (parsing approach)¶

public boolean isValidDate(String date, String format) {
    try {
        DateTimeFormatter formatter = DateTimeFormatter.ofPattern(format)
            .withResolverStyle(ResolverStyle.STRICT);
        LocalDate.parse(date, formatter);
        return true;
    } catch (DateTimeParseException e) {
        return false;
    }
}

Python¶

from datetime import datetime
def is_valid_date(date_str, format='%Y-%m-%d'):
    try:
        datetime.strptime(date_str, format)
        return True
    except (ValueError, TypeError):
        return False

Why parsing > regex: parsing catches invalid dates like Feb 30 that regex would miss.

7.9 URL validation¶

Java¶

public boolean isValidUrl(String url) {
    try {
        new URL(url).toURI();
        return true;
    } catch (Exception e) {
        return false;
    }
}

Python¶

from urllib.parse import urlparse
def is_valid_url(url):
    try:
        result = urlparse(url)
        return all([result.scheme, result.netloc])
    except:
        return False

7.10 GST number (Indian)¶

Format¶

15 chars: 2 state code + 10 PAN + 1 entity number + 1 'Z' + 1 check char

Java¶

public boolean isValidGST(String gst) {
    return gst != null && gst.matches("^\\d{2}[A-Z]{5}\\d{4}[A-Z]\\d[Z]\\w$");
}

Python¶

import re
def is_valid_gst(gst):
    return bool(re.match(r'^\d{2}[A-Z]{5}\d{4}[A-Z]\d[Z]\w$', gst or ''))

8. SQL CODING (SEPARATE ROUND)¶

SQL gets its own round in 80%+ of QA interviews. Master these.

Schema for examples¶

CREATE TABLE employees (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    salary DECIMAL(10,2),
    dept_id INT,
    manager_id INT,
    hire_date DATE
);

CREATE TABLE departments (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    location VARCHAR(100)
);

8.1 Second highest salary¶

-- Method 1: subquery
SELECT MAX(salary) AS second_highest
FROM employees
WHERE salary < (SELECT MAX(salary) FROM employees);

-- Method 2: DENSE_RANK (handles ties)
SELECT salary
FROM (
    SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
    FROM employees
) t
WHERE rnk = 2;

-- Method 3: LIMIT (MySQL/Postgres)
SELECT DISTINCT salary
FROM employees
ORDER BY salary DESC
LIMIT 1 OFFSET 1;

8.2 Nth highest salary¶

SELECT salary
FROM (
    SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
    FROM employees
) t
WHERE rnk = N;

8.3 Find duplicate emails¶

SELECT email, COUNT(*) AS cnt
FROM users
GROUP BY email
HAVING COUNT(*) > 1;

8.4 Delete duplicates, keep one¶

-- Keep row with smallest id per email
DELETE u FROM users u
WHERE id NOT IN (
    SELECT MIN(id) FROM users GROUP BY email
);

-- Postgres / Oracle: use ROW_NUMBER
DELETE FROM users
WHERE id IN (
    SELECT id FROM (
        SELECT id, ROW_NUMBER() OVER (PARTITION BY email ORDER BY id) AS rn
        FROM users
    ) t WHERE rn > 1
);

8.5 Employees earning more than their manager¶

SELECT e.name AS employee, m.name AS manager,
       e.salary AS emp_sal, m.salary AS mgr_sal
FROM employees e
JOIN employees m ON e.manager_id = m.id
WHERE e.salary > m.salary;

This is a self-join — common interview question.

8.6 Department with highest average salary¶

SELECT d.name AS department, AVG(e.salary) AS avg_salary
FROM employees e
JOIN departments d ON e.dept_id = d.id
GROUP BY d.id, d.name
ORDER BY avg_salary DESC
LIMIT 1;

8.7 Employees per department + employees with no department¶

SELECT d.name, COUNT(e.id) AS emp_count
FROM departments d
LEFT JOIN employees e ON d.id = e.dept_id
GROUP BY d.id, d.name;

Why LEFT JOIN: keeps departments that have zero employees.

8.8 Top 3 salaries per department¶

SELECT *
FROM (
    SELECT e.name, e.salary, d.name AS dept,
           DENSE_RANK() OVER (PARTITION BY e.dept_id ORDER BY e.salary DESC) AS rnk
    FROM employees e
    JOIN departments d ON e.dept_id = d.id
) t
WHERE rnk <= 3;

8.9 Customers who never ordered¶

SELECT c.name
FROM customers c
LEFT JOIN orders o ON c.id = o.customer_id
WHERE o.id IS NULL;

-- Or
SELECT name FROM customers
WHERE id NOT IN (SELECT customer_id FROM orders);

8.10 Cumulative salary¶

SELECT id, name, salary,
       SUM(salary) OVER (ORDER BY id) AS cumulative
FROM employees;

8.11 Find consecutive numbers (3 or more times)¶

SELECT DISTINCT num
FROM (
    SELECT num,
           LEAD(num, 1) OVER (ORDER BY id) AS next1,
           LEAD(num, 2) OVER (ORDER BY id) AS next2
    FROM numbers
) t
WHERE num = next1 AND num = next2;

8.12 Pivot rows to columns¶

-- Show count of each gender per dept
SELECT dept_id,
       SUM(CASE WHEN gender = 'M' THEN 1 ELSE 0 END) AS male,
       SUM(CASE WHEN gender = 'F' THEN 1 ELSE 0 END) AS female
FROM employees
GROUP BY dept_id;

8.13 Get every Nth row¶

SELECT * FROM (
    SELECT *, ROW_NUMBER() OVER (ORDER BY id) AS rn
    FROM employees
) t
WHERE rn % 3 = 0;   -- every 3rd row

8.14 Most recent record per group¶

SELECT * FROM (
    SELECT *,
           ROW_NUMBER() OVER (PARTITION BY customer_id ORDER BY created_at DESC) AS rn
    FROM orders
) t
WHERE rn = 1;

8.15 INNER vs LEFT JOIN scenarios — explain when each matters¶

-- INNER JOIN: only matched rows
SELECT u.name, o.amount
FROM users u
INNER JOIN orders o ON u.id = o.user_id;
-- Users without orders disappear.

-- LEFT JOIN: all users, NULL for those without orders
SELECT u.name, o.amount
FROM users u
LEFT JOIN orders o ON u.id = o.user_id;
-- Users without orders kept; amount is NULL.

-- Common bug: LEFT JOIN + WHERE on right-table column
-- This re-filters to inner-join behavior:
WHERE o.amount > 0
-- Fix: put condition in ON clause
ON u.id = o.user_id AND o.amount > 0

9. CONCURRENCY BASICS (SDET-2)¶

9.1 Print odd and even from two threads alternately¶

Java¶

public class OddEvenPrinter {
    private final Object lock = new Object();
    private boolean printOdd = true;

    public void printOdd(int max) {
        for (int i = 1; i <= max; i += 2) {
            synchronized (lock) {
                while (!printOdd) {
                    try { lock.wait(); } catch (InterruptedException e) {}
                }
                System.out.println("Odd: " + i);
                printOdd = false;
                lock.notify();
            }
        }
    }

    public void printEven(int max) {
        for (int i = 2; i <= max; i += 2) {
            synchronized (lock) {
                while (printOdd) {
                    try { lock.wait(); } catch (InterruptedException e) {}
                }
                System.out.println("Even: " + i);
                printOdd = true;
                lock.notify();
            }
        }
    }
}

9.2 Producer-Consumer with BlockingQueue¶

Java¶

public class ProducerConsumer {
    private final BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);

    public void produce() throws InterruptedException {
        int i = 0;
        while (true) {
            queue.put(i++);     // blocks if full
            System.out.println("Produced: " + (i - 1));
            Thread.sleep(100);
        }
    }

    public void consume() throws InterruptedException {
        while (true) {
            int val = queue.take();   // blocks if empty
            System.out.println("Consumed: " + val);
            Thread.sleep(200);
        }
    }
}

9.3 Thread-safe counter (AtomicInteger vs synchronized)¶

Java¶

// AtomicInteger — preferred
public class CounterAtomic {
    private final AtomicInteger count = new AtomicInteger(0);
    public void increment() { count.incrementAndGet(); }
    public int get() { return count.get(); }
}

// synchronized — fallback
public class CounterSync {
    private int count = 0;
    public synchronized void increment() { count++; }
    public synchronized int get() { return count; }
}

Why AtomicInteger wins: lock-free, uses CAS instructions. Much faster under contention.

9.4 Singleton with double-checked locking¶

Java¶

public class Singleton {
    private static volatile Singleton instance;

    private Singleton() {}

    public static Singleton getInstance() {
        if (instance == null) {
            synchronized (Singleton.class) {
                if (instance == null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

The volatile matters: without it, JVM may publish a partially-constructed object.

9.5 ExecutorService example¶

Java¶

ExecutorService pool = Executors.newFixedThreadPool(4);

List<Future<Integer>> futures = new ArrayList<>();
for (int i = 0; i < 100; i++) {
    int n = i;
    futures.add(pool.submit(() -> n * n));
}

for (Future<Integer> f : futures) {
    System.out.println(f.get());
}

pool.shutdown();
pool.awaitTermination(60, TimeUnit.SECONDS);

9.6 Deadlock example + fix¶

Java (deadlock)¶

Object lock1 = new Object(), lock2 = new Object();

// Thread A
synchronized (lock1) {
    synchronized (lock2) { ... }
}

// Thread B
synchronized (lock2) {
    synchronized (lock1) { ... }
}
// Deadlock — A holds lock1 wants lock2; B holds lock2 wants lock1

Fix: always acquire locks in same order¶

// Both threads:
synchronized (lock1) {
    synchronized (lock2) { ... }
}

10. PATTERN PRINTING¶

10.1 Pyramid of stars¶

   *
  ***
 *****
*******

Java¶

public void pyramid(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < n - i; j++) System.out.print(" ");
        for (int j = 0; j < 2 * i - 1; j++) System.out.print("*");
        System.out.println();
    }
}

Python¶

def pyramid(n):
    for i in range(1, n + 1):
        print(' ' * (n - i) + '*' * (2 * i - 1))

10.2 Pascal's Triangle¶

Java¶

public List<List<Integer>> pascals(int n) {
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) row.add(1);
            else row.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
        }
        result.add(row);
    }
    return result;
}

Python¶

def pascals(n):
    result = [[1]]
    for i in range(1, n):
        row = [1] + [result[i-1][j-1] + result[i-1][j] for j in range(1, i)] + [1]
        result.append(row)
    return result

10.3 Diamond¶

   *
  ***
 *****
  ***
   *

Python¶

def diamond(n):
    for i in range(n):
        print(' ' * (n - i - 1) + '*' * (2 * i + 1))
    for i in range(n - 2, -1, -1):
        print(' ' * (n - i - 1) + '*' * (2 * i + 1))

10.4 Number triangle¶

Python¶

def num_triangle(n):
    for i in range(1, n + 1):
        print(''.join(str(j) for j in range(1, i + 1)))

10.5 Hollow square¶

*****
*   *
*   *
*   *
*****

Python¶

def hollow_square(n):
    for i in range(n):
        if i == 0 or i == n - 1:
            print('*' * n)
        else:
            print('*' + ' ' * (n - 2) + '*')

10.6 FizzBuzz¶

Java¶

public void fizzBuzz(int n) {
    for (int i = 1; i <= n; i++) {
        if (i % 15 == 0) System.out.println("FizzBuzz");
        else if (i % 3 == 0) System.out.println("Fizz");
        else if (i % 5 == 0) System.out.println("Buzz");
        else System.out.println(i);
    }
}

Python¶

def fizz_buzz(n):
    for i in range(1, n + 1):
        s = ('Fizz' if i % 3 == 0 else '') + ('Buzz' if i % 5 == 0 else '')
        print(s or i)

11. TEST DATA GENERATORS / PARSERS¶

11.1 CSV parser¶

Java (basic; for production use Apache Commons CSV)¶

public List<String[]> parseCsv(String content) {
    List<String[]> rows = new ArrayList<>();
    for (String line : content.split("\\r?\\n")) {
        rows.add(line.split(","));
    }
    return rows;
}

Python¶

import csv
from io import StringIO

def parse_csv(content):
    return list(csv.reader(StringIO(content)))

11.2 Generate N random emails¶

Java¶

public List<String> randomEmails(int count) {
    Random r = new Random();
    String[] domains = {"gmail.com", "yahoo.com", "test.com"};
    return IntStream.range(0, count)
        .mapToObj(i -> "user" + System.currentTimeMillis() + i
            + "@" + domains[r.nextInt(domains.length)])
        .collect(Collectors.toList());
}

Python¶

import random
import time

def random_emails(count):
    domains = ['gmail.com', 'yahoo.com', 'test.com']
    return [f'user{int(time.time())}_{i}@{random.choice(domains)}' for i in range(count)]

11.3 Generate fake user POJO (Faker)¶

Java (use `com.github.javafaker:javafaker`)¶

import com.github.javafaker.Faker;
Faker faker = new Faker();
String name = faker.name().fullName();
String email = faker.internet().emailAddress();
String address = faker.address().fullAddress();

Python¶

from faker import Faker
fake = Faker()
print(fake.name(), fake.email(), fake.address())

11.4 Read JSON file into POJO¶

Java (Jackson)¶

ObjectMapper mapper = new ObjectMapper();
User user = mapper.readValue(new File("user.json"), User.class);

Python¶

import json
with open('user.json') as f:
    user = json.load(f)

11.5 Flatten nested JSON¶

Python¶

def flatten(d, parent='', sep='.'):
    items = []
    for k, v in d.items():
        new_key = f"{parent}{sep}{k}" if parent else k
        if isinstance(v, dict):
            items.extend(flatten(v, new_key, sep).items())
        else:
            items.append((new_key, v))
    return dict(items)

# Input: {"a": {"b": {"c": 1}}, "d": 2}
# Output: {"a.b.c": 1, "d": 2}

11.6 Log parser — extract error lines¶

Java¶

public List<String> errorLines(String logContent) {
    return Arrays.stream(logContent.split("\\r?\\n"))
        .filter(line -> line.toUpperCase().contains("ERROR"))
        .collect(Collectors.toList());
}

Python¶

def error_lines(content):
    return [line for line in content.splitlines() if 'ERROR' in line.upper()]

11.7 Count word occurrences from a file¶

Python¶

from collections import Counter

def word_count_file(path):
    with open(path) as f:
        words = f.read().lower().split()
    return Counter(words).most_common()

12. LINKED LISTS BASICS¶

12.1 Reverse linked list¶

Java¶

class Node {
    int val;
    Node next;
    Node(int val) { this.val = val; }
}

public Node reverse(Node head) {
    Node prev = null, curr = head;
    while (curr != null) {
        Node next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

12.2 Detect cycle (Floyd's)¶

Java¶

public boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

12.3 Find middle node¶

Java¶

public Node findMiddle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

12.4 Merge two sorted linked lists¶

Java¶

public Node merge(Node a, Node b) {
    Node dummy = new Node(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    return dummy.next;
}

12.5 Remove duplicates from sorted linked list¶

Java¶

public Node removeDuplicates(Node head) {
    Node curr = head;
    while (curr != null && curr.next != null) {
        if (curr.val == curr.next.val) {
            curr.next = curr.next.next;
        } else {
            curr = curr.next;
        }
    }
    return head;
}

13. MINI CHEAT-SHEET — WHAT TO REMEMBER¶

Top 10 SQL queries¶

Second highest salary (8.1)
Duplicate emails (8.3)
Employees > manager salary (8.5)
Top 3 salaries per dept (8.8)
Customers who never ordered (8.9)
Delete duplicates keep one (8.4)
INNER vs LEFT join scenarios (8.15)
Pivot rows to columns (8.12)
Most recent per group (8.14)
Nth highest salary (8.2)

How to approach a coding question in 5 steps¶

Restate the problem in your own words; ask 1-2 clarifying questions
Walk through an example to confirm understanding
State the brute force with complexity, then propose an optimization
Code it (talk through as you write)
Trace through with the example; mention edge cases (empty, null, negative, max-int)

Five lines that signal seniority in coding rounds¶

"Let me clarify — should I handle null/empty input?"
"The brute force is O(N²); can I trade space for time with a HashMap?"
"Let me trace through with [1, 2, 3]..."
"Edge cases I'd test: empty array, single element, all duplicates, negative numbers."
"In production I'd add input validation; for this interview I'm focusing on the algorithm."

Owner: Rohan Dsouza | Complement to: 01_DSA_Patterns.md (FAANG-tier algorithmic patterns) | Updated: 2026