Implement course scheduling and rate limiter analysis

You are given two independent coding problems.

Problem 1: Course Scheduling

You are planning to take a set of courses and are given prerequisite relationships between them.

• There are n courses labeled from 0 to n - 1 .
• You are given a list of prerequisite pairs prerequisites , where each pair [a, b] means you must complete course b before you can take course a .

Task A

Determine whether it is possible to finish all n courses.

• Return true if you can complete all courses (i.e., the prerequisite graph has no cycle); otherwise return false .

You should specify the time and space complexity of your algorithm.

Task B (Follow-up)

Assume:

• Each course takes exactly one semester to complete.
• In any given semester, you may take any number of courses, as long as you have completed all of their prerequisites in earlier semesters.

If it is possible to finish all courses, compute the minimum number of semesters required to complete all n courses. If it is impossible (due to cycles), indicate that it cannot be done.

Describe an efficient algorithm for this and its time and space complexity.

You may assume:

• 1 <= n <= 10^5 .
• 0 <= len(prerequisites) <= 2 * 10^5 .

Problem 2: Analyze Dropped Requests Under a Rate Limiter

You are running a social media website that suddenly went viral. To protect your backend, you added a rate limiter. Now you want to analyze logs to determine which requests would be dropped by this limiter.

You are given:

• An array requests , where the index is the request ID (0-based), and the value requests[i] is the time in seconds when the i -th request arrived.
• The array requests is non-decreasing (requests are logged in arrival order; multiple requests can have the same timestamp if they arrive in the same second).

Your rate limiter enforces the following rules:

1. At most 3 requests per second can be processed.
2. At most 20 requests per any sliding 10-second window can be processed.

Formally:

• For rule (1): For any timestamp t , among all requests with arrival time exactly t , at most 3 can be processed; any additional requests arriving at time t must be dropped.
• For rule (2): For any request arriving at time t , consider all requests with arrival times in the interval [t - 9, t] (inclusive). If processing this request would cause the total number of processed requests in that interval to exceed 20, then this request must be dropped.

Rules are applied in arrival order:

• For each request in index order, first consider whether it is dropped due to rule (1) or rule (2), taking into account only previously processed requests (not the dropped ones).
• If a request is dropped by either rule, it is not counted as processed for any future checks.

Task

Given the array requests, return a list of the times of all dropped requests, in the order they appear in the input.

You should:

• Clearly define the algorithm you use to determine dropped requests.
• Aim for an efficient solution that can handle up to 10^5 requests.
• State the time and space complexity of your approach.

You may assume:

• 1 <= len(requests) <= 10^5 .
• 0 <= requests[i] <= 10^9 .
• requests is non-decreasing.