Frontend School

Diverse Test Sequences

DSA
hard

Diverse Test Sequences

Hard
Two Pointers
Sliding Window
HashMap

Overview

In Browserstack's continuous integration environment, optimizing test suite diversity is crucial. We define a "diverse test sequence" as a contiguous block of executed tests where the number of unique device-browser configurations used is exactly k. Your task is to count how many such diverse test sequences exist within a given log of test configurations. This problem is vital for identifying optimal test batching strategies and ensuring comprehensive coverage without redundancy.

What you need to do / Task

  1. Implement a function countDiverseSequences that takes an array of integers configurations and an integer k.
  2. The function should return the total number of contiguous subarrays (test sequences) within configurations that contain exactly k distinct configuration IDs.

Input & output

  • configurations: An array of integers (number[] in TypeScript, number[] in JavaScript). Each integer represents a unique ID for a specific device-browser configuration. These IDs can be large, so a hash map/object is suitable for frequency tracking.
  • k: An integer (number in TypeScript, number in JavaScript). The target number of distinct configurations for a sequence to be considered diverse.
  • Returns: An integer (number) representing the total count of diverse test sequences.

Clarifications

  • An empty configurations array will yield 0 diverse sequences.
  • k will always be a positive integer (1 <= k).
  • The elements in configurations can be any non-negative integers.

Examples

1

Example 1

Input:

configurations = [1, 2, 1, 2, 3], k = 2

Output:

8

Note:

Subarrays with exactly 2 distinct elements are: [1, 2], [2, 1], [1, 2] (from index 2 to 3), [1, 2, 1], [2, 1, 2], [1, 2, 1, 2], [2, 3], [1, 2] (from index 2 to 3).

2

Example 2

Input:

configurations = [1, 1, 1, 1], k = 1

Output:

10

Note:

All subarrays contain only one distinct element (1). There are 4 single-element subarrays, 3 two-element subarrays, 2 three-element subarrays, and 1 four-element subarray. Total: 4 + 3 + 2 + 1 = 10.

3

Example 3

Input:

configurations = [5, 3, 5, 2, 3], k = 3

Output:

3

Note:

Subarrays with exactly 3 distinct elements are: [5, 3, 5, 2] (distinct: 5, 3, 2) [3, 5, 2] (distinct: 3, 5, 2) [5, 2, 3] (distinct: 5, 2, 3)

Constraints

Constraints & assumptions

  • 1 <= configurations.length <= 10^5
  • 0 <= configurations[i] <= 10^9
  • 1 <= k <= configurations.length

What interviewers evaluate

  • Correctness and efficiency of the algorithm, specifically leveraging two-pointers or sliding window techniques.
  • Ability to handle edge cases and constraints (e.g., k=1, array length).
  • Code clarity, organization, and choice of data structures.
  • Communication of thought process and complexity analysis.

Loading editor...