How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Answer suffix maximum-frequency queries | Microsoft Coding Question

Answer suffix maximum-frequency queries

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given: - An integer array `nums` of length `n`. - An integer array `queries` of length `m`, where each `queries[k]` is an index `i` (0-based) into `nums`. For each query index `i`, consider the suffix subarray `nums[i..n-1]`. - Let `mx` be the maximum value in that suffix. - Return how many times `mx` occurs in that suffix. ### Example - `nums = [7, 5, 7, 2, 7]` - `queries = [0, 1, 2, 3, 4]` Suffixes and answers: - `i=0`: `[7,5,7,2,7]` → max=7 occurs 3 → 3 - `i=1`: `[5,7,2,7]` → max=7 occurs 2 → 2 - `i=2`: `[7,2,7]` → max=7 occurs 2 → 2 - `i=3`: `[2,7]` → max=7 occurs 1 → 1 - `i=4`: `[7]` → max=7 occurs 1 → 1 Output: `[3, 2, 2, 1, 1]` ### Requirements Design an algorithm that answers all queries efficiently (faster than scanning the suffix for each query). ### Constraints (assume typical interview-scale) You may assume `n, m` can be up to ~200,000.

Quick Answer: This question evaluates algorithm design skills and array-processing competency for answering repeated queries efficiently, focusing on time and space complexity with large input sizes.

You are given an integer array `nums` of length `n` and an integer array `queries` of length `m`. Each value `queries[k]` is a 0-based index into `nums`. For each query index `i`, look at the suffix subarray `nums[i..n-1]`. - Let `mx` be the maximum value in that suffix. - Return how many times `mx` appears in that suffix. Your task is to return an array of answers, one for each query, in the same order as `queries`. The solution should be efficient: faster than scanning the whole suffix separately for every query.

Constraints

0 <= n, m <= 200000
If n == 0, then queries is empty
0 <= queries[k] < n for every query when n > 0
-10^9 <= nums[i] <= 10^9

Examples

Input: ([7, 5, 7, 2, 7], [0, 1, 2, 3, 4])

Expected Output: [3, 2, 2, 1, 1]

Explanation: The suffix maximum is 7 for every queried suffix, and its frequencies are 3, 2, 2, 1, and 1 respectively.

Input: ([4, 4, 4, 4], [0, 2, 3])

Expected Output: [4, 2, 1]

Explanation: Every suffix has maximum 4. In suffixes starting at indices 0, 2, and 3, it appears 4, 2, and 1 times.

Input: ([-3, -1, -1, -2], [0, 1, 2, 3])

Expected Output: [2, 2, 1, 1]

Explanation: Negative values are allowed. The suffix maximums are -1, -1, -1, and -2 with frequencies 2, 2, 1, and 1.

Input: ([9, 8, 7, 6], [0, 1, 3])

Expected Output: [1, 1, 1]

Explanation: In a strictly decreasing array, the first element of each suffix is the maximum and appears once.

Input: ([2, 1, 2, 3, 3], [1, 1, 4, 0])

Expected Output: [2, 2, 1, 2]

Explanation: Repeated queries should return the same result. The suffix starting at 1 has maximum 3 appearing twice, index 4 has only one 3, and index 0 also has maximum 3 appearing twice.

Input: ([1, 3, 2], [])

Expected Output: []

Explanation: If there are no queries, the answer is an empty list.

Hints

Process the array from right to left. If you already know the suffix maximum and its count for `i+1`, you can update the answer for `i` using only `nums[i]`.
Precompute an answer for every starting index once, then each query becomes a simple array lookup.

Quick Overview

This question evaluates algorithm design skills and array-processing competency for answering repeated queries efficiently, focusing on time and space complexity with large input sizes.