Implement rotation, LRU cache, streaming median, cycle detection

Complete the following coding tasks. For each, provide code, justify time/space complexity, and describe edge cases: 1) Image rotation: Given an n×n integer matrix representing an image, rotate it 90 degrees clockwise in place using only O( 1) extra space. 2) LRU cache: Design an in-memory cache with capacity cap that supports get(key) and put(key, value) in O( 1) average time and evicts the least recently used entry. Describe your data structures and how you'd handle concurrency and optional TTL expiration. 3) 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( 1) median retrieval. Specify how you handle both odd and even counts. 4) 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.