← Upstart Interview Insights

Upstart·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Got a coding problem at Upstart for a software engineer role that was more simulation-heavy than I expected. The problem looked like a straightforward capacity check but the pay-once-across-all-visits rule tripped me up for a bit.

Questions Asked (1)

Q1

A casino buffet has a fixed seating capacity. You're given a prices array where prices[i] is the one-time fee customer i will pay, and an events array of customer IDs where each pair of appearances for the same ID represents one arrive-then-leave cycle. A customer gets seated only if there's open capacity when they arrive, and they pay at most once across all their visits (the first time they're successfully seated). Return the total revenue.

Algorithms & Data Structures
Author's notes

The capacity simulation part was fine, I just tracked how many seats were occupied and toggled on arrival vs departure.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a simulation over time, tracking current occupancy and a set of customers who have already paid. Process events in order, updating occupancy on each arrival/departure and adding revenue only when a customer is first successfully seated.

Pro tip: Clarify edge cases upfront: what if a customer appears only once (incomplete cycle)? What if they arrive when full and later return? Confirm that payment occurs only on first successful seating, not on every visit.

1. Clarify the problem and constraints

Ask about input format, capacity limits, event ordering, and whether a customer can have multiple cycles. Confirm that revenue is counted only once per customer, on their first successful seating.

2. Choose data structures

Use a set to track customers who have already paid, a counter for current occupancy, and possibly a map to track pending arrivals for customers who haven't completed a cycle.

3. Simulate events in order

Iterate through the events array. For each event, determine if it's an arrival or departure (e.g., by toggling a state per customer). On arrival, if capacity allows and customer hasn't paid, seat them, increment occupancy, add revenue, and mark as paid. On departure, decrement occupancy.

4. Handle edge cases and validate

Consider incomplete cycles (odd number of appearances), customers arriving when full, and multiple visits. Walk through a small example to verify logic.

5. Analyze complexity and optimize

Discuss time complexity O(n) and space O(m) where n is number of events and m is number of unique customers. Mention potential optimizations if needed.

Key Points to Mention

  • Track occupancy with a simple counter, incrementing on arrival and decrementing on departure.
  • Use a set to remember which customers have already paid to avoid double-counting revenue.
  • Determine arrival vs. departure by toggling a boolean state per customer or using a map of visit counts.
  • Only seat a customer if current occupancy < capacity and they haven't paid before.
  • Handle incomplete cycles gracefully (e.g., ignore or treat as arrival only).
  • Time complexity is O(n) and space O(m) where n is events and m is unique customers.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.