Implement Game Physics and Block Mining
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given two independent coding tasks from the same interview category. Solve both.
### Task A: Flappy-Bird-Style Jump Boundary Function
Implement a function for a simple side-scrolling game that updates a bird's vertical position for one simulation tick and reports whether the bird is still inside the playable area.
The game uses the following coordinate system:
- `y = 0` is the ceiling.
- `y = height` is the floor.
- Positive velocity moves the bird downward.
Function signature:
`update_bird(y, velocity, jump_pressed, height, gravity, jump_velocity) -> (new_y, new_velocity, alive)`
Rules:
1. If `jump_pressed` is true, set the bird's velocity to `jump_velocity`. `jump_velocity` may be negative.
2. Otherwise, keep the current velocity.
3. Apply gravity to the velocity for this tick: `new_velocity = velocity_after_jump + gravity`.
4. Update position: `new_y = y + new_velocity`.
5. The bird is alive only if `0 <= new_y <= height`.
6. Return the new position, new velocity, and alive status.
Handle edge cases such as jumps near the ceiling, falling below the floor, and zero gravity.
### Task B: Build a Cryptocurrency Block with Transaction Dependencies
You are building a simplified block-mining simulator. Each pending transaction has:
- `id`: unique string
- `fee`: integer fee paid by the transaction
- `size`: integer size in bytes
- `parents`: list of transaction IDs that must appear earlier in the same block if this transaction is included
Given a maximum block size `max_size`, choose an ordered list of transaction IDs to include in the block.
Rules:
1. A transaction can be included only if all of its parent transactions are also included earlier in the returned order.
2. The total size of all included transactions must be at most `max_size`.
3. Use the following greedy strategy rather than solving the globally optimal knapsack problem:
- For each not-yet-included transaction, compute the package consisting of that transaction plus all missing ancestors required to include it.
- The package fee is the sum of fees of missing transactions in the package.
- The package size is the sum of sizes of missing transactions in the package.
- Repeatedly choose the valid package with the highest `package_fee / package_size` ratio that fits in the remaining block size.
- Add the package transactions in dependency order.
4. If the dependency graph contains a cycle, report an error.
5. Return the ordered transaction IDs, total fee, and total size.
Discuss the time complexity of your implementation and how you would cache ancestor-package computations for large mempools.
Quick Answer: This question evaluates implementation skills in deterministic game physics (discrete position and velocity updates with boundary and edge-case handling) alongside dependency-aware greedy selection for block construction, testing graph dependency resolution, greedy heuristics, and complexity analysis in the Coding & Algorithms domain, and is commonly asked to verify correctness under constraints, handling of boundary conditions, and trade-offs between optimality and performance. Level of abstraction spans both conceptual understanding (kinematic update rules, cycle detection, fee/size ratio reasoning) and practical application (implementing the tick update and returning a topologically ordered block while considering caching and scalability for large mempools).
Part 1: Flappy-Bird-Style Jump Boundary Function
Write a function that simulates exactly one game tick for a bird in a side-scrolling game. The bird has a vertical position y, a current vertical velocity, and an optional jump input for this tick. If jump is pressed, the bird's velocity is first replaced by jump_velocity. Then gravity is applied, then the position is updated. Finally, report whether the bird is still inside the playable area. The playable range is inclusive: y = 0 is the ceiling and y = height is the floor, so landing exactly on either boundary still counts as alive.
Constraints
- 0 <= height <= 10^9
- -10^9 <= y, velocity, gravity, jump_velocity <= 10^9
- jump_pressed is either True or False
- Use exactly one simulation tick with the update order described in the statement
Examples
Input: (5, 2, False, 10, 1, -3)
Expected Output: (8, 3, True)
Explanation: No jump happens. Velocity becomes 2 + 1 = 3, then position becomes 5 + 3 = 8.
Input: (1, 4, True, 10, 2, -5)
Expected Output: (-2, -3, False)
Explanation: Jump replaces velocity with -5, then gravity makes it -3. The new position is -2, above the ceiling, so the bird is not alive.
Input: (9, 0, False, 10, 2, -4)
Expected Output: (11, 2, False)
Explanation: The bird falls below the floor after gravity is applied.
Input: (8, 1, False, 10, 1, -4)
Expected Output: (10, 2, True)
Explanation: The bird lands exactly on the floor, which is still inside the playable area.
Input: (0, 0, True, 10, 0, 0)
Expected Output: (0, 0, True)
Explanation: Zero gravity and zero jump velocity keep the bird exactly at the ceiling, which is still valid.
Hints
- Apply the jump first, then gravity, then update the position.
- The bird is still alive when new_y is exactly 0 or exactly height.
Part 2: Build a Cryptocurrency Block with Transaction Dependencies
You are given a mempool of pending transactions and a maximum block size. Build a block using this exact greedy strategy: for each transaction not yet included, form its package consisting of that transaction plus every not-yet-included ancestor required by its parent list. The package fee is the sum of fees of the missing transactions in that package, and the package size is the sum of their sizes. Repeatedly choose the package with the highest package_fee / package_size ratio that fits in the remaining block space, then add that package's missing transactions in dependency order. To make the result deterministic, break ties by larger package fee, then smaller package size, then lexicographically smaller root transaction id. When outputting a chosen package, use the lexicographically smallest valid topological order of its missing transactions. If the dependency graph contains a cycle, return {'error': 'cycle detected'}. A strong implementation memoizes each transaction's full ancestor closure, which is also the key caching idea for large mempools.
Constraints
- 0 <= len(transactions) <= 200
- 0 <= max_size <= 10^6
- Each transaction id is unique
- 0 <= fee <= 10^6
- 1 <= size <= 10^6
- Each parent id listed for a transaction appears somewhere in the input
Examples
Input: ([{'id': 'a', 'fee': 10, 'size': 5, 'parents': []}, {'id': 'b', 'fee': 9, 'size': 3, 'parents': []}, {'id': 'c', 'fee': 8, 'size': 4, 'parents': ['a']}], 8)
Expected Output: {'order': ['b', 'a'], 'total_fee': 19, 'total_size': 8}
Explanation: Package b has the best fee/size ratio first. After taking b, package c no longer fits because it still requires a, so a is taken next.
Input: ([{'id': 'a', 'fee': 4, 'size': 2, 'parents': []}, {'id': 'b', 'fee': 10, 'size': 4, 'parents': ['a']}, {'id': 'c', 'fee': 7, 'size': 4, 'parents': []}], 6)
Expected Output: {'order': ['a', 'b'], 'total_fee': 14, 'total_size': 6}
Explanation: The package for b is {a, b}, which has fee 14 and size 6, giving the best ratio among packages that fit.
Input: ([], 100)
Expected Output: {'order': [], 'total_fee': 0, 'total_size': 0}
Explanation: An empty mempool produces an empty block.
Input: ([{'id': 'a', 'fee': 5, 'size': 2, 'parents': ['b']}, {'id': 'b', 'fee': 6, 'size': 2, 'parents': ['a']}], 10)
Expected Output: {'error': 'cycle detected'}
Explanation: a depends on b and b depends on a, so the dependency graph is cyclic.
Input: ([{'id': 'a', 'fee': 6, 'size': 3, 'parents': []}, {'id': 'b', 'fee': 4, 'size': 2, 'parents': []}], 3)
Expected Output: {'order': ['a'], 'total_fee': 6, 'total_size': 3}
Explanation: Both packages have the same ratio 2.0, so the tie is broken by larger package fee, choosing a.
Hints
- Use DFS with a recursion-state map to detect cycles and memoize the full ancestor set of each transaction.
- For large mempools, cache each transaction's ancestor closure and aggregate fee/size totals; after including new transactions, only descendant packages need to be invalidated or recomputed.