How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Apple.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Apple during technical interviews.

Solve linked list, grid BFS, and median queries

Quick Overview

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.

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.

Part 1: Reorder a Linked List by Odd and Even Positions

Given a singly linked list, reorder its nodes so that all nodes originally at odd 1-indexed positions appear first, followed by all nodes originally at even 1-indexed positions. The relative order inside the odd-position group and inside the even-position group must be preserved. For testability, the linked list is represented as a Python list of values; your function should return the reordered values. Conceptually, this should be solved by rewiring linked-list pointers in-place.

Constraints

0 <= len(values) <= 100000
-10^9 <= values[i] <= 10^9
The intended linked-list algorithm must run in O(n) time.
The intended linked-list algorithm must use O(1) extra space, excluding input/output conversion.

Examples

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

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

Explanation: Odd positions are 1, 3, 5; even positions are 2, 4.

Input: ([],)

Expected Output: []

Explanation: An empty list remains empty.

Input: ([1],)

Expected Output: [1]

Explanation: A single-node list has only an odd-position node.

Input: ([1, 2],)

Expected Output: [1, 2]

Explanation: The odd group is [1] and the even group is [2].

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

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

Explanation: Odd-position values are [2, 3, 6, 7], followed by even-position values [1, 5, 4].

Hints

Maintain two chains: one for odd-position nodes and one for even-position nodes.
Keep a pointer to the head of the even chain so you can attach it after the odd chain at the end.

Part 2: Shortest Distance Between Any Two Islands

You are given an m x n grid containing 0s and 1s. A 1 represents land and a 0 represents water. An island is a connected component of land cells using 4-directional adjacency. You may convert water cells to land. The distance between two distinct islands is the minimum number of water cells that must be converted to create a 4-directional land path between them. Return the minimum such distance over all pairs of distinct islands.

Constraints

1 <= len(grid) <= 1000
1 <= len(grid[0]) <= 1000
grid[r][c] is either 0 or 1
There are at least two islands in the grid.
Connectivity is 4-directional: up, down, left, and right.

Examples

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

Expected Output: 1

Explanation: The single water cell between the two islands must be flipped.

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

Expected Output: 1

Explanation: The two diagonal land cells are separate islands; flipping either adjacent water cell connects them.

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

Expected Output: 2

Explanation: The closest path between the two islands crosses two water cells.

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

Expected Output: 1

Explanation: The two islands in the top row can be connected by flipping the water cell between them.

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

Expected Output: 3

Explanation: The Manhattan distance between the two land cells is 4, so 3 water cells must be flipped.

Hints

First label each island with a unique id.
After labeling, run a multi-source BFS starting from all land cells at once. When BFS frontiers from two different islands meet, you have a candidate answer.

Part 3: Find the Median Using a Rank-Count Oracle

There are N hidden integers. You do not get direct access to the array values. Instead, for any integer x, an oracle countLessGreater(x) returns two values: L(x), the number of hidden integers strictly less than x, and G(x), the number of hidden integers strictly greater than x. Return a median value. If N is odd, return the usual median. If N is even, return the lower median, meaning the N/2-th smallest value using 1-indexing. Assume all hidden integers lie in a known inclusive range [lower_bound, upper_bound]. For testability, this version passes the hidden values into solution so the oracle can be simulated internally; the algorithm should still use only oracle-style rank counts.

Constraints

1 <= len(values) <= 100000
lower_bound <= values[i] <= upper_bound for every i
-10^9 <= lower_bound <= upper_bound <= 10^9
The intended algorithm should make O(log(upper_bound - lower_bound + 1)) oracle queries.
Duplicate values are allowed.

Examples

Input: ([7], 0, 10)

Expected Output: 7

Explanation: With one value, that value is the median.

Input: ([5, 1, 9, 3, 7], 0, 10)

Expected Output: 5

Explanation: Sorted order is [1, 3, 5, 7, 9], so the median is 5.

Input: ([10, 2, 8, 4], 0, 10)

Expected Output: 4

Explanation: Sorted order is [2, 4, 8, 10], so the lower median is the 2nd smallest value, 4.

Input: ([-5, -1, -5, 10, 3, 3], -10, 10)

Expected Output: -1

Explanation: Sorted order is [-5, -5, -1, 3, 3, 10], so the lower median is the 3rd smallest value, -1.

Input: ([4, 4, 4, 4], 0, 10)

Expected Output: 4

Explanation: All values are equal, so the median is 4.

Hints

For a candidate x, the number of values less than or equal to x is N - G(x).
Binary search for the smallest x whose less-than-or-equal count reaches the target median rank.

Quick Overview