Solve linked list, grid BFS, and median queries
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given three separate algorithmic tasks.
## 1) Reorder a linked list by odd/even positions
Given the head of a singly linked list, reorder the nodes so that all nodes at **odd indices** come first, followed by all nodes at **even indices** (1-indexed positions). Within the odd group and within the even group, preserve the original relative order.
- **Input:** `head` of a singly linked list
- **Output:** reordered list head
- **Constraints:** O(1) extra space (excluding recursion), O(n) time
Example: `1 -> 2 -> 3 -> 4 -> 5` becomes `1 -> 3 -> 5 -> 2 -> 4`.
## 2) Shortest distance between any two islands (grid variant)
You are given an `m x n` grid of `0/1` where `1` indicates land and `0` indicates water. An **island** is a connected component of `1`s using 4-directional adjacency.
You may convert water cells to land; the “distance” between two islands is the minimum number of `0` cells that must be converted to create a 4-directional land path between them.
Return the **minimum distance over all pairs of distinct islands**.
- **Input:** `grid[m][n]` of `0/1`
- **Output:** integer minimum number of flips
- **Assumptions/constraints:**
- `m, n` up to ~`10^3` (design an efficient approach)
- There are at least 2 islands
## 3) Find the median using a rank-count oracle
There are `N` unknown integers (you do not get direct access to the array). You are given:
- The total count `N`.
- An oracle function `countLessGreater(x)` that returns two integers:
- `L(x)`: how many numbers are **strictly less than** `x`
- `G(x)`: how many numbers are **strictly greater than** `x`
Using only calls to this oracle, find a **median value**.
- If `N` is odd, return the value `m` such that exactly `(N-1)/2` numbers are less than `m` and `(N-1)/2` are greater than `m`.
- If `N` is even, return the **lower median** (the `N/2`-th smallest; 1-indexed).
State any additional assumptions you need (e.g., known bounded integer range), and design an algorithm minimizing the number of oracle queries.
Quick Answer: This multi-part question evaluates proficiency in in-place linked list manipulation, reasoning about shortest connections between connected components in grid graphs, and selection under limited-information rank-count queries, testing algorithmic design, complexity analysis, and data-structure handling in the Coding & Algorithms domain.