Latest Questions | Page 2

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

Minimum Time to Complete Tasks with Dependencies

You are given N tasks numbered from 0 to N-1. Each task takes 1 unit of time to complete. Some tasks depend on the completion of other tasks and can only start once all their prerequisite tasks are finished. You are given a list of dependency pairs (a, b), meaning task a must be completed before task b can start.

You have unlimited resources a nd can run multiple tasks in parallel as long as their dependencies are satisfied. Your task is to find the minimum time required to complete all tasks.

Function Description:
Implement the function minimumTimeToCompleteTasks with parameters:
- N: integer, total number of tasks
- M: integer, number of dependency pairs
- dependencies: list of pairs (a, b) where task a must be completed before task b

Return:
- int: minimum time to complete all tasks

Constraints:
- 1 ≤ N ≤ 10^5
- 0 ≤ M ≤ 10^5
- 0 ≤ a, b < N

Sample Input:
5 4
0 1
1 2
0 3
3 4

Sample Output:
3

Explanation:
- Task 0 starts at time 1
- Tasks 1 and 3 depend on task 0, so they start at time 2
- Task 2 depends on 1, and task 4 depends on 3, so they start at time 3
Thus, the minimum time to complete all tasks is 3. Show More

Rotten Oranges

You are given an N x M grid representing a storage area for oranges. Each cell in the grid can be:
- 0: empty cell
- 1: fresh orange
- 2: rotten orange

A rotten orange at position (i, j) spreads rot to its adjacent fresh oranges (up, down, left, right) every minute. The rotting process happens simultaneously for all rotten oranges at each time step.

Your task i s to determine the minimum time required for all fresh oranges to become rotten. If at least one fresh orange cannot rot, return -1.

Function Description:
Implement the function minTimeToRottenOranges with parameters:
- int N: number of rows in the grid
- int M: number of columns in the grid
- int[][] grid: a 2D array representing the orange states

Returns:
- int: minimum minutes for all fresh oranges to rot, or -1 if impossible. Show More

Implement a prototype for a text editor application with the following functionalities:

Command
Actions:
- ["Insert", s]: Insert the string s at the current cursor position. The cursor moves right by the length of s.
- ["Left", x]: Move the cursor x positions to the left, but not past the start of the string.
- ["Right", x]: Move the cursor x positions to the right, but not past the end of the string.
- ["Backspace", x]: Remove x characters immediately to the left of the cursor, moving the cursor left accordingly.
- ["Delete", x]: Remove x characters immediately to the right of the cursor. Cursor position does not change.
- ["Print", x]: If the cursor is at position m, print all characters from index m - x to m + x (inclusive), adjusting for string boundaries.

Given a 2D array of commands of size n x 2, perform the operations starting from an empty string and cursor at position 0. For each "Print" command, record the resulting substring. Return all printed substrings as an array, in the order they are printed.

Note: The second argument in commands is always a string and should be converted to integer where applicable.

Function Description
Complete the function getPrintedStrings with parameter:
commands[n][2]: list of commands to execute.

Returns
string[]: list of printed strings from "Print" commands.

Constraints
- 1 ≤ n ≤ 5000
- Sum of lengths of all inserted strings ≤ 5 * 10^3
- First inserted string length ≤ 100, subsequent insertions ≤ 25
- All strings contain only lowercase English letters.

Input Format For Custom Testing
- First line: integer n, number of commands
- Second line: integer 2
- Next n lines: two space-separated strings commands[i][0] and commands[i][1]

Sample Case 0

Input:
7
2
Insert addthis
Print 5
Left 4
Right 2
Backspace 1
Delete 1
Print 10

Output:
dthis
addts

Explanation:
1. Insert "addthis": string = "addthis", cursor = 7
2. Print 5: substring from 7 - 5 = 2 to 7 + 5 = 12 → "dthis"
3. Left 4: cursor moves from 7 to 3
4. Right 2: cursor moves from 3 to 5
5. Backspace 1: remove 1 char left of cursor → string = "addtis", cursor = 4
6. Delete 1: remove 1 char right of cursor → string = "addts", cursor = 4
7. Print 10: substring from max(0, 4 - 10) = 0 to min(len, 4 + 10) = 9 → "addts"

Sample Case 1

