Count segments and optimize 3-server assignment
Company: Goldman Sachs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
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).
Overview: 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.
Read the full Goldman Sachs Software Engineer interview experience this question came from
Community answers
Answer by qinzhengquan
Solution 1
/*
What is the question asking?
Count how many strictly increasing subarrays have exactly length k.
Example:
transactions = [1, 2, 3, 4]
k = 3
High level idea:
Keep a strictly increasing window [l..r].
If the increasing condition breaks:
reset l = r
If the current window reaches exactly size k:
count it
move l forward by 1 so we can look for the next length-k window.
Visualization:
transactions = [1, 2, 3, 4]
k = 3
Start:
l
|
[ 1, 2, 3, 4 ]
|
r
window size = 2
not enough yet
Move r:
l
|
[ 1, 2, 3, 4 ]
|
r
window = [1,2,3]
size = 3 == k
count = 1
move l forward:
l
|
[ 1, 2, 3, 4 ]
|
r
Move r:
l
|
[ 1, 2, 3, 4 ]
|
r
window = [2,3,4]
size = 3 == k
count = 2
Answer:
2
Valid subarrays:
[1,2,3]
[2,3,4]
Example where increasing streak breaks:
transactions = [1, 2, 1, 3]
k = 2
Start:
l
|
[ 1, 2, 1, 3 ]
|
r
[1,2] is increasing
size = 2 == k
count = 1
l++
Next:
l
|
[ 1, 2, 1, 3 ]
|
r
1 <= 2
increasing streak breaks
reset:
l = r
l
|
[ 1, 2, 1, 3 ]
|
r
Move r:
l
|
[ 1, 2, 1, 3 ]
|
r
[1,3] is increasing
size = 2 == k
count = 2
Key intuition:
r - l + 1 tells us the length of the current increasing window.
When it becomes k:
we found exactly one valid length-k subarray ending at r.
Then l++ so the next r can form the next overlapping
length-k subarray.
*/
public class CountSegmentsK {
// k = 2
// c = 1
// l
// r
//
// [1,2,1,3]
// l
// r
// [1,2,3,4]
// l
// r
// [2,1]
// k = 3
// l
// r
// [1,2,3,4,5]
public int countSegmentsK(int [] transactions, int k)
{
int l = 0, r = 1;
int
Answer by qinzhengquan
Solution 2
public class EfficientTaskServers {
public long maxEfficiency(int[] difficulty)
{
Arrays.sort(difficulty);
int n = difficulty.length;
long ans = 0;
for (int t = 1; t < n; t++) {
// t means the split where
// left of t is s1, s3
// t to right is s2
// CASE 1
// 0 1 2
// [1,3,5,10]
// t=1
// s1,s3 s2
// [1] [3,5,10] -> not quite a valid split, because s1 and s3 needs 1 element each and their only choice is 1
// t = 2 -> boss arrange this
// s1,s3 s2
// [1,3] [5,10] -> now we're talking. s1,s3 has at least 1 elemt each, and s2 has a choice of 5,10
// best choice for s2: 5-1 + 5-3 = 4+2=6
// what is s2 best choice? to minimise his distance, he has to choose 1 from s1 (furthest element) -> difficulty[0]
// his next best choice is the element closest to him (sorted array) difficulty[t-1] -> closest to the split
// t = 3 -> boss arrange this
// s1,s3 s2
// [1,3,5] [10]
// best choices for s2:
// s1: [3] s3: [1,5], s2: [10]
// pick 3 from s1, pick 5 from s3 -> 10-3 + 10-5 -> but boss doesn't like this, not max
// s1: [1] s3: [3,5], s2: 10
// best choice for s2: 10-1 + 10-5 = 9+5=14 -> boss is happy. Boss got more out of s2 as opposed to splitting at t=2
// hence we enforce difficulty[0] as an extreme choice that s2 has to pick
// now lets try the extreme case. Assuming we now choose s2 to be at the left instead
// CASE 2
// 0 1 2
// [1,3,5,10]
// t=1
// s2 s1,s3
// [1] [3,5,10]
// s2 choices:
// s2: [1], s1: [3] s3: [5,10] -> s2 chooses, 3, 5. But boss is not happy since 1