Array and String Coding Questions

Arrays and strings make up roughly half of all coding-round questions. These are the problems asked most at product companies, each solved optimally with the pattern named — so you can recognise the next variation.

1. Move all zeroes to the end while keeping the order of other elements.

Pattern: write pointer. Copy non-zero values forward, then fill the rest with zeroes. O(n), in place.

void moveZeroes(int[] a) {
    int w = 0;
    for (int x : a) if (x != 0) a[w++] = x;
    while (w < a.length) a[w++] = 0;
}

2. Product of array except self, without division.

Pattern: prefix and suffix products. First pass stores the product of everything to the left; second pass multiplies by everything to the right. O(n), O(1) extra besides the output.

int[] productExceptSelf(int[] a) {
    int n = a.length;
    int[] res = new int[n];
    res[0] = 1;
    for (int i = 1; i < n; i++) res[i] = res[i - 1] * a[i - 1];
    int right = 1;
    for (int i = n - 1; i >= 0; i--) { res[i] *= right; right *= a[i]; }
    return res;
}

3. Find the majority element (appears more than n/2 times).

Pattern: Boyer–Moore voting. Keep a candidate and a count; matching elements add, others subtract. O(n) time, O(1) space.

int majority(int[] a) {
    int candidate = 0, count = 0;
    for (int x : a) {
        if (count == 0) candidate = x;
        count += (x == candidate) ? 1 : -1;
    }
    return candidate;      // verify with a second pass if a majority is not guaranteed
}

4. Sort an array of 0s, 1s and 2s in one pass.

Pattern: Dutch national flag with three pointers: low (next 0), mid (current), high (next 2). O(n), one pass.

void sortColors(int[] a) {
    int low = 0, mid = 0, high = a.length - 1;
    while (mid <= high) {
        if (a[mid] == 0) swap(a, low++, mid++);
        else if (a[mid] == 1) mid++;
        else swap(a, mid, high--);            // do not advance mid: re-check the swapped value
    }
}

5. Find the longest palindromic substring.

Pattern: expand around centre. Every palindrome has a centre (a character or a gap); expand from each of the 2n−1 centres. O(n²) time, O(1) space.

String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len = Math.max(expand(s, i, i), expand(s, i, i + 1));
        if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; }
    }
    return s.substring(start, end + 1);
}
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;
}

6. Find the minimum window substring containing all characters of t.

Pattern: variable sliding window with counts. Expand right until the window covers t, then shrink left while it still does, tracking the smallest window. O(n).

String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int missing = t.length(), left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
    for (int right = 0; right < s.length(); right++) {
        if (need[s.charAt(right)]-- > 0) missing--;
        while (missing == 0) {
            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
            if (++need[s.charAt(left++)] > 0) missing++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

7. Best time to buy and sell a stock (one transaction).

Pattern: track the minimum so far. For each price, the best profit selling today is price − lowest earlier price. O(n).

int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, best = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);
        best = Math.max(best, p - minPrice);
    }
    return best;
}

8. Rotate an n × n matrix by 90 degrees clockwise in place.

Pattern: transpose, then reverse each row. O(n²) time, O(1) extra space.

void rotate(int[][] m) {
    int n = m.length;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) { int t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t; }
    for (int[] row : m)
        for (int l = 0, r = n - 1; l < r; l++, r--) { int t = row[l]; row[l] = row[r]; row[r] = t; }
}