Quick Overview

This question evaluates spatial reasoning on an integer 2D grid, geometric line relationships for queens' attack paths, and the use of efficient data structures to count interactions and handle occlusion, in the Coding & Algorithms domain.

Count queen attacks on points with blockers

Company: Voleon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given positions on an (unbounded) 2D integer grid. - `queens`: coordinates of queens - `points`: query coordinates A queen attacks along 8 directions: horizontal, vertical, and the two diagonals. ## Part 1 — No blockers For each point `p` in `points`, compute how many queens can attack `p`. - A queen at `q` attacks `p` if `p` lies on the same row, column, or diagonal as `q`. Return an array `ans` where `ans[i]` is the number of queens attacking `points[i]`. ## Part 2 — Blockers (rocks) Now you are also given: - `rocks`: coordinates of rocks Rocks block attacks. A queen attacks a point `p` only if, along the line from the queen to `p`, there is **no rock strictly between** them. Again return `ans[i]` for each query point. ### Input/Output - Input: `queens`, `points`, and optionally `rocks` - Output: integer array of size `len(points)` ### Constraints (reasonable interview constraints) - `1 <= len(queens), len(points), len(rocks) <= 2*10^5` - Coordinates fit in 32-bit signed integers. - Aim for about `O((Q + R + P) log(Q+R))` time for Part 2.

Quick Answer: This question evaluates spatial reasoning on an integer 2D grid, geometric line relationships for queens' attack paths, and the use of efficient data structures to count interactions and handle occlusion, in the Coding & Algorithms domain.

Part 1: Count Queen Attacks Without Blockers

You are given positions of queens and query points on an unbounded 2D integer grid. A queen attacks along rows, columns, and the two diagonal directions. For each query point, return how many queens can attack it. A queen attacks a point if the point is on the same row, same column, same main diagonal, or same anti-diagonal as the queen. A queen located exactly on a query point does not count as attacking that point.

Constraints

  • 0 <= len(queens) <= 2 * 10^5
  • 0 <= len(points) <= 2 * 10^5
  • Coordinates fit in 32-bit signed integers.
  • Query points may repeat.
  • If a queen is exactly on a query point, that queen does not count as attacking that point.

Examples

Input: ([[0, 0], [1, 2], [3, 0], [2, 2]], [[0, 2], [2, 0], [1, 1], [5, 5]])

Expected Output: [3, 3, 3, 2]

Explanation: For example, [0, 2] is attacked by two queens on row y=2 and one queen on column x=0.

Input: ([], [[0, 0], [1, 1]])

Expected Output: [0, 0]

Explanation: With no queens, no point is attacked.

Hints

  1. A queen can attack a point based only on four line identifiers: row, column, x - y diagonal, and x + y diagonal.
  2. Be careful not to count a queen on the query point itself four times.

Part 2: Count Queen Attacks With Blocking Rocks

You are given positions of queens, query points, and rocks on an unbounded 2D integer grid. A queen attacks along rows, columns, and the two diagonal directions. Rocks block attacks: a queen attacks a query point only if the queen and point are on the same row, column, or diagonal, and there is no rock strictly between them on that line. Only rocks block attacks; other queens do not block line of sight. A queen located exactly on a query point does not count as attacking that point. A query point may coincide with a rock; because blockers must be strictly between the queen and query point, a rock at the query coordinate itself does not block attacks to that coordinate.

Constraints

  • 0 <= len(queens) <= 2 * 10^5
  • 0 <= len(points) <= 2 * 10^5
  • 0 <= len(rocks) <= 2 * 10^5
  • Coordinates fit in 32-bit signed integers.
  • Queens and rocks do not occupy the same coordinate.
  • Query points may repeat and may coincide with a queen or a rock.

Examples

Input: ([[0, 0], [0, 3], [3, 0], [2, 2], [-2, 2]], [[0, 2], [0, -1], [1, 1], [3, 3]], [[0, 1], [1, 1], [2, 0]])

Expected Output: [3, 1, 2, 3]

Explanation: For [0,2], the rock at [0,1] blocks the queen at [0,0], but not the queen at [0,3]. The query [1,1] is itself a rock, but endpoint rocks are not strictly between.

Input: ([[0, 0], [1, 1], [2, 0]], [[1, 0], [1, 1], [3, 3]], [])

Expected Output: [3, 2, 2]

Explanation: With no rocks, this reduces to the no-blockers version.

Hints

  1. Handle each row, column, and diagonal as a separate sorted 1D line.
  2. For a query point on a line, only queens between the nearest rock before the point and the nearest rock after the point can attack along that line.

Loading coding console...