Latest Questions | Page 3

Q. Package Drop Optimization

Uber Connect's package delivery team is reviewing how delivery agents handle packages across multiple zones.

For each of the n delivery zones:
- `scheduledDrop[i]` stores the scheduled time (in minutes) to drop the package in the i-th zone.
- `realDrop[i]` stores the actual time (in minutes) the package was dropped in the i-th zone.

Due to system limitations , the assignment of scheduled times and actual times to zones was not fixed, and can be shuffled independently before analysis. To evaluate overall performance, Uber calculates a weighted drop delay, where each zone is given a weight equal to its zone number. The weighted drop delay is formally defined as:

Total Weighted Drop Delay = ∑ i * (realDrop[i] - scheduledDrop[i]), where i is from 1 to n (1-based indexing).

Implement a function that determines the maximum possible weighted drop delay defined above. You are allowed to reorder both arrays independently in any way to maximize the total delay score. The function `maximizeDropDelay` takes the following parameters:
- `int scheduledDrop[]`: the scheduled drop times (in minutes)
- `int realDrop[]`: the actual drop times (in minutes)

The function should return an integer representing the maximum possible weighted drop delay. Since the answer can be very large, return the answer modulo (10⁹ + 7).

Note: The arrays use 1-based indexing in the formula, but are given as 0-based arrays in implementation.

Example
n = 4
scheduledDrop = [2, 1, 3, 4]
realDrop = [2, 3, 2, 3]

Some of the possible rearrangements and their resulting weighted drop delay scores:
Weighted Drop Delay = ∑ i * (realDrop[i] - scheduledDrop[i])

It is guaranteed that no other possible rearrangement of the arrays will generate a weighted drop delay greater than 7.
Hence, the answer is **7**.

Constraints
- 1 ≤ n ≤ 10⁵
- 1 ≤ scheduledDrop[i] ≤ 10⁹
- 1 ≤ realDrop[i] ≤ 10⁹

Sample Input
3
1 2 3
10 10 10

Sample Output
50

Explanation
It is optimal to rearrange scheduledDrop to: [3, 2, 1] and keep realDrop the same.
Calculating weighted drop delay for each index:
- i = 1 → 1 × (10 - 3) = 7
- i = 2 → 2 × (10 - 2) = 16
- i = 3 → 3 × (10 - 1) = 27
Total = 7 + 16 + 27 = 50, which is the maximum possible weighted drop delay.
Hence, the answer is 50. Show More

Finally, a basketball court has been opened in SIS, so Demid has decided to hold a basketball exercise session. 2 * n students have come to Demid's exercise session, and he lined them up into two rows of the same size (there are exactly n people in each row). Students are numbered from 1 to n in each row in order from left to right.

Now Demid wants to choose a team to play basketball. He will c hoose players from left to right, and the index of each chosen player (excluding the first one taken) will be strictly greater than the index of the previously chosen player. To avoid giving preference to one of the rows, Demid chooses students in such a way that no consecutive chosen students belong to the same row.

The first student can be chosen among all 2n students (there are no additional constraints), and a team can consist of any number of students. Demid thinks that in order to compose a perfect team, he should choose students in such a way that the total height of all chosen students is maximum possible. Help Demid to find the maximum possible total height of players in a team he can choose.

Array or integers. The first element is n. The next n elements are the heights of the students in the first row. The next n elements are the heights of the students in the second row.

Output
Print a single integer - the maximum possible total height of players in a team Demid can choose.

Examples
Input: {5, 9, 3, 5, 7, 3, 5, 8, 1, 4, 5}
Output: 29

Input: {3, 1, 2, 9, 10, 1, 1}
Output: 19

Browse Resources
Search for any documentation you might need for this problem. For example: array indexing, React props, etc.

powered by Google Show More

A company is organizing a batch process, where each batch consists of several task groups arranged in a line and numbered from left to right. Each group currently has a certain number of tasks assigned, represented by the array tasks[], where tasks[i] is the number of tasks in the i-th group.

To optimize the process, the company wants the number of tasks in each group to be non-increasing from left to right.

In one move, a single task can be shifted from any group to its immediate neighbor (either to the left or right). More formally, you can select a group i (tasks[i] > 0) and do one of the following:
- If i > 1, move one task from group i to group i-1 (the previous group). After this move, tasks[i] decreases by 1 and tasks[i-1] increases by 1.
- If i < n, move one task from group i to group i+1 (the next group). After this move, tasks[i] decreases by 1 and tasks[i+1] increases by 1.

Determine the minimum number of moves required to rearrange the tasks so that the array becomes non-increasing.

Example:
n = 6
tasks = [5, 3, 2, 3, 3, 3]

In this example, you first need to move one task from group 1 to group 2, resulting in [4, 4, 2, 3, 3, 3]. After that, you need to move one task from group 2 to group 3, and the array will become non-increasing tasks = [4, 3, 3, 3, 3, 3].

Hence, the answer is 2.

Function Description:
Complete the function getMinimumMoves in the editor below.

getMinimumMoves has the following parameters:
int tasks[n]: the number of tasks in each group.

Returns:
int: the minimum number of moves required.

Constraints:
- 1 ≤ n ≤ 250
- 0 ≤ tasks[i] ≤ 250
- It is guaranteed that the total number of tasks across all groups will not exceed 250.

Input Format For Custom Testing

Sample Case 0
Sample Input For Custom Testing
STDIN:
tasks = [3, 4, 3, 3, 5, 1] Show More

A digital art gallery has an art collection which is represented as a binary string. Each digit in the string represents an artwork and there are two types of artworks: '0' represents a traditional artwork, '1' represents a modern artwork. Your task is to find out the number of ways to choose three artworks in ascending order of their position in the collection, such that no two adjacent selected artworks are of the same type.

Example:
collection = '01001'

The following sequences of artworks match the criterion:
- [1, 2, 3], that is, 01001 → 010
- [1, 2, 4], that is, 01001 → 010
- [2, 3, 5], that is, 01001 → 101
- [2, 4, 5], that is, 01001 → 101

The answer is 4.

Function Description:
Complete the function countWays in the editor below.

countWays has the following parameter:
string collection: a string that represents the collection

Returns:
long: the total number of ways to select 3 artworks that meet the criterion

Constraints:
- 1 ≤ |collection| ≤ 2×10⁵
- Each character in collection is either '0' or '1'

Input Format For Custom Testing

Sample Case 0
Sample Input For Custom Testing
STDIN:
10111

Sample Output:
collection = "10111"

Explanation:
The following sequences of artworks match the criterion:
- [1, 2, 3], that is, 10111 → 101
- [1, 2, 4], that is, 10111 → 101
- [1, 2, 5], that is, 10111 → 101 Show More

Given a series of integer intervals, determine the size of the smallest set that contains at least 2 integers within each interval.

Example:
first = [0, 1, 2]
last = [2, 3, 3]

The intervals start at first[i] and end at last[i].
- Interval 0: [0, 2] → contains 1 and 2
- Interval 1: [1, 3] → contains 2 and 3
- Interval 2: [2, 3] → contains 2 and 3

To satisfy all intervals , we must select integers such that each interval has at least 2 of them.
The smallest such set is {1, 2, 3}, and the answer is 3.

Function Description
Complete the function `interval` with the following parameters:
- `int first[]`: each element represents the start of interval[i]
- `int last[]`: each element represents the end of interval[i]

Returns:
- `int`: the size of the smallest set such that every interval contains at least two integers from it

Constraints:
- 1 ≤ n ≤ 10^5
- 0 ≤ first[i] < last[i] ≤ 10^9

Input Format for Custom Testing:

The first line contains the integer n, the number of intervals.
The second line contains n integers representing the array `first`.
The third line contains n integers representing the array `last`.

Sample Input 0
4
3 2 0 4
5 4 2 6

Explanation:
The intervals are:
- [3, 5]
- [2, 4]
- [0, 2]
- [4, 6]

