Simulate Alternating Stick Collection for a Nest
Company: Hudson River Trading
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: trading - 网上海投 - 在线笔试
A bird is building a nest in a forest represented by an array `forest`. Positive integers are sticks, where the integer value is the stick length. Zeroes are empty spaces.
The bird starts at index `bird`, and `forest[bird]` is guaranteed to be `0`. It repeats this process:
1. Fly to the right until it finds the nearest stick.
2. Return that stick to the starting position.
3. Fly to the left until it finds the nearest stick.
4. Keep alternating directions after each collected stick.
The bird stops once the total length of collected sticks is at least `100`.
Return the 0-based indices of the sticks in the exact order the bird collects them.
Example:
```text
forest = [25, 0, 50, 0, 0, 0, 0, 15, 0, 0, 45]
bird = 4
output = [7, 2, 10]
```
Explanation:
- The first stick to the right of index `4` is at index `7`, length `15`.
- The first stick to the left is at index `2`, length `50`, bringing the total to `65`.
- The next stick to the right is at index `10`, length `45`, bringing the total to `110`, so the search stops.
Constraints:
- `forest[bird] == 0`
- `sum(forest) >= 100`
- The bird will always find a stick in the current direction before reaching the array boundary.
Quick Answer: This Hudson River Trading coding question evaluates simulation logic, turn alternation, and state updates across a sequence of collection decisions. It is useful for practicing precise loop invariants and translating rules into code that handles edge cases cleanly.
A bird starts at an empty forest index. It alternates flying right and left to collect the nearest stick in that direction, removing each collected stick, until total collected length reaches at least 100. Return collected indices in order.
Constraints
- forest[bird] == 0
- sum(forest) >= 100
- A stick always exists in the current direction before the boundary is reached.
Examples
Input: ([25, 0, 50, 0, 0, 0, 0, 15, 0, 0, 45], 4)
Expected Output: [7, 2, 10]
Input: ([0, 60, 0, 50, 0], 2)
Expected Output: [3, 1]
Input: ([0, 0, 100], 1)
Expected Output: [2]
Input: ([0, 0, 40, 0, 70], 3)
Expected Output: [4, 2]
Input: ([30, 0, 40, 0, 35, 0, 50], 3)
Expected Output: [4, 2, 6]
Input: ([55, 0, 0, 0, 60], 2)
Expected Output: [4, 0]
Input: ([0, 60, 0, 30, 0, 40, 0, 50], 2)
Expected Output: [3, 1, 5]
Input: ([10, 0, 90, 0, 10, 0, 90], 3)
Expected Output: [4, 2]
Hints
- Alternate directions after each collected stick.
- Remove a collected stick so it cannot be collected again.
- Stop as soon as the collected total reaches 100.