Company: UBER

Analyze the efficiency of the following sorting algorithm by counting the number of swaps it performs:

For an array `arr` of size `n`:
1. Find the smallest pair of indices 0 ≤ i < j ≤ n-1 such that arr[i] > arr[j], where "smallest" means lexicographical ordering of pairs (i1, j1) < (i2, j2) if i1 < i2 or (i1 = i2 and j1 < j2).
2. If no such pair exists, the algorithm stops.
3. Otherwise, swa p arr[i] and arr[j] and search for the next pair.

Your task is to determine how many swaps this algorithm performs to sort a given array.

Example
n = 4
arr = [5, 1, 4, 2]

The algorithm performs these swaps:
- [5, 1, 4, 2] → [1, 5, 4, 2] (swap indices 0 and 1)
- [1, 5, 4, 2] → [1, 4, 5, 2] (swap indices 1 and 2)
- [1, 4, 5, 2] → [1, 4, 2, 5] (swap indices 2 and 3)
- [1, 4, 2, 5] → [1, 2, 4, 5] (swap indices 1 and 2)
Total number of swaps: 4

Function Description
Complete the function `howManySwaps` in the editor with the following parameter:
- `int arr[n]`: the array to sort

Returns
- `int`: the number of swaps

Constraints
- 1 ≤ n ≤ 10⁵
- 1 ≤ arr[i] ≤ 10⁹
- All elements of arr are distinct

Input Format for Custom Testing

Sample Case 0

Sample Input
STDIN
3
7 1 2

Function
arr[] size n = 3
arr = [7, 1, 2]

Sample Output
2

Explanation
[7, 1, 2] → [1, 7, 2] → [1, 2, 7] Show More

Bitwise Palindromic Paths

You are given a binary matrix of size N x M where each cell contains either 0 or 1. A path from the top-left cell (0,0) to the bottom-right cell (N-1,M-1) is valid if you can only move right or down at each step.

A path is called bitwise palindromic if the sequence of bits collected along the path forms a palindrome when interpreted as a string (e.g., 0110, 1, 101).

Your task is to count the number of such bitwise palindromic paths.

Function Description: You need to implement the function countBitwisePalindromicPaths.

Parameters:
. N: An integer representing the number of rows.
· M: An integer representing the number of columns.
· grid: A 2D list of size N x M consisting of binary values (0 or 1).

Return: An integer representing the number of valid bitwise palindromic paths from (0,0) to (N-1,M-1), modulo 10⁹+7.

Input Format:
· The first line contains a single integer N.
. The second line contains a single integer M.
. The next N lines each contain M space-separated binary digits

· 1 ≤ N, M ≤ 15

Sample input
2
2
1 0
0 1

Sample output
2

Explanation

There are 2 paths:
. Path 1: 1 → 0 → 1 forms "101", which is a palindrome
. Path 2: 1 → 0 → 1 – same path, same pattern, counted again

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: 5.0 sec(s) for each input file
Memory Limit: 256 MB
Source Limit: 1024 KB

Scoring
Score is assigned if any test case passes

Allowed Languages Show More

Q Trip Tag Generator Uber's platform auto-generates trip tags which are short strings summarizing key trip metadata. To validate the tagging logic, the infrastructure team is checking how many different ways a specific tag can be constructed using segments from historical tags.

You are given an array tags of length n, where each tag is a string of length m. You're also given a targetTag that ne eds to be formed by picking characters from the tags as follows: Characters in targetTag must be picked in order (left to right). For the i-th character in targetTag, pick it from any tag but only from position j such that indices j are strictly increasing as you build the tag. You may pick multiple characters from the same tag. Two ways are considered different if the positions used or tags selected differ at any step.

Implement a function that determines the number of distinct ways to form the targetTag using the given rules. The function getTotalDistinctWays takes the following inputs: string tags[n]: List of strings, each of equal length; string targetTag: the string that needs to be constructed. The function should return an integer denoting the number of ways to form the targetTag, modulo 10^9 + 7.

Example: n = 3 tags = ["adc", "aec", "efg"] targetTag = "ac"

There are 4 distinct ways to reach the targetTag:
1. Select the 1st character of "adc" and the 3rd character of "adc".
2. Select the 1st character of "adc" and the 3rd character of "aec".
3. Select the 1st character of "aec" and the 3rd character of "adc".
4. Select the 1st character of "aec" and the 3rd character of "aec".

Constraints:
- 1 ≤ n ≤ 10^3
- 1 ≤ length of tags[i] ≤ 3000
- All tags[i] are of equal length per test case.
- The sum of the lengths of all tags[i] ≤ 10^5
- 1 ≤ length of targetTag ≤ length of tags[0]
- All characters are lowercase English letters.

Input Format For Custom Testing

Sample Case 0
Sample Input For Custom Testing STDIN
valya
lygtb
vldoh
val

Sample Output
4

Explanation: There are 4 ways to construct the targetTag "val" such that the indices will be in strictly increasing order.
- Select the 1st character of "valya", the 2nd character of "valya" and the 3rd character of "valya".
- Select the 1st character of "valya", the 2nd character of "valya" and the 4th character of "lygtb".
- Select the 1st character of "vldoh", the 2nd character of "valya" and the 3rd character of "valya".
- Select the 1st character of "vldoh", the 2nd character of "valya" and the 4th character of "lygtb".

Sample Case 1
Function

tags[] size n = 3
tags = ["valya", "lyglb", "vldoh"]
targetTag = "val" Show More

Fleet Upgrades

You're building a system for Uber Fleet Management to optimize vehicle upgrades within a limited operations budget.

There are a total of n vehicles where:
- `upgradeCost[i]`: cost to upgrade the i-th vehicle
- `expectedResale[i]`: expected resale value of the i-th vehicle after one year of operation

You may choose to upgrade any vehicle once, and the total upgrade cost mu st not exceed the given budget. The net gain from upgrading a vehicle is calculated as: `expectedResale[i] - upgradeCost[i]`.

Implement a function that determines the maximum net gain achievable by selecting a subset of vehicle upgrades. The function `maximizeFleetGain` takes the following inputs:
- `int budget`: the total upgrade budget
- `int upgradeCost[]`: an array representing the upgrade costs for the vehicles
- `int expectedResale[]`: an array representing the expected resale values after one year

The function should return an integer denoting the maximum possible net gain.

Example
budget = 250
upgradeCost = [175, 133, 109, 210, 97]
expectedResale = [200, 125, 128, 228, 133]

One optimal selection:
- Choose vehicles at index 2 and 4 → upgrade costs = 109 + 97 = 206
- Resale values = 128 + 133 = 261
- Net gain = 261 - 206 = **55**
So, the function should return **55**.

Constraints
- 0 < n ≤ 100
- 0 < budget ≤ 30000

Input Format for Custom Testing
Sample Input
30
4
1
2
4
6
5
3
5
6

Sample Output
6

Explanation
The optimal strategy is to upgrade all 4 vehicles and achieve net gain of:
(5 - 1) + (3 - 2) + (5 - 4) + (6 - 6) = 4 + 1 + 1 + 0 = **6** Show More

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

Academic Decathlon
Students are being selected for an academic decathlon team at a school. Each student has a skill level, and for a team to be uniform, the difference between any two consecutive skill levels (when arranged in increasing order) must be either 0 or 1.

Your task is to find the maximum possible team size.

Example
skills = [0, 12, 13, 9, 14]
Valid teams, when sorted, ar e (9, 10) and (12, 13, 14). These teams have sizes 2 and 3, respectively, so the maximum team size is 3.

Function Description
Complete the function findMaxTeamSize with the following parameter:
- int skills[n]: the skill levels of each student

Returns
- int: the maximum possible size of the team

Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ skills[i] ≤ 10^9

Input Format for Custom Testing

Sample Case 0

Sample Input
skills[] size n = 4
skills = [4, 13, 2, 3]

Sample Output
3

Explanation
There are two valid teams possible: (2, 3, 4) and (13). These have team sizes of 3 and 1, respectively. So the maximum possible team size is 3. Show More

Sum of Arrays
Given two arrays each of length n, arr1 and arr2, in one operation, any two elements of an array can be swapped. This can occur any number of times.

Find the maximum possible sum of i * (arr2[i] - arr1[i]) for all 1 ≤ i ≤ n after rearranging the arrays. Since the maximum possible sum can be large, return the value modulo (10^9 + 7).

Example
n = 4
arr1 = [2, 1, 3, 4]

arr2 = [2, 3, 2, 3]

Some of the possible rearrangements:
arr1: [2, 1, 3, 4], arr2: [2, 3, 2, 3] → sum = 0 + 4 + 0 - 4 = 0
arr1: [3, 1, 2, 4], arr2: [2, 3, 2, 3] → sum = -1 + 4 + 0 - 4 = -1
arr1: [3, 1, 2, 4], arr2: [3, 2, 2, 3] → sum = 0 + 2 + 0 - 4 = -2
The maximum sum possible is 7, and 7 modulo (10^9 + 7) = 7.

Function Description
Complete the function getMaxSumOfArray in the editor below.
getMaxSumOfArray has the following parameter(s):
- int arr1[n]: an array of integers
- int arr2[n]: an array of integers

