Cuez - Tinkelist Assignment to Theofanis Vardatsikos

Coding challenge - Part Position.md

Cuez - Tinkelist Assignment

Coding challenge - Part Position answered by Theofanis Vardatsikos (vardtheo@gmail.com).

What potential actions do you identify as requiring a recalculation of positions in the Parts linked to the Episode?

Actions create and update require recalculation of positions. For update only when the position is changed. Position would not need to be sequential in order for indexing to work e.g., 1,4,5,7 would be acceptable, then delete does not need recalculation. However, if position is required to be sequential then recalculation is needed also in delete. I assume another endpoint exists solely for sorting all the parts, in UI terms it could be a list with draggable records, then recalculation is needed at the endpoint.

What API Request payload structure would you use to reliable place the Parts in the position they should end up on? Consider separate endpoints to add, delete and sort Parts.

For adding Parts

• I would suggest to simply add the position property in the request sent.
  • This might produce false result when two users send the request simultaneously with the same position. In this occasion one of them would be moved one position after the other. Finally, we would have to recalculate the position for the ones after it.
• Another method would be to send ... "position_after": 1 .... position_after is the id of the previous Part, so this new Part must be added after that existing part. It is like using the existing Part as pointer like a node in a linked list. A similar approach could be used for position_before.
  • However, if the existing part is deleted by the time the user submits the request then this could result in error.
  • Also, if the existing part has been moved to another position until the user submits the request, then the new one will be implicitly moved. However, this might be the correct result if the two Parts have some logic correlation between each other.
• Third option would be to send an array of the ids of all the Parts. The sequence of each id would imply the position of the equivalent Part. One of these items would be a placeholder for the new item. This would result in setting up the absolute correct list, but possibly overwriting existing changes that were made until the form was submitted.

If I could have more information I could select the most appropriate option or even provide an alternative one better suited for your requirements.

For deletion simply delete the particular Part. If sequential positions are required then recalculate the position of all the Parts after it.

For sorting send an array of ids of all the Parts (the same as the third approach from addition). The sequence of each id in the array would imply the position of each Part. This would result in setting up the absolute correct list, but possibly overwriting existing changes that were made since the user loaded that page and until the form was submitted.

Implement the calculation of the new positions for Parts when changes are performed that affect them.

Ideally, the best approach would be to make all the necessary changes withing a single query. In this way we eliminate errors by minimising back-forth between PHP and SQL otherwise we would need to wrap those PHP statements in a SQL transaction. Additionally, limiting back-forth between PHP and SQL and not using transaction would result in significantly less execution time. Which in each turn would produce less delay for the consequent requests as it would lock the SQL tables for significantly less time, and that is an imperative requirement for repeating changes in a large dataset.

Having said all that, the following Laravel code updates the position of all Parts from an array of IDs like in sorting in the previous question in a single upsert statement.

$ids = [10, 13, 7, 18, 11]; // IDs of Parts in the same sequence as they should be positioned.
$upsert = array_map(fn(int $id, int $index) => ['id' => $id, 'position' => $index], $ids);
Part::upsert($upsert, ['id'], ['position']);

An alternative implementation (maybe not so performant) with the same result would be.

$ids = [8, 1, 5, 2, 3, 7]; // Sanitize contents for sql-injection
Part::whereIn('id', $ids)->update(['position' => DB::raw("FIND_IN_SET(id, '" . implode(',', $ids) . "')")]);
// UPDATE parts SET position = FIND_IN_SET(id, '8,1,5,2,3,7') WHERE id IN (8,1,5,2,3,7);

In the following code we change the position of one Part and recalculate the position for every Part in the range between the old and new position. The rest of the Parts [below min(new,old), above max(new,old)] remain unchanged since they are not affected. In a single query we change the position for the designated Part and increase/decrease all the other Parts by one according to whether the designated Part moved down/up respectively.

$part = Part::findOrFail($some_id); 
$old_position = $part->position;
$new_position = 3; // Recalculate all Parts between old and new position.
$sign = $old_position < $new_position ? -1 : 1; // Whether the rest of the Parts need to be increased/decreased.
Part::where('episode_id', $part->episode_id)
    ->whereBetween('position', [min($new_position, $old_position), max($new_position, $old_position)])
    ->update(['position' => DB::raw("IF(id = {$part->id}, $new_position, position + $sign)")]);

Do you have another approach on how this can be tackled efficient and reliably at scale?

Another solution would be to create endpoints for increasing/decreasing position by one, or exchanging the position between two specific Parts. These solutions have straight-forward implementation with limited room for error. However, I am skeptical about these solutions, because I do not believe they would be particularly useful for the users.

