How should I practice Longest Chain Booking?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Airbnb phone screen problems in FastPrep.

Is Longest Chain Booking associated with Airbnb?

FastPrep tags this as a Airbnb phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Longest Chain Booking

Learn this problem

● Medium

AirbnbFULLTIMEPHONE SCREEN

Problem statement

There are bookingCount bookings numbered from 0 through bookingCount - 1. Each directed pair [u, v] in canFollow means booking v may immediately follow booking u in one valid chain.

The compatibility graph is a directed acyclic graph. A chain may use each booking at most once. Return the maximum number of bookings in any valid chain. A single booking is a valid chain.

Function

longestBookingChain(bookingCount: int, canFollow: int[][]) → int

Examples

Example 1

bookingCount = 5canFollow = [[0,1],[1,2],[0,3],[3,4]]return = 3

Both 0 -> 1 -> 2 and 0 -> 3 -> 4 contain three bookings.

Example 2

bookingCount = 4canFollow = []return = 1

With no compatibility edges, every longest chain contains one booking.

Example 3

bookingCount = 6canFollow = [[0,2],[1,2],[2,3],[2,4],[4,5]]return = 4

A longest chain is 0 -> 2 -> 4 -> 5.

Constraints

1 <= bookingCount <= 100000.
0 <= canFollow.length <= 200000.
Every pair is [u, v] with 0 <= u, v < bookingCount and u != v.
The directed graph contains no cycle.
Duplicate edges may appear and have no additional effect.