Coding round in Java

How to run the round

1. Restate the problem and confirm input/output with an example.
2. Ask: size of input, duplicates, negatives, empty input, sorted?
3. Say the brute force and its complexity.
4. Improve: which pattern fits? Say the new complexity before coding.
5. Code cleanly, naming things well.
6. Test out loud with the example and one edge case; fix bugs calmly.

Patterns to recognise

Signal in the problem	Pattern	Example
Find pairs / complements, counts	HashMap	Two sum, anagrams, first unique
Sorted array, pairs, in-place	Two pointers	Pair with sum, remove duplicates, container with most water
Contiguous subarray/substring with a condition	Sliding window	Longest substring without repeats, max sum of size k
Top / smallest k, streaming	Heap (PriorityQueue)	Top-k frequent, k closest, merge k lists
Sorted input, "minimum that satisfies"	Binary search	Search rotated array, first bad version
Shortest path in unweighted grid/graph	BFS	Number of islands, word ladder
All combinations / paths	DFS / backtracking	Subsets, permutations
Matching brackets, next greater	Stack	Valid parentheses, daily temperatures
Overlapping intervals	Sort by start	Merge intervals, meeting rooms
Optimal over choices with overlap	Dynamic programming	Climbing stairs, coin change, LCS

Must-know solutions

Two sum (HashMap, O(n))

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

Longest substring without repeating characters (sliding window, O(n))

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

LRU cache (asked very often)

// Short version: LinkedHashMap in access order
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LRUCache(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
}

If they want it by hand: a HashMap<K, Node> plus a doubly linked list; get moves the node to the head, put inserts at the head and evicts the tail when full; both O(1). Thread-safe version: wrap with a lock, or use Caffeine in real code.

Top-k frequent elements (heap, O(n log k))

List<Integer> topK(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int n : nums) count.merge(n, 1, Integer::sum);
    PriorityQueue<Map.Entry<Integer, Integer>> heap =
        new PriorityQueue<>(Map.Entry.comparingByValue()); // min-heap by count
    for (var e : count.entrySet()) {
        heap.offer(e);
        if (heap.size() > k) heap.poll();
    }
    List<Integer> out = new ArrayList<>();
    while (!heap.isEmpty()) out.add(heap.poll().getKey());
    Collections.reverse(out);
    return out;
}

Valid parentheses (stack)

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        switch (c) {
            case '(' -> stack.push(')');
            case '[' -> stack.push(']');
            case '{' -> stack.push('}');
            default -> { if (stack.isEmpty() || stack.pop() != c) return false; }
        }
    }
    return stack.isEmpty();
}

Merge intervals (sort, O(n log n))

int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    List<int[]> out = new ArrayList<>();
    for (int[] cur : intervals) {
        if (out.isEmpty() || out.get(out.size() - 1)[1] < cur[0]) out.add(cur);
        else out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], cur[1]);
    }
    return out.toArray(new int[0][]);
}

Number of islands (BFS/DFS on a grid)

int numIslands(char[][] g) {
    int count = 0;
    for (int r = 0; r < g.length; r++)
        for (int c = 0; c < g[0].length; c++)
            if (g[r][c] == '1') { count++; sink(g, r, c); }
    return count;
}
void sink(char[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0';
    sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
}

Reverse a linked list

ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; }
    return prev;
}

Binary search (first index ≥ target)

int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;           // search in [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;    // avoids overflow
        if (a[mid] < target) lo = mid + 1; else hi = mid;
    }
    return lo;
}

Max profit from one buy and one sell (finance favourite)

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

Mini order book (a domain twist they might give you)

// Price-time priority with TreeMaps of FIFO queues. Prices as long (paise), never double.
record Order(long id, boolean buy, long price, long qty) {}

final class OrderBook {
    private final TreeMap<Long, ArrayDeque<long[]>> bids = new TreeMap<>(Comparator.reverseOrder());
    private final TreeMap<Long, ArrayDeque<long[]>> asks = new TreeMap<>();

    /** Returns trades as {buyId, sellId, price, qty}. long[] = {id, remainingQty}. */
    List<long[]> submit(Order o) {
        List<long[]> trades = new ArrayList<>();
        TreeMap<Long, ArrayDeque<long[]>> opposite = o.buy() ? asks : bids;
        long remaining = o.qty();
        while (remaining > 0 && !opposite.isEmpty()) {
            var best = opposite.firstEntry();
            boolean crosses = o.buy() ? best.getKey() <= o.price() : best.getKey() >= o.price();
            if (!crosses) break;
            ArrayDeque<long[]> queue = best.getValue();
            long[] resting = queue.peekFirst();
            long fill = Math.min(remaining, resting[1]);
            trades.add(o.buy() ? new long[] {o.id(), resting[0], best.getKey(), fill}
                               : new long[] {resting[0], o.id(), best.getKey(), fill});
            remaining -= fill;
            resting[1] -= fill;
            if (resting[1] == 0) queue.pollFirst();
            if (queue.isEmpty()) opposite.pollFirstEntry();
        }
        if (remaining > 0) {
            (o.buy() ? bids : asks).computeIfAbsent(o.price(), p -> new ArrayDeque<>())
                                   .addLast(new long[] {o.id(), remaining});
        }
        return trades;
    }
}

Then mention: "In Prayog, cancel is O(1) because each order is a node in an intrusive linked list with an index from order id; an ArrayDeque would make cancel O(n)."

Complexity cheat sheet

Structure	Access	Search	Insert	Delete
Array / ArrayList	O(1)	O(n)	O(1) amortised at end, O(n) middle	O(n)
HashMap / HashSet	–	O(1) avg	O(1) avg	O(1) avg
TreeMap / TreeSet	–	O(log n)	O(log n)	O(log n)
PriorityQueue	O(1) peek	O(n)	O(log n)	O(log n) poll
ArrayDeque	O(1) ends	O(n)	O(1) ends	O(1) ends
Sorting			O(n log n)