Question: Microsoft | Online Assessments | 14th September

Entering edit mode

Avg CTC: 29LPA

Location: Hyderabad and Noida

Software Engineer Roles, apply here: SE Hyderabad and SE Noida

Question 1

A string is called palindrome string if the reverse of the string is also the same as original string. For example 'radar' and 'level' are palindrome but 'microsoft' is not palindrome.

A string S is called an extended palindrome string if the string becomes palindrome after chucking it in chunks of length d, whether d is either 1 or a prime divisor of |S|. For example, 'abcxyzabc' is an extended palindrome string because it can be chucked in chunks of length 3 and become a palindrome string '{abc}{xyz}{abc}'.

The degree of a string is defined as the minimum possible chunk length that can make the string become an extended palindrome string.

Note that, a palindrome string is an extended palindrome string of degree 1.

Write function:

 int solution(string &S);

that, given a string S(1<= |S| <= 100,000), returns the degree of S, or -1 if Sis not an extended palindrome string.

Example 1:

Input:

S: 'radar'

Output:

Explanation:

The string is already a palindrome string which is, by definition, an extended palindrome string of degree 1.

Example 2:

Input:

S: 'abcxyzabc'

Output:

Explanation:

By chunking the string into chunks of length 3 (i.e., '{abc}{xyx}{abc}'), the string can be read exactly the same from left to right or from right to left.

Note that 3 is a prime divisor of the length of the string.

Example 3

Input

S: 'microsoft'

Output:

-1

Question 2

Click here to Practice

An infrastructure consisting of n cities from 1 to n, and m bidirectional roads between them are given. Roads do not intersect apart from at their start and endpoints (they can pass through underground tunnels to avoid collisions).

For each pair of cities directly connected by a road, lets define their network rank as the total number of roads that are connected to either of the two cities.

Write a function, given two arrays starts, ends consisting of m integers each and an integer n, where starts[i] and ends[i] are cities at the two ends of the i-th road, returns the maximal network rank in the whole infrastructure.

Example

Input

1starts = [1, 2, 3, 3]  2ends = [2, 3, 1, 4]  3n = 4

Output

Explanation

The chosen cities may be 2 and 3, and the four roads connected to them are: (2,1), (2,3), (3,1), (3,4).

Question 3

Click here to Practice

Min Deletions To Obtain String in Right Format

Given a string with only characters X and Y. Find the minimum number of characters to remove from the string such that there is no interleaving of character X and Y and all the Xs appear before any Y.

Example 1:

Input:

YXXXYXY

Output:

Explanation:

We can obtain XXXYY by:

Delete first Y --- XXXYXY

Delete last occurrence of X --- XXXYY

Example 2:

Input:

YYXYXX

Output:

Explanation:

We can remove all occurrence of X or Y.

Example 3:

Input:

XXYYYY

Output:

Explanation:

String matches the format required.

Question 4

Click here to Practice

Day of week that is K days later

Given current day as day of the week and an integer K, the task is to find the day of the week after K days.

Example 1:

Input:

day = 'Monday'
K = 3

Output:

Thursday

Example 2:

Input:

day = 'Tuesday'
K = 101

Output:

Friday

Question 5

Given a string composed of a-z and also the letters B and C, where B denotes a backspace and C denotes a caps lock. The first 'C' denotes Caps lock on, then a second 'C' denotes caps lock off. Find the resultant string after resolving the string.

e.g. CrCellBax -- Relax

Explanation:

first C -- caps lock on, therefore till now string becomes R, then second C --- caps lock off.

Till now:

Rell, B --- backspace --- Relax

Question 6

Click here to Practice

Longest Semi-Alternating Substring

Given a string S containing only characters a and b. A substring (contiguous fragment) of S is called a semi-alternating substring if it does not contain three identical consecutive characters. In other words, it does not contain either 'aaa' or 'bbb' substrings. Note that the whole S is its own substring.

Example 1:

Input:

baaabbabbb

Output:

Explanation:

The longest semi-alternating substring is aabbabb

Example 2:

Input:

babba

Output:

Explanation:

Whole S is semi-alternating.

Example 3:

Input:

abaaaa

Output:

Explanation:

The first four letters of S create a semi-alternating substring.

ADD COMMENT • link 3 months ago John 500

Entering edit mode

Solution to Question 1

Extended Palindrome String

The question states that the string is an extended palindrome, if it is a palindrome, when we group the string into chunks of size d, and then check whether the chunks form a palindrome or not. Two chunks are said to be same, if they are exactly the same (string comparison). Also, it is mentioned that d should either be 1 or a prime divisor of the length of the string S.

We can approach this by first finding all the prime divisors of the length of the string, and then checking for each prime divisor and 1. But if the number of prime divisors is very large, then checking for each prime divisor will take time leading to a very large time complexity and therefore a TLE verdict. Hence, we need to make sure that the number of prime divisors is not very large.

So let us multiply the first few prime numbers, and see what can be the maximum number of distinct prime divisors of a number in the given constraints. To find the maximum number of distinct prime divisors, we multiply the smallest prime numbers (because multiplying larger numbers inplace of smaller will always lead to a smaller result) only once and see till how many can we go inside the constraints of the problem.

2 x 3 x 5 x 7 x 11 x 13 x 15 = 450450, which is larger than the constraints of the problem, since the maximum length of the string can be 100000. 2 x 3 x 5 x 7 x 11 x 13 = 30030, which is inside the constraints of the problem. So, at max, the length of the string can have 6 prime divisors. So even if we check for the solution at all prime divisors and 1, the total number of points at which we would have to check is just 7.

