Seating random groups of people at a random number of tables
Download the code and
download the supporting library utlist.h
The final challenge for my coding test was to write an algorithm to seat groups of random size at a limited number of tables. We are allowed to seat two groups at the same table, provided there are enough chairs.
This looks like it should be simple - restaurants do this every day. But it gets more complicated when it scales up. When we have, say, 100 tables (of different sizes), and 10,000 customers, it becomes extremely difficult. The complexity of the solution will be around O(n), depending on the exact algorithm I use. Good implementations can get down to O(logn), and I think I can do better for this particular problem.
So the important thing is to get a solution that works well enough, given my time limit and goals. Luckily, this is a common problem, which appears in situations like allocating memory and disk space in computers. Your computer is doing this hundreds of times per second while reading this article. A lot of people have written about the solutions to this problem e.g. memory pools, free lists and the buddy memory allocator, and SLUB allocators.
What are the strategies here? The default strategy is to not have a strategy. Every time you need to seat a new group at a table, just walk along the tables until you find one that has enough spaces, then seat the new group there. This has the appeal of not needing any extra data structures or complicated code. Unfortunately this strategy guarantees that eventually you will have a couple of people lingering at every table, which will prevent the largest groups from being seated, even though you have enough seats for them. But those seats are scattered across many tables, and the group insists on being seated together at the same table.
You can fix this by asking current diners to move to a nearby table and share with another group, until you have made an empty table to seat your large group. This works, but not well. It is slow when the restaurant is nearly full, which is the exact time when you don't want to be doing extra work. In a computer, it is even worse, because you typically have to pause the whole computer while moving a group. And it is possible to get to the point where the computer spends more time trying to organise the tables than actually doing any work. Thesedays there are solutions that don't require a pause, but they are quite complicated.
A popular and simple solution is to keep a "free list". We will note which tables are free, and cross them off the list as people come in.
| 4 seats |
8 seats |
16 seats |
| Table A |
Table D |
Table G |
| Table B |
Table E |
Table H |
| Table C |
Table F |
Table I |
When a group of 5 comes in, we can immediately find a table large enough for them (at table D which has 8 seats). Now we adjust our free lists, noting that Table D has 3 free seats left. This takes a little bit of time, but this amount of time doesn't get longer no matter how many tables or people we have (in theory). Seating people is always fast with free lists, which is important for providing services quickly in a computer.
| 3 seats |
4 seats |
8 seats |
16 seats |
| Table D |
Table A |
Table E |
Table G |
|
Table B |
Table F |
Table H |
|
Table C |
|
Table I |
This was the solution I chose to submit. It is acceptably fast, doesn't use too much memory, and should not have any "worst case scenarios" that cause it to lock up or become unacceptably slow. In practise, it will get slower the more tables you have, and will spend a lot of memory storing the lists, but it only wastes a lot of memory if you already have a lot of memory to keep track of, so that works out nicely.
The algorithm has bad locality of reference, which means it will cause physical caches to function badly. But I can't tune that until I know what kind of machine it would be running on, so the solution ends here.
Recently I've been thinking of turning it into a user space malloc library, so the first change I would have to make would be to switch the table sizes into multiples of 2. Because in base 2, we can reduce the number of free lists by breaking everything down to a power of 2.
| 1 seat |
2 seats |
4 seats |
8 seats |
16 seats |
| Table D |
Table D |
Table A |
Table E |
Table G |
|
|
Table B |
Table F |
Table H |
|
|
Table C |
|
Table I |
This cuts down the number of free lists to log2(n), where n is the largest group we will accept. To keep track of all the possible free memory in my computer, I only need 64 free lists to account for 17000000000000 Mib of memory. Of course, those lists might get a bit long....
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "utlist.h"
#define maxTables 100
#define maxCustomers 100000
#define log //printf //Uncomment printf to print debug messages
typedef void* pointer;
typedef struct Table {
char name[20];
int size;
int vacant;
} Table;
enum counters_enum {
ARRIVED,
ENQUEUED,
QUEUE_SCANS,
QUEUE_HOPS,
PERFECT_FIT,
NOT_PERFECT_FIT,
MAX_QUEUE_LENGTH,
LEFT_WITHOUT_BEING_SEATED,
LEFT_FROM_TABLE,
QUEUE_TO_TABLE
};
int counter[20]; //Collect some statistics
typedef struct CustomerGroup {
int id;
int size;
Table* table;
struct CustomerGroup *next, *prev;
} CustomerGroup;
struct CustomerGroup* customers= NULL;
CustomerGroup* customerPool[maxCustomers];
Table* tables[7][maxTables]; //We could have almost all the tables end up in queue 2
CustomerGroup *waiting = NULL; //The groups-waiting queue
int maxTableSize=6;
int queue_length=0;
int lastTable[7]; //Pointer to the last free table in free list
int initted = 0; //Safety check that data structure have been initialised.
/* Seat a group, either at a table or on the waiting list */
void arrives(CustomerGroup* aGroup) {
int i;
assert(initted);
log("Seating group of size %d\n", aGroup->size);
int tablesize = canSeat(aGroup);
assert(tablesize<maxTableSize+1);
log("canSeat recommends a table of size %d, and there are %d tables of size %d free.\n", tablesize, lastTable[tablesize], tablesize);
if(tablesize) {
if (tablesize == aGroup->size) {
aGroup->table = tables[aGroup->size][lastTable[aGroup->size]--];
aGroup->table->vacant-=aGroup->size;
counter[PERFECT_FIT]++;
log("Assigned group %d of size %d to table %s, vacant seats: %d, lastTable: %d\n", aGroup->id, aGroup->size, aGroup->table->name, aGroup->table->vacant, lastTable[aGroup->size]);
} else {
aGroup->table = tables[tablesize][lastTable[tablesize]--];
aGroup->table->vacant-=aGroup->size;
log("Assigned group %d to table %s, vacant seats: %d, lastTable: %d\n", aGroup->id, aGroup->table->name, aGroup->table->vacant, lastTable[tablesize]);
counter[NOT_PERFECT_FIT]++;
return;
}
} else {
//We're out of tables, add the customer group to the queue
log("Adding customers to wait queue\n");
DL_APPEND(waiting, aGroup);
counter[ENQUEUED]++;
queue_length++;
counter[MAX_QUEUE_LENGTH]=(queue_length)>counter[MAX_QUEUE_LENGTH]?queue_length:counter[MAX_QUEUE_LENGTH];
}
log("arrived: %d, fit: %d, partial fit: %d, queue_length %d\n", counter[ARRIVED], counter[PERFECT_FIT] , counter[NOT_PERFECT_FIT] , queue_length);
assert(counter[ARRIVED] == counter[PERFECT_FIT] + counter[NOT_PERFECT_FIT] + queue_length+counter[LEFT_WITHOUT_BEING_SEATED]);
}
CustomerGroup* scanForMaxSize(CustomerGroup* aList,int size) {
counter[QUEUE_SCANS]++;
for (aList=aList->next;aList;aList=aList->next) {
counter[QUEUE_HOPS]++;
if (aList->size<=size) { return aList;}
}
return NULL;
}
/* Check the free lists to see if there are any tables, at all, that can hold the group */
int canSeat (CustomerGroup* aGroup) {
int i;
log("Checking if we can seat group %d of size %d\n", aGroup->id, aGroup->size);
if(lastTable[aGroup->size]<1) {
log("Attempting to seat group at a larger table\n");
if (aGroup->size<maxTableSize) {
//Maybe we can fit the group at a bigger table
for (i=aGroup->size; i<maxTableSize+1;i++) {
if (lastTable[i]>0) return i;
}
}
} else {
return aGroup->size;
}
return 0;
}
/* See if we can seat any groups from the waiting list. Groups can "jump the queue" if they are smaller than the groups in front */
void reSeat() {
int i;
CustomerGroup* candidate;
if(queue_length) {
//Attempt to seat the first group on the list
counter[QUEUE_SCANS]++;
for (candidate=waiting;candidate;candidate=candidate->next) {
counter[QUEUE_HOPS]++;
if(canSeat(candidate)) {
queue_length--;
DL_DELETE(waiting, candidate);
arrives(candidate);
counter[QUEUE_TO_TABLE]++;
return;
}
}
}
}
/* A group leaves their table (or the waiting list - NOT GOOD). Adjust the lists appropriately */
void leaves(CustomerGroup* aGroup) {
assert(initted);
if(aGroup->table) {
//If the party was seated
log("Removing group %d from table %s(%d), next: %d, prev: %d\n", aGroup->id, aGroup->table->name, aGroup->table, aGroup->next, aGroup->prev);
aGroup->table->vacant+=aGroup->size;
tables[aGroup->table->vacant][++lastTable[aGroup->table->vacant]]=aGroup->table;
aGroup->table=NULL;
//Now we have an empty table, let's try to reseat someone from the queue
reSeat();
counter[LEFT_FROM_TABLE]++;
} else {
//They are still in the queue
log("Removing group of size %d from queue, next: %d, prev: %d\n", aGroup->size, aGroup->next, aGroup->prev);
DL_DELETE(waiting,aGroup);
queue_length--;
counter[LEFT_WITHOUT_BEING_SEATED]++;
assert(queue_length>=0);
}
log("Queue length: %d\n", queue_length);
}
/* Returns the table that a group is seated at */
/* I chose to modify the customer data structure to add a table value, so finding the table is trivial. If I couldn't alter the data structure, I could always just wrap the customer struct in a new struct to keep track of data. I think both these solutions are better than yet another list to track groups->tables. */
Table* locate(CustomerGroup* aGroup){
assert(initted);
return aGroup->table;
}
/* Make sure it all works (it didn't the first time!). Create a lot of customer groups (customers), have them all arrive at the restaurant, then leave. */
int test (int customers) {
int i;
int leaveGroup = 0;
for (i=0;i<customers/2;i++) {
counter[ARRIVED]++;
CustomerGroup* testGroup =(CustomerGroup*)calloc(1, sizeof(CustomerGroup));
testGroup->size = rand()%6+1;
testGroup->id = i;
customerPool[i] = testGroup;
/* Group arrives at restaurant */
log("Customer group %d is arriving...\n", i);
arrives(testGroup);
assert(customerPool[0]->table);
}
/* Simulate churn - one group leaves, another group arrives */
for (i=customers/2;i<customers;i++) {
counter[ARRIVED]++;
CustomerGroup* testGroup =(CustomerGroup*)calloc(1, sizeof(CustomerGroup));
testGroup->size = rand()%6+1;
testGroup->id = i;
customerPool[i] = testGroup;
/* Group arrives at restaurant */
arrives(testGroup);
/* Another group leaves */
log("Customer group %d is leaving...\n", leaveGroup);
leaves(customerPool[leaveGroup]);
free(customerPool[leaveGroup]);
leaveGroup++;
}
/* Customers leave */
while (leaveGroup<customers) {
log("Customer group %d is leaving...\n", leaveGroup);
leaves(customerPool[leaveGroup]);
free(customerPool[leaveGroup]);
leaveGroup++;
}
}
/* Allocate structures */
void init() {
int i,t;
srand(time(NULL));
for(t=2;t<7;t++) {
for (i=1; i<maxTables; i++) {
tables[t][i]=(Table*)calloc(1,sizeof(Table));;
tables[t][i]->size=t;
tables[t][i]->vacant=t;
snprintf(tables[t][i]->name, 19, "%d-%d", t, i);
}
lastTable[t]=maxTables-1;
}
initted=1;
}
int main(int argc, char* argv[])
{
init();
test(90000);
/* At first my implementation didn't work, so I started added debugging information to track what was going on. It made a nice summary */
printf("%d groups arrived. Seated %d groups at a table of the same size, and %d at a larger table than was necessary. %d groups had to wait in queue, and the maximum queue length was %d. %d moved from the queue to a table. %d queue scans performed, visiting %d list elements in total, for an average of %d items per scan. %d groups left without being seated, %d left from a table.\n", counter[ARRIVED], counter[PERFECT_FIT], counter[NOT_PERFECT_FIT], counter[ENQUEUED], counter[MAX_QUEUE_LENGTH], counter[QUEUE_TO_TABLE], counter[QUEUE_SCANS], counter[QUEUE_HOPS], counter[QUEUE_HOPS]/(1+counter[QUEUE_SCANS]), counter[LEFT_WITHOUT_BEING_SEATED], counter[LEFT_FROM_TABLE]);
}