Solve four algorithmic library problems

Solve the following coding tasks:

1. Maximum Points from Different Categories: Given an array of items (category, points) and an integer k, choose exactly k items with all categories distinct to maximize the total points. Return the maximum achievable sum.
2. Library Location Management: Design a data structure to manage book locations in a library. Support add(book_id, location), move(book_id, new_location), remove(book_id), and get_location(book_id) in efficient time, where location may include branch, aisle, shelf, and position.
3. Book Checkout Log Validation: Given a chronological list of events (timestamp, book_id, member_id, action in {checkout, return, renew}), validate the log. A book cannot be held by multiple members simultaneously; returns must follow a checkout; renewals only by the current holder; and timestamps for the same book must be non-decreasing. Return a boolean and, if invalid, the index of the first violating event.
4. Two String Validation (no Counter): Given two lowercase strings s and t, determine whether they are anagrams of each other using only basic data structures (e.g., arrays or dicts) and without using collections.Counter. Return true or false.

Part 1: Maximum Points from Different Categories

You are given a list of items, where each item is represented as [category, points]. Choose exactly k items such that no two chosen items have the same category. Return the maximum possible total points. If it is impossible to choose k items with distinct categories, return -1. If k is 0, choose no items and return 0.

Constraints

• 0 <= len(items) <= 100000
• 0 <= k <= 100000
• Each category is an integer in the range [-10^9, 10^9]
• Each points value is an integer in the range [-10000, 10000]
• You must choose exactly k items when possible

Examples

Example 1

Input: ([[1, 10], [2, 5], [1, 7], [3, 8]], 2)
Output: 18

Explanation: The best item from category 1 has 10 points, and category 3 has 8 points. Choosing them gives 18.

Example 2

Input: ([[4, -5], [4, -2], [5, -3], [6, 10]], 2)
Output: 8

Explanation: The best per category values are -2, -3, and 10. The top 2 sum to 8.

Hints

1. For each category, only the item with the maximum points can ever be useful.
2. After reducing to one best value per category, the task becomes choosing the k largest values.

Part 2: Library Location Management

Design a simple library location manager. The system stores the current location of each book. Process a sequence of operations: add a new book location, move an existing book, remove a book, or get a book's current location. A location is represented as an opaque string, such as 'Main:A1:S3:P5', which may encode branch, aisle, shelf, and position.

Constraints

• 0 <= len(operations) <= 100000
• book_id is a non-empty string
• location is a non-empty string for add and move operations
• All operation names are one of 'add', 'move', 'remove', 'get_location'
• Expected average time per operation should be O(1)

Examples

Example 1

Input: ([['add', 'B1', 'Main:A1:S1:P1'], ['get_location', 'B1'], ['move', 'B1', 'East:A2:S3:P4'], ['get_location', 'B1']],)
Output: ['added', 'Main:A1:S1:P1', 'moved', 'East:A2:S3:P4']

Explanation: B1 is added, found, moved, and then found at the new location.

Example 2

Input: ([['add', 'B1', 'L1'], ['add', 'B1', 'L2'], ['get_location', 'B1']],)
Output: ['added', 'exists', 'L1']

Explanation: The second add does not overwrite an existing book.

Hints

1. A hash map from book_id to location gives efficient add, move, remove, and lookup.
2. Decide clear behavior for duplicate adds and operations on missing books before coding.

Part 3: Book Checkout Log Validation

You are given a list of library checkout log events in input order. Each event contains a timestamp, book_id, member_id, and an action in {'checkout', 'return', 'renew'}. Validate the log and identify the first invalid event. A book cannot be checked out by multiple members simultaneously. A return must be made by the current holder. A renewal must be made by the current holder. For each individual book, timestamps must be non-decreasing across that book's events. Equal timestamps are allowed.

Constraints

• 0 <= len(events) <= 100000
• timestamp is a decimal string representing an integer in the range [0, 10^12]
• book_id and member_id are non-empty strings
• action is one of 'checkout', 'return', or 'renew'
• Timestamps are checked independently per book, not globally across all books

Examples

Example 1

Input: ([['1', 'B1', 'M1', 'checkout'], ['2', 'B1', 'M1', 'renew'], ['3', 'B1', 'M1', 'return'], ['4', 'B2', 'M2', 'checkout']],)
Output: [True, -1]

Explanation: All actions are consistent and timestamps for each book are non-decreasing.

Example 2

Input: ([['1', 'B1', 'M1', 'checkout'], ['2', 'B1', 'M2', 'checkout']],)
Output: [False, 1]

Explanation: B1 is already checked out by M1 when M2 tries to check it out.

Hints

1. Track the current holder of each checked-out book.
2. Track the last timestamp seen for each book before validating the action.

Part 4: Two String Validation Without Counter

Given two lowercase strings s and t, determine whether they are anagrams of each other. Two strings are anagrams if they contain exactly the same characters with exactly the same frequencies, possibly in a different order. You may not use collections.Counter or any equivalent built-in frequency counter.

Constraints

• 0 <= len(s), len(t) <= 100000
• s and t contain only lowercase English letters 'a' through 'z'
• Do not use collections.Counter or similar built-in frequency-counting utilities

Examples

Example 1

Input: ('listen', 'silent')
Output: True

Explanation: Both strings contain the same letters with the same frequencies.

Example 2

Input: ('rat', 'car')
Output: False

Explanation: The character counts differ.

Hints

1. If the strings have different lengths, they cannot be anagrams.
2. A fixed-size array of 26 counts is enough for lowercase English letters.