Katkat
Back

Solve Digit-Square and Grid BFS Problems

AppleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.