Median of a Large Integer Collection
Updated
Problem statement
You are given a very large collection of integers nums. Think of it as a file of numbers that is too big to fit in memory. You can only read it from the first number to the last, one number at a time. You cannot jump to a position, and you cannot sort or copy the numbers.
Return the median of nums:
- If
nums.lengthis odd, the median is the middle value when the numbers are in sorted order. - If
nums.lengthis even, the median is the average of the two middle values.
Aim to read the collection only a small, fixed number of times and to use a constant amount of extra memory.
Function
findMedian(nums: int[]) → doubleExamples
Example 1
nums = [7,1,5,3,9]return = 5.0In sorted order the numbers are [1, 3, 5, 7, 9]. There are 5 numbers, an odd count, so the median is the middle one: 5.
Example 2
nums = [5,2,9,4]return = 4.5In sorted order the numbers are [2, 4, 5, 9]. There are 4 numbers, an even count, so the median is the average of the two middle values: (4 + 5) / 2 = 4.5.
Example 3
nums = [-3,8,-3,-3]return = -3.0Values can repeat and can be negative. In sorted order the numbers are [-3, -3, -3, 8]. The two middle values are both -3, so the median is (-3 + -3) / 2 = -3.
Constraints
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
More Airbnb Phone Screen questions
- Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
- Text JustificationPHONE SCREEN · Seen Nov 2026
- Decode and Store StringsPHONE SCREEN · Seen Oct 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
- Smallest Common RegionPHONE SCREEN · Seen Aug 2026
- Longest Chain BookingPHONE SCREEN · Seen Aug 2026
- Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
- Parse Query StringPHONE SCREEN · Seen May 2026
- Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023
Similar questions at other companies
- Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
- Koko Eating BananasThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Find First and Last Position in a Sorted ArrayInstacart · PHONE SCREENInstacart interview questions
- Random Pick with Weight Using Recorded DrawsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Longest Increasing SubsequenceAngel One · PHONE SCREEN
- Aggressive CowsAmazon · PHONE SCREEN
- Find First and Last Position of Element in Sorted ArrayEPAM · PHONE SCREENEPAM interview questions
- Find K Closest Elements in a Sorted ArrayNavi · PHONE SCREEN
- Search in Rotated Sorted ArrayZoomInfo · PHONE SCREEN
- Find a Peak ElementFox Corporation · PHONE SCREEN
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
- Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)