Katkat
Back

Count segments and optimize 3-server assignment

Goldman SachsSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This two-part problem evaluates array-processing and counting competency for identifying fixed-length strictly increasing subarrays and combinatorial partitioning and optimization competency for assigning elements to three groups to maximize a minimal pairwise-difference metric, and is commonly asked to assess efficient algorithm design, correctness under constraints, and the ability to handle large inputs. Belonging to the Coding & Algorithms domain, it tests practical algorithmic application, data-structure-aware implementation and complexity analysis rather than purely theoretical understanding.

There are two independent programming tasks.

Problem 1: Transaction Segments

You are given:

  • An integer n, the length of an array.
  • An integer k (1 ≤ k ≤ n).
  • An integer array transactionValues of length n, where transactionValues[i] represents the transaction amount at time i (0-based index).

A contiguous segment transactionValues[l..r] (where 0 ≤ l ≤ r < n) is called strictly increasing if:

  • For every i with l ≤ i < r, we have transactionValues[i] < transactionValues[i + 1].

Your task is to count how many contiguous subarrays of length exactly k are strictly increasing.

Formally, count the number of starting indices s such that:

  • 0 ≤ s ≤ n - k, and
  • transactionValues[s] < transactionValues[s + 1] < ... < transactionValues[s + k - 1].

Input

  • n, k
  • Array transactionValues[0..n-1]

Output

  • A single integer: the number of strictly increasing contiguous subarrays of length exactly k.

Design an algorithm that runs efficiently for large n (e.g., up to around 2 × 10^5).

Problem 2: Efficient Tasks Across 3 Servers

You are given:

  • An integer n (n ≥ 3), the number of software modules.
  • An integer array difficulty of length n, where difficulty[i] is the difficulty of the i-th software module.

You must assign all modules to 3 servers subject to:

  • Each server must receive at least one module.
  • Every module must be assigned to exactly one server.

After a particular assignment (partition) of modules into 3 non-empty groups S1, S2, and S3 (one group per server) is fixed, you are allowed to choose one module from each server:

  • Choose index i1 ∈ S1 with difficulty d1 = difficulty[i1].
  • Choose index i2 ∈ S2 with difficulty d2 = difficulty[i2].
  • Choose index i3 ∈ S3 with difficulty d3 = difficulty[i3].

For this assignment, define the value:

[ F(S_1,S_2,S_3) = \min_{i_1 \in S_1,\ i_2 \in S_2,\ i_3 \in S_3} \bigl(|d_1 - d_2| + |d_2 - d_3|\bigr) ]

That is, for the given partition of modules into three servers, you choose one module from each server so that the expression (|d1 - d2| + |d2 - d3|) is as small as possible, and that minimal value is (F) for this partition.

Your overall goal is to choose an assignment of modules to the three servers that maximizes this minimal value.

In other words, over all valid partitions (S1, S2, S3) of the modules into three non-empty, disjoint sets whose union is all modules, compute:

[ \max_{(S_1,S_2,S_3)} F(S_1,S_2,S_3) ]

and output this maximum.

Input

  • n
  • Array difficulty[0..n-1]

Output

  • A single integer: the maximum possible value of (F(S_1,S_2,S_3)) over all valid assignments.

Design an algorithm that is significantly more efficient than enumerating all possible assignments (which is exponential in n) and can handle large n (e.g., up to around 2 × 10^5).