Split Stay Availability And Interval Pairing

What's being tested

This tests whether you can design a low-latency search API that combines correctness-heavy interval logic with scalable backend architecture. Airbnb cares because split stays expand bookable inventory: if no single listing is available for an entire trip, two listings may satisfy the trip with one checkout/check-in boundary. The interviewer is probing for API clarity, availability data modeling, efficient pair generation, deterministic ordering, pagination, deduplication, caching, and edge-case correctness. A strong Software Engineer answer should connect algorithmic interval reasoning to production constraints like `p99` latency, index freshness, and stable results across pages.

Core knowledge

• Split stay means a guest’s requested trip [start_date, end_date) is divided at a boundary split_date, producing two contiguous stays: listing A covers [start_date, split_date) and listing B covers [split_date, end_date). Treat dates as half-open intervals to avoid off-by-one checkout/check-in bugs.

• Availability intervals should be modeled as normalized half-open ranges, for example {listing_id, available_start, available_end} where available_start < available_end. A listing can satisfy a segment if available_start <= segment_start and available_end >= segment_end.

• Minimum-stay and maximum-stay rules must be applied per listing segment, not just to the full trip. For a split at s, nights are $n_1 = s - start$ and $n_2 = end - s$; validate min_nights <= n_i <= max_nights for each listing.

• Candidate generation usually starts by finding listings available for the left segment and listings available for the right segment, then joining them. If there are $L$ left candidates and $R$ right candidates, naive pairing is $O(LR)$, so ranking cutoffs and filters matter.

• Interval indexing can use sorted range indexes, segment trees, interval trees, or search-engine filters. In a relational store like `Postgres`, range types plus `GiST` indexes can support overlap/containment queries; in a search service, precomputed availability bitsets by date can make containment checks fast.

• Bitset availability is powerful for bounded booking horizons, such as 365–540 days. Represent each listing’s available nights as a bit vector; checking whether a segment is fully available becomes a masked comparison. This trades storage and update complexity for fast query-time filtering.

• Deduplication depends on whether pair order matters. For a fixed split, (A first, B second) is not equivalent to (B first, A second) because the stay order differs. But if the API aggregates across multiple split dates, dedupe by canonical keys like (first_listing_id, second_listing_id, split_date) and exclude A == B unless single-listing fallback is allowed.

• Deterministic pagination requires a stable sort key, not offset over a changing result set. Use cursor pagination with a tuple such as (rank_score, first_listing_id, second_listing_id, split_date) and encode the last seen tuple. Results should be reproducible for the same request and index snapshot.

• Ranking should be separated from correctness. First generate valid pairs, then rank by business-neutral technical factors such as price, distance between listings, review quality, availability confidence, or listing score. In a SWE interview, focus on where ranking plugs in, not deep ML model design.

• Caching works best at multiple levels: availability segment lookups, listing metadata fetches, and final query responses for popular destinations/date windows. Cache keys must include location, dates, guests, filters, currency, and versioned availability index state; stale availability must be bounded because booking correctness is user-visible.

• Freshness and consistency are central tradeoffs. Search can use an eventually consistent availability index for speed, but the booking flow must revalidate both listing segments against the source of truth before checkout. Phrase this as “fast search, authoritative confirmation.”

• API validation should reject invalid ranges, impossible trip lengths, unsupported guest counts, too-wide date windows, malformed cursors, and filters that exceed service limits. Return structured errors with stable codes like `INVALID_DATE_RANGE`, `CURSOR_EXPIRED`, or `NO_VALID_SPLIT_BOUNDARY`.

Worked example

For Design API for split-stay combinations, a strong candidate should first clarify the contract: “Are we returning pairs for one explicit split date or should the service consider all valid split dates between check-in and checkout? Do listings need to be geographically close? Should the same listing be excluded? What freshness guarantee is expected before booking?” Then declare assumptions: trip dates are half-open, the search horizon is bounded to about one year, and final booking revalidates availability.

The answer can be organized around four pillars. First, define the HTTP interface: `GET /v1/split-stays/search?location_id=...&checkin=...&checkout=...&guests=...&limit=...&cursor=...`, returning pairs with first_listing, second_listing, split_date, segment prices, and a next_cursor. Second, describe the data model: listing metadata, normalized availability intervals or bitsets, rule constraints, and denormalized search documents. Third, explain the query flow: enumerate valid split dates, fetch candidates for left and right segments, join under constraints, score, dedupe, and paginate. Fourth, cover production concerns: caching, snapshot-aware cursors, index freshness, and authoritative revalidation.

One explicit tradeoff to flag is precompute versus query-time generation. Precomputing all possible pairs explodes roughly as listings squared per market and per date window, while query-time generation may be expensive for large markets. A balanced design precomputes per-listing availability/search indexes, then generates top pair candidates at query time with cutoffs. Close by saying: “If I had more time, I’d discuss geo-distance constraints, price consistency, and how to degrade gracefully when candidate counts are huge.”

A second angle

For Generate split-stay pairs efficiently, the same concept shifts from service design to algorithm design. Instead of starting with endpoints and caches, start with sorted availability intervals and ask how to avoid $O(N^2)$ scans over all listings. One approach is to iterate possible split dates, build left-eligible and right-eligible candidate lists using interval containment checks, then generate only top-ranked or filtered cross-products. If the input is sparse intervals, an interval tree or sorted sweep over starts/ends can reduce repeated scans. The key transfer is the same: correctness comes from half-open interval containment, while scalability comes from bounding candidate generation before pair enumeration.

Common pitfalls

Pitfall: Treating availability as simple date overlap.

Overlap is insufficient: a listing available for [Jan 1, Jan 5) does not satisfy a requested segment [Jan 3, Jan 8). Say “containment” explicitly and use half-open interval notation; it signals you understand checkout-date semantics.

Pitfall: Designing pagination with `offset` after ranking dynamic results.

Offset pagination can skip or duplicate pairs when availability changes or ranking scores shift. A better answer uses cursor pagination over a deterministic composite sort key and, ideally, ties the cursor to an index snapshot or version.

Pitfall: Jumping straight to “use `Elasticsearch`” without explaining pair generation.

A search engine can filter listings, but it does not automatically solve split-boundary enumeration, cross-product explosion, deduplication, or booking-time revalidation. Lead with the algorithm and data model, then mention search infrastructure as an implementation choice.

Connections

Interviewers may pivot from here to calendar availability systems, range indexing, cursor-based pagination, search ranking architecture, or booking consistency. Be ready to discuss how final reservation creation prevents double booking, how availability updates invalidate cached search results, and how to cap combinatorial explosion in large markets.

Further reading

• Designing Data-Intensive Applications — Excellent background on indexes, caching, consistency, and tradeoffs in read-heavy distributed systems.

• PostgreSQL Range Types Documentation — Useful reference for thinking precisely about interval containment and indexed range queries.

• Elasticsearch Search After — Practical model for stable cursor-style pagination over ranked search results.