Implement a versioned recipe management system

You are asked to implement an in-memory Recipe Management System (similar in difficulty to a simple banking/in-memory DB exercise). The system supports incremental feature “levels”. Design the data structures and implement the required APIs.

Data model

Assume each Recipe has at least:

• recipeId (unique string or integer)
• name (string)
• size (integer; used only for sorting)

Assume each User has at least:

• userId (unique)
• userName

No persistence is required (everything is in memory).

Level 1: Basic CRUD for recipes

Implement the following operations:

• addRecipe(recipe): add a new recipe (reject or overwrite if recipeId already exists—state your choice clearly).
• updateRecipe(recipeId, fields...): update an existing recipe.
• getRecipe(recipeId): return the recipe or “not found”.
• deleteRecipe(recipeId): delete an existing recipe.

Define expected behavior for edge cases (e.g., updating/deleting a non-existent recipe).

Level 2: Search and list

Implement:

• searchRecipes(query): search recipes by name, case-insensitive (define whether it’s exact match or substring match; choose one and be consistent).
• listRecipes(sortBy): return all recipes sorted by either:
• name (lexicographic, case-insensitive), or
• size (numeric ascending)

Specify tie-breaker behavior (e.g., tie-break by recipeId).

Level 3: Add user

Implement:

• addUser(user): add a user (keep it simple—no extra features unless needed).

Define behavior on duplicate userId.

Level 4: Version history and rollback

Add versioning to support:

• versionHistory(): return stored version metadata (at minimum, a monotonic versionId and what changed).
• rollback(versionId): restore the system state to exactly how it was at that versionId.

Guidance: treat each mutating operation (e.g., add/update/delete recipe, add user) as producing a new version; maintain whatever additional structures you need (e.g., a versionMap).

Constraints / expectations

• Assume up to ~100k recipes/users.
• Aim for clean APIs and reasonable time complexity.
• You may implement this as a class/module with methods in your preferred language.