Microsoft | Software Engineer | University Grad 2024 | India

• What is the optimal solution to the two questions given below?

Question 1 :

The uniqueness of an array of integers is defined as the number of distinct elements present. For example, the uniqueness of [1, 5, 2, 1, 3, 5] is 4, element values 1, 2, 3, and 5.

For an array arr of n integers, the uniqueness values of its subarrays is generated and stored in another array, call it subarray_uniqueness. Find the median of the generated array subarray_uniqueness.

Notes :- 1. The median of a list is defined as the middle value of the list when it is sorted in non-decreasing order. If there are multiple choices for median, the smaller of the two values is taken. For example, the median of [1, 5, 8] is 5, and of [2, 3, 7, 11] is 3.

2. A subarray is a contiguous part of the array. For example, [1, 2, 3] is a subarray of [6, 1, 2, 3, 5] but [6, 2] is not.

Example 1: There are n = 3 elements in arr = [1, 2, 1]. The subarrays along with their uniqueness values are: [1]: uniqueness = 1 [1, 2] : uniqueness = 2 [1,2, 1]: uniqueness = 2 [2] : uniqueness = 1 [2, 1]: uniqueness = 2 [1] : uniqueness = 1

The subarray_uniqueness array is [1, 2, 2, 1, 2, 1]. After sorting, the array is [1, 1, 1, 2, 2, 2]. The choice is between the two bold values. Return the minimum of the two,1. Output : 1

Example 2 : arr = [1, 2, 3] [1]: uniqueness = 1 [1, 2] : uniqueness = 2 [1,2, 3]: uniqueness = 3 [2] : uniqueness = 1 [2, 3]: uniqueness = 2 [3] : uniqueness = 1

After sorting, the array is [1, 1, 1, 2, 2, 3]. Output : 1.

• Constraints : 1 <= n <= 1e5. 1 <= arr[i] <= 1e5

Question 2 :

A string s, is similar to another string t, if it possible to swap two adjacent characters at most once in s to turn it into t. Given a keyword string named key, find how many substrings of text are similar to key.

Example 1 : key : "moon" text : "monomon"

Explanation : * Consider the first four characters in text. i.e "mono". Swap the last two characters to match the keyword "moon". * The last four characters in the text are "omon". Swap the first two characters to match the keyword.

Thus,there are 2 substrings of "monomon" that are similar to "moon". Note, that no other substring is similar to the given key.

Example 2 : key : "aaa" text : "aaaa"

Output : 2. There are 2 substrings of "aaaa" that are similar to "aaa" are: aaaa aaaa

Example 3 : key : "xxy" text : "zxxyxyx"

Output : 3.

• Constraints :

1. key and text will consist solely of lowercase english letters.
2. 1 <= | key | <= | text | <= 50, Where | s | denotes the length of a string s.