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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Pinduoduo.

What role is this question designed for?

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

Find Shortest Square-Sum Path | Pinduoduo Coding Question

Q: Find Shortest Square-Sum Path

This question evaluates algorithmic problem-solving skills with number-theoretic reasoning about perfect squares and the ability to reconstruct a minimal-length additive sequence.

Find Shortest Square-Sum Path

Company: Pinduoduo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Given a positive integer `n`, find one shortest path from `0` to `n` where each step adds a perfect square number. Equivalently, return a shortest sequence of perfect square numbers whose sum is exactly `n`. For example, if `n = 12`, one valid shortest sequence is `[4, 4, 4]` because `4 + 4 + 4 = 12`, and no sequence with fewer than 3 perfect squares sums to 12. Requirements: - Return the actual sequence/path, not just the minimum number of steps. - If multiple shortest sequences exist, return any one of them. - You may assume `1 <= n <= 10^4`. Example: ```text Input: n = 13 Output: [4, 9] Explanation: 4 + 9 = 13, and this uses only 2 perfect squares. ```

Quick Answer: This question evaluates algorithmic problem-solving skills with number-theoretic reasoning about perfect squares and the ability to reconstruct a minimal-length additive sequence.

Given a positive integer n, start at 0. In one move, you may add any perfect square number (1, 4, 9, 16, ...) as long as the running total does not exceed n. Return one shortest sequence of perfect squares that takes you from 0 to exactly n. Equivalently, return a shortest list of perfect square numbers whose sum is exactly n. If multiple shortest sequences exist, return any one of them. Example: if n = 12, one valid shortest sequence is [4, 4, 4] because 4 + 4 + 4 = 12, and no sequence with fewer than 3 perfect squares sums to 12.

Constraints

1 <= n <= 10^4
Each chosen value in the returned sequence must be a perfect square
The sum of the returned sequence must be exactly n

Examples

Input: 1

Expected Output: [1]

Explanation: 1 is already a perfect square, so the shortest path uses one step.

Input: 2

Expected Output: [1, 1]

Explanation: The only way to reach 2 is 1 + 1, so the shortest sequence has length 2.

Input: 12

Expected Output: [4, 4, 4]

Explanation: 12 = 4 + 4 + 4, and it cannot be written as the sum of 1 or 2 perfect squares.

Input: 18

Expected Output: [9, 9]

Explanation: 18 = 9 + 9, so the shortest sequence has length 2.

Input: 48

Expected Output: [16, 16, 16]

Explanation: 48 = 16 + 16 + 16, and there is no way to express 48 as the sum of 1 or 2 perfect squares.

Input: 100

Expected Output: [100]

Explanation: 100 is itself a perfect square, so one step is enough.

Hints

Think of each value from 0 to n as a node in a graph. From x, you can go to x + s for every perfect square s such that x + s <= n.
Use BFS to guarantee the fewest number of steps, and store the previous total plus the square used so you can reconstruct the actual path.

Quick Overview

This question evaluates algorithmic problem-solving skills with number-theoretic reasoning about perfect squares and the ability to reconstruct a minimal-length additive sequence.