Implement in-memory data structures and booking API

Q: Implement in-memory data structures and booking API

This question evaluates proficiency in data structures and algorithms, systems-level data modeling, and practical API design by testing in-memory key-value stores, list and string operations, LRU eviction mechanics, linked-list and tree manipulation, and stateful booking behavior.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Oracle.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Oracle during technical interviews.

Question

Loading...

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

SET(key, value)
- Set key to a string value .
- If the key already exists, override the previous value (regardless of prior type).
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.
GET(key)
- Return the value for key , which may be:
  - a string, or
  - a list of strings, or
  - “not found”.
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

Given two sorted singly linked lists, merge them into a single sorted linked list.
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.