Microsoft Online Assessment Questions
1. Maximal Network Rank Solution
There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.
The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.
The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.
Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.
Example 1:
Maximal Network Rank Solution
Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.
Example 2:
Maximal Network Rank Solution
Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.
Example 3:
Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.
Constraints:
2 <= n <= 100
0 <= roads.length <= n * (n - 1) / 2
roads[i].length == 2
0 <= ai, bi <= n-1
ai != bi
Each pair of cities has at most one road connecting them.
Solution
Program C++:
Create Adjacency Matrix for the graph
Create degree of all the nodes and insert into max heap.
Pop first max element from the heap
Pop second element from the heap
Keep finding element in heap utill it is equal to second max.
If first and second are not same , find if there exists are pair of popped out element with no path between first max and the all of the second maxs (return f+s) otherwise (return f+s-1)
If first and second element are same find if there exists a pair in all the first maxs with no path between them (return f+s) otherwise (f+s-1)
class Solution {
public:
int maximalNetworkRank(int n, vector<vector>& roads) {
vector<vector> grid;
grid.resize(n);
for(int i=0;i<n;i++)
{
grid[i].resize(n);
}
for(int i=0;i<roads.size();i++)
{
grid[roads[i][0]][roads[i][1]]=1;
grid[roads[i][1]][roads[i][0]]=1;
}
priority_queue<pair<int,int>, vector<pair<int,int>> > pq;
for(int i=0;i<n;i++)
{
int sum=0;
for(int j=0;j<n;j++)
{
sum+=grid[i][j];
}
pq.push(make_pair(sum,i));
}
vector<int> v;
pair<int,int> a= pq.top();
int x=a.first;
v.push_back(a.second);
pq.pop();
pair<int,int> b=pq.top();
int y=b.first;
v.push_back(b.second);
pq.pop();
while(pq.size()!=0 && pq.top().first==b.first)
{
v.push_back(pq.top().second);
pq.pop();
}
if(x!=y)
{
for(int i=1;i<v.size();i++)
{
if(grid[v[0]][v[i]]==0)
{
return x+y;
}
}
return x+y-1;
}
for(int i=0;i<v.size();i++)
{
for(int j=0;j<v.size();j++)
{
if(i!=j && grid[v[i]][v[j]]==0)
{ return x+y;
break;
}
}
}
return x+y-1;
}};Program Python:
Solve this problem we need to :
Find all candidates for most connected city
If there’s only 1 candidate for most connected city (let’s call it city1):
Find all candidates for second most connected city (let’s call it city2/cities2)
Loop through all cities in cities2
If any city2 has no connections to city1, return the sum of their (city1, and city2) connections
Otherwise return the sum of their connections -1 (to account for the common connection)
Otherwise loop through all possible combination of candidates:
If in any combination there’s no common edge, return the sum of their connections.
Otherwise return the sum of their number of connections -1.
from collections import defaultdict
class Solution:
def computeConnections(self, roads):
res = defaultdict(list)
for road in roads:
a, b = road
res[a].append(b)
res[b].append(a)
return res
def rankingConnections(self, connections):
res = defaultdict(list)
sortedRank = set()
for city in connections:
nOfConnections = len(connections[city])
res[nOfConnections].append(city)
sortedRank.add(nOfConnections)
return res, sorted(list(sortedRank))
def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
if not roads:
return 0
connections = self.computeConnections(roads)
citiesWithNConnections, possibleNumberOfConnections = self.rankingConnections(connections)
highestNumberOfConnections = possibleNumberOfConnections[-1]
if len(citiesWithNConnections[highestNumberOfConnections]) == 1:
# we loop through all the cities with the second highest number of connections
# O(n) for n being the number of cities
secondHighestNumberOfConnections = possibleNumberOfConnections[-2]
city1 = citiesWithNConnections[highestNumberOfConnections][0]
for city2 in citiesWithNConnections[secondHighestNumberOfConnections]:
if city2 not in connections[city1]:
return highestNumberOfConnections+secondHighestNumberOfConnections
return highestNumberOfConnections+secondHighestNumberOfConnections - 1
else:
# we loop through all the possible combination of cities that has
# the highest number of connections
# O(n^2) for n being the number of cities
for i in range(len(citiesWithNConnections[highestNumberOfConnections])):
for j in range(i+1, len(citiesWithNConnections[highestNumberOfConnections])):
city1 = citiesWithNConnections[highestNumberOfConnections][i]
city2 = citiesWithNConnections[highestNumberOfConnections][j]
if city2 not in connections[city1]:
return 2*highestNumberOfConnections
return 2*highestNumberOfConnections-1Program Java:
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
int[] count=new int[n];
int[][] direct=new int[n][n];
for(int[] r:roads)
{
count[r[0]]++;
count[r[1]]++;
direct[r[0]][r[1]]=1;
direct[r[1]][r[0]]=1;
}
int rank=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
rank=Math.max(rank,count[i]+count[j]-direct[i][j]);
}
}
return rank;
}
}2. Min Deletions To Obtain String in Right Format
You are given a string s consisting only of characters 'a' and 'b'. You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.
Return the minimum number of deletions needed to make s balanced.
Example 1:
Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").
Example 2:
Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.
Constraints:
1 <= s.length <= 105
s[i] is 'a' or 'b'.
Solution
Program Python:
Two pointer Python O(N) time and O(1) space solution
The idea is to use two pointers i and j where i traverses from left to right and j traverses from right to left.
While traversing right, get to the first position where s[i] == ‘b’ and similarly while traversing left, get to the first position where s[j] == ‘a’. We also keep on adjusting the count of ‘a’ and ‘b’ accordingly. Now we reach to a point where s[0:i] is all ‘a’ and s[j+1:] is all ‘b’. At this point we need to decide whether we want to delete ‘a’ or ‘b’. So we go greedy and delete that char whose count is less. So if count_a < count_b, we delete char ‘a’ else we delete char ‘b’.
def get_a_count(word):
count = 0
for ch in word:
if ch == 'a':
count += 1
return count
def get_minimum_deletions(word):
result = 0
i = 0
j = len(word)-1
count_a = get_a_count(word)
count_b = len(word)-count_a
while i < j:
# get to the point where word[i] = 'b'
while i < j and word[i] == 'a':
i += 1
count_a -= 1
# get to the point where word[j] = 'a'
while i < j and word[j] == 'b':
j -= 1
count_b -= 1
# we go greedy here and delete that char whose count is less
if count_a != 0 and count_b != 0:
if count_a < count_b:
j -= 1 # simulates deletion of 'a'
result += 1
count_a -= 1
else:
i += 1 # simulates deletion of 'b'
result += 1
count_b -= 1
return resultProgram C++:
Logic:
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;
1.1 If next char is the same as the previous one increase counter of the same chars “count”;
1.2 If next char is different drop counter of the same chars “count” to 1;
2 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;
}Program Java:
class Solution {
public int minimumDeletions(String s) {
int n=s.length();
int []dp=new int[n+1];
int bcount=0;
for(int i=0;i<n;i++){
char c=s.charAt(i);
if(c=='a'){
dp[i+1]=Math.min(dp[i]+1,bcount);
}else{
dp[i+1]=dp[i];
bcount++;
}
}
return dp[n];
}
}3. Day of week that is K days later Solution
Given a day of the week, with an integer K representing numbers, find the day of the week after K days.
Example 1:
Input:
day = “Monday”
K = 3
Output: Thursday
Solution
Program C++:
Day of week that is K days later Leetcode
By description we have as input parameters: string with name of day of week and distance in days till another day of week. We have to find name of the second day of week and return a string with it’s name. To solve this task it would be good to convert given day of week from string to a number of day. Let’s count the days from 0. That is Sunday is 0, Monday is 1 … Saturday is 6.
Then we have a distance between two days of week in days. And we need to find out which day of week is the last day on this distance. Or in other words which number of the day inside of week.
Each week contains 7 days so in order to find a number of day of week we need to convert the distance between of these days from days to weeks. It is easy to calculate the distance in weeks if we have integer number of weeks between the given days.
For example if we have S = “Sun” and K = 7, a day of week in 7 days is “Sun” too.
But if the distance is not divided entirely we may use the remainder after division by 7 it order to find a number of day within a week. For example let’s S = “Tue” and K = 10. Tuesday is 2 day of week. We should add to 10 to 2. 10+2=12 and divide 12 by 7. We get remainder = 5.
Thus day of week of the last day is Friday because 5th day of week is Friday and there are 10 days between Tuesday this week and Friday next week.
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
string solution(const string &day, int k) {
vector<string> days = {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};
unordered_map<string, int> week_map = {{"Sun", 0},
{"Mon", 1},
{"Tue", 2},
{"Wed", 3},
{"Thu", 4},
{"Fri", 5},
{"Sat", 6}};
return days[(week_map[day] + k) % 7];
}
int main() {
cout << solution("Sat", 23) << " Expected: Mon" << endl;
return 0;
}4. Minimum Adjacent Swaps to Make Palindrome Solution
This question can be called as “Minimum Adjacent Swaps to Make Palindrome” or “Min Swaps to Make Palindrome” either way both are same. Make sure you look through the code before copying it.
A palindrome is a string of letters that is equal to itself when reversed. Given an input string, not necessarily a palindrome, compute the number of times you need to swap to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols. For example, the string “mamad” may be transformed into the palindrome “madam” with 3 swaps:
swap “ad” to get “mamda”
swap “md” to get “madma”
swap “ma” to get “madam”
Input
The Input will have number of test cases. For each test case, one line of input containing a string of up to 100 lowercase letters will be there. Terminate the input with a 0(zero).
Output
Output consists of one line. This line will contain the number of swaps, or “Impossible” if it is not possible to transform the input string to a palindrome.
Example
Input:
mamad
asflkj
aabb
0
Output: 3
Impossible 2
Solution
Program Python:
def is_permutation_of_palindrome(s):
s = s.lower()
bit_vector = 0 << 25
for char in s:
index = ord(char) - 97
bit_vector = (1 << index) ^ bit_vector
return (bit_vector - 1) & bit_vector == 0
def solution(s):
if is_permutation_of_palindrome(s):
s = list(s)
i, j = 0, len(s) - 1
total_swaps = 0
while j > i:
k = j
while k > i and s[i] != s[k]:
k -= 1
while k < j:
if s[i] == s[j]:
break
s[k], s[k + 1] = s[k + 1], s[k]
total_swaps += 1
k += 1
i += 1
j -= 1
return total_swaps
else:
//Based on the question you can either return -1 or Impossible.
return "Impossible"
while True:
s=input().strip()
if s[0]=='0':
break
print(solution(s))Program Java:
Algorithm:
- First check the given string is a jumbled/shuffled palindrome or not.
- Next have two pointers p1 at 0 and p2 at s.length – 1 and start iterating.
- If chars at both the pointers are same then just shrink the window (increase the p1 and decrease the p2).
- or Else
a. find the matching pair and swap the char to p2 index (increase swap count while swapping) and finally shrink the window.
b. if not found just swap once with adjacent index and increase the swap count (do not shrink the window here) - Print the Swap Count
Time Complexity: O(n) to find Palindrome + [ O(n) for two pointer iteration * O(n) for checking and swapping ] so => O(n^2)
Space Complexity: O(n)
private int getNoOfSwaps(String s) {
if(s == null || s.length() == 0) return -1;
int totalSwaps = 0;
if(isShuffledPalindrome(s)) {
char[] chars = s.toCharArray();
int p1 = 0, p2 = chars.length - 1;
while(p2 > p1) {
if(chars[p1] != chars[p2]) {
int k = p2;
while(k > p1 && chars[k] != chars[p1]) k--;
if(k == p1) { //When no matching character found
swap(chars, p1, p1 + 1);
totalSwaps++;
} else { //When Matching character found swap until K reaches p2 position
while(k < p2) {
swap(chars, k, k + 1);
totalSwaps++;
k++;
}
p1++; p2--;
}
} else {
p1++; p2--; //When the characters are equal move on
}
}
return totalSwaps;
}
else return -1;
}
private static void swap(char[] chars, int k, int i) {
char temp = chars[k];
chars[k] = chars[i];
chars[i] = temp;
}
private boolean isShuffledPalindrome(String s) {
int [] occurrence = new int[26];
int oddCount = 0;
for(int i = 0; i < s.length(); i++) occurrence[s.charAt(i) - 'a']++;
for (int value : occurrence) if (value % 2 != 0) oddCount++;
return oddCount <= 1;
}Program C++:
General idea of the algorithm:
palindrome has mirrored sides where letters on the same distance from the middle of the word are the same.
Check if given string is a shuffled palindrome. If no return -1.
We checking if the letters from both sides are the same stared from edges of the word toward the center
If the check is OK for all letters we return 0 because it is a correct palindrome and we should move nothing.
If we meet different letters we trying to find the same letter going from the end to the beginning of the word
2.1. If we meet the same letter we shift it by swaps to it’s right place and return to the phase 1
2.2. If we don’t meed the same letter we swap the first letter with it’s neighbour and return to the phase 1.
Count all swaps and return the number.
Algorithm:
- First check the given string is a jumbled/shuffled palindrome or not.
- Next have two pointers p1 at 0 and p2 at s.length – 1 and start iterating.
- If chars at both the pointers are same then just shrink the window (increase the p1 and decrease the p2).
- or Else
a. find the matching pair and swap the char to p2 index (increase swap count while swapping) and finally shrink the window.
b. if not found just swap once with adjacent index and increase the swap count (do not shrink the window here) - Print the Swap Count
Time Complexity: O(n) to find Palindrome + [ O(n) for two pointer iteration * O(n) for checking and swapping ] so => O(n^2)
Space Complexity: O(n)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool is_palindrom(const string & word){
int i1 = 0;
int i2 = word.size() - 1;
while (i2 > i1) {
if (word[i1] != word[i2]) {
return false;
}
++i1;
--i2;
}
return true;
}
bool is_shuffled_palindrome(const string & s) {
vector<int> occurrence(26, 0);
int odd_count = 0;
for(char i : s) { occurrence[i - 'a']++; }
for (int value : occurrence) {
if (value % 2 != 0) {
odd_count++;
}
}
return odd_count <= 1;
}
/*
int solution(string s) {
int start = 0;
int end = s.size() - 1;
int result = 0;
while (start < end) {
// if we found different chars
if (s[start] != s[end]) {
int i = end; // make an additional iterator from the end
// move toward the start until we found the same char
while (i > start && s[i] != s[start]) { --i; }
// if we have not scanned whole string yet
if (i > start) {
// swap all chars from i to the end
while (i < end) {
swap(s[i], s[i + 1]);
result++;
i++;
}
}
// if we scanned whole the string and found
// no one the same char swap char on the start with adjacent char
// it needs for case when the first char is not on it's right place
// all other parts of the algorithm don't process a char on the start
// we don't need to shrink the processing window here so we start
// a new iteration of the loop here.
else {
swap(s[start], s[start+1]);
result++;
continue;
}
}
// if s[start] == s[end] shrink the processing window
start++;
end--;
}
return result;
}
*/
int solution(string s) {
int s_size = s.size();
int result = 0;
int start = 0, end = s_size - 1;
// if string is empty or it is not a palindrome return -1
if ((s_size == 0) || (!is_shuffled_palindrome(s))) {
return -1;
}
while (end > start) {
// if we found different chars
if (s[start] != s[end]) {
int i = end; // make an additional iterator from the end
// move toward the start until we found the same char
while (i > start && s[i] != s[start]) { --i; }
// if we scanned whole the string and found
// no one the same char swap char on the start with adjacent char
// it needs for case when the first char is not on it's right place
// all other parts of the algorithm don't process a char on the start
if (i == start) {
swap(s[start], s[start + 1]);
++result;
}
// if the same character found swap all chars from i to the end
else {
while (i < end) {
swap(s[i], s[i + 1]);
++result;
++i;
}
++start; --end;
}
}
// if s[start] == s[end] shrink the processing window
else {
++start; --end;
}
}
return result;
}
int main() {
cout << solution("abcba") << endl;
cout << solution("ntaiain") << endl;
cout << solution("niaiatn") << endl;
cout << solution("damam") << endl;
cout << solution("mamad") << endl;
return 0;
}5. Lexicographically Smallest String
Lexicographically smallest string formed by removing at most one character.
Example 1:
Input: abczd
Output: abcd
Solution
Program C++:
By definition of lexicographical order each next string is larger
than the previous one А < АА < ААА < АAB < ААC < АB < B < … < ZZZ
Since we could only remove one character, we should remove the first char
we meet that is greater than the next from left to right.
In this case our string will be lexicographically smallest.
May be it looks more clear on numbers. Let us have a number 1324,
we should remove 3 in order to make it smallest.
Or let us have a number 389575, it is obvious we should remove 9 to make it smallest.
#include <iostream>
#include <vector>
using namespace std;
string solution(const string &s) {
int i = 0, s_size = s.size();
string result(s);
for (; i < s_size - 1; ++i) {
if (s[i] > s[i + 1]) {
break;
}
}
result.erase(i, 1);
return result;
}
int main() {
cout << "Result: " << solution("bba") << " Expected: ba" << endl;
cout << "Result: " << solution("abczd") << " Expected: abcd" << endl;
cout << "Result: " << solution("abcdz") << " Expected: abcd" << endl;
return 0;
}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