Input:
7
2
Insert present
Print 5
Left 4
Insert test
Print 8
Delete 4
Print 7

Output:
esent
pretestsent
pretest

Explanation:
1. Insert "present": string = "present", cursor = 7
2. Print 5: substring 7 - 5 = 2 to 7 + 5 = 12 → "esent"
3. Left 4: cursor = 3
4. Insert "test": string = "pretestsent", cursor = 7
5. Print 8: substring 7 - 8 = -1 to 7 + 8 = 15 → "pretestsent"
6. Delete 4: remove 4 chars right of cursor → string = "pretest", cursor = 7
7. Print 7: substring max(0, 7 - 7) = 0 to min(len, 7 + 7) = 14 → "pretest" Show More

Given a string, determine how many different substrings exist that have no repeating characters. Two substrings are considered different if they have different start or end indices.

Example
s = "abac"

The substrings with no repeating characters are "a", "b", "a", "c", "ab", "ba", "ac", and "bac".
Note that "aba" and "abac" do not qualify because the character 'a' is repeated in them. Also, "a" and "a" both qualify because their start indices are different: s[0] and s[2]. There are 8 such substrings.

Function Description
Complete the function findSubstrings in the editor with the following parameter:
string s: the given string

Returns
int: the number of substrings in s that have no repeating characters

Constraints
- 1 ≤ length of s ≤ 10⁵
- s consists of only lowercase English letters, ascii['a'-'z']

Input Format For Custom Testing
The only line of input contains a string, s.

Sample Case 0

Sample Input For Custom Testing
bcada

Sample Output
12

Explanation
There are 12 substrings in "bcada" that have no repeating characters: "b", "c", "a", "d", "a", "bc", "ca", "ad", "da", "bca", "cad", and "bcad"

Sample Case 1

Sample Input For Custom Testing
abcd

Sample Output
10

Explanation
There are 10 substrings in "abcd" that have no repeating characters: "a", "b", "c", "d", "ab", "bc", "cd", "abc", "bcd", and "abcd" Show More

A coding competition organized to recruit software developers includes a problem involving the bitwise-OR operation. The score of a sequence is defined as the result of the bitwise-OR operation on its elements. Given an array arr of length n, identify all possible distinct scores that can be obtained by selecting any strictly increasing subsequence from the array. Return the results sorted in asce nding order.

Note: A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without altering the order of the remaining elements.

Example

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

There are n = 4 elements in the array. The strictly increasing subsequences that can be chosen to have distinct score values are:

- Empty subsequence; score = 0
- [1]; score = 1
- [2]; score = 2
- [4]; score = 4
- [2, 4]; score = 6

There are no other strictly increasing subsequences that yield a different score value. So, the answer is [0, 1, 2, 4, 6], which is sorted in ascending order.

Function Description

Complete the function getDistinctScoreValues in the editor with the following parameter:
int arr[n]: an array of integers

Returns
int[]: all possible distinct score values, sorted ascending

Constraints
- 1 ≤ n ≤ 10⁴
- 1 ≤ arr[i] < 1024

Input Format For Custom Testing

Sample Case 0

Sample Input For Custom Testing

STDIN
arr[] size, n = 4
arr = [3, 2, 4, 6]

4

Sample Output
[0, 2, 3, 4, 6, 7]

Explanation

Some strictly increasing subsequences that have distinct score values are:

- Empty subsequence; score = 0
- [2]; score = 2
- [3]; score = 3
- [4]; score = 4
- [2, 4]; score = 6
- [3, 4]; score = 7 Show More

Java: Social Network Interaction System

Design and implement a social media platform where users can follow and unfollow each other, post content, and receive notifications about new posts from the users they follow. You should print a message when a new user is added, when a user follows or unfollows another user, and when a user posts or receives a notification.

Complete the following meth ods:

1. User class:
- update(String message, User followee): void, should print: "{UserName} received notification: {followeeName} posted: {message}."
- addFollowers(User user): void
- removeFollowers(User user): void
- notifyFollowers(String message): void
- post(String content): void, should print: "{UserName} posted: \"{content}\""
- follow(User user): void
- unfollow(User user): void

2. Platform class:
- addUser(Integer id, String name): void, should print: "{UserName} added successfully."
- follow(Integer followerId, Integer followeeId): void, should print: "{FollowerName} is now following {FolloweeName}."
- unfollow(Integer followerId, Integer followeeId): void, should print: "{FollowerName} has unfollowed {FolloweeName}."
- post(Integer userId, String content): void

Input Format: You are not responsible for reading any input from stdin.

Output Format: You should print a message when a new user is added, when a user follows or unfollows another user, and when a user posts or receives a notification.

Input Format for Custom Testing:

Sample Case 0

Sample Input 0:
8
Add User 0 Alexander
Add User 1 Isabella
Add User 2 Emma
Follow 1 0
Post 0 Hiking in the mountains.
Follow 2 0
Post 0 Enjoying a beautiful day!
Unfollow 1 0

Sample Output 0:
Alexander added successfully.
Isabella added successfully.
Emma added successfully.
Isabella is now following Alexander.
Alexander posted: "Hiking in the mountains.".
Isabella received notification: Alexander posted: "Hiking in the mountains.".
Emma is now following Alexander.
Alexander posted: "Enjoying a beautiful day!".
Isabella received notification: Alexander posted: "Enjoying a beautiful day!".
Emma received notification: Alexander posted: "Enjoying a beautiful day!".
Isabella has unfollowed Alexander. Show More

You've been asked to program a bot for a popular bank that will automate the management of incoming requests. Every request has its own timestamp in seconds, and it is guaranteed that all requests come sequentially, i.e. the timestamp is strictly increasing. There are two types of incoming requests:

. deposit <timestamp> <holder_id> <amount> - request to deposit <amount> amount of money in the <holder_id> account;

. withdraw <timestamp> <holder_id> <amount> - request to withdraw <amount> amount of money from the <holder_id> account. As a bonus, the bank also provides a cashback policy - 2% of the withdrawn amount rounded down to the nearest integer will be returned to the account exactly 24 hours after the request timestamp. If the cashback and deposit/withdrawal happen at the same timestamp, assume cashback happens earlier.

Your system should also handle invalid requests. There are two types of invalid requests:

. invalid account number;

. withdrawal of a larger amount of money than is currently available.

For the given list of initial balances and requests, return the state of balances straight after the last request has been processed, or an array of a single element [-<request_id>] (please note the minus sign), where <request_id> is the 1-based index of the first invalid request. Note that cashback requests which haven't happened before the last request timestamp should be ignored.

Example

Example 1: For balances = [1000, 1500] and requests = ["withdraw 1613327630 2 480", "withdraw 1613327644 2 800", "withdraw 1614105244 1 100", "deposit 1614108844 2 200", "withdraw 1614108845 2 150"], the output should be solution(balances, requests) = [900, 295].

Explanation: Here are the states of balances after each request:

. Initially: [1000, 1500];
. "withdraw 1613327630 2 480": [1000, 1020];
. "withdraw 1613327644 2 800": [1000, 220];
. At 1613414030 the 2nd account will receive the cashback of 480 * 0.02 = 9.6, which is rounded down to 9: [1000, 229];
. At 1613414044 the 2nd account will receive the cashback of 800 * 0.02 = 16: [1000, 245];
. "withdraw 1614105244 1 100": [900, 245];
. At 1614191644 the 1st account will receive cashback of 2: [902, 245];
. "deposit 1614108844 2 200": [902, 445];
. "withdraw 1614108845 2 150": [902, 295];
. Final state: [902, 295].

Example 2: For balances = [20, 1000, 500, 40, 90] and requests = ["deposit 1613327630 3 400", "withdraw 1613327635 1 20", "withdraw 1613327651 1 50", "deposit 1613327655 1 50"], the output should be solution(balances, requests) = [-3].

Explanation: Here are the states of balances after each request:

. Initially: [20, 1000, 500, 40, 90];
. "deposit 1613327630 3 400": [20, 1000, 900, 40, 90];
. "withdraw 1613327635 1 20": [0, 1000, 900, 40, 90];
. "withdraw 1613327651 1 50": it is not possible to withdraw 50 from the 1st account, so the request is invalid;
. The rest of the requests are not processed.

Input/Output

. [execution time limit] 4 seconds (py3)
. [memory limit] 1 GB
. [input] array.integer balances: Array of integers, where balances[i] is the amount of money in the (i + 1)th account.

Guaranteed constraints: 1 ≤ balances.length < 100 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