Longest Single-Venue Execution Window Within Price-Range and Slippage Limits
Company: Falconx
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
You are building an audit module for a high-frequency trading platform. It receives trade-execution logs from several exchanges (venues) as an asynchronous stream, so the logs arrive unordered and interleaved across venues. For one target venue, rebuild its execution timeline in time order, then find the longest run of consecutive executions that stays within two operational risk limits.
Process the input in these steps:
1. **Filter:** keep only the logs whose `venue` equals `target_venue`.
2. **Reconstruct:** sort the kept logs by `timestamp` in ascending order.
3. **Compute the metric:** for each kept log, its slippage cost is `abs(fill_price - benchmark_price) * volume`.
4. **Evaluate windows:** a window is a contiguous, non-empty run of logs in the sorted sequence. A window is valid when both conditions hold:
- `max(fill_price) - min(fill_price) <= V` over the logs in the window;
- the sum of the slippage costs of the logs in the window is `<= S`.
5. **Return** the number of logs in the longest valid window, or `0` if no log matches `target_venue` or no window is valid.
### Function Signature
```python
def longest_compliant_window(logs: list[dict], target_venue: str, V: int, S: int) -> int:
```
Each element of `logs` is a dictionary with exactly these keys:
| Key | Type | Meaning |
|---|---|---|
| `venue` | `str` | Identifier of the venue that executed the trade |
| `timestamp` | `int` | Execution time |
| `fill_price` | `int` | Price at which the trade was filled |
| `benchmark_price` | `int` | Reference price the fill is compared against |
| `volume` | `int` | Quantity traded |
### Rules
- Venue matching is exact and case-sensitive.
- Logs with equal `timestamp` keep their relative order from `logs` (the sort is stable). This order decides which logs are adjacent, so it can change the answer.
- Both limits are inclusive: a window whose price range equals `V`, or whose total slippage cost equals `S`, is valid.
- The price range uses `fill_price` only; `benchmark_price` is used only to compute slippage cost.
- A single log is a window of length 1 with price range 0, so it is valid exactly when its own slippage cost is at most `S`.
- Return only the length of the longest valid window, which is unique even when several windows share that length.
### Constraints
- `0 <= len(logs) <= 10^5`
- `venue` and `target_venue` are non-empty strings of at most 20 characters.
- `0 <= timestamp <= 10^15`
- `1 <= fill_price <= 10^6` and `1 <= benchmark_price <= 10^6`. Prices are integers in the smallest price increment (ticks), so all arithmetic is exact.
- `1 <= volume <= 10^4`
- `0 <= V <= 10^6`
- `0 <= S <= 10^15`
- A single slippage cost is below `10^10`, and the sum over all logs is below `10^15`, so every value stays within `2^53`. Timestamps, slippage costs and their sums can exceed `2^31 - 1`; use 64-bit integers in languages with fixed-width types.
### Examples
**Example 1**
```text
Input:
logs = [
{"venue": "A", "timestamp": 5, "fill_price": 101, "benchmark_price": 100, "volume": 2},
{"venue": "B", "timestamp": 1, "fill_price": 500, "benchmark_price": 100, "volume": 10},
{"venue": "A", "timestamp": 1, "fill_price": 100, "benchmark_price": 100, "volume": 5},
{"venue": "A", "timestamp": 3, "fill_price": 103, "benchmark_price": 100, "volume": 1},
{"venue": "A", "timestamp": 9, "fill_price": 99, "benchmark_price": 100, "volume": 4},
{"venue": "A", "timestamp": 7, "fill_price": 102, "benchmark_price": 101, "volume": 3}
]
target_venue = "A", V = 3, S = 8
Output: 4
```
After filtering and sorting, venue `A` has logs at timestamps 1, 3, 5, 7, 9 with fill prices 100, 103, 101, 102, 99 and slippage costs 0, 3, 2, 3, 4. The first four logs have price range 103 - 100 = 3 and total cost 0 + 3 + 2 + 3 = 8, both exactly at the limits, so the window is valid. All five logs have price range 4, and the other window of length 4 (prices 103, 101, 102, 99) also has range 4, so no longer valid window exists.
**Example 2**
```text
Input:
logs = [
{"venue": "A", "timestamp": 1, "fill_price": 10, "benchmark_price": 12, "volume": 3},
{"venue": "a", "timestamp": 2, "fill_price": 10, "benchmark_price": 10, "volume": 1}
]
target_venue = "A", V = 5, S = 5
Output: 0
```
Venue matching is case-sensitive, so only the first log is kept. Its slippage cost is 2 * 3 = 6, which exceeds `S = 5`, so no window is valid.
**Example 3**
```text
Input:
logs = [
{"venue": "X", "timestamp": 2, "fill_price": 50, "benchmark_price": 50, "volume": 1},
{"venue": "X", "timestamp": 1, "fill_price": 60, "benchmark_price": 60, "volume": 1},
{"venue": "X", "timestamp": 2, "fill_price": 60, "benchmark_price": 60, "volume": 1}
]
target_venue = "X", V = 0, S = 100
Output: 1
```
The stable sort gives fill prices 60 (timestamp 1), 50 (timestamp 2, first in the input) and 60 (timestamp 2, third in the input). With `V = 0` a valid window needs equal fill prices, and no two adjacent logs have equal prices, so the longest valid window has length 1. If the two logs at timestamp 2 were ordered the other way, the two 60s would be adjacent and the answer would be 2.
Overview: Coding problem that filters unordered trade execution logs to one venue, orders them by timestamp with a stable tie rule, and returns the length of the longest contiguous run whose fill-price range and total slippage cost both stay within given limits. Tests careful preprocessing and efficient window search.
Read the full Falconx Software Engineer interview experience this question came from