FastPrepApartment Housemate Preferences
Problems/Apartment Housemate Preferences

Apartment Housemate Preferences

Google logoGoogle● MediumFULLTIMEPHONE SCREEN
QuestionExamples

Problem statement

Source note: A Google technical phone screen asked how to house a group of people across several apartments of different sizes, where each person either hopes to share or prefers to be on their own. Everyone needs a place and the rooms suffice overall, but wishes can clash, so the task was to make as many people happy as possible. The report includes one small worked example and two small class sketches.

The report asks for the placement itself and gives no limits or tie rules. Practice choices here: each room holds one person, someone who hopes to share is happy with at least one other person in the apartment, the judged answer is the largest number of happy people (the editorial shows how to build a matching placement), names and apartment numbers are dropped, and the limits and other examples are ours.

The judged task matches the report at about 80%.

Apartment i has rooms[i] rooms, and each room holds one person, so the apartment can house at most rooms[i] people. Person p either wants housemates (wantsHousemates[p] is true) or wants to live alone (false).

Every person must be placed in exactly one apartment; apartments may stay empty. The rooms are enough in total for everyone, yet some people may end up in an arrangement they did not ask for:

The problem statement continues
Pro

Examples

Example 1

rooms = [2,1,4]wantsHousemates = [true,false,true]return = 3

Put person 1 (who wants to live alone) in the 1-room apartment, and persons 0 and 2 (who both want housemates) together in the 2-room apartment. The 4-room apartment stays empty. All 3 people get what they want.

02 · Example 2
FastPrep Pro
Reported in 1 Google interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week
All Google interview questionsSee Google hiring insights
CodePython 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
from collections import defaultdict
 
class Solution:
def solve(self, values, queries):
# Build the adjacency structure
n = len(values)
graph = defaultdict(list)
for u, v in queries:
graph[u].append(v)
 
best = [float("inf")] * n
heap = [(0, 0)]
while heap:
cost, node = heapq.heappop(heap)
if cost > best[node]:
continue
Run and Submit unlock with Pro
FastPrep Pro
Reported in 1 Google interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week