Answer Policy Violation Log Queries

Question

This question asks the candidate to perform various queries on a sorted violation log list, focusing on counting unique posts and retrieving policies based on specific criteria.

Codemia · Accepted Answer

To tackle the problem, we will break it down into the five sub-questions. Each question requires us to manipulate the violation log list, which is sorted by timestamp. We will leverage efficient data structures such as dictionaries and sets to facilitate quick lookups and counts.

1. **Count Unique Posts by Policy**: Use a dictionary to map policies to sets of post IDs. Iterate through the log and add post IDs to the corresponding policy set. The size of each set will give the unique count.

2. **Get Policies Violated by a Post**: Iterate through the log and collect policies associated with the given post ID.

3. **Count Unique Posts at a Timestamp**: Use binary search to find the index of the first entry with the given timestamp, then count unique posts from that index onward until the next timestamp.

4. **Count Unique Posts in a Time Range**: Use binary search to find the start and end indices for the given time range and count unique posts in that slice of the log.

5. **Count Violations by Policy**: Similar to the first question, iterate through the log and maintain a count of violations for each policy.

The time complexity for each of the queries can vary:
- Counting unique posts by policy: O(n) where n is the number of logs.
- Getting policies violated by a post: O(n) in the worst case.
- Counting unique posts at a timestamp: O(log n) for binary search + O(m) for counting, where m is the number of posts at that timestamp.
- Counting unique posts in a time range: O(log n) for finding indices + O(k) for counting, where k is the number of posts in the range.
- Counting violations by policy: O(n). Overall, the solution is efficient given the constraints.

```python
from collections import defaultdict

# Sample log format: [postId, policy, timestamp]
violation_log = [[1, 'policyA', 123], [2, 'policyB', 124], [1, 'policyA', 125]]

# Count Unique Posts by Policy
def count_unique_posts_by_policy(log):
    policy_map = defaultdict(set)
    for postId, policy, timestamp in log:
        policy_map[policy].add(postId)
    return {policy: len(posts) for policy, posts in policy_map.items()}

# Example usage
print(count_unique_posts_by_policy(violation_log))
```

Interviewers will be looking for clarity in your thought process and how you approach breaking down complex problems. They will assess your ability to write efficient code and handle edge cases, as well as your understanding of algorithmic complexity. Communication is key, so explaining your reasoning and decisions during the coding process is crucial.

Answer Policy Violation Log Queries

Pinterest

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Pinterest Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string