Suffix Maximum Frequency Queries

Reported in interviews at Millennium Management

Problem statement

You are given two arrays, nums and queries. For each value q in queries, look at the suffix of nums that starts at the q-th element (1-indexed) and runs to the end. Find the maximum element of that suffix and report how many times that maximum occurs in it. Return the results as an array, one per query.

Example: nums = [4, 3, 3, 1, 2], queries = [1, 2, 3, 4, 5].

  • q = 1: suffix [4, 3, 3, 1, 2], max 4 occurs once -> 1.
  • q = 2: suffix [3, 3, 1, 2], max 3 occurs twice -> 2.
  • q = 3: suffix [3, 1, 2], max 3 occurs once -> 1.
  • q = 4: suffix [1, 2], max 2 once -> 1.
  • q = 5: suffix [2], max 2 once -> 1.

So the answer is [1, 2, 1, 1, 1].

Show hint

How is the suffix that starts at one position related to the suffix that starts right after it?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems