Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
O(N)
time and O(1)
space. Where N
is the number of students. HAPPY CASE
Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0
Explanation:
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.
Input: students = [1], sandwiches = [0]
Output: 1
EDGE CASE
Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For Array problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We will use the idea of queue and stack to solve this problem. Our limiting data structure is the stack. So we need the queue of students to accommadate the stack. As long as have a count of student with round sandwich and square sandwich we can remove them from queue. It doesn't matter where they are in the queue.
1. Create a count of students with round sandwich and square sandwich.
2. Start at the top of stack of sandwiches and distribute sandwich to appropriate student
3. Once no more students want the top sandwich then we cannot distribute sandwiches and we are left with students without lunch.
4. Return the total number of students without lunch.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
Basic Solution:
class Solution:
def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
# Create a count of students with round sandwich and square sandwich.
squareStudents = roundStudents = 0
for student in students:
if student == 0:
squareStudents += 1
else:
roundStudents += 1
# Start at the top of stack of sandwiches and distribute sandwich to appropriate student
# Once no more students want the top sandwich then we cannot distribute sandwiches and we are left with students without lunch.
for sandwich in sandwiches:
if sandwich == 0:
if squareStudents == 0:
break
else:
squareStudents -= 1
elif sandwich == 1:
if roundStudents == 0:
break
else:
roundStudents -= 1
# Return the total number of students without lunch.
return roundStudents + squareStudents
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
// Create a count of students with round sandwich and square sandwich.
int ones = 0; //count of students who prefer type1
int zeros = 0; //count of students who prefer type0
for(int student : students){
if(student == 0) zeros++;
else ones++;
}
// Start at the top of stack of sandwiches and distribute sandwich to appropriate student
// Once no more students want the top sandwich then we cannot distribute sandwiches and we are left with students without lunch
for(int sandwich : sandwiches){
if(sandwich == 0){ // if sandwich is of type0
if(zeros == 0){ // if no student want a type0 sandwich
break;
}
zeros--;
}
else{ // if sandwich is of type1
if(ones == 0){ // if no student want a type1 sandwich
break;
}
ones--;
}
}
// Return the total number of students without lunch.
return zeros + ones;
}
}
Advanced Python Solution:
class Solution:
def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
# Create a count of students with round sandwich and square sandwich.
counter = Counter(students)
# Start at the top of stack of sandwiches and distribute sandwich to appropriate student
# Once no more students want the top sandwich then we cannot distribute sandwiches and we are left with students without lunch.
for sandwich in sandwiches:
if counter[sandwich] == 0:
break
counter[sandwich] -= 1
# Return the total number of students without lunch.
return counter[0] + counter[1]
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of items in the sandwich/student array.
O(N)
because we need to go through every sandwich.O(1)
because we only need to count the number of students.