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.

Hints

  1. First mirror the left half to the right.
  2. 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.

Hints

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

Loading coding console...