PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • Apple
  • Coding & Algorithms
  • Software Engineer

Implement rotation, LRU cache, streaming median, cycle detection

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

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.

Quick Answer: 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.

Rotate Image 90 Degrees Clockwise (In Place)

Given an n x n integer matrix `matrix` representing an image, rotate the image by 90 degrees clockwise. You must rotate the image in place, modifying the input matrix directly using O(1) extra space — do not allocate another 2D matrix. Return the rotated matrix. The rotation works by processing the matrix in concentric square rings (layers) from the outside in. Within each ring, elements are cycled four at a time: top -> right -> bottom -> left. For position (i, j) on the top edge, the four positions that swap together are (i, j), (n-1-j, i), (n-1-i, n-1-j), and (j, n-1-i). Edge cases: a 1x1 matrix is unchanged; an empty matrix returns an empty list; even and odd n are both handled because the inner loop runs over j in [i, n-1-i).

Constraints

  • matrix is square: len(matrix) == len(matrix[i]) for all i (n x n).
  • 0 <= n <= 100.
  • Elements are arbitrary 32-bit integers (may be negative).
  • Must mutate the input in place using O(1) extra space.

Examples

Input: ([[1,2,3],[4,5,6],[7,8,9]],)

Expected Output: [[7,4,1],[8,5,2],[9,6,3]]

Explanation: Standard 3x3 rotation: the first column (1,4,7) becomes the first row reversed (7,4,1).

Input: ([[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]],)

Expected Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Explanation: 4x4 case exercises two concentric rings (outer and inner).

Input: ([[1]],)

Expected Output: [[1]]

Explanation: A 1x1 matrix has no layers to rotate, so it is unchanged.

Input: ([[1,2],[3,4]],)

Expected Output: [[3,1],[4,2]]

Explanation: Smallest non-trivial even case: a single four-cell cycle.

Input: ([],)

Expected Output: []

Explanation: Empty matrix: n=0, no work, returns empty.

Hints

  1. Process the matrix in concentric layers/rings from outside to inside; there are n//2 layers.
  2. For each layer, rotate groups of four cells at once using one temporary variable: top -> right -> bottom -> left.
  3. The four indices that cycle for offset (i, j) are (i, j), (n-1-j, i), (n-1-i, n-1-j), and (j, n-1-i).
  4. An alternative O(1) approach is transpose-then-reverse-each-row, but the four-way layer swap avoids the second pass.

LRU Cache (get / put with Eviction)

Design an in-memory cache with a fixed `capacity` that supports two operations in O(1) average time: - put(key, value): insert or update the value for key. If inserting a new key exceeds capacity, evict the least recently used (LRU) entry first. - get(key): return the value for key, or -1 if the key is not present. A get counts as a use and refreshes recency. Both get and put mark the touched key as most-recently-used. To make this executable in the harness, `solution(capacity, operations)` replays a list of operations and returns the list of results produced by every `get`. Each operation is `['put', key, value]` or `['get', key]`. The function returns the get results in order. Real-world design notes: a production LRU uses a hash map (key -> node) plus a doubly linked list ordering nodes by recency, giving O(1) lookup, move-to-front, and tail eviction. For concurrency, guard the structure with a lock (or shard the cache and lock per shard) since the map and list must be mutated atomically together. For TTL, store an expiry timestamp on each node and treat an expired entry as a miss (lazily evicting it on access, optionally with a background sweeper). The reference implementation uses Python's OrderedDict, where move_to_end and popitem(last=False) provide the same O(1) recency operations.

Constraints

  • 1 <= capacity <= 10^4.
  • Keys and values fit in 32-bit integers.
  • get on an absent key returns -1.
  • put on an existing key updates the value and refreshes recency.
  • 0 <= number of operations <= 10^5.

Examples

Input: (2, [['put',1,1],['put',2,2],['get',1],['put',3,3],['get',2],['put',4,4],['get',1],['get',3],['get',4]])

Expected Output: [1, -1, -1, 3, 4]

Explanation: Capacity 2. get(1)=1 (refreshes 1); put(3) evicts 2; get(2)=-1; put(4) evicts 1; get(1)=-1; get(3)=3; get(4)=4.

Input: (1, [['put',2,1],['get',2],['put',3,2],['get',2],['get',3]])

Expected Output: [1, -1, 2]

Explanation: Capacity 1: put(3) evicts key 2, so get(2)=-1 and get(3)=2.

Input: (2, [['get',1]])

Expected Output: [-1]

Explanation: Reading from an empty cache returns -1.

Input: (2, [['put',1,1],['put',1,10],['get',1]])

Expected Output: [10]

Explanation: put on an existing key updates the stored value to 10.

Input: (3, [['put',1,1],['put',2,2],['put',3,3],['get',1],['put',4,4],['get',2],['get',1],['get',3],['get',4]])

Expected Output: [1, -1, 1, 3, 4]

Explanation: get(1) makes 1 most-recent, so the next insert (4) evicts the LRU key 2; get(2)=-1, get(1)=1 survives.

Hints

  1. Combine a hash map (key -> node) with a doubly linked list ordering nodes from most- to least-recently used.
  2. On get/put of an existing key, move its node to the most-recently-used end.
  3. When size exceeds capacity after an insert, remove the node at the least-recently-used end and delete it from the map.
  4. Python's OrderedDict gives O(1) move_to_end and popitem(last=False), making it a clean stand-in for the map + linked list.
  5. For thread safety, protect the map+list mutations with a single lock; for TTL, store an expiry per entry and treat expired entries as misses.

