Programming Brain Teaser 001

Consider the following struct(s):

struct my_data {
/* ... */
};
struct sparse_sorted_data {
    uint32_t occupied_flags = 0;
    struct my_data data[32] = {};
};

Our application allocates an instance of the defined sparse_sorted_data struct.

Occupied and free slots are tracked using the bits of sparse_sorted_data::occupied_flags.

Data is stored within the 32-length sparse_sorted_data::data array.

Example:
occupied_flags = 0 -> empty, all slots available
occupied_flags = 1 -> slot 0 occupied

During normal operation of the application, any given index of the array can be marked as free or no longer occupied. The application properly handles updating occupied_flags when this happens.

This newly-freed index may now have data moved into it again. However, to preserve accurate ordering, new data will ALWAYS be inserted into slot 0 and all contiguous occupied indexes will be shifted into the next available slot.

Task:

Using the language of your choice, write a function to update the integer when a new struct is inserted at the front of the array.

The function should:

• accept an integer
• update the integer by occupying slot 0, shifting any existing contiguous bits
• return the modified result

Use the validity tests table below to ensure application accuracy.

Note: you may safely assume the application will not call this function where the result would lead to an invalid state (overflow, etc), therefore no error handling is necessary.

C function definition example:

uint32_t
update_index_inserted(uint32_t occupied_flags) {
    // update bits
    return occupied_flags;
}

Validity tests:

Hint 1: This logic is equivalent to walking a batter in baseball. A runner on first would be pushed to second. A runner on second would be pushed to third if and only if there is also a runner on first.

Hint 2: Reminder that manipulating the array data is handled elsewhere by the application.

Bonus Problem:

Our application has a new requirement to ensure that N number of slots at the beginning of the array are marked as open after an insert.

Task

Write a new function that takes an additional parameter shift. shift represents the number of slots by which the new data should be shifted. Slots [0,shift) should be marked unoccupied.

A value of 0 for shift is equivalent to the base function.

Like before, the application is ensured to call the function if and only if the result will be valid (no data overflows). No error checking or handling is needed.

C function definition example:

uint32_t
update_index_shifted(uint32_t state, uint8_t shift) {
    // update bits && shift
    return state;
}

Validity tests:

Hint 1 You may call the original function from part 1.

Hint 1 This logic is equivalent to a ground rule double in baseball. A runner on first or second (but not both) would be pushed to third.

Final Thoughts

I would be curious to hear the steps or process that you go through to solve this brain teaser.

I would also be curious to hear if you attempted to use AI to solve this problem, and the wild answers it gave you (I was amused).

I will eventually write a new post detailing my experience with this problem.

I will update this post and link to the solution once written.

Updates:

1.0 : Initial release.

1.1 : Add Final Thoughts section. Add sparse_sorted_data struct to better illustrate the relationship between the data and the tracking integer. Clarify several descriptions of the hypothetical application, some of which were unnecessary or obtuse. Clarify expectations from the user.