House Robber Series — Databricks — Intervues

← Back to companies
[ OK ] Loaded  — 
[ INFO ] 
$ cd 
$ ls -lt 
01
02
03
04
05
$ ls -lt 
01
02
03
04
05
user@intervues:~/$ 

← Databricks
House Robber Series[ OK ] databricks-code-16 — full content available
[ INFO ] category: Coding  difficulty: medium  freq: Must  first seen: 2026-03-13
[MEDIUM][CODING][MUST]
$ cat problem.md
Practice/Databricks/House Robber Series
House Robber SeriesCodingMust
Problem OverviewDesign and implement a revenue tracking system that supports customer referrals. The system should track each customer's revenue and maintain their referral relationships, where a customer who refers another customer earns credit from that referral's revenue.
This problem tests understanding of:
System design with custom data structures
Efficient querying with sorted data structures
Trade-offs between write-heavy vs read-heavy optimization
Handling referral trees and relationship tracking
Core RequirementsImplement a RevenueSystem class with the following methods:
insert(revenue: int) -> int: Create a new customer account with the given revenue, return an auto-incremented customer ID (starting from 0)
insert(revenue: int, referrer_id: int) -> int: Create a new customer account referred by an existing customer. The referrer's total revenue increases by the new customer's revenue. Return the new customer's ID.
get_lowest_k_by_total_revenue(k: int, min_total_revenue: int) -> Set[int]: Return a set of up to K customer IDs that have the lowest total revenue among all customers whose total revenue is at least min_total_revenue. Results should be sorted by total revenue ascending, with ties broken by customer ID ascending.
Revenue Calculation Ruletotal_revenue(customer_id) = revenue[customer_id] + sum(revenue[direct_referral] for direct_referral in children[customer_id]) 
Important: Only direct referrals (one level) contribute to a customer's total revenue in the base version.
Example``
RequirementsCustomer IDs start at 0 and auto-increment
Only direct referrals contribute to total revenue
Query results must be sorted by total revenue ascending, with ties broken by ID
Return at most K results, or fewer if not enough customers meet the threshold
system = RevenueSystem()

# Create customers without referrals
id0 = system.insert(300)  # Returns: 0, customer 0 has revenue=300, total_revenue=300
id1 = system.insert(200)  # Returns: 1, customer 1 has revenue=200, total_revenue=200

# Customer 0 refers a new customer with revenue 100
id2 = system.insert(100, 0)  # Returns: 2
# Now:
#   - Customer 2: revenue=100, total_revenue=100
#   - Customer 0: revenue=300, total_revenue=300+100=400 (gains from referral)

# Customer 0 refers another customer
id3 = system.insert(150, 0)  # Returns: 3
# Now:
#   - Customer 3: revenue=150, total_revenue=150
#   - Customer 0: revenue=300, total_revenue=300+100+150=550

# Customer 2 refers a new customer
id4 = system.insert(50, 2)  # Returns: 4
# Now:
#   - Customer 4: revenue=50, total_revenue=50
#   - Customer 2: revenue=100, total_revenue=100+50=150
#   - Customer 0: revenue=300, total_revenue=300+100+150=550 (NO change - only direct referrals count)

# Query: Get customers with total_revenue >= 100, lowest 3
result = system.get_lowest_k_by_total_revenue(k=3, min_total_revenue=100)
# Returns: {2, 3, 1}
# Explanation:
#   Customer 4: total_revenue=50 (excluded, < 100)
#   Customer 2: total_revenue=150
#   Customer 3: total_revenue=150
#   Customer 1: total_revenue=200
#   Customer 0: total_revenue=550
# Sorted by total_revenue ascending: [150, 150, 200, 550]
# Ties (customers 2 and 3) broken by ID: [2, 3, 1, 0]
# Return first 3: {2, 3, 1}
user@intervues:~/databricks$ 