Implement Binary Search for Policy Violation Logs
Company: Pinterest
Role: Data Scientist
Category: Data Manipulation (SQL/Python)
Difficulty: medium
Interview Round: Onsite
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.
Overview: 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.
Write SQL/Python to return all pin_ids that violated a given policy type for a specified date range, using binary search over date-sorted logs instead of a full scan.
Tables
violations(pin_id INTEGER, type VARCHAR, violation_date DATE)
Hints
- Create an index on (type, violation_date) to enable efficient range scans.
- In Python, pre-sort or group by policy type and use bisect_left/bisect_right on the date list to binary-search the date window.