Microsoft Online Assessment Questions
6. Longest Substring Without Two Contiguous Occurrences of Letter
Given a string Given a string s containing only a and b, find longest substring of s such that s does not contain more than two contiguous occurrences of a and b
Example 1:
Input: aabbaaaaabb
Output: aabbaa
Example 2:
Input: aabbaabbaabbaaa
Output: aabbaabbaabbaa
Solution
Program C++:
Approach:
Scan the string from left to right
drop all sequences of the same chars longer than 2;
count length of sequences of different chars;
save length of the longest sequence.
Algorithm:
We should have a counter of the same chars and index which points to the last two chars of this sequence.
Lets call them “count” and “start”
And we should have two variable where we will save length of the longest sequence of different chars
and index which points to the beginning of this sequence.
Lets call them “max_length” and “start_ml”
So the algorithm in general:
Scan the string from left to right:
Take next char of the string;
If next char is the same as the previous one increase counter of the same chars “count”;
1.1 If next char is different drop counter of the same chars “count” to 1;
If number of previous the same chars is:
2.1 More than 2. Move pointer to the beginning of the current sequence of different chars “start” to
the previous char before the current one, to keep only two the same chars at the beginning of the sequence.
drop counter of the same chars “count” to 2.
2.2. Less or equal 2. Check if current sequence of different chars is longer than current maximum.
If yes – update maximum to the current length. Save pointer to the beginning of the new longest sequence.
Go to phase 0;
#include <iostream>
#include <vector>
using namespace std;
string solution(const string &s) {
int s_size = s.size();
// start position and length of the longest sequence
// which doesn't contain 3 contiguous occurrences of a and b
int start_ml = 0, max_length = 0;
int start = 0; // start of current processing string of the same letters.
int count = 1; // length of current processing string of the same letters.
for (int i = 1; i < s_size; ++i) {
if (s[i] == s[i - 1]) {
// if we met two the same letters increase the counter of the same letters
count++;
}
else {
// if next letter is different drop the counter to 1
count = 1;
}
if (count <= 2) {
// if the sequence of different letters continuing, set it's current length as
// max_length if it is bigger than current max_length
// "i - start + 1" is length of the current processed sequence
if (i - start + 1 > max_length) {
max_length = i - start + 1;
start_ml = start;
}
}
else {
// if the sequence of the same letters continuing,
// move the pointer to points to the last two chars of this sequence
// drop the count to 2
start = i - 1;
count = 2;
}
}
return s.substr(start_ml, max_length);
}
int main() {
cout << "Result: " << solution("aabbaabbaabbaa") << " Expected: aabbaabbaabbaa" << endl;
cout << "Result: " << solution("aabbaaaaabb") << " Expected: aabbaa" << endl;
return 0;
}7. String Without 3 Identical Consecutive Letters
String Without 3 Identical Consecutive Letters
Given a string str having letters, shrink the string to no more than 2 character consecutively exists.
Example 1:
Input: ssupppss
Output: ssuppss
Explanation:Here “p” is repeated 3 times so it’s deleted
Example 2:
Input: uvuuu
Output: uvuu
Explanation: Here we can see that “u” was repeated 3 times so it’s deleted, if the letters are “uuuu” then it will be “uu” the letter cannot be more then 2 times in case of “uuuuu” it will be “uu”.
Solution
Program Python:
Brief: Shrink the string to no more than 2 character consecutively exists
Edge Cases:
- Empty 2. originally valid
Approaches:
- Traverse + Counter, when exceeds 2, adding 2 and find next different one, if not exceeds 2 but different, add the exact amount characters
Group up, shrink the list to the maximum of length 2, then concatenate together, group could use itertools.groupby or manually
Travese + Ordered Counter, generate the result finally
Let’s go with approach 2
from itertools import groupby
def solution(s):
group = [list(l) for _, l in groupby(s)]
group = ["".join(l[:2]) for l in group]
return "".join(group)
print(solution("aaasuaaa"))Program C++:
#include <iostream>
#include <string>
using namespace std;
string solution2(const string & s) {
const int MAX_COUNT = 3;
int s_len = s.length();
int prev_count = 1;
string res;
res.push_back(s[0]);
for (int i = 1; i < s_len; ++i) {
if(s[i] == s[i-1]) {
prev_count++;
}
else {
prev_count = 1;
}
if(prev_count < MAX_COUNT) {
res.push_back(s[i]);
}
}
return res;
}
string solution(const string & s) {
int s_len = s.length();
string res(s.begin(), s.begin()+2);
for (int i = 2; i < s_len; ++i) {
if (s[i] != s[i-1] || s[i] != s[i-2]) {
res.push_back(s[i]);
}
}
return res;
}
int main() {
cout << solution("eedaaad") << endl;
cout << solution("xxxtxxx") << endl;
cout << solution("uuuuxaaaaxuuu") << endl;
return 0;
}8. Microsoft OA Longest Semi-Alternating Substring
You are given a string SS of length NN containing only characters a and b. A substring (contiguous fragment) of SS 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 whole SS is its own substring.
Write a function, which given a string SS, returns the length of the longest semi-alternating substring of SS.
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.
Solution
Program Python:
Double pointer, fix the pointer on the left, then move the pointer on the right until the condition is met, and then move the pointer on the left.
class Solution:
def longestSemiAlternatingSubstring(self, s):
n = len(s)
if n < 3:
return n
res, cnt = 0, 1
left = 0
for right in range(n):
if right > 0 and s[right] == s[right - 1]:
cnt += 1
else:
cnt = 1
if cnt == 3:
left = right - 1
cnt = 2
res = max(res, right - left + 1)
return res Program Java:
The idea is a double pointer, we use a variable to record the last character we saw c c c , then use a variable x x x records the number of consecutive occurrences of the character, and also needs to record the left end point of the longest substring that satisfies the condition ending at the current position; traverse s s s , if it is found that the current character is different from the one seen last time, it means that the substring can be extended, update c c c and update x = 1 x=1 x=1 , keep the left endpoint unchanged; otherwise, it means that the same character is seen, update x x x is x + 1 x+1 x+1 , look at x ≥ 3 x\ge 3 x≥3 is it true, if it is true, it means that you have seen three consecutive identical characters, move the left pointer to the current position minus 1 1 1 , otherwise it will not move; the answer will be updated every time a character is traversed. code show as below:
import java.util.Scanner;
class Solution {
public int longestSemiAlternatingSubstring(String s) {
// write your code here
int res = 0, count = 0;
char ch = 0;
for (int i = 0, j = 0; i < s.length(); i++) {
if (i == 0 || s.charAt(i) != ch) {
ch = s.charAt(i);
count = 1;
} else {
count++;
if (count >= 3) {
j = i - 1;
}
}
res = Math.max(res, i - j + 1);
}
return res;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
int res = longestSemiAlternatingSubstring(s);
System.out.println(res);
}
}Program C++:
This question is similar to String Without 3 Identical Consecutive Letters but here we need to find a longest substring which doesn’t contain three identical consecutive characters and return it’s length.
#include <iostream>
#include <string>
using namespace std;
int solution(const string & s) {
const int MAX_COUNT = 3;
int s_len = s.length();
if(s_len < MAX_COUNT) { return s_len; }
int count = 1, result = 1;
// Scan whole string and count it's characters.
for(int i = 1; i < s_len - 1; ++i) {
// If we meet 3 consecutive characters
if((s[i-1] == s[i]) && (s[i+1] == s[i])) {
// save the counter as result if it is bigger than the previous result
result = max(result,count+1);
// and drop the counter to 1
count = 1;
}
else { count++; }
}
// return maximal result
return max(result,count+1);
}
int main() {
cout << solution("baaabbabbb") << " Expected: 7" << endl;
cout << solution("babba") << " Expected: 5" << endl;
cout << solution("abaaaa") << " Expected: 4" << endl;
cout << solution("eedaaad") << endl;
cout << solution("xxxtxxx") << endl;
cout << solution("uuuuxaaaaxuuu") << endl;
return 0;
}9. Microsoft OA Min Steps to Make Piles Equal Height
Alexa is given n piles of equal or unequal heights. In one step, Alexa can remove any number of boxes from the pile which has the maximum height and try to make it equal to the one which is just lower than the maximum height of the stack. Determine the minimum number of steps required to make all of the piles equal in height.
Example 1:
Input: piles = [5, 2, 1]
Output: 3
Explanation:
Step 1: reducing 5 -> 2 [2, 2, 1]
Step 2: reducing 2 -> 1 [2, 1, 1]
Step 3: reducing 2 -> 1 [1, 1, 1]
So final number of steps required is 3.
Solution
Program: Min Steps to Make Piles Equal Height Solution in Python
Let’s take an example:
Input : [1, 1, 2, 2, 2, 3, 3, 3, 4, 4]
Output : 15
After sorting in reverse, we have…
[4, 4, 3, 3, 3, 2, 2, 2, 1] –> (2 steps to transform the 4’s) –> The 3’s must wait for 2 numbers before it to finish their reduction
[3, 3, 3, 3, 3, 2, 2, 2, 1] –> (5 steps to transform the 3’s) –> The 2’s must wait for 5 numbers before it to finish their reduction
[2, 2, 2, 2, 2, 2, 2, 2, 1] –> (8 steps to transform the 2’s) –> The 1’s must wait for 8 numbers before it to finish their reduction
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Why did we sort in reverse? Because we want to process the maximum / largest number(s) first, which is what the question wants. At each step, we can only reduce the largest number(s) to the value of the 2nd-largest number(s)
The main idea throughout the algorithm is that – Every time I meet a different number in the reverse-sorted array, I have to count how many numbers came before it. This represents the number of steps that was taken to reduce these numbers to the current number
from typing import List
def min_steps_balance(piles: List[int]) -> int:
"""
Time : O(N log N)
Space : O(1), where N = len(s)
"""
# EDGE CASE
if len(piles) < 2:
return 0
# SORT THE BLOCKS
piles = sorted(piles, reverse=True)
# COUNT THE STEPS WE NEED
steps = 0
# EACH TIME WE SEE A DIFFERENT ELEMENT, WE NEED TO SEE HOW MANY ELEMENTS ARE BEFORE IT
for i in range(1, len(piles)):
steps += i if piles[i - 1] != piles[i] else 0
return steps
if __name__ == "__main__":
print(min_steps_balance([50]) == 0)
print(min_steps_balance([10, 10]) == 0)
print(min_steps_balance([5, 2, 1]) == 3)
print(min_steps_balance([4, 2, 1]) == 3)
print(min_steps_balance([4, 5, 5, 4, 2]) == 6)
print(min_steps_balance([4, 8, 16, 32]) == 6)
print(min_steps_balance([4, 8, 8]) == 2)
print(min_steps_balance([4, 4, 8, 8]) == 2)
print(min_steps_balance([1, 2, 2, 3, 3, 4]) == 9)
print(min_steps_balance([1, 1, 2, 2, 2, 3, 3, 3, 4, 4]) == 15)Min Steps to Make Piles Equal Height Python Easiest Solution
from collections import Counter
def minStepEqualPiles(A):
cnt = Counter(A)
nums = sorted(cnt.keys(), reverse=True)
k, ans = 0, 0
for x in nums[:-1]:
k += cnt[x]
ans += k
return ansA = [5, 2, 1]
print(minStepEqualPiles(A))
A = [4, 5, 5, 4, 2]
print(minStepEqualPiles(A))
Program: Min Steps to Make Piles Equal Height Solution in Java
For piles = [5, 2, 1], 5 needs 2 steps to come to 1(5 -> 2 -> 1) and 2 needs 1 step to 1(2 -> 1) and 1 for 0 step. We just need to sort the array and record how many different numbers appeared before and sum them up.
public class Main {
public int minSteps(int[] piles){
int len = piles.length;
if(len <= 1) return 0;
Arrays.sort(piles);
int res = 0, distinctNums = 0;
for(int i = 1; i < len; ++i){
if(piles[i] == piles[i - 1]){
res += distinctNums;
}
else{
++distinctNums;
res += distinctNums;
}
}
return res;
}
public static void main(String[] args) {
int[][] testcases = {{5, 2, 1}, {4,5,5,4,2}};
for(int[] testcase: testcases)
System.out.println(new Main().minSteps(testcase));
}
}Program: Min Steps to Make Piles Equal Height Solution in C++
Lets visualize the piles, lets use A instead of boxes
5: AAAAA
2: AA
1: A
On the first step we cut 5: AAAAA to 2: AA
2: AA
2: AA
1: A
On the second step we cut first strings of 2: AA to 1: A
1: A
1: AA
1: A
On the third step we cut first strings of 2: AA to 1: A
1: A
1: A
1: A
If we will have two piles with the same length, for example:
5: AAAAA
5: AAAAA
1: A
On the first step we cut first 5: AAAAA to 1: A:
1: A
5: AAAAA
1: A
On the second step we cut second 5: AAAAA to 1: A:
1: A
1: A
1: A
In other words in order to determine the minimum number of steps required to make all of the piles equal in height we need to sort the array and count how many piles with different height exists and sum them up.
The C++ code:
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <set>
#include <iterator>
#include <unordered_map>
using namespace std;
/*
int solution(const vector<int> & v) {
priority_queue<int> pq(v.begin(), v.end());
int tallest_num = 0;
int steps = 0;
while ( ! pq.empty()) {
int tallest = pq.top(); pq.pop();
if (pq.empty()) { return steps; }
if (tallest == pq.top()) {
++ tallest_num;
}
else {
steps += tallest_num;
}
}
return steps;
}
*/
int solution3(const vector<int> & v) {
int v_size = v.size();
int result = 0;
int min_num = *std::min_element(v.begin(), v.end());
std::unordered_map<int, int> um;
for(auto i : v) {
++ um[i];
}
for(auto i: um) {
result += i.second;
}
return result;
}
int solution2(vector<int> v) {
int v_size = v.size();
int result = 0;
unordered_set<int> us(v.begin(), v.end());
unordered_multiset<int> ums(v.begin(), v.end());
for(auto i : us) {
result += ums.count(i);
}
return result;
}
int solution(vector<int> v) {
int v_size = v.size();
if(v_size < 2) { return 0; }
std::sort(v.begin(), v.end());
// std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
int sum = 0;
for (int i = 1; i < v_size; ++i) {
if (v[v_size - i - 1] != v[v_size - i]) {
sum += i;
}
}
return sum;
}
int main() {
cout << solution({5,2,1}) << " Expected: 3" << endl;
cout << solution({5,5,2,2,1,1}) << " Expected: 6" << endl;
cout << solution({5,5,1}) << " Expected: 2" << endl;
cout << solution({5,5,5,5,1}) << " Expected: 4" << endl;
cout << solution({3,2,2}) << " Expected: 1" << endl;
return 0;
}Complexity of this solution is O(N* Log(N)) where N is length of the string but I believe there is a solution with linear complexity I just can’t process well all corner cases.
10. Max Inserts to Obtain String Without 3 Consecutive ‘a’
Write a function solution that, given a string S consisting of N characters, returns the maximum number of letters ‘a’ that can be inserted into S (including at the front and end of S) so that the resulting string doesn’t contain 3 consecutive letters ‘a’. If string S already contains the substring “aaa”, then your function should return -1.
Examples:
-
Given S = “aabab”, the function should return 3, because a string “aabaabaa” can be made.
-
Given S = “dog”, the function should return 8, because a string “aadaaoaagaa” can be made.
-
Given S = “aa”, the function should return 0, because no longer string can be made.
-
Given S= “baaaa”, the function should return -1, because there is a substring “aaa”.
Example 1:
Input: aabab
Output: 3
Explanation: A string aabaabaa can be made
Example 2:
Input: egg
Output: 8
Explanation: A string aaeaagaagaa can be made
Example 3:
Input: aa
Output: 0
Explanation: No longer string can be made.
Example 4:
Input: uaaaa
Output: -1
Explanation: There is a substring aaa
Solution
Program Python:
Max Inserts to Obtain String Without 3 Consecutive ‘a’ in Python is very similar to the logic we applied in C++, but in python we used groupby function to make is easier to count the letters.
from itertools import groupby
n=input()
c=0
flg='#'
for i,j in groupby(n):
l=len(list(j))
if i=='a':
if l<3:
c+=2-l
else:
print(-1)
else:
c+=2*(l-(flg=='a'))
flg=i
c+=2*(n[-1]!='a')
print(c)Program C++:
If N is number of chars in the given string and all chars are not ‘a’ we can insert into this string 2 * (N + 1)
chars because we can insert two As between of each two chars in the string and two As to the begin and
to the end of the string.
Thus in order to solve this task we need to count all non A chars. When we will know this number it will be easy to calculate how many As we can add. This number will be 2 * (number of possible places to insert + 1) – number of found As In other words 2 * (N + 1) – (N – number of As)
#include <iostream>
#include <string>
using namespace std;
int solution(const string & s) {
int count_As = 0, count_others = 0, s_len = s.length();
for (int i = 0; i < s_len; ++i) {
if (s[i] == 'a') {
count_As++;
}
else {
count_others++;
count_As = 0;
}
if (count_As == 3) {
return -1;
}
}
return 2 * (count_others + 1) - (s_len - count_others);
}
int main() {
cout << solution("aabab") << " Expected: 3" << endl;
cout << solution("dog") << " Expected: 8" << endl;
cout << solution("aa") << " Expected: 0" << endl;
cout << solution("baaaa") << " Expected: -1" << endl;
return 0;
}Part 1 : https://leetcode.com/discuss/interview-question/2209187/microsoft-online-assessment-1/
Part 2 : https://leetcode.com/discuss/interview-question/2209192/Microsoft-Online-Assessment-Questions-2
Part 3 : https://leetcode.com/discuss/interview-question/2209201/Microsoft-Online-Assessment-Questions-3
Part 4 : https://leetcode.com/discuss/interview-question/2209220/Microsoft-Online-Assessment-Questions-4