Coding & SQL Sprint
The exact problem mix of TCS NQT, Infosys DSE/SP, Accenture, Cognizant, Wipro and Capgemini: 30 algorithm drills with multi-language solutions, plus the 20 SQL queries that appear in some form in every test.
Two Sum
Given an array and target, return indices of the two numbers adding to the target (exactly one solution).
Approach: Hash map of value → index; for each x check if target−x was seen before.
Complexity: O(n) time, O(n) space. Brute force O(n²) also passes small tests.
- No answer (defensive return)
- Duplicates — store first occurrence only
Trapping Rainwater
Given elevation bars, compute total water trapped between them.
Approach: Two pointers: water at each index = min(maxLeft, maxRight) − height. Move the pointer on the smaller side inward while tracking running maxima.
Complexity: O(n) time, O(1) space (DP prefix-max version is O(n) space).
- Empty/2-bar arrays trap 0
- Monotonic arrays trap 0
- Plateaus (equal heights)
Longest Substring Without Repeating Characters
Length of the longest substring with all distinct characters.
Approach: Sliding window: expand right; on duplicate, shrink left past the previous occurrence (store last index per char).
Complexity: O(n) time, O(min(n, alphabet)) space.
- Empty string → 0
- All-same characters → 1
- Charset beyond ASCII (use map)
Valid Anagram
Check whether two strings are anagrams of each other.
Approach: Count character frequencies of s, subtract t; all counts must end at zero.
Complexity: O(n) time, O(alphabet) space.
- Different lengths → false immediately
- Unicode (use a dict, not a fixed array)
- Case sensitivity per problem statement
Maximum Subarray Sum (Kadane's Algorithm)
Find the contiguous subarray with the largest sum.
Approach: Running sum: extend the current run, or restart at the current element when the running sum goes negative. Track the global best.
Complexity: O(n) time, O(1) space. Divide-and-conquer O(n log n) is the alternative interview narrative.
- All negatives → answer is the largest single element
- All positives → whole array
- Empty array per problem constraints
Next Permutation
Rearrange the array into the next lexicographically greater permutation; if none, sort ascending.
Approach: 1) Find longest non-increasing suffix. 2) If a pivot exists (element before suffix smaller than its next), swap it with the smallest suffix element greater than it. 3) Reverse the suffix.
Complexity: O(n) time, O(1) space.
- Already the largest permutation → full sort
- Single element
- All equal elements
Prime Sieve of Eratosthenes
Print all primes up to N (campus tests ask this constantly, often with prime-count queries).
Approach: Mark multiples of each prime starting from p²; iterate only odd numbers for a small speed-up.
Complexity: O(n log log n) time, O(n) space.
- N < 2 → no primes
- Use long/index types for large N
- Sieve up to sqrt(n) for single-primality checks
GCD & LCM
Compute GCD of two numbers (Euclid) and LCM = a*b/gcd. Campus variants: GCD of an array, reduce fraction a/b.
Approach: Euclid: gcd(a,b) = gcd(b, a mod b) until b == 0.
Complexity: O(log min(a,b)) time, O(1) space.
- Zero: gcd(x,0) = x
- Overflow in a*b — compute a/g*b in 64-bit
- Negative inputs: take absolute values
Power of Two
Check whether n is an exact power of 2.
Approach: Bit trick: n > 0 and (n & (n-1)) == 0 — only one bit set.
Complexity: O(1) time, O(1) space.
- n = 0 and negative n → false
- n = 1 = 2⁰ → true
- Watch the sign bit in 32-bit languages
Fast Exponentiation (power in O(log n))
Compute base^exp (often modulo M) without O(n) multiplication loops.
Approach: Binary exponentiation: square the base, halve the exponent, multiply into the result on set bits.
Complexity: O(log n) multiplications, O(1) space.
- exp = 0 → 1
- Overflow — apply mod at every step
- Negative exponents → modular inverse (state assumption)
Matrix Transpose / Rotate 90°
Transpose an N×N matrix in place; rotate clockwise 90° = transpose + reverse each row.
Approach: Transpose: swap (i,j) ↔ (j,i) for i<j. Rotate CW: transpose then reverse every row.
Complexity: O(n²) time, O(1) space.
- Non-square matrices (transpose needs a new matrix)
- n = 1
- Verify rotation direction (CCW = reverse columns then transpose)
Reverse Words in a String
Reverse the order of words, removing extra spaces: ' hello world ' → 'world hello'.
Approach: Split on whitespace, reverse, join with single spaces.
Complexity: O(n) time, O(n) space (in-place char-array two-pointer version is O(1)).
- Leading/trailing/multiple spaces
- Single word
- Punctuation stays attached to words
Valid Palindrome (alphanumeric only)
Check if a string is a palindrome ignoring case and non-alphanumeric characters.
Approach: Two pointers skip non-alphanumerics; compare lowercased chars.
Complexity: O(n) time, O(1) space.
- Empty/punctuation-only → true
- Mixed case
- Numbers count as characters
First Unique Character
Index of the first non-repeating character, or −1.
Approach: Two passes: count frequencies, then find the first char with count 1.
Complexity: O(n) time, O(alphabet) space.
- No unique char → −1
- Single char string
- Repeated at both ends
Longest Common Prefix
Longest prefix common to all strings in a list.
Approach: Vertical scan: compare character i across all strings; stop at first mismatch or short string.
Complexity: O(S) where S = total characters, O(1) extra space.
- Empty list → ""
- Any empty string → ""
- All strings identical
Remove Duplicates from Sorted Array (in place)
Deduplicate a sorted array in place; return the new length k with the first k elements unique.
Approach: Write-pointer: copy each value only when it differs from the previous kept value.
Complexity: O(n) time, O(1) space.
- Empty array → 0
- All identical → 1
- Must not allocate a new array (campus testers check)
Move Zeroes to End
Shift all zeros to the array's end in place, keeping the relative order of non-zeros.
Approach: Two pointers: write non-zeros forward, fill the rest with zeros.
Complexity: O(n) time, O(1) space, single pass.
- All zeros
- No zeros
- Preserving order is the tested part
Binary Search + first/last occurrence
Search a sorted array in O(log n); campus variants ask first/last occurrence and rotation point.
Approach: Halve the interval on comparison; for first occurrence keep moving left on a hit; overflow-safe mid = l + (r−l)/2.
Complexity: O(log n) time, O(1) space.
- Target absent → −1
- Infinite loop from wrong mid update
- int overflow in mid (use l + (r-l)/2)
Rotate Array by K
Rotate an array right by k steps, in place, in O(n) time.
Approach: Reversal trick: reverse whole array, then reverse first k, then the rest. Normalise k %= n.
Complexity: O(n) time, O(1) space.
- k > n → k %= n
- k = 0 or k = n → unchanged
- n = 1
Majority Element (Boyer–Moore)
Element appearing more than n/2 times, in O(1) space.
Approach: Boyer–Moore voting: keep a candidate; on same element increment, else decrement; on zero, replace. Verify with a second pass if majority isn't guaranteed.
Complexity: O(n) time, O(1) space.
- No majority exists → verify pass returns −1
- Single element
- Two-way tie (no majority)
Fibonacci (iterative, n-th term)
Print the n-th Fibonacci number or first n terms (campus default).
Approach: Iterate two variables — the recursive version without memoisation is the trap they set.
Complexity: O(n) time, O(1) space (naive recursion is exponential).
- n = 0/1 → base cases
- Overflow for n > ~45 in 32-bit (use long)
- Ask if they want the series or the term
Armstrong / Narcissistic Number
A number equal to the sum of its digits each raised to the digit-count power (153 = 1³+5³+3³).
Approach: Count digits, sum digit^count, compare.
Complexity: O(d) where d = digit count.
- Single digits 0–9 are trivially Armstrong
- Count must equal digit length, not fixed 3
- Large inputs → use appropriate integer types
Trailing Zeros in Factorial
Count trailing zeros of n! without computing n!.
Approach: Count factor-of-5 contributions: n/5 + n/25 + n/125 + …
Complexity: O(log₅ n) time, O(1) space.
- n < 5 → 0
- Never compute n! — overflows trivially
- Powers of 5 contribute an extra zero each
Perfect Number / Sum of Divisors
Check whether n equals the sum of its proper divisors (28 = 1+2+4+7+14).
Approach: Iterate divisors only up to √n, adding both i and n/i.
Complexity: O(√n) time — the naive O(n) scan is the expected trap.
- n = 1 → not perfect (sum of proper divisors = 0)
- Perfect squares: don't double-count √n
- Negative/zero inputs rejected
String Compression (a3b2 encoding)
Compress runs: 'aaabbc' → 'a3b2c1' (or 'a3b2c' depending on the paper — clarify!).
Approach: Single scan counting run length; append char+count at run end.
Complexity: O(n) time, O(n) space.
- Return the SHORTER of original/compressed when the paper says so
- Single characters
- Counts > 9 (multi-digit)
Group Anagrams
Group words that are anagrams of each other.
Approach: Key = sorted word (or a 26-letter count signature); group by key in a hash map.
Complexity: O(n·k log k) time (k = word length), O(n·k) space.
- Empty strings
- Case sensitivity per problem
- Unicode letters → count-signature via dict
Merge Intervals
Merge overlapping intervals: [[1,3],[2,6],[8,10]] → [[1,6],[8,10]].
Approach: Sort by start; extend the current interval while the next starts ≤ current end.
Complexity: O(n log n) time (sort), O(n) space.
- Touching intervals [1,4],[4,5] → merge (clarify inclusivity)
- Unsorted input
- Single interval / empty list
Digit Sum & Recursion Drills
Sum of digits recursively; variants: reverse a number, count digits, digital root.
Approach: n%10 + f(n/10) until n == 0. Digital root: repeat until single digit.
Complexity: O(d) per call.
- n = 0 → 0
- Negative numbers: take abs or define per problem
- Tail-recursion depth is fine (≤ 10 digits)
Word Frequency Counter
Count occurrences of each word in a sentence; print sorted by frequency (ties alphabetical).
Approach: Hash map counts → collect pairs → sort by (−count, word).
Complexity: O(n log n) with sort, O(n) with a bucket array.
- Case folding per problem statement
- Punctuation handling
- Empty input
Sort Colors (Dutch National Flag)
Sort an array of 0s, 1s, 2s in one pass, in place.
Approach: Three pointers: low (boundary of 0s), mid (current), high (boundary of 2s). Swap 0s to front, 2s to back, advance mid otherwise.
Complexity: O(n) time, single pass, O(1) space.
- All one colour
- Two colours only
- Don't advance mid after swapping with high
Min & Max in One Scan
Find both minimum and maximum with minimal comparisons (pairwise trick: ~3n/2 comparisons).
Approach: Process elements in pairs: compare pair members first, then compare larger with max and smaller with min.
Complexity: O(n) time with ~3n/2 comparisons, O(1) space.
- Odd length (last element handled alone)
- Single element (min = max)
- All equal values