Frontend School

Oyo Hotel Guest Path Optimization

DSA
hard

Oyo Hotel Guest Path Optimization

Hard
Dynamic Programming
2D DP
Pathfinding
Grid

Overview

Oyo is constantly innovating its guest experience. One challenge is optimizing guest flow through our hotels, ensuring they experience the best amenities while managing resource allocation for premium services. This problem simulates a guest's journey through a multi-floor, multi-section hotel.

What you need to do / Task

You are tasked with finding the maximum total amenity value a guest can accumulate when traversing from the top-left room (0,0) to the bottom-right room (M-1, N-1) of a hotel grid. Guests can only move right or down. Each room (r, c) has a base amenity value. Some rooms are designated as "Premium Zones" and offer an additional bonus if visited. However, due to limited staff and resources for premium services, a guest can visit at most maxPremiumVisits Premium Zones throughout their entire path.

Your function should return the maximum possible total amenity value, including premium bonuses, a guest can achieve.

Input & output

The function signature will be: function maxGuestPathValue(M: number, N: number, amenityValues: number[][], isPremium: boolean[][], premiumBonuses: number[][], maxPremiumVisits: number): number

  • M: An integer representing the number of floors (rows) in the hotel.
  • N: An integer representing the number of sections per floor (columns) in the hotel.
  • amenityValues: A 2D array (M x N) where amenityValues[r][c] is the base amenity value for room (r, c).
  • isPremium: A 2D boolean array (M x N) where isPremium[r][c] is true if room (r, c) is a Premium Zone, and false otherwise.
  • premiumBonuses: A 2D array (M x N) where premiumBonuses[r][c] is the additional bonus value gained if room (r, c) is a Premium Zone and is visited. This value is only considered if isPremium[r][c] is true.
  • maxPremiumVisits: An integer representing the maximum number of Premium Zones a guest is allowed to visit on their path.

The function should return a single integer representing the maximum total amenity value. If no valid path exists (e.g., maxPremiumVisits is too low for a required premium start/end), return -1.

Clarifications

  • Guests start at (0,0) and must reach (M-1, N-1).
  • Movement is restricted to only 'right' (increase column index) or 'down' (increase row index).
  • The maxPremiumVisits constraint applies to the total number of Premium Zones visited along the entire path, not per floor or segment.
  • If maxPremiumVisits is 0, guests cannot visit any Premium Zones, even if they are on the path. The premiumBonuses for such rooms are ignored.

Examples

1

Example 1

Input:

M = 2, N = 2, amenityValues = [[10,10],[10,10]], isPremium = [[false,true],[false,false]], premiumBonuses = [[0,50],[0,0]], maxPremiumVisits = 1

Output:

80

Note:

Path: (0,0) -> (0,1) -> (1,1). (0,0): amenity=10 (not premium) (0,1): amenity=10, premium_bonus=50 (is premium, 1 premium visit used) (1,1): amenity=10 (not premium) Total value: 10 + (10+50) + 10 = 80. This path uses 1 premium visit, which is <= maxPremiumVisits=1. This is the maximum possible value.

2

Example 2

Input:

M = 3, N = 3, amenityValues = [[1,1,1],[1,1,1],[1,1,1]], isPremium = [[false,true,false],[true,false,true],[false,true,false]], premiumBonuses = [[0,10,0],[10,0,10],[0,10,0]], maxPremiumVisits = 0

Output:

5

Note:

Since maxPremiumVisits is 0, no premium bonuses can be collected. All rooms contribute only their base amenity value (1 in this case). Any path from (0,0) to (2,2) consists of (3-1) + (3-1) + 1 = 5 rooms. Thus, the total value for any path is 5 * 1 = 5.

3

Example 3

Input:

M = 1, N = 3, amenityValues = [[10,5,20]], isPremium = [[false,true,false]], premiumBonuses = [[0,100,0]], maxPremiumVisits = 0

Output:

35

Note:

The only path is (0,0) -> (0,1) -> (0,2). (0,0): amenity=10. (0,1): amenity=5. (isPremium=true, bonus=100, but maxPremiumVisits=0, so bonus is ignored). (0,2): amenity=20. Total value: 10 + 5 + 20 = 35.

Constraints

Constraints & assumptions

  • 1 <= M, N <= 1000
  • 0 <= amenityValues[r][c] <= 1000
  • 0 <= premiumBonuses[r][c] <= 1000
  • 0 <= maxPremiumVisits <= 50
  • All input matrices (amenityValues, isPremium, premiumBonuses) will have dimensions M x N.
  • The starting room (0,0) and ending room (M-1, N-1) can be Premium Zones.

What interviewers evaluate

  • Correctness: The solution must correctly identify the maximum possible total amenity value under all given constraints.
  • Efficiency (Time): The solution should be optimal, demonstrating appropriate use of Dynamic Programming for the given constraints.
  • Efficiency (Space): The solution should manage memory efficiently, potentially optimizing space complexity where applicable.
  • Clarity & Structure: Code should be well-organized, readable, and follow good software engineering practices.
  • Problem-solving Approach: Ability to break down the problem, identify the DP state, and formulate correct recurrence relations.

Loading editor...