Checking for a single length will take only O(n) time complexity, and so the total time complexity will be O(7*n) = O(700000) which will work. We can check for a single prime divisor, whether the string is a palindrome, by iterating over the (number of chunks)/2, i.e. the first half of chunks, and then comparing the letters in that chunk, to their corresponding mirror chunk in the second half of the string.

Also, we can find the prime divisors of the length using a precomputed Sieve of Erastothenes. You can refer this for [Sieve.][1]

Implementation for checking for extended palindrome

int divisor = prime_divisors[i];
int chunks = n/divisor;
bool palindrome = true;
for (int i = 0; i &lt; chunks/2; i++)
{
    for (int j = 0; j &lt; divisor; j++)
    {
        if (s[i * divisor + j] != s[n- (i + 1) * divisor + j])
            palindrome = false;
    }
}
if (palindrome)
{
    cout &lt;&lt; divisor &lt;&lt; '\n';
    return;
}

ADD COMMENT • link

Entering edit mode

Solution to Question 4

Let's make an array of length 7(0-indexed) having all the days of a week in order. Now, if the given day occurs at position i, then the answer will be the day at index (i+k)%7.

Psudocode

string answer(string pres,int k){
    days = {"monday","tuesday","wednesday","thursday","friday","saturday","sunday"}
    int p=0
    for(i in 0,1,2...6){
        if(days[i]==pres) p=i
    }
    print days[(p+k)%7]
}

ADD COMMENT • link 5 months ago Ayush Kumar Shaw 60

Entering edit mode

Question 3

Overview

we are given a string S of length N consisting of only characters X and Y.
Goal is to convert that string in the right format by removing some characters right format is when every X appears before Y for eg: XXX......XXYY.......Y.
In this string consist of the only letter A or only letter B fits in this format.

Solution

After analysing the problem we can note down that we need to find some equilibrium point where most of "X" characters will be placed on the left from this point and most of the "Y" letters on the right.
The simplest solution we could this is to remove all of X or Y but that is something that does not fit the criteria "The minimum number of letters need to be deleted".
So what next? we need to find a point such that if we remove the minimum number of letters X on the left, and the minimum number of letters Y on the right, we get a string in the format XX.....XY.....YY.
Consider an example XXYXYYY here is two such indexes from which we can convert our string in the right format.
Basic Algorithm is simple we go through the whole string and for each item count how many letters X we need to remove from the left and how many letters Y we need to remove from the right and then return the sum of the minimum.
This algo takes (ON2) as we need to rescan the string for each item.
Optimized approach we can use here to Dynamic Programming :

Assume the minimum deletions to format s[0..i] (index 0 to index i in string s) is computed and we keep numbers of deletions for range s[0..i] in variable int min_dels, then the minimum deletions to format s[0..i+1] is: `

    if(s[i+1] == ‘X’) {
     //There are two options: either to include this ‘X’ or exclude it.
      // If ‘X' is included then all Y’s before it should be deleted 
      //   If ‘X' is excluded then increment min_dels for range s[0..i] to one,
      // that is add the ‘A’ which we going to exclude/delete to the number of deleted items
     min_dels[0..i+1] = std::min(num_Ys, min_dels[0..i]+1); // num_Ys is the total number of Ys in s[0..i]
    }
   else {
     // Since Y is at the end there is no need to exclude this Y
          min_dels[0..i+1] = min_dels[0..i];
        }

Here min_del[0..i+1] doest means array but value of int min_del calculated on the range.
Time complexity O(N)

ADD COMMENT • link 5 months ago Akshay Sharma 860

Entering edit mode

Question 2

Overview

We are given N cities and M bidirectional edges between them means that we can go from city A to B and from city B to A.
We are given two arrays start and end both containing M integers means there is an edge from start[i] to end[i] from (i ranges from 0 to m ) and N cities.
Network rank is defined by the total number of roads connected to either both the cities (For each pair of connected cities ).
We have to return the maximal number of network ranks in the whole infrastructure.

prerequisite

Graph theory

Solution

Its a good approach if we visualize the example first

Tables of connected cities should look like :`

 1------2
 2------3
 3------1
 3------4
 Graph :
  1 ----------  2
    \          |
       \       |
          \    |
    4----------3
   It seems that in the problem we just need to count  connected of each pair of given cities
  --&gt;we can see that pairs 2 and 3 have the biggest number of connections to cities and the number of such connections is 4

  Here is a quick snippet for the code :
  // count number of roads to the pair of cities
      for(int i = 0; i &lt; roads_num; ++i) {
       cities[A[i]]++;
       cities[B[i]]++;
       }
      int result = INT_MIN;
      // Find maximum number of roads connected to the pair
        // of cities except the road between these two cities
        // because it was counted twice for each city.
       for(int i = 0; i &lt; roads_num; ++i) {
          result = max(result, cities[A[i]] + cities[B[i]] - 1);
        }

After that, we can return the result.
Time complexity :O(N)

ADD COMMENT • link 5 months ago Akshay Sharma 860

Entering edit mode

Question 6

Overview

We are given a string containing only the alphabet a and b .
A substring (continuous fragment) is said to be semi alternating substring. If it doesn't contain three identical consecutive characters.
we can say that if any substring contains aaa or bbb is not said to be semi alternating substring.
We have to return the maximum length of semi alternating substring.

Solution

We need to return the maximum length of the substring that doesn't contain more than 2 identical consecutive characters.
In order to do this let's make two counters count andresult.
Count will keep the length of the current substring which we processing and the result will keep the length of the longest substring we found.
we can iterate over the given string and count its character in the count.
Whenever we find three identical characters in the string we needed to save the length of the current processing in the result variable.
before saving the length we have to check that is count is greater than the result or not. After that, we can reset the count length of the current substring.
When the whole string is processed return the saved counter.
Time complexity : O(N)

ADD COMMENT • link 5 months ago Akshay Sharma 860