FastPrepObstacle Placement Queries

Obstacle Placement Queries

Hudson River Trading logoHudson River Trading● MediumFULLTIMENEW GRADINTERNOA
Learn

Problem statement

You are given an infinite integer number line and an array operations. Process the operations in order while maintaining the coordinates that contain obstacles.

  • [1, x]: Place an obstacle at coordinate x. Coordinate x is guaranteed to contain no obstacle when this operation is performed.
  • [2, x, size]: Check whether a block of length size can end immediately before coordinate x. The block would occupy every integer coordinate from x - size through x - 1. Append '1' to the answer if none of those coordinates contains an obstacle; otherwise append '0'. This operation only checks feasibility and does not place the block.

Return the binary string formed by the results of all type-2 operations in their original order.

Function

solution(operations: int[][]) → String

Examples

Example 1

operations = [[1,2],[1,5],[2,5,2],[2,6,3],[2,2,1],[2,3,2]]return = "1010"
  1. Place obstacles at coordinates 2 and 5.
  2. The block before 5 covers 3 and 4, so append 1.
  3. The block before 6 covers 3, 4, and 5; coordinate 5 is blocked, so append 0.
  4. The block before 2 covers only coordinate 1, so append 1.
  5. The block before 3 covers coordinates 1 and 2; coordinate 2 is blocked, so append 0.

More Hudson River Trading problems

See Hudson River Trading hiring insights
public String solution(int[][] operations) {
  // Write your code here.
}
operations[[1,2],[1,5],[2,5,2],[2,6,3],[2,2,1],[2,3,2]]
expected"1010"
Checking account…