Implement in-memory data structures and booking API

Part A — Implement a simplified Redis-like in-memory store (Go)

Implement an in-memory key-value store that supports string values and list-of-strings values.

Supported operations

1. SET(key, value)
   • Set key to a string value .
   • If the key already exists, override the previous value (regardless of prior type).
2. LIST_PUSH(key, value)
   • Treat key as a list of strings .
   • Push value to the head of the list.
   • If the key does not exist, create a new list.
   • If the key exists as a string, define the expected behavior (e.g., overwrite to a list, or return an error) and be consistent.
3. GET(key)
   • Return the value for key , which may be:
     • a string, or
     • a list of strings, or
     • “not found”.
4. LIST_REMOVE(key, count, value)
   • Remove elements equal to value from the list at key .
   • Removal semantics:
     • if count > 0 : remove the first count matching elements scanning from head → tail.
     • if count < 0 : remove the last |count| matching elements scanning from tail → head.
     • if count = 0 : remove all matching elements.
   • Return an appropriate result (e.g., number removed, or error if key missing/not a list).

Notes / constraints

• Expiration/TTL support is deferred (do not implement unless asked).
• Aim for clean interfaces and well-defined error cases.
• Assume single-process, in-memory storage (no persistence required).

Part B — LRU cache

Design and implement an LRU (Least Recently Used) cache with typical operations:

• Get(key) -> value or not found
• Put(key, value)

Constraints/requirements:

• Fixed capacity C .
• Get / Put should be O(1) average time.
• When capacity is exceeded, evict the least recently used item.

Part C — Merge sorted linked lists

1. Given two sorted singly linked lists, merge them into a single sorted linked list.
2. Follow-up: Given K sorted singly linked lists, merge them into one sorted list.

Clarify:

• Whether you can reuse nodes (in-place) or must allocate new nodes.
• Expected time complexity targets.

Part D — Delete target leaf nodes from a binary tree

Given a binary tree root and an integer target, repeatedly delete all leaf nodes whose value equals target.

• After deletions, a parent may become a new leaf; if its value is also target , it should be deleted as well.
• Return the resulting tree root (which may be null ).

Part E — Hospital appointment booking API (implementation-focused)

Implement a stateful API/service for booking appointments.

Scenario

• A hospital has 1,000 doctors .
• Each doctor works 9:00 AM to 5:00 PM .
• Appointment slot duration is 15 minutes .

Required behavior

• Provide an operation such as Book(doctorId, date) -> bookedTimeSlot | error .
• The call should book the first available 15-minute slot for the given doctorId on the given date .
• If there is no availability, return an error.
• The system must maintain booking state across API calls (e.g., across multiple POST requests during the program run).

Clarifications to handle

• Timezone/date representation.
• Concurrency expectations (e.g., two callers booking the same doctor/date at the same time).
• What data structure you will use to track availability efficiently.