• Brute force checks every pair — O(n²).
• Optimal: single pass with a HashMap<value, index>. For each number, check if target - number is already in the map — if so, we've found the pair; otherwise store the current number and move on.
• Works in one O(n) pass because we only need to look backward at numbers already seen.

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> index

    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[]{seen.get(complement), i};
        }
        seen.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}
// nums = [2,7,11,15], target = 9 -> [0,1]  (2+7=9)

• Push opening brackets onto a stack as they're encountered.
• On a closing bracket, pop the stack and check that it matches the expected opening bracket. If the stack is empty or it doesn't match — invalid.
• At the end, the string is valid only if the stack is empty (every opener was closed).

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}
// "{[()]}"  -> true
// "([)]"    -> false
// "(("      -> false

• A number is prime if it's greater than 1 and has no divisors other than 1 and itself.
• Only need to check divisibility up to √n — any factor larger than the square root would pair with a smaller factor already checked.
• Skip even numbers after checking 2, to roughly halve the work.

public 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) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

public int firstPrimeAfter(int n) {
    int candidate = n + 1;
    while (!isPrime(candidate)) {
        candidate++;
    }
    return candidate;
}

• Naive recursion recomputes the same sub-values repeatedly — exponential O(2ⁿ) time.
• Iterative approach (two running variables a, b, each step next = a + b) avoids that entirely — O(n) time, O(1) space.
• Test cases should cover the base cases (n=0, n=1) plus a general case verifying the first several terms.

public int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int next = a + b;
        a = b;
        b = next;
    }
    return b;
}

@Test
void fibonacci_baseCase_zero() {
    assertEquals(0, fib.fibonacci(0));
}

@Test
void fibonacci_baseCase_one() {
    assertEquals(1, fib.fibonacci(1));
}

@Test
void fibonacci_generalCase() {
    int[] expected = {0, 1, 1, 2, 3, 5, 8, 13};
    for (int n = 0; n < expected.length; n++) {
        assertEquals(expected[n], fib.fibonacci(n));
    }
}

• At each step, one half of the array (left of mid, or right of mid) is always properly sorted — figure out which one.
• Check if the target falls within that sorted half's value range. If yes, search there; if no, search the other half.
• Repeat until found or the search space is exhausted — still O(log n) because each step halves the range.

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;

        if (nums[left] <= nums[mid]) {              // left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {                                      // right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}
// nums = [4,5,6,7,0,1,2], target = 0 -> index 4

• Because events can arrive out of order, first sort them by timestamp (or insert into a structure that keeps them sorted as they arrive, e.g. a TreeMap<timestamp, latency>).
• Once sorted, this becomes a straightforward sliding-window scan: track the start timestamp of the current "good" run.
• While latency stays under the threshold, keep extending the window and update the max window length seen so far (currentTimestamp - windowStart).
• The moment an SLA violation is hit, the current run ends; the next window starts from the following event's timestamp.

public class LatencyEvent {
    long timestamp;
    long latencyMs;

    public LatencyEvent(long timestamp, long latencyMs) {
        this.timestamp = timestamp;
        this.latencyMs = latencyMs;
    }
}

public long longestSlaWindow(List<LatencyEvent> events, long slaThresholdMs) {
    events.sort(Comparator.comparingLong(e -> e.timestamp));   // handle out-of-order arrival

    long maxWindow = 0;
    long windowStart = -1;
    long lastTimestamp = -1;

    for (LatencyEvent event : events) {
        if (event.latencyMs < slaThresholdMs) {
            if (windowStart == -1) {
                windowStart = event.timestamp;      // start a new compliant window
            }
            maxWindow = Math.max(maxWindow, event.timestamp - windowStart);
            lastTimestamp = event.timestamp;
        } else {
            windowStart = -1;                       // SLA violated -> window resets
        }
    }
    return maxWindow;
}