← Booking.com Interview Insights

Booking.com·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Got a coding question from Booking.com that looked simple on the surface but had a few edge cases worth thinking through carefully.

Questions Asked (1)

Q1

Given an integer, you're allowed to swap any two of its digits at most once. Return the largest possible number you can form.

Algorithms & Data Structures
Author's notes

My first instinct was greedy: find the largest digit and move it to the front.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Convert the integer to a string or list of digits. Scan from left to right to find the first digit that has a larger digit to its right; swap it with the largest such digit (rightmost if ties) to maximize the number. If no such digit exists, return the original number.

Pro tip: Clarify edge cases upfront, such as negative numbers or leading zeros, and mention that the algorithm runs in O(n) time with O(n) space, which is optimal for this problem.

1. Clarify constraints and edge cases

Ask about input range, negative numbers, and whether leading zeros are allowed after swap. Confirm that the number is non-negative and we can swap any two digits at most once.

2. Convert to mutable sequence

Convert the integer to a string or list of characters to easily access and swap digits.

3. Identify the first swap opportunity

Traverse from left to right. For each digit, find the maximum digit to its right. If a larger digit exists, swap the current digit with the rightmost occurrence of that maximum digit and stop.

4. Handle no-swap case

If no such pair is found (digits are in non-increasing order), return the original number unchanged.

5. Return the result

Convert the modified sequence back to an integer and return it.

Key Points to Mention

  • Greedy approach: swap the leftmost digit that can be increased with the largest possible digit to its right.
  • Time complexity O(n) and space complexity O(n) where n is the number of digits.
  • Handling ties: choose the rightmost occurrence of the maximum digit to preserve larger digits in more significant positions.
  • Edge cases: single-digit numbers, numbers with all digits in descending order, and numbers containing zeros.
  • Alternative approach: using a stack to find the next greater digit, but the greedy scan is simpler.
  • Correctness proof: swapping the first improvable digit yields the maximum number because it increases the most significant digit possible.

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