Streaming Median (add / median)

Build a data structure over a stream of integers that supports: - add(num): insert a number, in O(log n) time. - median(): return the median of all numbers seen so far, in O(1) time. The median is the middle value when the count is odd, and the average of the two middle values when the count is even. The classic approach maintains two heaps that partition the data into a lower half and an upper half: - a max-heap `lo` holding the smaller half (its top is the largest of the small numbers), - a min-heap `hi` holding the larger half (its top is the smallest of the large numbers). After each add, rebalance so the heaps differ in size by at most one, with `lo` allowed to hold the extra element. Then the median is `lo.top()` when sizes differ, or the average of `lo.top()` and `hi.top()` when sizes are equal. Both tops are O(1), and rebalancing is a constant number of O(log n) heap operations. To make this executable, `solution(operations)` replays a list of operations and returns the list of `median()` results. Each operation is `['add', num]` or `['median']`. Medians are returned as floats; a median() on an empty stream returns None.

Constraints

  • Numbers are integers (may be negative); medians can be non-integer (.5) for even counts.
  • median() on an empty stream returns None.
  • Insertion must be O(log n); median retrieval must be O(1).
  • 0 <= number of operations <= 10^5.

Examples

Input: ([['add',1],['add',2],['median'],['add',3],['median']],)

Expected Output: [1.5, 2.0]

Explanation: After 1,2 the median is (1+2)/2 = 1.5; after adding 3 the median is the middle value 2.0.

Input: ([['add',5],['median'],['add',15],['median'],['add',1],['median'],['add',3],['median']],)

Expected Output: [5.0, 10.0, 5.0, 4.0]

Explanation: Running medians of 5; 5,15; 5,15,1; 5,15,1,3 — i.e. 5.0, 10.0, 5.0, then (3+5)/2 = 4.0.

Input: ([['median']],)

Expected Output: [None]

Explanation: Querying the median before any add returns None.

Input: ([['add',-1],['add',-2],['add',-3],['median']],)

Expected Output: [-2.0]

Explanation: Negatives are handled normally; the middle of -1,-2,-3 is -2.0.

Input: ([['add',2],['add',2],['add',2],['add',2],['median']],)

Expected Output: [2.0]

Explanation: Duplicates: median of four 2's is (2+2)/2 = 2.0.

Hints

  1. Keep two heaps: a max-heap for the lower half and a min-heap for the upper half.
  2. In Python, simulate a max-heap by pushing negated values into a min-heap (heapq).
  3. After each add, rebalance so |len(lo) - len(hi)| <= 1, keeping the extra element in lo.
  4. If counts are equal the median is the average of the two heap tops; otherwise it is the top of the larger heap.
  5. Both heap tops are O(1), so median() is O(1); only add() pays the O(log n) heap cost.

Detect Cycle in a Directed Graph

Given a directed graph with `n` nodes labeled 0..n-1 and a list of directed `edges` (each `[u, v]` means an edge from u to v), determine whether the graph contains a cycle. Return True if any cycle exists, otherwise False. Use DFS with three-color marking: - WHITE: unvisited, - GRAY: in the current DFS recursion stack (being processed), - BLACK: fully processed. During DFS, encountering an edge to a GRAY node means we found a back edge to an ancestor on the current path — that is a cycle. A self-loop (u -> u) is a cycle. After exploring all out-edges of a node, color it BLACK. For directed graphs you must track the recursion stack (GRAY), because a node reachable by two different forward paths is not a cycle. For undirected graphs the rule differs: you instead check whether DFS reaches an already-visited neighbor that is not the immediate parent (a back edge), since the same edge can be traversed both ways.

Constraints

  • 0 <= n <= 10^4 nodes, labeled 0..n-1.
  • Edges are directed; [u, v] means u -> v.
  • A self-loop [u, u] counts as a cycle.
  • Multiple disconnected components must all be checked.
  • Graph may be empty (n = 0 or no edges).

Examples

Input: (4, [[0,1],[1,2],[2,3],[3,1]])

Expected Output: True

Explanation: 1 -> 2 -> 3 -> 1 forms a cycle; DFS hits the GRAY node 1 via the back edge 3 -> 1.

Input: (4, [[0,1],[1,2],[2,3]])

Expected Output: False

Explanation: A simple path with no back edges is acyclic.

Input: (1, [[0,0]])

Expected Output: True

Explanation: A self-loop is a cycle.

Input: (3, [])

Expected Output: False

Explanation: No edges means no cycle.

Input: (2, [[0,1],[1,0]])

Expected Output: True

Explanation: Two nodes pointing at each other form a 2-cycle.

Input: (0, [])

Expected Output: False

Explanation: An empty graph has no cycle.

Hints

  1. Run DFS from every unvisited node to cover disconnected components.
  2. Use three colors: WHITE (unseen), GRAY (on the current recursion stack), BLACK (done).
  3. Finding an edge to a GRAY node is a back edge -> a cycle exists.
  4. Color a node BLACK only after all its out-edges are explored; reaching a BLACK node is not a cycle.
  5. For undirected graphs, instead check for a visited neighbor that is not the immediate parent.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Minimum Cells to Bridge a Magic Grid - Apple (hard)
  • Find Common Prefix Across Strings - Apple (easy)
  • Find Minimum Processing Rate - Apple
  • Compute Earliest Bus Arrival - Apple (medium)
  • Find the Extra Edge - Apple (hard)