The smallest set containing at least 2 integers in each interval might be {1, 2, 3, 4, 5}.
The correct set would be calculated by the function, and its size would be returned. Show More

A forklift operator navigates products within an automotive parts warehouse. The dashboard displays a real-time map showing open and blocked sections as an n x m matrix of 1's (open) and 0's (blocked). The operator starts at the top-left corner of the map at warehouse[0][0] and aims to reach the bottom-right corner at warehouse[n-1][m-1]. Movements can only be made to the right or downward. Given the warehouse map, calculate the number of distinct paths from warehouse[0][0] to warehouse[n-1][m-1]. Return the result modulo (10^9 + 7).

Example:
warehouse =
[1, 1, 0, 1],
[1, 1, 1, 1]

This matrix shows open (1) and blocked (0) sections of the warehouse. It is only possible to travel through open sections, so no path can go through the section at (0, 2). There are 2 possible paths from warehouse[0][0] to warehouse[1][3], and 2 modulo (10^9 + 7) = 2.

Function Description
Complete the function `numPaths` in the editor with the following parameter(s):
- `warehouse[n][m]`: a two-dimensional array of integers with n rows and m columns

Returns
- `int`: the number of paths through the matrix, modulo (10^9 + 7)

Constraints
- 1 ≤ n, m ≤ 1000
- Each cell in matrix warehouse contains either a 0 or a 1 Show More

School renovation

Given N classrooms in a school and each classroom has a capacity of A[i] students. Bob is a builder and follows the instructions of Alice.

Alice gives Q instructions of the following types:
- 1 L 0: Move L classrooms to the left
- 2 R 0: Move R classrooms to the right
- 3 X Y: Remove the next classroom and add two new classrooms of capacity X and Y respectively to the ri ght of the current classroom. (After performing this operation, classroom numbers change accordingly)

Note: The queries are always valid.

Initially, Bob is in the first classroom. After performing all instructions from Alice, print the capacity of all classrooms from 1 to the total number of classrooms.

Function description

Complete the solve function. This function takes the following 2 parameters and returns the required answer.

Parameters:
- A: Represents a linear array denoting the capacity of classrooms in the old school
- queries: Represents a 2D array denoting instructions given by Alice of the given types

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.

- The first line contains two space-separated integers N and Q denoting the initial number of classrooms and the number of instructions.
- The second line contains N space-separated integers denoting initial classroom capacities.
- Next Q lines contain queries of the form:
- 1 L 0
- 2 R 0
- 3 X Y

Output format

After performing all instructions from Alice, return the capacity of all classrooms from 1 to K (K = total number of classrooms in the renovated school).

Sample input

5 4
1 2 1 4 5
2 1 0
1 1 1
1 2 0
3 5 2

Sample output

1 2 5 7 4 1 1

Explanation

