Common Interview Problem Patterns Questions

def max_events_in_window(timestamps, window_size_seconds):
    """
    timestamps: sorted list of ints/floats (seconds since epoch)
    window_size_seconds: positive number (inclusive window length)
    Returns the maximum number of timestamps within any window of length window_size_seconds.
    """
    if not timestamps or window_size_seconds < 0:
        return 0

    left = 0
    max_count = 0
    for right, t in enumerate(timestamps):
        # Move left forward while the current window is larger than allowed.
        # We treat window as inclusive: events with timestamps >= t - window_size_seconds are inside.
        min_allowed = t - window_size_seconds
        while left <= right and timestamps[left] < min_allowed:
            left += 1
        # Count is right - left + 1
        curr_count = right - left + 1
        if curr_count > max_count:
            max_count = curr_count

    return max_count

from bisect import bisect_left

def lis_length(nums):
    """
    Returns length of Longest Increasing Subsequence in O(n log n) time.
    Uses tails array + binary search (patience sorting idea).
    """
    if not nums:
        return 0

    tails = []  # tails[i] = smallest tail of all increasing subseqs of length i+1
    for x in nums:
        # find leftmost index where tails[idx] >= x
        idx = bisect_left(tails, x)
        if idx == len(tails):
            tails.append(x)   # extend largest subsequence
        else:
            tails[idx] = x    # improve existing subsequence tail
    return len(tails)

from collections import deque

class MovingAverage:
    def __init__(self, k):
        """
        Sliding-window moving average of window size k.
        """
        if k <= 0:
            raise ValueError("Window size k must be > 0")
        self.k = k
        self.window = deque()     # store last up to k values
        self.sum = 0.0

    def add(self, val):
        """
        Add a numeric observation and return current window average.
        """
        self.window.append(val)
        self.sum += val
        # If window exceeds size k, pop oldest and adjust sum
        if len(self.window) > self.k:
            oldest = self.window.popleft()
            self.sum -= oldest
        return self.sum / len(self.window)

# pseudocode
ema = None
alpha = 2 / (k + 1)
def add(x):
    nonlocal ema
    ema = x if ema is None else alpha * x + (1 - alpha) * ema
    return ema

from collections import Counter
import heapq

def top_k_ips(logs, k):
    """
    logs: iterable of strings, each containing an IP (assume IP is the token at position 0 or extractable)
    Returns list of (ip, count) sorted by descending count.
    """
    # Count frequencies (works if counts fit in memory)
    cnt = Counter()
    for line in logs:
        ip = line.split()[0]  # adjust extraction as needed
        cnt[ip] += 1

    # Use heap to get top k in O(n log k)
    heap = []
    for ip, c in cnt.items():
        if len(heap) < k:
            heapq.heappush(heap, (c, ip))
        else:
            if c > heap[0][0]:
                heapq.heapreplace(heap, (c, ip))

    # return sorted descending
    return sorted([(ip, c) for c, ip in heap], key=lambda x: -x[1])  # careful: want by count

# Correct sorting (count desc)
def top_k_ips_correct(logs, k):
    cnt = Counter()
    for line in logs:
        ip = line.split()[0]
        cnt[ip] += 1
    heap = []
    for ip, c in cnt.items():
        if len(heap) < k:
            heapq.heappush(heap, (c, ip))
        else:
            if c > heap[0][0]:
                heapq.heapreplace(heap, (c, ip))
    return sorted([(ip, c) for c, ip in heap], key=lambda x: -x[1])