Microsoft | OA Coding Questions and Solutions | Set - 3| 2022

Question

Bonus : Best Image2Pdf feature is here : https://www.desiqna.in/image2pdf/

All past online assesments of Microsoft  can be found using the tag "microsoft_oa" in the search bar.

Here is the link : https://www.desiqna.in/tag/microsoft_oa

 

Answer 1

Microsoft Online Assessment (OA) - 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: 7

Explanation:

the longest semi-alternating substring is aabbabb

Example 2:

Input: babba

Output: 5

Explanation:

Whole S is semi-alternating.

Example 3:

Input: abaaaa

Output: 4

Explanation:

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

Answer 2

An infrastructure consisting of n cities from l 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, let’s 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:

14

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).