Problem Solving Skill

walterf25

Expert
Licensed User
Longtime User
Hi all, just wanted to post this on here and have a little fun, I have come across the following quiz problem while preparing for an interview.

A cafeteria table consists of a row of N seats, numbered from 1 to N from left to right. Social distancing guidelines require that every diner be seated such that K seats to their left and K seats to their right (or all the remaining seats to that side if there are fewer than K) remain empty.
There are currently M diners seated at the table, the ith of whom is in seat Si. No two diners are sitting in the same seat, and the social distancing guidelines are satisfied.
Determine the maximum number of additional diners who can potentially sit at the table without social distancing guidelines being violated for any new or existing diners, assuming that the existing diners cannot move and that the additional diners will cooperate to maximize how many of them can sit down.
Please take care to write a solution which runs within the time limit.

Constraints​


1≤N≤10^15
1≤K≤N
1≤M≤500,000
M≤N
1≤Si≤N

Sample test case #1
N = 10
K = 1
M = 2
S = [2, 6]

Expected Return Value = 3

Sample test case #2
N = 15
K = 2
M = 3
S = [11, 6, 14]

Expected Return Value = 1

How would you guys resolve this, no cheating, can not use AI, I'm curious to see your algorithms.

Have fun.
 
E

emexes

Expert
Licensed User
Longtime User
walterf25 said:
while preparing for an interview
Click to expand...

Job interview? What field? This puzzle is the sort of thing I was doing when programming school timetabling. I've still got the book somewhere, which included BASIC code for various operations.

Just tried to find it. Cover looked like this book, but I don't remember it being called a cookbook.

The TimeTabler's CookBook | School Timetabling | TimeTabler

Timetabling - A TimeTabler's CookBook is known as the 'Timetabling Bible', having sold thousands of copies worldwide. Read more about the book here.
www.timetabler.com
 

LucaMs

Expert
Licensed User
Longtime User
That's one of the reasons restaurants (or "cafeteria") close down
 
E

emexes

Expert
Licensed User
Longtime User
walterf25 said:
Sample test case #1
N = 10
K = 1
M = 2
S = [2, 6]

Expected Return Value = 3

Sample test case #2
N = 15
K = 2
M = 3
S = [11, 6, 14]

Expected Return Value = 1
Click to expand...

Simplest I've come up with so far that passes all supplied test cases is:

Expected Return Value = N / M - K - K

Would I pass the interview?

p.s. close runner-up: Expected Return Value = (N + M) / (K * M * M)
 
Last edited:
P

PaulMeuris

Well-Known Member
Licensed User
That was fun...
The calculation has to run within the time limit... how long?
The maximum constraints are not really realistic...
To test the calculations from @emexes : N=20,K=3,M=3,[2,6,10] ... The result should be 2: index 14 and 18, right?
How much time does an applicant have to solve this puzzle?
 

MikeH

Well-Known Member
Licensed User
Longtime User
Sorry, my answer, after much thought, is...

Takeaway

 

Daestrum

Expert
Licensed User
Longtime User
I did write one, but in tidying it up I used an AI - so excluded myself
 

walterf25

Expert
Licensed User
Longtime User
So, after banging my head against the wall for a few days, I went ahead and asked ChatGPT, however that stupid thing took me through a rabbit hole and in the end none of the solutions worked, I sort of came up with the following


Cafeteria seating problem: 
   public static long getMaxAdditionalDiners(long N, long K, int M, long[] S) {
        Arrays.sort(S);

        long additionalDiners = 0;
        long currentSeat = 1;
        int index = 0;

        while (currentSeat <= N) {
            // Check if current seat is in the block of an existing diner
            if (index < M && currentSeat >= S[index] - K && currentSeat <= S[index] + K) {
                currentSeat = S[index] + K + 1;
                index++;
            } else {
                // Safe to place a new diner
                additionalDiners++;
                currentSeat += (K + 1);
            }
        }

        return additionalDiners;
}

