Katkat
Back

Implement rotation, LRU cache, streaming median, cycle detection

AppleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of array/matrix manipulation, cache and data structure design, streaming algorithms for median maintenance, and graph theory for cycle detection, with emphasis on algorithmic complexity analysis and handling of edge cases.

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(
  2. extra space.
  3. LRU cache: Design an in-memory cache with capacity cap that supports get(key) and put(key, value) in O(
  4. average time and evicts the least recently used entry. Describe your data structures and how you'd handle concurrency and optional TTL expiration.
  5. 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(
  6. median retrieval. Specify how you handle both odd and even counts.
  7. 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.