Katkat
Back

Count queen attacks on points with blockers

VoleonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.