Complete the following coding tasks. For each, provide code, justify time/space complexity, and describe edge cases:
-
Image rotation: Given an n×n integer matrix representing an image, rotate it 90 degrees clockwise in place using only O(
-
extra space.
-
LRU cache: Design an in-memory cache with capacity cap that supports get(key) and put(key, value) in O(
-
average time and evicts the least recently used entry. Describe your data structures and how you'd handle concurrency and optional TTL expiration.
-
Streaming median: Build a data structure that supports add(num) and median() queries over a stream of integers, with O(log n) insertion and O(
-
median retrieval. Specify how you handle both odd and even counts.
-
Graph cycle detection: Given a graph expressed as adjacency lists, determine whether it contains a cycle. Provide an algorithm for directed graphs and note how it differs for undirected graphs. Optionally return one example cycle if present.