Query on Huge Sparse Matrix | Dataford Interview Questions

Given a large matrix size of 10^18X10^18 and list sub tables with top-left and right bottom coordinates and number filled in those tables. Find the coordinates of number 'n'.

Asked in the Round 1 stage. Write a PostgreSQL query using the provided tables to return the coordinates for every requested number.

Output

One row per matching matrix region and request.
Return request_id, target_number, top_left_row, top_left_col, right_bottom_row, and right_bottom_col.
Exclude requests with no matching region and order by request_id, then top_left_row, top_left_col.

Schema

matrix_subtables

Column	Type	Description
subtable_idPK	BIGINT	Unique identifier for a rectangular matrix region
top_left_row	BIGINT	One-based row of the region's top-left cell
top_left_col	BIGINT	One-based column of the region's top-left cell
right_bottom_row	BIGINT	One-based row of the region's bottom-right cell
right_bottom_col	BIGINT	One-based column of the region's bottom-right cell
filled_number	BIGINT	Number filling every cell in the region

target_requests

Column	Type	Description
request_idPK	BIGINT	Unique identifier for a lookup request
target_number	BIGINT	Number whose containing regions must be found

Your question is Query on Huge Sparse Matrix. Start with the requirements and the two tables in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem