We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Students Unable to Eat Lunch

Number: 1802

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Microsoft

Problem Description

Given a queue of students each with a preference for either a circular (0) or square (1) sandwich, and a stack of sandwiches arranged such that the top sandwich is at index 0, simulate the process where the student at the front of the queue takes the sandwich if it matches their preference. If it does not match, the student moves to the end of the queue. The simulation stops when no student in the queue will take the top sandwich. The goal is to determine the number of students that are unable to eat.

Key Insights

  • Instead of simulating every rotation of the queue, count the number of students preferring each type.
  • The sandwiches are arranged in a stack (first element is the top); process them one by one.
  • For each sandwich, if there is at least one student with a matching preference, decrement that count.
  • As soon as a sandwich type is not available among the remaining students, the simulation stops.

Space and Time Complexity

Time Complexity: O(n) or O(n^2) in a naïve simulation; with the counting strategy it is O(n) where n is the number of students/sandwiches. Space Complexity: O(1) extra space (only a few counters are used).

Solution

We can solve the problem by using a counting approach instead of simulating the queue rotations. First, count how many students prefer each sandwich type (0 and 1). Then, iterate through the sandwich stack (from the top) and for each sandwich, check if there is a student with the matching preference. If yes, decrement that count; if not, break out of the loop, because no further sandwich can be taken. Finally, sum the remaining counts to get the number of students who are unable to eat.

Code Solutions

# Python solution for the problem

def countStudents(students, sandwiches):
    # Count the preference of each type of sandwich
    count0 = students.count(0)
    count1 = students.count(1)
    
    # Process the sandwiches from the top of the stack
    for sandwich in sandwiches:
        if sandwich == 0:
            # If a student who likes type 0 is available, give them the sandwich
            if count0 > 0:
                count0 -= 1
            else:
                # No student prefers type 0, break out
                break
        else:
            # For a sandwich of type 1, check the availability of a matching student
            if count1 > 0:
                count1 -= 1
            else:
                # No student prefers type 1, break out
                break
    # The remaining students who couldn't get their sandwich
    return count0 + count1

# Example usage:
students = [1,1,0,0]
sandwiches = [0,1,0,1]
print(countStudents(students, sandwiches))  # Output should be 0
← Back to All Questions