How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Calculate Circular Route Query Distance

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a circular route with `n` stops numbered `0` to `n - 1`. The array `distances` has length `n`, where `distances[i]` is the clockwise distance from stop `i` to stop `(i + 1) mod n`. You are also given a list of queries, where each query `[start, end]` asks for the shortest distance between `start` and `end` along the circular route. For each query, you may travel either clockwise or counterclockwise. Return the sum of the shortest distances over all queries. For example, if `distances = [1, 2, 3, 4]`, the clockwise distance from stop `0` to stop `2` is `1 + 2 = 3`, while the other direction is `3 + 4 = 7`, so the shortest distance is `3`. Design an efficient algorithm for many queries. **Function signature:** ```python def total_shortest_circular_distance(distances: list[int], queries: list[list[int]]) -> int: pass ``` **Constraints:** - `2 <= n <= 100000` - `1 <= distances[i] <= 100000` - `1 <= len(queries) <= 100000` - `0 <= start, end < n` - The answer fits in a 64-bit signed integer.

Quick Answer: This question evaluates a candidate's ability to reason about circular arrays, distance computations, and query-efficient algorithms, assessing concepts such as modular indexing and cumulative distances.

You are given a circular route with n stops numbered from 0 to n - 1. The array distances has length n, where distances[i] is the clockwise distance from stop i to stop (i + 1) mod n. You are also given a list of queries, where each query [start, end] asks for the shortest distance between start and end on the circle. For each query, you may travel either clockwise or counterclockwise. Return the sum of the shortest distances for all queries. The distance from a stop to itself is 0. Your solution should be efficient enough to handle many queries.

Constraints

2 <= len(distances) <= 100000
1 <= distances[i] <= 100000
1 <= len(queries) <= 100000
0 <= start, end < len(distances)
The final answer fits in a 64-bit signed integer

Examples

Input: ([1,2,3,4], [[0,2],[2,0],[1,1],[3,1]])

Expected Output: 11

Explanation: Shortest distances are 3 for 0->2, 3 for 2->0, 0 for 1->1, and 5 for 3->1. Their sum is 11.

Input: ([10,1,1,1], [[0,1],[1,3],[2,0]])

Expected Output: 7

Explanation: For 0->1, clockwise is 10 and counterclockwise is 3, so choose 3. For 1->3, the shortest distance is 2. For 2->0, the shortest distance is 2. Total = 3 + 2 + 2 = 7.

Input: ([5,8], [[0,1],[1,0],[0,0]])

Expected Output: 10

Explanation: With two stops, 0->1 has shortest distance 5, 1->0 also has shortest distance 5, and 0->0 is 0. Total = 10.

Input: ([2,2,2,2,2], [[4,2],[0,3],[1,4]])

Expected Output: 12

Explanation: Each query has clockwise distance 6 and counterclockwise distance 4, so each contributes 4. Total = 12.

Hints

Precompute the clockwise distance from stop 0 to every stop using a prefix sum array.
For a query (start, end), compute the clockwise distance in O(1), then compare it with total_route_length - clockwise_distance.

Quick Overview

This question evaluates a candidate's ability to reason about circular arrays, distance computations, and query-efficient algorithms, assessing concepts such as modular indexing and cumulative distances.