FastPrep
Problem · Design

Cache Access Statistics

Learn this problem
● MediumGoldman Sachs logoGoldman SachsFULLTIMEONSITE INTERVIEW

Problem statement

Process operations against an initially empty string cache:

  • PUT key value inserts or overwrites key.
  • GET key emits HIT value when the key exists, otherwise MISS. A hit increments that key's frequency by one.

After all operations, append STATS h m, where h and m are total hits and misses. Append each key with positive hit frequency as key:frequency in lexicographic key order. There is no capacity limit or eviction.

Function

trackCacheStatistics(operations: String[]) → String[]

Examples

Example 1

operations = ["PUT a 10","GET a","GET b","PUT b 20","GET b"]return = ["HIT 10","MISS","HIT 20","STATS 2 1 a:1 b:1"]

Both stored keys are hit once, and the first read of b is the only miss.

Example 2

operations = ["PUT x old","PUT x new","GET x","GET x"]return = ["HIT new","HIT new","STATS 2 0 x:2"]

The second PUT overwrites x without changing its read frequency.

Constraints

  • 0 <= operations.length <= 200000
  • Each command is exactly PUT key value or GET key.
  • Keys and values are nonempty ASCII tokens without whitespace.

More Goldman Sachs problems

drafts saved locally
public String[] trackCacheStatistics(String[] operations) {
  // write your code here
}
operations["PUT a 10","GET a","GET b","PUT b 20","GET b"]
expected["HIT 10", "MISS", "HIT 20", "STATS 2 1 a:1 b:1"]
checking account