From Data Structures and Algorithms

PlainSpec Practice

The point of these exercises is not to write code or optimize runtime. It is to produce a correct, complete model of the problem: the entities, their relationships, the persistent state, the cases that change behavior, and the simplest algorithm that handles every case.

Choose structures from operations

Do not add a structure because the domain could theoretically use it. Add it when an operation asks for the access pattern that structure provides.

  • Set: default for a collection whose meaning is unique, unordered membership. Use it when the operation asks whether something is present, or needs to add or remove members without preserving order.
  • Dictionary: use when an operation asks to retrieve something by a specific key or identity. Each dictionary should answer a concrete lookup the API actually requires; do not create an index merely because one might be convenient.
  • List: use when order, position, or duplicates are part of the required behavior. A list is not chronological merely because it is a list; that order must be maintained or produced explicitly.
  • Heap: use when an operation repeatedly needs to inspect or remove the current minimum or maximum.
  • Deque: use when an operation needs efficient insertion or removal at both ends.

The heuristic is: name the operation’s required access pattern first, then choose the smallest structure that directly supports it.

Practice 1: Meeting calendar

Design an in-memory meeting-calendar system.

A meeting has one organizer, one or more participants, a start time, and an end time. The organizer is also a participant.

The system must support:

  • creating users;
  • scheduling a meeting only if every participant exists and is available;
  • cancelling a meeting, but only by its organizer;
  • listing a user’s meetings chronologically.

Time intervals are half-open: [start, end), so back-to-back meetings do not overlap. Scheduling must be all-or-nothing: a failed request changes nothing. Assume all inputs arrive in order and ignore persistence, concurrency, and runtime efficiency.

txt
- set of users
- dict: user -> list(meetings)
- global id counter
- a meeting is represented by a (id, start, end) tuple

- case: user is already in system -> do nothing
- case: user is new -> add them to the set of active users

Scheduling a Meeting
- case: all participants (including self) is available -> 1) schedule the meeting in the list of meetings for all participants
- case: one or more participants is not available -> do nothing

Cancelling a meeting:
- case: user is the organizer -> cancel meeting with id for all meeting participants
- case: user is NOT the organizer -> do nothing

Listing meetings chronologically:
- case: is an active user -> return the user's meetings
- case: is not active -> do nothing

Practice 2: Course enrollment Design an in-memory course-enrollment system. Each course has a fixed positive capacity. Students and courses must be created before use. The system must support:

  • enrolling a student in a course;
  • dropping a student from a course;
  • listing a course’s enrolled students and waitlisted students. If capacity remains, enrollment succeeds immediately. Otherwise, the student joins the end of a FIFO waitlist. A student cannot appear twice or be both enrolled and waitlisted for the same course. When an enrolled student drops, the earliest waitlisted student is immediately promoted. A waitlisted student may also drop without affecting enrollment. Requests involving unknown students or courses fail without changing anything. Preserve enrollment order and waitlist order. Ignore persistence, concurrency, and runtime efficiency. Model the entities, relationships, persistent state, operation contracts, mutually exclusive cases, and straightforward algorithms. No code.
txt
State

Course Dictionary:
- keyed on the course name
- stores the 1) students currently enrolled 2) the capacity of the class and 3) a deque of waitlist requests

Student Enrollment Requests Dictionary
- keyed on the student name, representing an active student
- stores a set of requests for a course the student wants to take, stored as a (course, id) pair

Id
- unique identifier for each enrollment operation

Actions

Enroll
- if both the course and student exists, add the course to the student's intended classes along with an enrollment id
- Add student to the class's enrollment list if possible, otherwise the waitlist

Drop
- if both the course and student exists, remove the course from the student's intended courses
- if the student is currently enrolled in the course's enrolled students, remove them
- if the course was previous at capacity (now there is 1 new spot), advance the waitlist repeated until we find a waitlist request who still has the class in the student's course requests

Listing a course's enrolled students
- return the course's enrolled student