Bob moves 1 classroom right, so he is in the 2nd classroom now.
He moves 1 classroom left, so he is back to the 1st classroom.
He moves 2 classrooms left (stays at index 0 since it's the start).
Then, from current position (0), he removes the next classroom (2nd) with capacity 2 and adds classrooms with capacities 5 and 7.
Final classroom capacities: [1, 2, 5, 7, 4, 1, 1] Show More

Number in a range

You are given three integers L, R, and K. A number X represents a lucky number if the binary representation of X contains the pattern 101 as a substring. Determine the Kth lucky number between L and R. If the Kth lucky number does not exist, then print -1.

Function description

Complete the solve function. This function takes the following 3 parameters and returns the Kth lucky number in between L and R.

Parameters:
- L: Represents an integer denoting the value of L
- R: Represents an integer denoting the value of R
- K: Represents an integer denoting the Kth lucky number to be found

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.

- The first line contains T, which represents the number of test cases.
- For each test case:
- The first line contains three space-separated integers L, R, and K.

Output format

For each test case, print the Kth lucky number in the range [L, R] on a new line. If the Kth lucky number does not exist, then print -1.

Constraints

1 ≤ T ≤ 200
1 < L ≤ R ≤ 10^18
1 ≤ K ≤ 10^18

Sample input

6
5 40 6
5 12 4
9 20 5
7 7 1
14 37 4
13 25 4

Sample output

21
-1
-1
-1
23
22

Explanation:

For test case 1: All lucky numbers between 5 and 40 are 5, 10, 11, 13, 20, 21, 22, 23, 26, 27, 29, 37, and 40. The sixth lucky number is 21.
For test case 2: All lucky numbers between 5 and 12 are 5, 10, and 11. There are less than 4 lucky numbers, so print -1.
For test case 3: All lucky numbers between 9 and 20 are 10, 11, and 13. There are less than 5 lucky numbers, so print -1.
For test case 4: There are 0 lucky numbers between [7, 7], so print -1.
For test case 5: All lucky numbers between 14 and 37 are 20, 21, 22, 23, 26, 27, 29, and 37. The fourth lucky number is 23.
For test case 6: All lucky numbers between 13 and 25 are 13, 20, 21, 22, and 23. The fourth lucky number is 22.

Note:

Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement.

Limits

Time Limit: 1.0 sec(s) for each input file
Memory Limit: 256 MB
Source Limit: 1024 KB

Allowed Languages: Bash, C, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java 8, Java 14, JavaScript(Node.js), Julia, Kotlin, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, Racket, Ruby, Rust, Scala, Swift, TypeScript, Visual Basic Show More

You are given a board of size M × N where each cell can be either empty ('O') or a wall ('X').
A robot is initially placed at the top-left cell (0,0) and can move in four directions: up, down, left, and right — but not diagonally.
The robot can only move through empty cells and cannot pass through or land on walls.

Your task is to print the maximum number of empty cells the robot can vi sit starting from the top-left cell, including the starting cell.

Input Format:
- First line: Two integers M and N — the number of rows and columns of the board.
- Next M lines: Each contains a string of length N, consisting of characters 'O' and 'X'.

Output Format:
- A single integer — the number of empty cells the robot can visit.

Constraints:
- 1 ≤ M, N ≤ 100

Sample Input 1:
4 3
OXO
OOX
XOO
OOO

Sample Output 1:
8

Explanation:
Starting at (0,0), the robot can move through a connected component of 8 'O' cells. One cell ('O' at (0,2)) is isolated and cannot be reached.

Sample Input 2:
4 3
000
00X
OXO
X00

Sample Output 2:
6

Explanation:
Starting at (0,0), the robot can visit 6 cells before being blocked by walls. Show More

Undirected Coloured Graph Shortest Path

You are given an undirected weighted graph G(V, E) where each vertex is assigned a colour. Vertices form pairs of the same colour. Thus, total pairs = V/2 (if V is even) or (V/2)+1 (if V is odd). Each pair is assigned a unique colour.

A query Q specifies a colour, and your task is to find the shortest path (in terms of weight) between the two vertice s sharing this colour.

Input Format:
- The first line contains two integers V and E separated by a space (number of vertices and edges).
- The next E lines each contain three integers u, v, and w: an edge between vertex u and vertex v with weight w.
- The next V/2 (or V/2+1 if V is odd) lines specify the vertex pairs for each colour (each line has two vertex indices). If V is odd, the last line contains a single vertex with no pair.
- The final line contains a single integer Q, representing the colour number to query.

Output Format:
- Print the shortest path (by weight) between the vertex pair corresponding to colour Q.
- Each vertex in the path should be printed in order, separated by a single space.

Constraints:
- 2 ≤ V ≤ 100
- 1 ≤ E ≤ 100

Sample Input 1:
7 8
0 6 10
0 2 11
2 4 9
6 4 2
5 2 7
5 1 8
1 4 4
3 4 3
0 1
2 3
5 6
4
3

Sample Output 1:
5 1 4 6

Explanation:
There are 7 vertices and 8 edges.
Colour 1 → nodes 0, 1
Colour 2 → nodes 2, 3
Colour 3 → nodes 5, 6
Colour 4 → node 4 (no pair)

Query = 3 → Find shortest path between 5 and 6.
Shortest weighted path: 5 → 1 → 4 → 6 Show More