Returns
- int: the maximum possible sum, modulo (10^9 + 7)

Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ arr1[i] ≤ 10^9
- 1 ≤ arr2[i] ≤ 10^9

Input Format for Custom Testing

Sample Case 0

Sample Input
arr1[] size n = 3
arr1 = [1, 2, 3]
arr2[] size n = 3
arr2 = [10, 10, 10]

Sample Output
50

Explanation
Given n = 3, arr1 = [1, 2, 3] and arr2 = [10, 10, 10].
If arr1 is changed to [3, 2, 1] and arr2 remains unchanged, the value of i * (arr2[i] - arr1[i]) = [7, 16, 27], and the total sum is 50.

Sample Case 1

Sample Input
arr1[] size n = 4
arr1 = [3, 1, 2, 6]
arr2[] size n = 4
arr2 = [2, 8, 4, 9]

Sample Output
48

Explanation
Original calculation: i * (arr2[i] - arr1[i]) = [-1, 14, 6, 12] → sum = 31
Rearranging arr1 to [6, 1, 2, 3] → new sum = 40
Rearranging arr1 to [6, 3, 2, 1] and arr2 to [2, 4, 8, 9] → i * (arr2[i] - arr1[i]) = [-4, 2, 18, 32] → sum = 48 Show More

Count Swaps During Custom Sorting
Analyze the efficiency of the following sorting algorithm by counting the number of swaps it performs:
For an array arr of size n:
1. Find the smallest pair of indices 0 ≤ i < j ≤ n-1 such that arr[i] > arr[j], where "smallest" means lexicographical ordering of pairs (i1, j1) < (i2, j2) if i1 < i2 or (i1 = i2 and j1 < j2).
2. If no such pair exists, th e algorithm stops.
3. Otherwise, swap arr[i] and arr[j] and search for the next pair.
Your task is to determine how many swaps this algorithm performs to sort a given array.

Example
n = 4, the size of arr
arr = [5, 1, 4, 2]

The algorithm performs these swaps:
[5, 1, 4, 2] → [1, 5, 4, 2] (swap indices 0 and 1)
[1, 5, 4, 2] → [1, 4, 5, 2] (swap indices 1 and 2)
[1, 4, 5, 2] → [1, 4, 2, 5] (swap indices 2 and 3)
[1, 4, 2, 5] → [1, 2, 4, 5] (swap indices 1 and 2)
The total number of swaps is 4.

Function Description
Complete the function howManySwaps in the editor with the following parameter(s):
int arr[]: the array to sort

Returns
int: the number of swaps

Constraints
1 ≤ n ≤ 10^5
1 ≤ arr[i] ≤ 10^9
All elements of arr are distinct.

Input Format for Custom Testing

Sample Case 0

Sample Input
arr[] size n = 3
arr = [7, 1, 2]

Sample Output
2

Explanation
[7, 1, 2] → [1, 7, 2] → [1, 2, 7] Show More

Given a set of nodes and a list of connected pairs, determine the order (number of nodes) in each connected component in the graph. For each component, calculate the ceiling of the square root of its order, and return the sum of these values across all connected components.

Example
graph_nodes = 10
graph_from = [1, 1, 2, 3, 7]
graph_to = [2, 3, 4, 5, 8]

There are graph_edges = 5 ed ges to consider. There are 2 isolated sets with more than one node: {1, 2, 3, 4, 5} and {7, 8}. The ceilings of their square roots are: √5 ≈ 2.236 and ceil(2.236) = 3 √2 ≈ 1.414 and ceil(1.414) = 2

The other three isolated nodes are separate, and the square root of their orders is √1 = 1 respectively. The sum is 3 + 2 + (3 * 1) = 8.

Function Description
Complete the function `connectedSum` in the editor below.
connectedSum has the following parameter(s):
- int graph_nodes: the number of nodes
- int graph_from[graph_edges]: an array of integers that represent one end of an edge
- int graph_to[graph_edges]: an array of integers that represent the other end of an edge

Returns:
- int: an integer that denotes the sum of the values calculated

Constraints
- 2 ≤ graph_nodes ≤ 10^5
- 1 ≤ graph_edges ≤ 10^5
- 1 ≤ graph_from[i], graph_to[i] ≤ n
- graph_from[i] ≠ graph_to[i]

Input Format for Custom Testing
Sample Input 0
STDIN
12 >
4 2
graph_edges = 2 edges
graph_from[] = [1, 1]
graph_to[] = [2, 4]
14

Sample Output 0
graph_nodes = 4 nodes,
3
The values to sum are:
1. Set {1, 2, 4}: ceil(sqrt(3)) = 2
2. Set {3}: ceil(sqrt(1)) = 1
2 + 1 = 3 Show More