MediumCoding

Strictly Palindromic Number

Asked at

Uber

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Restate that bases range from 2 through n minus 2.
02Inspect representation of n in base n minus 2.
03Show it equals 12 for n at least 4.
04Conclude no such n exists and return false.

Reference answer

Do not convert the number into every base. For every integer n >= 4, consider base b = n - 2, which is one of the required bases. In that base, n = 1*b + 2, so its representation is 12. The digits are different, hence 12 is not a palindrome. Therefore no n >= 4 is strictly palindromic under the problem definition, and the implementation simply returns false. This is O(1) time and O(1) space. In an interview, explain the proof before the code; it demonstrates that the apparent base-conversion task has a structural shortcut. If a variant changes the permitted base range, revisit the proof rather than reusing this conclusion blindly.

Then expect these follow-ups

Why is base n minus 2 always allowed?
Tests: proof details
How would a changed base range affect the result?
Tests: assumptions

Hiring now

Get the Uber interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question