FastPrepSort an Array of Digits in Linear Time
Problems/Sort an Array of Digits in Linear Time

Sort an Array of Digits in Linear Time

Expedia logoExpedia● EasyINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Two 2023 reports from Expedia software development engineer intern interviews in India (one of them on campus) describe this task. In one, the candidate had to put a list of digits from 0 to 9 in order in O(n) time with only O(1) extra memory. The other also lists an easy counting sort question. Its candidate was asked to arrange the digits 1 to 9 into the biggest possible number under the same limits.

Neither report gives examples or limits. Here you sort digits 0 to 9 from smallest to largest in place and return the array, with up to 10^4 digits. The tests cannot check the time and space goal. The biggest-number version is the reverse order and is covered in the editorial, not tested.

Our version is about 80% the same as the reported questions.

You are given an array digits. Every value in it is a single digit from 0 to 9.

Sort the array in non-decreasing order and return it. You may change the array in place and return it.

The goal is O(n) time and O(1) extra space, where n is the length of the array. A general sorting routine takes O(n log n) time, so try to use the fact that there are only ten possible values.

Function

sortDigits(digits: int[]) → int[]

Examples

Example 1

digits = [3,0,7,3,1,9,0]return = [0,0,1,3,3,7,9]

The digits are two 0s, one 1, two 3s, one 7 and one 9. Written in that order they give [0, 0, 1, 3, 3, 7, 9].

Example 2

digits = [5,5,5]return = [5,5,5]

All digits are the same, so the array is already sorted.

Example 3

digits = [9,8,6,2]return = [2,6,8,9]

The digits are in decreasing order, so sorting reverses them.

Constraints

  • 1 <= digits.length <= 10^4
  • 0 <= digits[i] <= 9

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Group Transactions by HourAffirm · ONSITE INTERVIEWAffirm interview questions
  • Merge Sorted ArrayDP World · ONSITE INTERVIEW
  • Map and Accumulate Learning QueriesPalantir · ONSITE INTERVIEWPalantir interview questions
  • Meeting RoomsGoldman Sachs · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions
  • Sort Products by Aisle With Frozen Items LastInstacart · ONSITE INTERVIEWInstacart interview questions
  • Merge Two Arrays Into Sorted OrderNVIDIA · ONSITE INTERVIEWNVIDIA interview questions
  • Compress Consecutive Integer RangesDocuSign · ONSITE INTERVIEWDocuSign interview questions
  • Filter Anagrams of a TargetMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Rank Transform an ArrayAgoda · ONSITE INTERVIEWAgoda interview questions
  • Sort Documents Left to RightFigma · ONSITE INTERVIEWFigma interview questions

Interview reports that mention this question

  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int[] sortDigits(int[] digits) {
        // Write your code here.
    }
}
Checking account…