Round 1
Questions: In the context of an Amazon gaming product involving a snake and apples on a number line, the scenario unfolds with a set of unique coordinates representing the positions of the apples. The array named position of size n holds these unique integers, each denoting the coordinate of the ith apple.
The snake, starting at the origin (0 coordinate), decides to consume some of the apples. The snake can move left and right along the line at a constant speed of 1 unit/sec, allowing it to transition from a coordinate x to x + 1 or x - 1 in 1 second.
Additionally, the snake can instantly eat an apple when it occupies the same coordinate as the apple.
Given an integer k and the array position, determine the minimum time required for the snake to consume at least k apples.
Example k = 3 n = 3 position = [-20, 5, 10]
It is optimal to choose the following way:
- Initially, the snake is at coordinate 0. As the snake needs to eat all three apples,
- It will first go right for 5 seconds and eat the apple at position 5.
- It moves in the same direction for another 5 seconds to reach coordinate 10 and eat the apple there.
- Now it moves left for 30 seconds to reach the coordinate -20 and eat the apple there.
Time taken will be 5 + 5 + 30 = 40 seconds.
It can be shown that it is not possible for the snake to eat all the apples in less than 40 seconds.
Hence, the answer is 40.
Function Description
Complete the function findMinimumTime in the editor below. findMinimumTime has the following parameters:
- int k: the minimum number of apples the snake needs to eat.
- int position[n]: an array of integers denoting the coordinates of the apples on the number line.
Returns
int: the minimum time required for the snake to eat at least k apples.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ k ≤ n
- |position[i]| ≤ 10^8
- The array position consists of distinct integers.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Round 2
Questions: An Amazon fulfillment center receives a large number of orders each day. Each order is associated with a range of prices of items that need to be picked from the warehouse and packed into a box. There are n items in the warehouse, which are represented as an array items[n]. The value of items[i] represents the value of the ith item in the warehouse, and subsequently there are m orders. The start_index and end_index for the ith order are represented in the arrays start[i] and end[i]. Also start[i] and end[i] are 0-index based.
For each order, all the items are picked from the inclusive range from start[i] through end[i].
Given array items, start, end, and query. For each query, find the count of elements in the range with a value strictly less than query.
Example: Given, n = 5, items = [1, 2, 5, 4, 5], m = 3, start = [0, 0, 1], end = [1, 2, 2] and query = [2, 4].
Order Number | start index | end index | picked items --- | --- | --- | --- 1st | 0 | 1 | [1, 2] 2nd | 0 | 2 | [1, 2, 5] 3rd | 1 | 2 | [2, 5]
Over the 3 orders, the picked items are [1, 2, 1, 2, 5, 2, 5].
For the first query, 2 picked items have values less than 2. For the second query, 5 picked items have values less than 4. Hence the answer is [2, 5].
Function Description
Complete the function getSmallerItems in the editor below. getSmallerItems has the following parameters:
- int items[n]: the value of each item
- int start[m]: the start index for each order
- int end[m]: the end index for each order
- int query[q]: query values
Returns
long output[q]: the answer for each query, the number of picked items having a value strictly less than query.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ items[i] ≤ 10^9, where 0 ≤ i < n
- 0 < m ≤ 10^5
- 0 ≤ start[i] ≤ end[i] < n, where 0 ≤ i < m
- 1 ≤ q ≤ 10^5
- 1 ≤ query[i] ≤ 10^9, where 0 ≤ i < q
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.