Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE coding round, one problem the whole time but it had two parts and the second part is where things got real. Part 1 felt manageable, Part 2 (digit DP) is where most people apparently run out of clock.

Questions Asked (1)

Given a definition of a 'Perfect Wake Number' (positive integer with all distinct non-zero digits and no interior digit strictly smaller than both its neighbors), first implement a function to check if a single number qualifies, then count how many such numbers exist in the range [1, n].

Algorithms & Data Structures

Author's notes

Part 1 is basically a linear scan and I got through it fine.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the definition and edge cases, then implement a helper function to check if a number is a Perfect Wake Number by extracting digits and verifying distinctness and the interior digit condition. For counting, consider that the maximum possible number is 987654321 (all digits distinct), so for n beyond that, the count is fixed; for smaller n, you can either iterate with the check or use digit DP to count efficiently.

Pro tip: Mention that the total count of Perfect Wake Numbers is finite (at most 9! = 362880) and can be precomputed, so for large n you can just return the precomputed count. This shows you think about scalability and optimization.

1. Clarify the problem

Restate the definition of a Perfect Wake Number and confirm edge cases: single-digit numbers (trivially qualify), numbers with zero (disqualified), and the maximum possible number (987654321).

2. Implement the check function

Write a function that takes an integer, extracts its digits, checks that all digits are non-zero and distinct, and verifies that no interior digit is strictly smaller than both neighbors.

3. Choose counting strategy

For small n, iterate from 1 to n and apply the check. For large n, use digit DP or precompute all valid numbers (since the maximum is 987654321) and count those ≤ n.

4. Optimize and handle large n

If n ≥ 987654321, return the total count of Perfect Wake Numbers. Otherwise, use the chosen method to count efficiently, possibly with memoization or precomputed list.

5. Test and validate

Test with small ranges, edge cases (n=1, n=9, n=10, n=100), and compare with brute force for small n to ensure correctness.

Key Points to Mention

Definition of Perfect Wake Number: positive integer, all distinct non-zero digits, no interior digit strictly smaller than both neighbors.
Edge cases: single-digit numbers always qualify; numbers containing zero are invalid; maximum possible number is 987654321.
Time complexity: brute force O(n * d) where d is number of digits; digit DP can achieve O(d * states) for large n.
Space complexity: O(1) for check function; O(total valid numbers) for precomputation.
Optimization: precompute all valid numbers (at most 9! = 362880) and sort them for O(log N) queries.
Digit DP approach: count numbers with distinct non-zero digits and no interior local minimum, using state for previous digit and whether current is a local minimum.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.