Company: MICROSOFT

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

A foundry in Hackerland makes an alloy out of n different metals. In the manufacturing of an alloy, the composition of each metal is fixed, where the required quantity of the i-th metal in preparing 1 unit of the alloy is denoted by composition[i]. The company already has stock[i] units of metal i in their stock. The company has a budget to purchase any of the metals if needed. The cost of the i-t h metal is cost[i] per unit. Find the maximum units of alloys the company can produce by using available stock plus what they can purchase within their budget.

Note: Their supplier has an infinite supply of all metal types.

Example:
There are n = 2 metal types.
- their required composition = [1, 2]
- their available stock = [0, 1]
- their purchase cost = [1, 1]
- their budget = 3

A maximum of 1 unit of alloy can be produced.
- The cost for 1 unit: required quantity = [1, 2], stock = [0, 1], extra metal requirements = [1, 1], cost = (1 x 1) + (1 x 1) = 2, which is within the budget.
- The cost for 2 units: required quantity = [2, 4], stock = [0, 1], extra metal requirements = [2, 3], cost = (2 x 1) + (3 x 1) = 5, which is beyond the budget.

The answer is 1.

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

findMaximumAlloyUnits has the following parameters:
int composition[n]: the composition of metals in 1 unit of alloy
int stock[n]: the units of metals type i that the company has in stock
int cost[n]: the costs of metals type i.
int budget: the total money the company can spend

Returns:
int: the maximum unit of alloys that can be produced

Constraints:
1 ≤ n ≤ 10^5
1 ≤ budget ≤ 10^9
1 ≤ composition[i] ≤ 10^5
1 ≤ stock[i] ≤ 10^5
1 ≤ cost[i] ≤ 10^5
composition[i] * cost[i] ≤ 2 * 10^9

Input Format For Custom Testing:
The first line contains an integer, n, the number of elements in array composition.
Each line i of the next n subsequent lines (where 0 ≤ i < n) contains an integer, composition[i].
The next line contains an integer, n, the number of elements in array stock.
Each line i of the next n subsequent lines (where 0 ≤ i < n) contains an integer, stock[i].
The next line contains an integer, n, the number of elements in array cost.
Each line i of the next n subsequent lines (where 0 ≤ i < n) contains an integer, cost[i].
The next line contains an integer, budget. Show More

An array of integers is almost sorted if at most one element can be deleted from it to make it perfectly sorted, ascending. For example, arrays [2, 1, 7], [13], [9, 2], and [1, 5, 6] are almost sorted because they have 0 or 1 elements out of place. The arrays [4, 2, 1] and [1, 2, 6, 4, 3] are not because they have more than one element out of place. Given an array of n unique integers, determine t he minimum number of elements to remove so that it becomes almost sorted.

Example:
arr = [3, 4, 2, 5, 1]
Remove 2 to get arr' = [3, 4, 5, 1] or remove 1 to get arr' = [3, 4, 2, 5], both of which are almost sorted. The minimum number of elements that must be removed in this case is 1.

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

minDeletions has the following parameter(s):
int arr[n]: an unsorted array of integers
Returns:
int: the minimum number of items that must be deleted to create an almost sorted array.

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

Sample Case 0:
Sample Input:
arr[] size n = 5
arr = [1, 2, 6, 4, 3]

Sample Output:
1

Explanation:
One can remove for example 4 to get [1, 2, 6, 3], which is almost sorted. Other choices are to remove 6 or 3. The minimum number of elements that have to be removed in this case is 1. Show More

The binary cardinality of a number is the count of 1's in its binary representation. For example, the decimal number 10 corresponds to the binary number 1010, which has a binary cardinality of 2 because it contains two 1's. Given an array of decimal integers, sort it by: 1. Increasing binary cardinality (primary criterion) 2. Increasing decimal value (secondary criterion, when cardinalities are eq ual) Return the sorted array.

Example n=4 nums = [1, 2, 3, 4] 110 → 12, so 1's binary cardinality is 1. 210 → 102, so 2's binary cardinality is 1. 310 → 112, so 3's binary cardinality is 2. 410 → 1002, so 4's binary cardinality is 1. The sorted elements with binary cardinality of 1 are [1, 2, 4]. The array to return is [1, 2, 4, 3].

Function Description: Complete the function cardinalitySort in the editor with the following parameter(s): int nums[n]: an array of decimal integers Returns int[n]: the integer array nums sorted ascending, by binary cardinality, then by decimal value for ties.

Constraints: 1 ≤ n ≤ 10^5, 1 ≤ nums[i] ≤ 10^6

STDIN Input Format for Custom Testing: Sample Case 0

Sample Input 0: nums size n = 5 nums = [31, 15, 7, 3, 2] Sample Output 0: [2, 3, 7, 15, 31]

Explanation 0: 3110 → 11111 so its binary cardinality is 5. 1510 → 1111 so its binary cardinality is 4. 710 → 111 so its binary cardinality is 3. 310 → 11 so its binary cardinality is 2. 210 → 10 so its binary cardinality is 1. Sort the array by ascending binary cardinality and then by ascending decimal value: nums sorted = [2, 3, 7, 15, 31].

Sample Case 1: Sample Input 1: nums size n = 1 nums = [3] Sample Output 1: [3]

Explanation 1: The binary cardinality of 310 → 11 is 2. The function returns nums sorted = [3]. Show More

Coding Wars
There are 'N' coders standing in a line, where i denotes the ith position of a coder with a rating of Ri. All ratings are distinct.
You have to form a team of 3 from amongst them with the condition:
Any three coders with positions (i, j, k) and ratings ("Ri< Rj< Rk" or "Ri > Rj > Rk") and(1 <= i < j < k <= N)
You have to find out how many such teams exist (1 coder can be part of m ultiple teams).
Input:
N = 5
Ratings = [5, 2, 3, 1, 4]
Output:
3
(5, 2, 1), (5, 3, 1), (2, 3, 4) Show More

String Encoding
Encode a given string by collapsing consecutive instances of a single character into two pieces of information: the number of instances and the character. Note that even single characters should be run-length encoded. If the string is empty, return an empty string. Your implementation should work on all alphanumeric characters.
Function Description
Complete the function collapse lnput which takes a string input as a parameter and returns the compressed string.
Sample Input:
GGGGGrrrrrrrrrrrrttt
Sample Output:
5G14r3t
Explanation:
There are 5 'G' characters, then there are 14 'r's, then there is 1 't'. Show More

Break a Palindrome
A palindrome reads the same forwards and backwards, like "mom". Modify a palindrome by changing exactly one character to another character within the ASCII range [a-z].
The goal is to ensure the new string fulfills the following criteria:
1.It is not a palindrome.
2.It is alphabetically lower than the original palindrome.
3.It is the smallest possible string alphabetically that can be obtained by changing just one character.
Return the new string, or "IMPOSSIBLE" if it is not feasible to create such a string.
Example:
palindromeStr = 'aaabbaaa'
* Possible strings lower alphabetically than 'aaabbaaa' after one change are ['aaaabaaa', 'aaabaaaa'].
* 'aaaabaaa' is not a palindrome and is the lowest string that can be created from palindromeStr.
Function Description
Complete the function breakPalindrome in the editor with the following parameter:
string palindromeStr: the original string
Returns:
string: the resulting string, or "IMPOSSIBLE" if one cannot be formed. Show More

Vaccination Drive
In order to curb the spread of the novel COVID-19 virus, the citizens of Hackerland need to be vaccinated on priority. There are center_nodes vaccination centers in Hackerland, where each center has a status denoted by status[i]:
• Centers with a shortage of vaccines have status 1.
• Those with sufficient vaccines have status 2.
• Those with a surplus have status 3.

Vac cines can be transferred from centers with a surplus to centers with a deficit. There is a network of bidirectional roads between centers where the ith road is between cities center_from[i] and center_to[i]. Each road takes 1 unit of time to traverse. Find the minimum time in which all deficient centers can receive a supply of vaccines from some surplus center.

Note: • Surplus centers have an inexhaustible supply of vaccines.
• Multiple surplus centers can ship their surplus simultaneously.
• Multiple deliveries from a single surplus center can leave simultaneously.
• Vaccines are only shipped from centers with status 3 to centers with status 1. Status 2 centers do nothing. Show More