Skip to main content

Morgan Stanley

Morgan Stanley OA-9 2024

Problem Description

The library has a strategy for issuing books to its members. If a requested book is not available and there is no space for new books, the least recently used (LRU) book is removed to make room for the requested one. If there is space, the book is added and marked as the most recently used. If a requested book is already in the library, it simply becomes the most recently used.

Your task is to determine how many times the library experiences a "miss," which occurs when a requested book is 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.