Master Multi‑Round Interview Coding: Parsing, Concurrency, and Matrix Multiplication

Round 1: String‑to‑Int Parsing

The first interview task asks for converting a given string to an integer. The solution must handle null or empty input, trim whitespace, detect optional sign characters, validate digit characters, and detect overflow. The implementation returns -1 on any failure instead of throwing an exception.

public int myAtoi(String str) {
    if (str == null || str.length() == 0) {
        return -1;
    }
    str = str.trim();
    if (str.length() == 0) {
        return -1;
    }
    int res = 0, len = str.length();
    boolean positive = true;
    if (str.charAt(0) == '+') {
        positive = true;
        if (len == 1) return -1;
    } else if (str.charAt(0) == '-') {
        positive = false;
        if (len == 1) return -1;
    } else if (str.charAt(0) >= '0' && str.charAt(0) <= '9') {
        res = str.charAt(0) - '0';
    } else {
        return -1;
    }
    for (int i = 1; i < str.length(); i++) {
        char c = str.charAt(i);
        if (c >= '0' && c <= '9') {
            if (res > Integer.MAX_VALUE / 10) {
                return -1;
            }
            res = res * 10 + (c - '0');
        } else {
            return -1;
        }
    }
    return positive ? res : -res;
}

Key corner cases include null/empty strings, strings containing only a sign, non‑digit characters, and integer overflow.

Round 2: High‑Concurrency Trace‑Storage API

The second round requires designing an interface that can insert and retrieve trace data under high concurrency. The core idea is to store all trace objects in a ConcurrentHashMap. Simple put/get operations are thread‑safe, but updates to a trace may need additional locking to avoid race conditions.

To further improve scalability, the design hashes the incoming key and distributes entries across multiple ConcurrentHashMap instances, reducing contention on any single map.

Round 3: Matrix Multiplication and Optimizations

The third task asks for a matrix multiplication implementation and a brief description of test cases. The provided code validates input dimensions, allocates the result matrix, and performs the classic triple‑nested loop. It also notes the need to handle integer overflow.

public class Matrix {
    public int[][] multiply(int[][] a, int[][] b) throws Exception {
        // validation
        if (a.length == 0 || a[0].length == 0 || b.length == 0 || b[0].length == 0) {
            throw new Exception("invalid input");
        }
        if (a[0].length != b.length) {
            throw new Exception("dimension mismatch");
        }
        int[][] c = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                int sum = 0;
                for (int k = 0; k < b.length; k++) {
                    sum += a[i][k] * b[k][j]; // overflow handling omitted for brevity
                }
                c[i][j] = sum;
            }
        }
        return c;
    }
}
// Test ideas:
// 1. Empty arrays
// 2. Non‑rectangular matrices
// 3. Overflow cases
// 4. 1×m and m×1 matrices (initially missed)
// 5. Small dimensions
// 6. Very large dimensions

During the interview the candidate missed the special case of multiplying a 1×m matrix with an m×1 matrix because no dedicated matrix class was created.

Performance improvements:

Since matrix b is accessed column‑wise, cache misses are frequent. Transposing b beforehand allows row‑wise access during multiplication, improving CPU cache utilization.

Loop unrolling or using parallel streams can further reduce runtime for large matrices.

For high‑dimensional sparse matrices, the article suggests storing only non‑zero entries as triples (row, column, value) and using auxiliary arrays for quick access:

typedef struct NODE{ // sparse matrix node
    int j;      // column index
    int data;   // value
} Node;

typedef struct MATRIX{ // sparse matrix container
    int mu, nu, tu; // rows, columns, non‑zero count
    Node matrix[MAXSIZE+1];
    int rpos[MAXR+1];
} Matrix;

Multiplication of sparse matrices can then be performed by iterating over non‑zero entries only, dramatically reducing computational work.