Latest Questions

Amazon Prime Video is developing a new feature called "Segmentify." This feature applies to a video with n (even) visual frames, where each frame is represented by a binary character in the array `frames`. In this format, a "0" represents a black pixel, and a "1" represents a white pixel.

Due to factors like lighting and camera angles, some frames may need horizontal or vertical flips (changing "0"s to "1"s and vice versa) to create consistent visuals. The objective is to divide the video into subsegments so that all frames in a subsegment are visually identical (i.e., the frames in a subsegment are either all "0"s or all "1"s). Additionally, each subsegment should have an even length.

The goal is to accomplish this segmentation with two criteria in mind:
1. Minimize the number of flips required to form valid segments — let this be denoted by B.
2. Among all configurations requiring B flips, minimize the total number of subsegments.

Given the binary string `frames`, determine the minimum number of such subsegments that meet the criteria.

Note: A subsegment is a segment that can be derived from another segment by deleting some elements without changing the order of the remaining elements.

Example:
`frames = "1110011000"`
One set of optimal moves is as follows:
- Flip the first 0 to 1 → "1111011000"
- Flip the next 0 to 1 → "1111111000"
- Flip the final 0 to 1 → "1111111100"

All resulting subsegments (11111111 and 00) are of even length. So, the minimum number of subsegments is 2 with a total of 3 flips. Hence, the answer is 2.

Another example:
`frames = "110011"`
In this case, the string already consists of groups of "0"s and "1"s that have even lengths. Therefore, no flipping is necessary, and the string can be divided into 3 even-length subsegments without modification. Hence, the answer is 3.

Function Description:
Complete the function `getminSubsegments` in the editor below.

`getminSubsegments` has the following parameter:
- string `frames`: the frames of the video as a binary string.

Returns:
- int: the minimum number of subsegments.

Constraints:
- 2 ≤ n ≤ 10^5, where n is even.
- It is guaranteed that the string `frames` only consists of '0's and '1's.

Sample Input:
`100110`

Sample Output:
2

Explanation:
Flip the first 0 to 1, resulting in "110110". All segments can then be grouped into even-length parts. Show More

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

Given a string composed of lowercase letters within the ASCII range 'a'-'z', determine the number of substrings that consist solely of vowels, where each vowel appears at least once. The vowels are ['a', 'e', 'i', 'o', 'u']. A substring is defined as a contiguous sequence of characters within the string.

Example
s = 'aeioaexaaeuiou'

There is a substring to the left that is made of vowel s, 'aeioee', which is followed by an 'x'. Since 'x' is not a vowel, it cannot be included in the substring. This substring does not contain all of the vowels, so it is not a qualifying substring. Moving to the right, there are four substrings that do qualify: 'aaeuiou', 'aaeuio', 'aeuiou', and 'aeuio'.

Function Description
Complete the function vowelSubstring in the editor with the following parameter:
- string s: a string

Returns
- int: the number of substrings that consist of vowels only ('a', 'e', 'i', 'o', 'u') where every vowel appears at least once

Constraints
- 1 ≤ size_of(s) ≤ 10⁵
- s[i] is in the range ASCII 'a'-'z' (where 0 ≤ i < size_of(s))

Input Format For Custom Testing

Sample Case 0

Sample Input For Custom Testing
STDIN
aaeiouxa

Sample Output
2

Explanation
s = "aaeiouxa"
There are two qualifying substrings:
s[0:6] = "aaeiou"
s[1:6] = "aeiou" 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

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