This works, however it fails when testing the following constraint
1≤N≤10^15
Click to expand...

with the above code when using a number of seats of 1_000_000_000_000_000, it takes about > 4 minutes, so obviously not a good solution as it needs to be under the 5 second time limit.

Any other ideas?
 
P

PaulMeuris

Well-Known Member
Licensed User
The size of the array will be a problem in B4J:
java.lang.OutOfMemoryError: Java heap space
java.lang.OutOfMemoryError: Requested array size exceeds VM limit
Click to expand...

With these accepted large numbers the calculation takes about 4.6 seconds...


So, it might be possible in a different language... the occupied seats are auto generated...
The real wait would probably be the printing of the occupied seats list (if you want to know where a person can sit)...
 
Last edited:

walterf25

Expert
Licensed User
Longtime User
Ok, so this seems to be the real solution, I've tested it with 10^15 seats and it works very fast

Cafeteria seating problem: 
  public long getMaxAdditionalDinersCount(long N, long K, int M, long[] S) {
        long seatsPerDiner = K + 1;
        long additionalDiners = 0;

        // If there are no diners initially, the entire table is one large gap.
        if (M == 0) {
            // In a gap of length L, we can place ceil(L / seatsPerDiner) diners.
            // This can be calculated using integer arithmetic as (L + K) / (K + 1).
            System.out.println("N = " + N + " / " + " K = " + K);
            System.out.println("seatsPerDiner = " + (K -1));
            System.out.println("returning: " + (N + K) / seatsPerDiner);
            return (N + K) / seatsPerDiner;
        }

        // Sort the array of existing diner positions to easily calculate gaps between them.
        Arrays.sort(S);

        // --- 1. Calculate available space before the first diner ---
        // The first diner is at S[0]. They block seats down to S[0] - K.
        // The available gap is from seat 1 to S[0] - K - 1.
        long firstGapLength = S[0] - K - 1;
        if (firstGapLength > 0) {
            additionalDiners += (firstGapLength + K) / seatsPerDiner;
        }

        // --- 2. Calculate available space between adjacent diners ---
        // Iterate through each pair of adjacent diners.
        for (int i = 0; i < M - 1; i++) {
            // Gap between diner at S[i] and diner at S[i+1].
            // Diner at S[i] blocks seats up to S[i] + K.
            // Diner at S[i+1] blocks seats down to S[i+1] - K.
            // The available gap is from S[i] + K + 1 to S[i+1] - K - 1.
            long betweenGapLength = (S[i+1] - K - 1) - (S[i] + K + 1) + 1;
            betweenGapLength = S[i+1] - S[i] - 2 * K - 1;
            if (betweenGapLength > 0) {
                additionalDiners += (betweenGapLength + K) / seatsPerDiner;
            }
        }

        // --- 3. Calculate available space after the last diner ---
        // The last diner is at S[M-1]. They block seats up to S[M-1] + K.
        // The available gap is from S[M-1] + K + 1 to N.
        long lastGapLength = N - (S[M - 1] + K);
        if (lastGapLength > 0) {
            additionalDiners += (lastGapLength + K) / seatsPerDiner;
        }

        return additionalDiners;
    }
  }

Cheers,
Walter
 

walterf25

Expert
Licensed User
Longtime User
DonManfred said:
I never saw a Cateria Table with this amount of Seats

Even not a Cinema, Concert-Hall, Football-Stadium ;-)
Click to expand...
Clearly you haven't been to my family's parties
 
P

PaulMeuris

Well-Known Member
Licensed User
walterf25 said:
1≤N≤10^15
1≤K≤N
1≤M≤500,000
M≤N
1≤Si≤N
Click to expand...
EDIT:
The constraints are not correct, i think...
There must be at least 2 seats: 1 empty seat (K) and 1 for the lonely diner (M)...
The number of diners (M) can't be equal to the number of seats (N) because there must be at least one empty seat...
 
Last edited:
You must log in or register to reply here.
Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…