Razorpay | OA (1st Round) | Senior MLE | Bengaluru

Implement a cache using the Least Frequently Used (LFU) eviction policy. When the cache reaches its capacity, remove the least frequently used key. If there's a tie, remove the smallest key among those with the least frequency.

Function Signature:

def solve(N: int, Q: int, operations: List[List[int]]) -> List[int]

Parameters:

• N: Capacity of the cache
• Q: Number of operations
• operations: List of operations where:
  • Type 1: 1 key → Get value from cache
  • Type 2: 2 key value → Insert/Update key-value pair

Constraints:

• 1 ≤ N ≤ 5 * 10^4
• 1 ≤ Q ≤ 2 * 10^5
• 1 ≤ key ≤ 2 * 10^5
• 1 ≤ value ≤ 10^9

Sample Input:

2
5
1 2 -1
2 1 3
2 2 4
2 4 5
1 2 -1

Sample Output:

-1 4

You're given a string S. Split it into parts such that each character appears in at most one part. The score of a part is the square of its length. Minimize the total score across all parts.

Function Signature:

def solve(S: str) -> int

Scoring Rule:

• For part of length x, score = x^2

Constraints:

• 1 ≤ len(S) ≤ 500
• S[i] contains lowercase letters

Sample Input:

eccbbbbdec

Sample Output:

100

You're given N types of chip packets, each with:

• happiness A[i]
• weight B[i]
• cost C[i]

Alice wants at least X happiness and at most Y total weight while minimizing the cost.

Function Signature:

def solve(N: int, A: List[int], B: List[int], C: List[int], X: int, Y: int) -> int

Parameters:

• A: Happiness values (length N)
• B: Weights (length N)
• C: Costs (length N)
• X: Minimum required happiness
• Y: Maximum allowed total weight

Constraints:

• 1 ≤ N ≤ 100
• 1 ≤ A[i], B[i], C[i], X, Y ≤ 100
• 1 ≤ C[i] ≤ 10^4

Sample Input:

5
1 2 3 4 5
1 2 3 4 5
5 4 3 2 1
10
10

Sample Output:

5