FastPrep
Problem · Design

Fair Multi-Tenant Cache

Learn this problem
● HardOkta logoOktaFULLTIMEONSITE INTERVIEW

Problem statement

Simulate a shared cache used by multiple tenants. The cache holds at most capacity entries across all tenants.

Each operation is one of:

  • PUT tenant key value: insert or update an integer value.
  • GET tenant key: return the value, or -1 when absent.

A successful GET and every PUT refresh recency. When a new entry needs space, find the largest per-tenant entry count, consider only tenants with that count, and evict the globally least-recently-used entry among those tenants. Return the results of the GET operations in order.

Function

runFairCache(capacity: int, operations: String[]) → int[]

Examples

Example 1

capacity = 3operations = ["PUT a x 10","PUT a y 20","PUT b z 30","GET a x","PUT b q 40","GET a y","GET b z","GET b q"]return = [10,-1,30,40]

Tenant a initially owns more entries, so its oldest entry is evicted when b inserts q.

Example 2

capacity = 1operations = ["PUT red k 7","GET red k","PUT blue x 9","GET red k","GET blue x"]return = [7,-1,9]

The single slot moves from red to blue; successful access refreshed red only before replacement.

Constraints

  • 0 <= capacity <= 50000
  • 1 <= operations.length <= 100000
  • Tenant and key tokens contain only letters, digits, underscores, and hyphens.
  • Values are signed 32-bit integers other than -1.
  • Operations are supplied in their complete serialized execution order.

More Okta problems

drafts saved locally
public int[] runFairCache(int capacity, String[] operations) {
    // Write your code here.
}
capacity3
operations["PUT a x 10","PUT a y 20","PUT b z 30","GET a x","PUT b q 40","GET a y","GET b z","GET b q"]
expected[10,-1,30,40]
checking account