Katkat
Back

Implement Binary Search for Policy Violation Logs

PinterestData Scientist · Onsite
MediumData ScientistOnsiteData Manipulation (SQL/Python)

Last updated

This question evaluates understanding of algorithmic search and data manipulation skills, specifically applying binary search over date-ordered logs and composing efficient queries using SQL and Python.

violations

+--------+---------+---------------+ | pin_id | type | violation_date| +--------+---------+---------------+ | 0 | spam | 2022-01-03 | | 1 | spam | 2022-01-03 | | 0 | privacy | 2022-01-03 | | 2 | child | 2022-02-06 | | 3 | spam | 2022-02-10 | +--------+---------+---------------+

Scenario

Pinterest wants to query pins that violated specific policies quickly from daily logs.

Question

Write SQL/Python to return all pin_ids that violated a given policy type. Logs are date-sorted; add a function that, for a (policy, start_date, end_date), returns the matching pins using binary search rather than full scan.

Hints

Create index on (type, violation_date); in Python, bisect left/right on pre-sorted list of dates.