Problem Solving Skill

[walterf25]

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.

 

[emexes]

while preparing for an interview

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

 

[walterf25]

What field?

Android Developer

 

[emexes]

Found my copy. Published 1980. Front is a bit faded, must have left it out in the Australian sun at some point.

 

[emexes]

which included BASIC code

Lol who remembers the good old days of typing in BASIC programs from magazines and books?!?! (and also "disturbed or disturbing" fellow students)

 

[LucaMs]

the ith of whom is in seat Si. No

Si.No -> italian = Yes. No.
What does "Si" mean?

No two diners are sitting in the same seat

(ChatGPT. It's not that great but Grok did much, much, much worse).

 

[LucaMs]

Lol who remembers the good old days of typing in BASIC programs from magazines and books?!?!

 

[emexes]

What does "Si" mean?

 

[LucaMs]

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.

That's one of the reasons restaurants (or "cafeteria") close down

 

[emexes]

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

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)

 

[PaulMeuris]

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]

Sorry, my answer, after much thought, is...

Takeaway

 

[walterf25]

So, nobody has presented a real solution

 

[Daestrum]

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

 

[walterf25]

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

   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

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?

 

[PaulMeuris]

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

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)...

 

[walterf25]

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

  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

 

[DonManfred]

using a number of seats of 1_000_000_000_000_000

I never saw a Cafeteria Table with this amount of Seats

Even not a Cinema, Concert-Hall, Football-Stadium ;-)

 

[walterf25]

I never saw a Cateria Table with this amount of Seats

Even not a Cinema, Concert-Hall, Football-Stadium ;-)

Clearly you haven't been to my family's parties

 

[PaulMeuris]

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

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...