Shortest Board Length to Cover Holes
Updated
Problem statement
There are N holes arranged in a row in the top of an old table. We want to fix the table by covering the holes with two boards. For technical reasons, the boards need to be of the same length.
The position of the K-th hole is A[K]. What is the shortest length of the boards required to cover all the holes? The length of the boards has to be a positive integer. A board of length L, set at position X, covers all the holes located between positions X and X+L (inclusive). The position of every hole is unique.
Complete the func in the editor 👉
which, given an array A of integers of length N, representing the positions of the holes in the table, returns the shortest board length required to cover all the holes.
Function
coverHotels(A: int[]) → intExamples
Example 1
A = [11, 20, 15]return = 4The first board would cover the holes in positions 11 and 15, and the second board the hole at position 20.
Example 2
A = [15, 20, 9, 11]return = 5The first board covers the holes at positions 9 and 11, and the second one the holes in positions 15 and 20.
Example 3
A = [0, 44, 32, 30, 42, 18, 34, 16, 35]return = 18The first board would cover the holes in positions between 0 and 18, and the second the positions between 30 and 44.
Example 4
A = [9]return = 1There is only one hole, so the board length required is 1.
Constraints
N is an integer within the range [1..100,000]each element of array A is an integer within the range 0..1,000,000,000the elements of A are all distinct
More Microsoft interview questions
- Minimum Cost to Process Priority TasksOA · Seen Nov 2026
- Most Visited Sprint MarkerOA · Seen Nov 2026
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Maximum Escape Game ScoreOA · Seen Nov 2026
- Count Subarrays with a Perfect-Square ProductOA · Seen Nov 2026
Similar questions at other companies
- Find Minimum TimeAlphaSense · OA
- Find Minimum TimeBlackRock · OABlackRock interview questions
- Minimize Maximum Group DifferenceDRW · OADRW interview questions
- Minimum-Cost Solar Rooftop AllocationDeloitte · OADeloitte interview questions
- K-Means ClusteringFortinet · OAFortinet interview questions
- Playlist PartitioningTikTok · OATikTok interview questions
- Get Minimum Pen Drive SizeAmazon · OA
- Collect PointsFlexport · OAFlexport interview questions
- Aggressive CowsPeopleStrong · OAPeopleStrong interview questions
- Spread Cows Across StallsExpedia · OAExpedia interview questions
Microsoft interview experiences
- Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
- Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
- Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
- Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
- Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
- Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)