Goldman Sachs·Software Engineer·Online Assessment (OA)·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Goldman Sachs SWE coding round, two algorithmic problems back to back. Both were harder than I expected for a screen and the second one especially had me second-guessing my approach the whole time.

Questions Asked (2)

Given an array of transaction values and an integer k, count how many contiguous subarrays of exactly length k are strictly increasing.

Algorithms & Data Structures

Author's notes

Felt manageable once I stopped overthinking it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem and edge cases, then propose an efficient sliding window solution that checks each window of length k for strict increasing order. Analyze time and space complexity, and discuss potential optimizations or alternative approaches.

Pro tip: Mention that you can precompute a 'good' array marking indices where the next element is greater, then use a sliding window sum to count valid windows in O(n) time. This shows you can optimize beyond the naive O(n*k) approach.

1. Clarify requirements and edge cases

Confirm that subarrays are contiguous, length exactly k, and strictly increasing means each element is greater than the previous. Discuss edge cases: k=1 (always increasing), k > array length (return 0), empty array, and arrays with duplicates.

2. Propose a naive approach

Start with a straightforward solution: iterate through all starting indices from 0 to n-k, and for each, check if the subarray of length k is strictly increasing. This takes O(n*k) time.

3. Optimize with sliding window

Improve to O(n) by maintaining a count of 'good' adjacent pairs within the current window. Slide the window by one: remove the leftmost pair, add the new rightmost pair, and check if the count equals k-1.

4. Analyze complexity and trade-offs

State that the optimized solution runs in O(n) time and O(1) extra space. Compare with the naive approach and explain why the sliding window is better for large n and k.

5. Test with examples

Walk through a small example, such as [1,2,3,4] with k=2, to demonstrate correctness. Also test edge cases like k=1 and k>n.

Key Points to Mention

Sliding window technique for O(n) time complexity
Handling edge cases: k=1, k > n, empty array, duplicates
Strictly increasing condition: each element > previous
Time and space complexity analysis (O(n) time, O(1) space)
Comparison with naive O(n*k) approach
Potential follow-up: count subarrays of length at least k or at most k

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

You have n software modules each with a difficulty score. Partition all modules into exactly 3 non-empty groups. For any partition, you pick one module from each group to minimize |d1 - d2| + |d2 - d3|. Find the partition that maximizes this minimized value.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one wrecked me a little.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem and constraints, then propose a solution that balances optimality and efficiency. Discuss sorting, binary search on the answer, and dynamic programming or greedy approaches, and analyze trade-offs.

Pro tip: Demonstrate strong communication by walking through a small example and explaining why a brute-force approach is infeasible, then optimize step by step.

1. Clarify and Restate

Confirm understanding of the problem: exactly 3 non-empty groups, pick one from each to minimize the sum of absolute differences, then maximize that minimized value over all partitions.

2. Sort and Observe

Sort the difficulty scores. Note that in an optimal partition, the chosen modules will likely be the medians or specific order statistics of each group.

3. Binary Search on Answer

Binary search the maximum possible minimized value. For a candidate value X, check if there exists a partition into 3 groups and a selection of one from each such that the sum of absolute differences is at least X.

4. Feasibility Check

Design a greedy or DP check: for a given X, determine if we can partition the sorted array into 3 non-empty groups and pick one element from each group with pairwise differences summing to at least X.

5. Complexity and Trade-offs

Analyze time and space complexity. Discuss alternative approaches (e.g., DP over sorted array) and their trade-offs in terms of implementation complexity and performance.

Key Points to Mention

Sorting the array to simplify the selection of representatives from each group.
Binary search on the answer (maximized minimized value) to reduce the problem to a decision problem.
Feasibility check using greedy or dynamic programming: for a given X, can we partition into 3 groups and pick elements with sum of absolute differences >= X?
Time complexity: O(n log n) for sorting plus O(n log(max-min)) for binary search, assuming O(n) feasibility check.
Edge cases: all elements equal, n=3, large n, and ensuring groups are non-empty.
Trade-offs between a direct DP approach (O(n^3) or O(n^2)) and the binary search + greedy approach.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.