Grumpy Shopkeeper
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 convenience store 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 shopkeeper is grumpy. If the shopkeeper is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the shopkeeper is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.
The shopkeeper 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 shopkeeper 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:
Login to Access Content
Java Code:
Login to Access Content
Python Code:
Login to Access Content
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:
Login to Access Content
Python Code:
Login to Access Content
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
