Katkat
Back

Library Catalog and Lending System: Five-Phase Engineering Assessment

InstacartSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentSoftware Engineering Fundamentals

Last updated

This problem tests the ability to design an extensible lending system, implement a search algorithm with concurrency constraints, and debug race conditions in a multi-threaded environment.

Library Catalog System

You are tasked with building a thread-safe Library Catalog API that supports searching for books and managing lending operations.

Part 1: Architecture

Design a class LibraryManager that holds a catalog of books. Each book has an ID, title, author, and an is_available status.

Part 2: Implementation

Implement the following methods:

  1. search_books(query: str): Returns a list of books matching the title or author (case-insensitive partial match).
  2. borrow_book(user_id: str, book_id: str): Atomically attempts to mark a book as unavailable. Returns True if successful, False if already checked out.
  3. return_book(book_id: str): Marks a book as available again.

Constraints

  • The system must handle concurrent requests to borrow_book without ever assigning the same book to two users.
  • Assume a catalog size of 10,000 books.
  • Memory usage should be optimized for frequent searches.

Example

# Setup
lib = LibraryManager(books=[{"id": "1", "title": "The Hobbit", "author": "J.R.R. Tolkien"}])

# Scenario
lib.borrow_book("user_A", "1") # returns True
lib.borrow_book("user_B", "1") # returns False
lib.return_book("1")
lib.borrow_book("user_B", "1") # returns True

Part 3: Debugging

You are provided with a legacy implementation where borrow_book first checks if book.is_available and then sets book.is_available = False. Explain how a race condition occurs here and provide the corrected code snippet using appropriate locking mechanisms.

Hints

Hint 1

Use a data structure like a Trie or an Inverted Index to optimize `search_books` beyond O(N) linear scanning.

Hint 2

Utilize a ReentrantLock or a mutex on each book object to ensure atomicity during the state transition from 'available' to 'borrowed'.

Hint 3

For the debugging portion, emphasize the 'check-then-act' fallacy and how wrapping the check and the update within the same lock block prevents interleaving.

Follow-up questions

  • How would you modify the system to track the lending history (who borrowed what and when) without degrading search performance?
  • If the library catalog were distributed across multiple microservices, what changes would you make to ensure consistency in borrowing?
  • How would you implement a 'waitlist' feature for books that are currently checked out, and what data structures would you use to notify users when a book is returned?