I do not have enough information about the infrastructure, the needs of the users, or how they use the platform. I could definitely provide more refined solutions had been given more details about the issue. Nevertheless, the previous solutions should be adequate as a starting point.

---

Thank you for your consideration, looking forward to your assessment❗️

Problem solving - transaction Structure.md

Cuez - Tinkelist Assignment

Problem solving - transaction Structure answered by Theofanis Vardatsikos (vardtheo@gmail.com).

As stated in the previous part: Ideally, the best approach would be to make all the necessary changes withing a single query. In this way we eliminate errors by minimising back-forth between PHP and SQL otherwise we would need to wrap those PHP statements in a SQL transaction. Additionally, limiting back-forth between PHP and SQL and not using transaction would result in significantly less execution time. Which in each turn would produce less delay for the consequent requests as it would lock the SQL tables for significantly less time, and that is an imperative requirement for repeating changes in a large dataset.

The solution I came up with is copying all the records for each level of hierarchy at database level like so.

INSERT INTO Items (name, some_attribute, ..., episode_id)
SELECT name, some_attribute, ..., <specific_new_episode_id>
FROM Items
WHERE part_id = <the_source_part_id>;

This helps in duplicating records in packs, instead of one-by-one saving some time. Then I query for the new records and proceed to the next level of the hierarchy, with the duplication of their nested items. The algorithm uses depth-first approach. To minimize queries for loading all the hierarchy structure of the Episode needing copy I utilize Laravel's eager loading mechanism. All insert queries are wrapped inside a transaction so in case of any failure then all records will be deleted, preventing the accumulation of junks in the DB. To mitigate the risk of stalling other users due to table lock, then a second read-only replica would be pretty usefull. This works for any number of items in any step of the hierarchy. It should be noted that the more the items items that need cloning then probably (but not necessarily) more time is needed to complete. I have attached real (but not tested) code below.

<?php

namespace App\Services;

use Illuminate\Database\Eloquent\Model;
use Illuminate\Support\Str;

class DuplicationService
{

    public function duplicate(Episode $old_episode): Episode
    {
        // Eager load all nested models to minimize future queries.
        $old_episode->loadMissing(
            'parts',
            'parts.items',
            'parts.items.blocks',
            'parts.items.blocks.blockFields',
            'parts.items.blocks.media',
        );

        return DB::transaction(function () use ($old_episode) {
            $new_episode = $old_episode->replicate();
            $new_episode->save();

            $this->duplicateRecordsOf($old_episode, $new_episode);


            return $new_episode;
        });
    }

    private function nextInHierarchy(Model $model): ?Model
    {
        $hierarchy = [Episode::class, Part::class, Item::class, Block::class, [BlockField::class, Media::class]];

        // ...
        // Find the next class in the hierarchy from the one provided.
        // e.g. Part => Item, Block => BlockField, BlockField => Media, Media => null.

        return new $next_class;
    }

    /**
     * Start the cloning for each step in hierarchy for each item in every step, depth first.
     */
    private function duplicateRecordsOf(Model $source, Model $target): void
    {
        $next_entity = $this->nextInHierarchy($source); // Episode => Part::class
        $attributes_to_clone = $this->getAttributesToClone($next_entity);
        $relation = Str::of(class_basename($next_entity))->plural()->camel()->toString(); // '/.../Models/Part' => 'parts'
        $parent_key = $source->getForeignKey(); // It is the equivalent foreign key for each model, e.g. Episode => episode_id

        // Check if the object has no nested items and return early.
        if ($source->{$relation}->isEmpty()) {
            return ;
        }

        // Sort all items of the relation by asc id, this is probably the default behaviour, but we have to be sure.
        $source->{$relation}->sortBy($next_entity->getKeyName());

        $subselect = $next_entity::select($attributes_to_clone)
            ->selectRaw($target->getKey())
            ->where($parent_key, $source->getKey())
            ->orderBy($next_entity->getKeyName());

        // Clone all first-level descendants ot this class with one query.
        $next_entity::insertUsing(array_merge($attributes_to_clone, [$parent_key]), $subselect);

        // Get all the newly cloned records and start the duplication for each of their nested items.
        $cloned_entities = $next_entity::where($parent_key, $target->getKey())->get();
        foreach ($cloned_entities as $i => $cloned_entity) {
            $this->duplicateRecordsOf($source->{$relation}[$i], $cloned_entity); // Clone its nested items recursively.
        }
    }

    private function getAttributesToClone(Model $model): array
    {
        return ['attribute_1', 'attribute_2', '...']; // ... some actual calculation per model class
    }
}

---

Thank you for your consideration, looking forward to your assessment❗️