FastPrepAllocate Mailboxes with Squared Distance
Problems/Allocate Mailboxes with Squared Distance

Allocate Mailboxes with Squared Distance

LinkedIn logoLinkedIn● HardFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a LinkedIn onsite for an experienced machine learning engineer role. It was a coding round about AI ideas, with no AI tool. The task was a harder take on the well-known problem of placing k mailboxes for houses on a street. Here the cost is squared distance instead of plain distance. The best answer uses dynamic programming with prefix sums of the positions and of their squares. The candidate also had to show why each mailbox belongs at the mean of its houses, not the median. The follow-up asked for a simpler answer that may not be optimal, and k-means clustering was the answer.

The report gives no input format, limits or examples. Here, a mailbox can go anywhere on the street, and you return the total cost, not the average per house. Answers within 10^-5 are accepted. The limits come from the original mailbox problem: up to 100 houses at different positions from 1 to 10^4. The k-means follow-up is in the editorial but is not tested.

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

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) → double

Examples

Example 1

houses = [10,1,12,3,2]k = 2return = 4.0
  • Sorted, the houses are at 1, 2, 3, 10, 12. Serve 1, 2, 3 with one mailbox at their mean 2, and 10, 12 with one at 11.
  • The costs are 1 + 0 + 1 = 2 and 1 + 1 = 2, so the total is 4.
  • Any other split costs more. For example, 1, 2, 3, 10 and 12 costs 9 + 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 cost 9 + 4 + 25 = 38.
  • The median 2 would cost 1 + 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 is 1, 3, 4 and 8, 9.
  • The first group's mean is 8 / 3, and its cost is 1 + 9 + 16 - 8 * 8 / 3 = 14 / 3. The second group's mailbox is at 8.5, with cost 0.25 + 0.25 = 0.5.
  • The total is 14 / 3 + 1 / 2 = 31 / 6, about 5.16667.

Constraints

  • 1 <= k <= houses.length <= 100
  • 1 <= houses[i] <= 10^4
  • All the values of houses are 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

Interview reports that mention this question

  • LinkedIn Senior MLE Interview Questions: 1 Experience

LinkedIn interview experiences

  • LinkedIn Staff AI Engineer Phone Screens: 1 Experience
  • LinkedIn Experienced MLE Onsite: 1 Experience
  • LinkedIn Coding with AI Interview: 4 Experiences
  • LinkedIn Experienced Infrastructure SWE Onsite: 1 Experience
All LinkedIn interview questionsSee LinkedIn hiring insights
Saved
class Solution {
    public double minDistance(int[] houses, int k) {
        // Write your code here.
    }
}
Checking account…