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 Take-home Project rounds at Uber.

What role is this question designed for?

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

Find next and closest palindromes | Uber Coding Question

Quick Overview

This question evaluates string-based numeric manipulation and palindrome construction, including edge-case handling (all 9s, single-digit inputs, length changes), candidate generation and magnitude comparison of large numbers as strings, and carry propagation for fixed-length decimal palindromes.

Find next and closest palindromes

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Given a non-negative integer represented as a string n (no leading zeros unless n == "0"), return the smallest palindromic integer strictly greater than n. Return the answer as a string. Aim for O(n) time and O( 1) extra space besides the output. Discuss how you handle edge cases such as all 9s, single-digit inputs, and length changes (e.g., "99" -> "101"). Follow-up A: Modify your solution to return the palindrome (not equal to n) with minimal absolute difference to n; if there is a tie, return the smaller palindrome. Explain which candidate palindromes you generate and how you compare magnitudes without using big-integer libraries. Follow-up B: If the input is a decimal number with a fixed number of fractional digits (e.g., "123.450"), define a palindromic decimal as one where the '.' mirrors itself and the digits mirror across it. Return the smallest palindromic decimal strictly greater than the input under this definition. Describe how you propagate carries across the decimal point and how you preserve the fixed fractional length.

Quick Answer: This question evaluates string-based numeric manipulation and palindrome construction, including edge-case handling (all 9s, single-digit inputs, length changes), candidate generation and magnitude comparison of large numbers as strings, and carry propagation for fixed-length decimal palindromes.

Next Greater Palindrome

Return the smallest palindromic integer string that is strictly greater than n.

Constraints

n is a non-negative integer string with no leading zeros except "0".
The returned palindrome must be strictly greater than n.

Examples

Input: ('12345',)

Expected Output: '12421'

Explanation: Mirroring is too small, so the prefix is incremented.

Input: ('12932',)

Expected Output: '13031'

Explanation: Incrementing the prefix gives the next larger palindrome.

Input: ('99',)

Expected Output: '101'

Explanation: All nines grow the length.

Input: ('8',)

Expected Output: '9'

Explanation: Single non-nine digits increment directly.

Hints

First mirror the left half to the right.
If mirroring is not enough, increment the middle prefix and mirror again.

Closest Palindrome

Return the palindrome not equal to n with the smallest absolute difference; break ties by returning the smaller number.

Constraints

n is a non-negative integer string with no leading zeros except "0".
If two palindromes are equally close, return the smaller numeric value.

Examples

Input: ('123',)

Expected Output: '121'

Explanation: The closest palindrome is below the input.

Input: ('1',)

Expected Output: '0'

Explanation: The closest palindrome not equal to 1 is 0.

Input: ('99',)

Expected Output: '101'

Explanation: The nearest palindrome is 101.

Input: ('1000',)

Expected Output: '999'

Explanation: 999 and 1001 tie, so the smaller one wins.

Hints

Generate palindromes from prefix - 1, prefix, and prefix + 1.
Also include boundary candidates such as 99..9 and 100..001.

Quick Overview