Practice 3: Task workflow Design an in-memory task workflow system. Each task has a unique name and zero or more prerequisite tasks. A task may be created only if every named prerequisite already exists. The system must support:

  • creating a task;
  • completing a task;
  • listing every task currently ready to be completed. A task is ready only when all its prerequisites are complete. Completing an unknown, already-completed, or not-yet-ready task fails without changing anything. Ready tasks must be listed in task-creation order. Tasks are never deleted, prerequisites never change after creation, and operations are processed sequentially.
txt

State

Task
- task name
- task index
- completed flag

Tasks Incomplete Prereq Graph (implemented by dict)
- task -> list of prerequisite tasks that are incomplete

Task Enabling Graph (implemented by dict)
- reverse of the prev graph
- task -> list of children that have the task as its prerequisite

Global Index
- starts from 0 and counts up as tasks get created

Ready Tasks
- set of tasks

Creation(task name, list of prerequisites)
- check if every prerequisite of task is in our existing prerequisite graph as registered tasks
- if not, raise: cannot add task whose prerequisites have yet to be registered
- if so, add task and its prereqs to the graph
- if the task's prereq list ie empty add it to ready tasks

Completion(task name)
- if task is in ready tasks, mark task as completed and remove from ready
- go through all of the task's children and remove this task from each child's incomplete prereq graph
- add any completed children to the ready tasks if their prereq list is now empty


Listing every task that can be completed
- sort all the tasks in ready tasks by index and return as a list

Practice 4: Auction Design an in-memory auction system. Bidders must be registered before participating. Each bidder may have at most one active bid. The system must support:

  • registering a bidder;
  • placing a positive-valued bid;
  • withdrawing a bidder’s active bid;
  • returning the current winning bid. Placing a new bid replaces that bidder’s previous active bid. The winner is the active bid with the highest amount. If several active bids have the same amount, the bid placed earliest wins. A replacement bid receives a new placement time. Registering an existing bidder, bidding from an unknown bidder, placing a nonpositive bid, or withdrawing without an active bid fails without changing anything. If no active bids exist, there is no winner. Assume operations are sequential. Correctness comes first, but repeated winner queries should not require scanning every bidder if a natural design avoids it. Model the named state, operation cases, and algorithms. No code.
txt

State
- We store a dictionary containing each bidder's bid mapping bidder -> (bid price, time)
- Time counter, starts at 0 and increments with each bid
- Heap containing (bid price, time) tuples that has the highest bid on top, with ties broken by the earliest timestamp

Registering
- case: bidder already exists in our dictionary of bidders -> do nothing
- else: update the bidder's bid to None

Placing a bid
- update the bidder's bid to reflect the new (bid, time) value
- insert (-bid, time) into a min-heap

Withdrawing a bid
- update the bidder's bid to None

Retruning winning bid:
- pop from the top of the heap, checking each time if the bid is still active by looking up the bid in our bidder dictionary
- return the first active bid
- if the heap has no elements, return None

Design an in-memory versioned key-value store. Every successful write receives a strictly increasing integer timestamp. The system supports:

  • setting a key to a value;
  • deleting a currently active key;
  • retrieving a key’s value as of any timestamp. A historical query returns the value from the latest set at or before the requested timestamp, unless a deletion after that set but no later than the requested timestamp made the key inactive. A later set may reactivate a deleted key. Historical queries may arrive in any order and never change state. Deleting an inactive or unknown key fails without changing anything. Model the named state, cases, and core algorithms. No code.
txt

State
- dictionary of each key's value record mapping key -> list((timestamp, value))
- global timestamp counter that increments with every action (lets assume integers)

Setting a key to a value:
- given a key, value pair
- append (current timestamp, value) to the key's value record
- return the current timestamp, then increment the timestamp

Deleting a key:
- if key doesn't have any value record OR the latest value is already None, raise error
- append (current timestamp, DELETED) to the key's value record
- return the current timestamp, then increment the timestamp

Retrieving a key’s value as of any timestamp.
- Do binary search on the key's historical values, using the timestamp
- Find the value at the greatest timestamp less than or equal to the queried timestamp
- If the value at that timestamp is DELETED, return None
- Otherwise, return that value