Katkat
Back

Implement Game Physics and Block Mining

CoinbaseSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

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).

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.
  1. If the dependency graph contains a cycle, report an error.
  2. 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.