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 Technical Screen 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 Digit-Square and Grid BFS Problems

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Solve the following coding problems. Problem 1: Digit-square convergence Given a positive integer n, repeatedly replace n with the sum of the squares of its decimal digits. Return true if the sequence eventually reaches 1. Return false if the sequence enters a cycle that does not contain 1. Example: - n = 19 - 1^2 + 9^2 = 82 - 8^2 + 2^2 = 68 - 6^2 + 8^2 = 100 - 1^2 + 0^2 + 0^2 = 1 - Return true. Problem 2: Shortest path in a grid You are given a 2D grid where 0 represents an open cell and 1 represents a blocked cell. You are also given a starting cell and a target cell. You may move one step at a time in the four cardinal directions: up, down, left, and right. Return the length of the shortest path from start to target, or -1 if no path exists. Follow-up: Suppose you may convert up to k blocked cells into open cells while traveling. Return the shortest path length under this rule.

Quick Answer: This question evaluates understanding of digit-based state convergence and cycle detection alongside graph traversal and constrained shortest-path search, testing skills in number manipulation, state-space search, and BFS-style exploration.

Part 1: Digit-Square Convergence

Given a positive integer n, repeatedly replace it with the sum of the squares of its decimal digits. Return True if this process eventually reaches 1. Return False if the sequence falls into a cycle that does not include 1.

Constraints

1 <= n <= 2^31 - 1
Only decimal digits are used when forming the next value

Examples

Input: (19,)

Expected Output: True

Explanation: 19 -> 82 -> 68 -> 100 -> 1, so the process converges to 1.

Input: (2,)

Expected Output: False

Explanation: 2 enters the cycle 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4.

Input: (1,)

Expected Output: True

Explanation: Edge case: the sequence already starts at 1.

Input: (7,)

Expected Output: True

Explanation: 7 -> 49 -> 97 -> 130 -> 10 -> 1.

Hints

Write a helper that computes the next number by repeatedly taking the last digit with modulo 10.
If a value repeats before reaching 1, you are in a cycle. A set can detect this.

Part 2: Shortest Path in a Grid

You are given a 2D grid where 0 represents an open cell and 1 represents a blocked cell. You are also given a start cell and a target cell as zero-indexed (row, col) coordinates. You may move one step at a time in the four cardinal directions: up, down, left, and right. Return the length of the shortest path from start to target, or -1 if no such path exists. The path length is the number of moves. For this part, if the start or target cell is blocked, return -1.

Constraints

1 <= rows, cols <= 200
grid[r][c] is either 0 or 1
start and target are valid zero-indexed coordinates inside the grid
For this part, blocked cells cannot be entered

Examples

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

Expected Output: 4

Explanation: One shortest path is right, right, down, down.

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

Expected Output: -1

Explanation: Both possible approaches are blocked, so the target is unreachable.

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

Expected Output: 0

Explanation: Edge case: start and target are the same open cell.

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

Expected Output: -1

Explanation: Edge case: the start cell is blocked and cannot be used in this version.

Hints

Because each move has equal cost, breadth-first search is the standard way to find the shortest path.
Mark a cell visited when you add it to the queue so you do not process it multiple times.

Part 3: Shortest Path in a Grid with Up to k Conversions

You are given a 2D grid where 0 represents an open cell and 1 represents a blocked cell. You are also given a start cell, a target cell, and an integer k. You may move one step at a time in the four cardinal directions. While traveling, you may convert up to k blocked cells into open cells. Stepping onto a blocked cell uses 1 conversion. If the start cell is blocked, occupying it also uses 1 conversion immediately. Return the length of the shortest path from start to target, or -1 if no path exists under these rules. The path length is the number of moves.

Constraints

1 <= rows, cols <= 40
grid[r][c] is either 0 or 1
0 <= k <= rows * cols
start and target are valid zero-indexed coordinates inside the grid
Stepping onto a blocked cell uses 1 conversion; starting on a blocked cell also uses 1 conversion immediately

Examples

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

Expected Output: 2

Explanation: Convert the blocked cell at (0, 1) and move directly across the top row.

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

Expected Output: 6

Explanation: Without any conversions, the path must go around the blocked column.

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

Expected Output: -1

Explanation: Any route from the start to the target requires at least 3 blocked cells to be converted.

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

Expected Output: 2

Explanation: Edge case: the start cell is blocked, so the single conversion is spent immediately, then the path is right and down.

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

Expected Output: 0

Explanation: Edge case: start and target are the same blocked cell. One conversion makes the starting cell usable, and no moves are needed.

Hints

A position alone is not enough state anymore. Reaching the same cell with different numbers of conversions used can lead to different futures.
Use BFS over states like (row, col, conversions_used) because every move still costs exactly 1.

Quick Overview

This question evaluates understanding of digit-based state convergence and cycle detection alongside graph traversal and constrained shortest-path search, testing skills in number manipulation, state-space search, and BFS-style exploration.