Oracle·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Oracle SWE interview with a greedy algorithm problem. Nothing too wild, but the question had a subtle edge case that could trip you up if you went in thinking it was straightforward.

Questions Asked (1)

Given an integer n, return the largest number less than or equal to n whose digits are monotone increasing (each digit is less than or equal to the next).

Algorithms & Data Structures

Author's notes

The greedy approach clicked pretty fast: scan from the right, and whenever you see a digit that's smaller than the one before it, decrement the left digit by 1 and set everything to its right to 9.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then propose a greedy algorithm that scans digits from left to right, and when a decrease is found, decrement the previous digit and set all following digits to 9. After the scan, fix any new violations by propagating the decrement leftward, and finally remove leading zeros.

Pro tip: Mention that the greedy approach works because we want the largest number, so we only decrease a digit when forced, and setting subsequent digits to 9 maximizes the value. Also, discuss how to handle large numbers as strings to avoid integer overflow.

1. Clarify and Edge Cases

Ask about constraints (e.g., n up to 10^9 or larger), negative numbers, and single-digit numbers. Confirm that monotone increasing means non-decreasing (each digit ≤ next).

2. Greedy Scan

Convert n to a string or digit array. Scan from left to right; when you find a digit greater than the next, decrement the current digit and set all following digits to 9.

3. Propagate Decrement

After the initial change, the decremented digit might now be less than the previous digit. Propagate the decrement leftward until the sequence is non-decreasing.

4. Remove Leading Zeros

Convert the digit array back to a number, stripping any leading zeros. If the result is empty, return 0.

5. Test and Validate

Test with examples like n=10 (result 9), n=1234 (result 1234), n=332 (result 299), and edge cases like n=0 or n=100.

Key Points to Mention

Greedy algorithm: only decrease a digit when a decrease is detected, and set subsequent digits to 9 to maximize the number.
Time complexity O(d) where d is the number of digits, and space complexity O(d) for the digit array.
Handling large numbers as strings to avoid integer overflow.
Edge cases: n < 10, n with all increasing digits, n with leading zeros after modification.
Proof of correctness: the greedy choice ensures the largest possible number because any smaller choice would yield a smaller result.
Alternative approaches: brute force (inefficient) or dynamic programming (overkill), but greedy is optimal.

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