← Meta Interview Insights

Meta·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate
May 2026

Summary

Meta SWE coding round, one problem about reconstructing the smallest number from only the odd digits of a given input. Pretty straightforward on the surface but the constraints (up to 1000 digits) mean you can't just treat it as a regular integer.

Questions Asked (1)

Q1

Given a positive integer, extract all its odd digits, sort them in ascending order, and return the resulting number. The input can have up to 1000 digits.

Algorithms & Data Structures
Author's notes

My first instinct was to just parse it as an int, filter odd digits, sort them, and reconstruct.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that the input is a string due to its size, then iterate through each character to collect odd digits. Sort the collected digits (e.g., using counting sort since digits are 0-9) and concatenate them to form the result, handling the case where no odd digits exist.

Pro tip: Mention that you would use counting sort (an array of size 10) to achieve O(n) time, which is optimal for up to 1000 digits, and discuss how to handle leading zeros in the output.

1. Clarify input and output

Confirm that the input is a string (or can be treated as one) and that the output should be a number (or string) with odd digits sorted ascending. Ask about handling no odd digits (e.g., return 0 or empty).

2. Extract odd digits

Iterate through each character of the input string, convert to integer, and if odd, add to a collection (e.g., list or count array).

3. Sort digits efficiently

Since digits are 0-9, use counting sort: maintain an array of size 10 to count occurrences of each odd digit. This avoids O(n log n) comparison sort.

4. Construct result

Build the output by appending each digit from 1 to 9 (odd digits) repeated according to its count. Handle leading zeros by ensuring the first digit is non-zero (but odd digits are 1,3,5,7,9 so no zero).

5. Test edge cases

Test with no odd digits, all odd digits, large input (1000 digits), and digits in random order. Verify time and space complexity.

Key Points to Mention

  • Input size up to 1000 digits means it cannot be stored as a standard integer; treat as string.
  • Time complexity: O(n) using counting sort, where n is number of digits.
  • Space complexity: O(1) extra space for count array (size 10) plus output string.
  • Handling no odd digits: return 0 or empty string as per requirement.
  • Leading zeros: not an issue since odd digits are 1,3,5,7,9.
  • Stability not required; sorting digits ascending.

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