Whiteboard and Chromebook Coding Proficiency Questions

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root):
    """Level-order -> comma-separated tokens, '#' for null."""
    if not root:
        return ""
    q = deque([root])
    out = []
    while q:
        node = q.popleft()
        if node:
            out.append(str(node.val))
            q.append(node.left)
            q.append(node.right)
        else:
            out.append('#')
    # trim trailing nulls to keep compact
    i = len(out) - 1
    while i >= 0 and out[i] == '#':
        i -= 1
    return ",".join(out[:i+1])

def deserialize(data):
    """Rebuild tree from level-order tokens iteratively."""
    if not data:
        return None
    tokens = data.split(',')
    root = TreeNode(int(tokens[0]))
    q = deque([root])
    i = 1
    while q and i < len(tokens):
        node = q.popleft()
        # left
        if tokens[i] != '#':
            node.left = TreeNode(int(tokens[i]))
            q.append(node.left)
        i += 1
        if i >= len(tokens):
            break
        # right
        if tokens[i] != '#':
            node.right = TreeNode(int(tokens[i]))
            q.append(node.right)
        i += 1
    return root

import java.util.concurrent.*;
import java.util.concurrent.locks.*;

public class LRUCache<K,V> {
    private final int capacity;
    private final ConcurrentHashMap<K, Node> map;
    private final Node head, tail; // sentinels
    private final ReentrantLock lock = new ReentrantLock();

    private class Node {
        final K key;
        V val;
        Node prev, next;
        Node(K k, V v){ key=k; val=v; }
    }

    public LRUCache(int capacity){
        this.capacity = capacity;
        this.map = new ConcurrentHashMap<>();
        head = new Node(null,null);
        tail = new Node(null,null);
        head.next = tail; tail.prev = head;
    }

    public V get(K key){
        Node n = map.get(key);
        if(n==null) return null;
        // try to move to head; acquire lock briefly
        lock.lock();
        try {
            removeNode(n);
            addAfterHead(n);
        } finally { lock.unlock(); }
        return n.val;
    }

    public void put(K key, V value){
        Node existing = map.get(key);
        if(existing!=null){
            // update value and move to head
            existing.val = value;
            lock.lock();
            try {
                removeNode(existing);
                addAfterHead(existing);
            } finally { lock.unlock(); }
            return;
        }
        Node n = new Node(key, value);
        // put in map first to avoid races reading null
        Node prev = map.putIfAbsent(key, n);
        if(prev != null){
            // someone inserted concurrently
            prev.val = value;
            lock.lock();
            try {
                removeNode(prev);
                addAfterHead(prev);
            } finally { lock.unlock(); }
            return;
        }

        lock.lock();
        try {
            addAfterHead(n);
            if(map.size() > capacity){
                Node lru = tail.prev;
                removeNode(lru);
                map.remove(lru.key);
            }
        } finally { lock.unlock(); }
    }

    // internal helpers - caller must hold lock
    private void addAfterHead(Node n){
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
    private void removeNode(Node n){
        if(n.prev!=null){
            n.prev.next = n.next;
            n.next.prev = n.prev;
            n.prev = n.next = null;
        }
    }
}

def search_rotated(nums, target):
    """
    Search target in rotated sorted array. Return index or -1.
    O(log n) time, O(1) space.
    """
    if not nums:
        return -1

    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid

        # If left..mid is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Otherwise mid..right must be sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1