← Hudson River Trading Interview Insights

Hudson River Trading·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Interviewed for a software engineering role at Hudson River Trading and got hit with an array problem that looked deceptively simple. The focus was clearly on algorithmic thinking and handling edge cases under pressure.

Questions Asked (1)

Q1

Given an array of integers and an integer K, remove exactly K contiguous elements so that the amplitude of the remaining array (max minus min) is minimized. Return the minimum possible amplitude.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The word 'amplitude' threw me off at first, took me a beat to realize it just meant the range.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that removing exactly K contiguous elements leaves a contiguous subarray of length n-K. The problem reduces to finding a contiguous subarray of length n-K with minimum difference between its maximum and minimum. Use a sliding window with a data structure that supports efficient insertion, deletion, and min/max queries, such as two monotonic deques or a balanced BST.

Pro tip: Clarify edge cases upfront: if K >= n, the array becomes empty (amplitude 0); if K = 0, return the original amplitude. Also discuss trade-offs between O(n log n) and O(n) approaches, showing awareness of practical performance.

1. Understand the problem

Restate that removing K contiguous elements is equivalent to selecting a contiguous subarray of length n-K. The goal is to minimize the amplitude of that subarray.

2. Choose an approach

Decide between a sliding window with monotonic deques (O(n)) or a balanced BST (O(n log n)). Explain the trade-offs and pick one based on constraints.

3. Implement the algorithm

For sliding window: maintain two deques for min and max, slide the window of size n-K, and track the minimum difference. For BST: insert first n-K elements, then slide by removing left and adding right, querying min and max each time.

4. Handle edge cases

Check if K >= n (return 0), K = 0 (return original amplitude), and ensure the window size is valid. Also consider negative numbers and duplicates.

5. Analyze complexity and test

State time and space complexity. Walk through a small example to verify correctness, and discuss potential optimizations or alternative solutions.

Key Points to Mention

  • Reduction to finding a contiguous subarray of length n-K with minimum amplitude.
  • Sliding window technique with two monotonic deques for O(n) time and O(n) space.
  • Alternative O(n log n) approach using a balanced BST (e.g., multiset) for min/max queries.
  • Edge cases: K >= n, K = 0, n = 0, and arrays with all equal elements.
  • Time and space complexity analysis of the chosen approach.
  • Trade-offs between implementation simplicity and optimal performance.

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