Grumpy Bartender
A Sliding Window Problem
-
Algorithms and Data Structures: TheAlgorist.com
-
System Design: DistributedComputing.dev
-
Low Level Design: LowLevelDesign.io
-
Frontend Engineering: FrontendEngineering.io
Problem Statement:
Today the neighborhood bar is open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the bar, and all those customers leave after the end of that minute.
On some minutes, the bartender is grumpy. If the bartender is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bartender is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.
The bartender knows a secret technique to keep herself not grumpy for X minutes straight, but can only use it once.
Return the maximum number of customers that can be satisfied throughout the day.
Example 1:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bartender keeps herself not grumpy for the last 3 minutes. The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.
Solution:
Prerequisite: Sliding Window Core Concept
Algorithm:
This is a Premium content.
Please subscribe to the Algorithms course to access the detailed Algorithm discussion.
Java Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
If you are beginner, the above code would look perfectly fine to you, but a little more experienced developer would not be satisfied with the above code and would demand a little more optimization, which often results in lesser number of code lines without compromising the readability. This often differentiates a good coder from an average one, and my goal is to make you not just a good coder but an exceptional one, over time. You may not be impressed by the Python code I write since I am not a Python developer. The most I do with Python script and Flask is to write necessary scripts to deploy Machine Learning models at scale, and that's it. But I strongly believe that you can learn a ton from the Java code. I will try to discuss various software engineering best practices and the art of writing clean code every now and then in between discussing algorithms.
In the below code we won't write a separate loop to initialize additionalSatisfiedCustomersUsingSecretTechniqueInCurrentWindow, rather we would use just one while loop.
Java Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
