Allocate Mailboxes with Squared Distance
Updated
Problem statement
There are n houses along a straight street. House i stands at position houses[i].
You must place exactly k mailboxes on the street. A mailbox can go at any point on the street, including a point that is not a whole number. Each house uses the mailbox closest to it, and the cost of a house is the square of its distance to that mailbox.
Return the smallest possible total cost over all houses. An answer within 10^-5 of the correct value is accepted; for values above 1, the allowed error is 10^-5 times the correct value.
Function
minDistance(houses: int[], k: int) → doubleExamples
Example 1
houses = [10,1,12,3,2]k = 2return = 4.0- Sorted, the houses are at
1, 2, 3, 10, 12. Serve1, 2, 3with one mailbox at their mean2, and10, 12with one at11. - The costs are
1 + 0 + 1 = 2and1 + 1 = 2, so the total is4. - Any other split costs more. For example,
1, 2, 3, 10and12costs9 + 4 + 1 + 36 + 0 = 50.
Example 2
houses = [1,2,9]k = 1return = 38.0- One mailbox serves all houses. The best spot is the mean
(1 + 2 + 9) / 3 = 4, with cost9 + 4 + 25 = 38. - The median
2would cost1 + 0 + 49 = 50, so it is not the best spot for squared distance.
Example 3
houses = [9,3,1,8,4]k = 2return = 5.166666666666667- Sorted, the houses are at
1, 3, 4, 8, 9. The best split is1, 3, 4and8, 9. - The first group's mean is
8 / 3, and its cost is1 + 9 + 16 - 8 * 8 / 3 = 14 / 3. The second group's mailbox is at8.5, with cost0.25 + 0.25 = 0.5. - The total is
14 / 3 + 1 / 2 = 31 / 6, about5.16667.
Constraints
1 <= k <= houses.length <= 1001 <= houses[i] <= 10^4- All the values of
housesare different.
More LinkedIn Onsite Interview questions
- Find Leaves of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Max Points on a LineONSITE INTERVIEW · Seen Nov 2026
- Explore an Unknown Grid and Find a PathONSITE INTERVIEW · Seen Nov 2026
- Fire Station Response BillONSITE INTERVIEW · Seen Nov 2026
- Roll a Weighted DieONSITE INTERVIEW · Seen Oct 2026
- Longest Binary Subarray With at Most K OnesONSITE INTERVIEW · Seen Oct 2026
- Kth Closest Element in a BSTONSITE INTERVIEW · Seen Oct 2026
- Longest Binary Window with at Most K OnesONSITE INTERVIEW · Seen Oct 2026
- LRU Cache OperationsONSITE INTERVIEW · Seen Oct 2026
- Lexicographically Smallest Course OrderONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Volunteer Awards: Totals Divisible by KNutanix · ONSITE INTERVIEWNutanix interview questions
- Best Restart Cutoff for a Long-Tailed JobOpenAI · ONSITE INTERVIEWOpenAI interview questions
- Decision Tree Regression from ScratchNVIDIA · OANVIDIA interview questions
- Possible Timer Intervals with One Wrong ReadingIndeed · OAIndeed interview questions
- Russian Doll EnvelopesGoogle · ONSITE INTERVIEWGoogle interview questions
- Russian Doll EnvelopesInMobi · ONSITE INTERVIEWInMobi interview questions
- Beam Search and Nucleus DecodingMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Count Ideal ArraysMorgan Stanley · ONSITE INTERVIEWMorgan Stanley interview questions
- Russian Doll EnvelopesAirbnb · ONSITE INTERVIEWAirbnb interview questions
- Allocate MailboxesBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions