Question: Uber OA | 2023

Entering edit mode

Question 1

Given two arrays of integers a and b of the same length,

find the number of pairs (i, j) such that i≤ j and a[i] - b[j] = a[j] - b[i].

Example

For a = [2, -2, 5, 3] and b = [1, 5, -1, 1],

the output should be solution(a, b) =6.

For (i, j) = (0, 0) equality holds: a[0]-b[0] = 2-1=1 and a[0] -b[0] = 2 - 1 = 1,

• For (i, j) =(0, 1) equality holds: a[0]- b[1] 25-3 and a[1] b[0] = (-2)- 1= -3,

For (i, j) = (0, 2) equality doesn't hold: a[0]- b[2] = 2 - (-1) =3 and a[2]-b[0] = 5 -1 = 4

。 For (i, j)=(0,3) equality doesn't hold: a[0] - b[3]=2-1=1 and a[3] - b[0] = 3 - 1 =2

。 For (i, j) = (1, 1) equality holds: a[1] -

Question 2

Given a string of lowercase English letters s. your task is to rearrange its letters by pairing them together according to the following rule: first letter with the last one, second letter with the second-to- last one, etc. More formally, if s= c1c2c3...Cn-2Cn-1Cn (where ci is the ith letter of s), then the letters should be arranged into C1CnC2Cn-1C3Cn-2... If s contains an odd number of letters, the middle letter should not be paired with any other letters, but placed at the end of the output string instead.

Note: You are not expected to provide the most optimal solution, but a solution with time complexity not worse than o(s.length) will fit within the execution time limit

Question 3

You are given a rectangular matrix of integers board and a square matrix of characters

pattern. The elements of board are digits (integers between 0 and 9). The characters pattern are either digits or lowercase English letters.

Your task is to find a submatrix in board which matches the pattern.

A submatrix of integers submatrix matches a matrix of characters pattern if:

The matrices have identical dimensions.

• If any character of pattern is a digit, then the corresponding integer of submatrix in the same position should be equal to that digit.

If any character of pattern is a letter, then all the occurrences of that letter in pattern should correspond to the same digit in submatrix.

For any two distinct letters of pattern, their corresponding digits should be different.

If there is a submatrix of board which matches the pattern, return an array of two integers representing the row and the column numbers (0-indexed) of the upper-left corner of the submatrix. If there are more than one such submatrices, return the coordinates of the submatrix with the lowest row index, and in case there is still a tie, return the coordinates of the submatrix with the lowest column index. If there are no suitable answers, return [-1, -1].

Note: You are not expected to provide the most optimal solution, but a solution with time

complexity not worse than o(board. length board[0].length pattern. length") will fit within the execution time limit.

Question 4

You are given a binary array state consisting of integers 0 and 1. You are also given operations an array of strings, each representing an operation of one of two types:

"L" find the smallest index i, for which state[i] 0, and set state[i]= 1..

If there is no such index, do nothing.

"C{index}" -set state[index] = 0.

This operation does not depend on the previous value of state[index]

It is guaranteed that index is a valid 0-based index of state (ie: index < state.length).

Given state and operations, your task is to return the binary string of state array after al the operations have been applied.

Example

For state [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] and operations

["L", "L", "co", "L", "C3"], the output should be solution (state, operations) ="1100000000".

Expand to see the example video.

[ L L C0 L C3 ]

set the leftmost 0 bit to 1

Question 5

You are given an array of integers an of size n and an integer K

You need to select the max number of integers in the array such that for every subsegment a[t], a[t+1].... a(t). containing strictly more than one element der), either of the following should satisfy

1. At least one element on this subsegment is not selected

2. a[t] + a[1+t] +.... + a[t] >= k*(i-t+1)

What is the maximum number of elements that can be selected

Constraints:

1 < =n <= 10^5

-10^5 <= arr[i] <= 10^5

-10^5 <= k <= 10^5

[execution time limit] 2 seconds (cpp)

[memory limit] 1 GB

[input] array.integer arr

[input] integer k

[output] integer

Question 6

Bhagya is a warehouse worker, who likes to place with boxes on the rack in a strange way.

He has n racks and the i-th rack has racks[i] blocks. His game consists of two steps:

1. he chooses an arbitrary rack i

2. he tries to move all boxes from the i-th rack to other racks.

If he can make the same number of boxes in each of n-1 other racks then he will be happy, otherwise, will be sad. Note that Bhagya can only move the boxes from the chosen rack to the other racks; he cannot move boxes from the other racks.

You don't want to make Bhagya sad, so you decided to put several extra boxes into some racks in such a way that no matter which rack he chooses he won't be sad. What is the minimum number of extra blocks you need to put?

Constraints:

1 <= n <= 10^5

1 <= racks[i] <= 10^9; 1 <= i<=n

Input

racks [2, 2, 3, 2)

Output

0

Explanation:

you don't need to put any extra blocks, since no matter which racks he chooses, he can always make other racks equal.

[execution time limit] 2 seconds (cpp)

[memory limit] 1 GB

[input] array.integer racks

[output] integer

Question 7

A password is called strong when it can satisfy below 3 rules:

Size of the password is always M (Integer 1- M<= 10^5)

Every element of the strong password string is a number between 0 and 9

. The strong password shouldn't be a subsequence of the password database P ( string of size _<10^5)

. There are 2 strings UPPER and LOWER each of size M, a strong password should be such that the ith element of strong password should always lie between LOWER[i] and UPPER[j], inclusive

Given M.P.LOWER UPPER you have to verify whether such strong password is possible

you will be given with numberOfTestCases number of tests and you are expected to return a int array of size numberOfTestCases with either 1 for "yes we can create such strong password" or 0 for "No, its not possible to create such password"

For second test case passwordDB contains "1234" UPPER is "4321", LOWER is "4321". Now only possible string according to last rule is "4321" and clearly is not a subsequence of "1234". So there exists such strong password, return value for this test-case is 1

[execution time limit] 0.5 seconds (cpp)

[memory limit] 1 GB

[input] integer numberOfTestCases

numberOfTestCases represents number of test-cases for you to verify if a password exists for a test case or not

1< numberOfTestCases<=10^5

[input] array.string passwordDB

passwordDB is array of string of size numberOfTestCases where in ith element of passwordDB represents P for ith test case

[input] array.integer passwordSize

passwordSize is array of integers of size numberOfTestCases where in ith element of passwordSize represents M for ith test case and always lies between 0 and 9

For all t 1 <<=i= numberOfTestCases,1 <= Sum of (len(passwordDB[i])'passwordSize[i]) =<10^5 and len(passwordDB[i]) >=passwordSize[i]

[input] array.string upperPasswords

upperPasswords is array of strings of size numberOfTestCases where in ith element of

upper represents UPPER string for ith test case

[input] array.string lowerPasswords

lowerPasswords is array of strings of size numberOfTestCases where in ith element of

upper represents LOWER string for ith test case

for all 1<t<=numberOfTestCases, len(upperPasswords[1])=len(lowerPasswords[t]

) = passwordSize[t]

for all 1<i<=len(lowerPasswords[t]) lowerPasswords[t][i]<=upperPasswords[t][i].

0<-upperPasswords[t][i]<=9,

0<=lowerPasswords[t][i]<=9

[output] array.integer

Array of integer of size numberOfTestcases where every element of array should either be 1 or 0. ith element of the array should represent whether such a password exists or not for ith test case

not possible to create such password"

Example:

Sample Input:

numberOfTestCases: 2
passwordDB: ["459","1234"]
passwordSize: [2,4]
upperPasswords: ["59", "4321"] lowerPasswords: ["49", "4321"]


Expected Output: [0, 1]

For first test case passwordDB contains "459", UPPER is "59", LOWER is "49" and so, as given in constraints required passwordSize is 2 same as length of string "59", "49". Now all the possible string that are possible according to last rule are only "49",59" and they both are substrings of "459". So there exists no such password, return value for this test-case is 0

For second test case passwordDB contains "1234", UPPER is "4321", LOWER is "4321". Now only possible string according to last rule is "4321" and clearly is not a subsequence of "1234". So there

exists such strong password, return value for this