Coding Round Problems

Find the middle with slow and fast pointers, reverse the second half in place, compare it with the first half, then reverse it back to restore the list. Copying into an array is O(n) space; recursion is O(n) stack.

class ListNode { int val; ListNode next; ListNode(int v) { val = v; } }

static boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode second = reverse(slow.next);
    boolean ok = true;
    for (ListNode a = head, b = second; b != null; a = a.next, b = b.next)
        if (a.val != b.val) { ok = false; break; }
    slow.next = reverse(second); // restore
    return ok;
}
static ListNode reverse(ListNode h) {
    ListNode prev = null;
    while (h != null) { ListNode n = h.next; h.next = prev; prev = h; h = n; }
    return prev;
}

Pass an allowed (low, high) range down the recursion; every node must lie strictly inside the range inherited from all its ancestors. Checking only left.val < node.val < right.val is wrong because a deep node can violate an ancestor.

class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }

static boolean isBst(TreeNode n, long low, long high) {
    if (n == null) return true;
    if (n.val <= low || n.val >= high) return false;
    return isBst(n.left, low, n.val) && isBst(n.right, n.val, high);
}
// isBst(root, Long.MIN_VALUE, Long.MAX_VALUE)

Time O(n), space O(h). An in-order traversal being strictly increasing is an equivalent test.

Use two pointers with backtracking to the last *: on a mismatch, retry from just after the star and let the star consume one more character. This is O(nm) worst case with O(1) space; the DP table version is O(nm) space.

static boolean match(String s, String p) {
    int i = 0, j = 0, star = -1, mark = 0;
    while (i < s.length()) {
        if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) { i++; j++; }
        else if (j < p.length() && p.charAt(j) == '*') { star = j++; mark = i; }
        else if (star != -1) { j = star + 1; i = ++mark; }
        else return false;
    }
    while (j < p.length() && p.charAt(j) == '*') j++;
    return j == p.length();
}

match("AMBAZOKN", "AM*AZO?N*") is true; match("AMAZON", "AM*AZO?N*") is false because nothing remains for ? plus N.

Scan once while tracking the lowest price seen so far and the best profit if you sold today. O(n) time, O(1) space.

static int[] bestTrade(int[] p) {          // returns {buyDay, sellDay, profit}
    int minDay = 0, buy = 0, sell = 0, best = 0;
    for (int i = 1; i < p.length; i++) {
        if (p[i] < p[minDay]) minDay = i;
        if (p[i] - p[minDay] > best) { best = p[i] - p[minDay]; buy = minDay; sell = i; }
    }
    return new int[] { buy, sell, best };
}

For [7, 1, 5, 3, 6, 4] the result is buy day 1, sell day 4, profit 5. If prices only fall, profit is 0 and no trade is made.

Keep the current head of each list in a min-heap, repeatedly pop the smallest, append it and push its successor. Time O(N log k) for N total nodes, extra space O(k), and nodes are relinked in place.

static ListNode mergeK(List<ListNode> lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(Comparator.comparingInt(n -> n.val));
    for (ListNode h : lists) if (h != null) pq.add(h);
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!pq.isEmpty()) {
        ListNode n = pq.poll();
        tail.next = n; tail = n;
        if (n.next != null) pq.add(n.next);
    }
    return dummy.next;
}

Scan every cell; on an unvisited 1, run a DFS that counts connected cells and marks them visited. Each cell is visited once: O(rows*cols) time.

static int largestIsland(int[][] g) {
    int best = 0;
    for (int r = 0; r < g.length; r++)
        for (int c = 0; c < g[0].length; c++)
            if (g[r][c] == 1) best = Math.max(best, dfs(g, r, c));
    return best;
}
static int dfs(int[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != 1) return 0;
    g[r][c] = 2; // visited
    return 1 + dfs(g, r + 1, c) + dfs(g, r - 1, c) + dfs(g, r, c + 1) + dfs(g, r, c - 1);
}

dp[i] is true if the first i characters can be segmented; it is true when some j < i has dp[j] true and s[j..i) is in the dictionary. A trie on its own does not solve it, because greedy longest-match fails.

static boolean wordBreak(String s, Set<String> dict) {
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++)
        for (int j = 0; j < i; j++)
            if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
    return dp[s.length()];
}

wordBreak("applepenapple", Set.of("apple", "pen")) is true. Cost is O(n^2) substring checks; bound j by the longest dictionary word to cut it down.

Store values in an ArrayList for O(1) random access, and a HashMap from value to index. To delete, swap the target with the last element, update that element's index, then remove the tail.

class RandomizedSet {
    private final List<Integer> vals = new ArrayList<>();
    private final Map<Integer, Integer> pos = new HashMap<>();
    private final Random rnd = new Random();

    boolean insert(int v) {
        if (pos.containsKey(v)) return false;
        pos.put(v, vals.size()); vals.add(v); return true;
    }
    boolean remove(int v) {
        Integer i = pos.remove(v);
        if (i == null) return false;
        int last = vals.remove(vals.size() - 1);
        if (i < vals.size()) { vals.set(i, last); pos.put(last, i); }
        return true;
    }
    int getRandom() { return vals.get(rnd.nextInt(vals.size())); }
}