Skip to main content

Morgan Stanley

Morgan Stanley OA 2024 - Count Book Misses

Problem Description:

A library follows a strategy to issue books to its members. If a requested book is not available in the library and there is no more space for new books, the least recently used book is removed to make space for the requested one. If there is space, the requested book is added to the library and marked as the most recently used. Only one copy of each book is allowed in the library. If a requested book is already in the library, it becomes the most recently used book.

Your task is to determine how many times the library "misses" when a book is requested but not available in the library.

Input Format:

  • The first line contains a single integer N, the number of book requests.
  • The second line contains N space-separated integers, representing the sequence of book requests made by members.
  • The last line contains a single integer size, representing the maximum size of the library number of books it can hold.

Output Format:

  • Print a single integer representing the number of times the library "missed" when issuing a book.

Constraints:

  • 1 <= N <= 10^5
  • 1 <= size <= 50
  • The book numbers range between 1 and 50.

Sample Input:

6
1 2 1 3 1 2
2

Sample Output:

4

Explanation:

  1. The library starts empty. Book 1 is requested. Miss → Add book 1 to the library.
    • Library: [1]
  2. Book 2 is requested. Miss → Add book 2 to the library.
    • Library: [1, 2]
  3. Book 1 is requested again. It is already in the library, so no miss. Book 1 becomes the most recently used.
    • Library: [1, 2] (but book 1 is now the most recently used)
  4. Book 3 is requested. Miss → Remove least recently used book (book 2), and add book 3 to the library.
    • Library: [1, 3]
  5. Book 1 is requested again. No miss. It is already in the library and becomes the most recently used.
    • Library: [1, 3] (but book 1 is now the most recently used)
  6. Book 2 is requested. Miss → Remove least recently used book (book 3), and add book 2 to the library.
    • Library: [1, 2]

Total misses: 4.

Note:

The problem revolves around implementing the Least Recently Used (LRU) caching strategy to manage the library's book inventory and count the number of misses during the process.