Hey guys I had an interview a few days ago and I got a bit stumbled on a question I was presented... I haven't quite been able to find an identical solution using my mediocre googling skills so here I am asking on the almighty stack to share with you guys. Nevertheless here is the prompt(as best as I can remember it)...

You are an usher at a theater and your job is to tell incoming parties whether you can or cannot seat them. The users give you the size of their party(numToBeSeated) and you tell them if they can be seated or not. If there is enough space you return a boolean value True or False if there is no space. Given a row (seats[]) write a function that returns whether the party fits or not.

The only constraint is that none of guests can be seated next to each other.

Only two parameters...

seatingProgram(seats[],numToBeSeated){}

The given array seats[] will have an array of 1s and 0s. 1 represents an already taken space and 0 represents an empty space.

numToBeSeated is a singular non-negative integer greater than zero.

• example 1)

seats[1,0,0,0,0,0,1,0,0]

numToBeSeated =3 ----> True

numToBeSeated = 4 -----> False

You can fit 3 guests but not 4. Your array would like this after putting in 3 guests...

[1,0,1,0,1,0,1,0,1]

• example 2)

seats[0]

numToBeSeated =1 ----> True

• example 3)

seats[1]

numToBeSeated =1 ----> False

• example 4)

seats[0,0]

numToBeSeated =1 ----> True

numToBeSeated =2 ----> False

What would be an efficient approach to this? Dynamic Programming perhaps? Lol I choked and just used brute force with a for loop and a bunch of edge cases. Probably not going to get a call back after that haha. But I imagine there is a more elegant approach.

For the sake of readability I was hoping we could keep things in Python but other languages are welcome too. =)

CodePudding user response：

You can add two 0 at the first and end of your list that you want to check, then check your list from index=1 until index=end-1, and for each iteration check three consecutive numbers if all these three numbers == zero, you have one place and insert one people in the middle and decrease numToBeSeated and if numToBeSeated==0 you can pass the problem:

def seatingProgram(seats, numToBeSeated):            
    if numToBeSeated == 0: 
        return True

    seats = [0]   seats   [0]
    for i in range(1, len(seats)-1):            
        if seats[i-1] == seats[i] == seats[i 1] == 0:
            seats[i] = 1
            numToBeSeated -= 1
            if numToBeSeated == 0: 
                return True
    return False

Output:

print(seatingProgram([1,0,0,0,0,0,1,0,0], 3))
# True
print(seatingProgram([1,0,0,0,0,0,1,0,0], 4))
# False
print(seatingProgram([0,0], 1))
# True
print(seatingProgram([0,0], 2))
# False

CodePudding user response：

Find every block of consecutive 0s that are not adjacent to 1s. In each of such blocks of length n you can place ceil(n/2) guests.

Short argument why it works:

• placement of guests in one block obviously doesn't affect seating in other blocks
  • this implies that maxxing every block is the way to go
• ceil(n/2) is the maximum of seats you can pack, from pigeonhole principle - if you seat more, then two will be adjacent.
  • obviously this upper bound is possible to reach, just alternate 1s and 0s

CodePudding user response：

Other answers are correct, but the dynamic programming solution is actually simplest

def seatingProgram(seats, n):
 fulln = 0   # number of people you can seat with a guest in the preceding seat
 emptyn = 0   # number of people you can seat without a guest in the preceding seat
 for seat in seats:
   if seat > 0:
     emptyn, fulln = max(fulln, emptyn), 0
   else
     emptyn, fulln = max(fulln, emptyn), emptyn 1
 return max(fulln, emptyn) >= n