Microsoft Online Assessment Questions
11. Concatenated String Length with unique Characters
You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.
Return the maximum possible length of s.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").
Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
Explanation: The only string in arr has all 26 characters.
Example 4:
Input: arr = ["aa","bb"]
Output: 0
Explanation: Both strings in arr do not have unique characters, thus there are no valid concatenations.
Constraints:
1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] contains only lowercase English letters.
Solution
Program Python: Concatenated String Length with unique Characters in Python
Explanation
Basic idea is to turn arr to [(set(word), len(word))] if word has no repeat letter
Then we can use union (&) operation to check whether length of set after union is same as the sum of two size
if (union_len:=len(union:=arr[i][0] | cur_s)) == arr[i][1] + cur_l]
if len(arr[i][0] | cur_s) == arr[i][1] + cur_l same as above
Due to the small data sacle (max length of arr is 16), use backtracking to try out all possbilities
Maintain a maximum length with ans
class Solution:
def maxLength(self, arr: List[str]) -> int:
arr = [(s, l) for word in arr if (l:=len(s:=set(word))) == len(word)]
ans, n = 0, len(arr)
def dfs(arr, cur_s, cur_l, idx):
nonlocal ans, n
ans = max(ans, cur_l)
if idx == n: return
[dfs(arr, union, union_len, i+1) for i in range(idx, n) if (union_len:=len(union:=arr[i][0] | cur_s)) == arr[i][1] + cur_l]
dfs(arr, set(), 0, 0)
return ansProgram C++:
This kind of problems (at least for the relatively small amount of strings provided to us) can be tackled using a DFS approach; a backtracking on and on top of that, to avoid duplicate effort, we will also use a support array with bitmasks to tell us what characters are used in each string.
To do so, we will declare at class level a few support variables:
bits is a pointer to the array we will create containing all the bitmasks equivalent to the provided strings;
pos will be the pointer we will use to write on bits and ultimately also the value of its size – initially set to 0;
res will be our usual accumulator variable, storing the longest combination found so far, with initial value of 0;
curr and currBits will store the values of our current string length and its composed bitmaks, respectively – both again pre-set to 0.
In the main function, we will first of all initialise bits to be an appropriately sized array and the we will parse each string s in arr and:
declare bit with initial value of 0 and tmp to help us in our parsing computations;
for each character c in s, we will:
compute tmp as the 1 raised to the c - 'a'th power of 2, using bitwise shifting;
check if bit & tmp, which means we have already encountered a character like c in s, in which case we will:
reset bit to 0;
break out of the inner loop;
alternatively, we will add tmp to bit with a binary OR;
finally, we will write bit into bits and move pos forward.
We can now move the action to our helper function dfs, that we will call passing justarr` (as a reference, of course).
This helper function will also take an extra parameter, start, that we will default to 0 and:
check first of all if we already encountered the maximum obtainable value (26), in which case no point in continuining and we can stop the call here with a return;
alternatively it will update res to be the maximum between its current value and curr;
another end case to consider now is when start == pos, meaning we are done parsing and we can just return (a bit reduntant given the following loop, but I just find it cleaner);
we will then loop with i from start to pos (excluded) and:
check if bits[i] is not 0 and if we can add the ith string to curr, not having duplicate characters (ie: (currBit & bits[i]) == 0) and, if so:
increase curr by arr[i].size()
add the bit flags in bits[i] to currBit;
call the function recursively, passing arr again and i + 1 as a second parameter (ie: we will try to check all the possible permutations with other strings after the startth one);
decrease curr by arr[i].size()
remove the bit flags in bits[i] to currBit.
Once done, we can just return res.
class Solution {
// support variables
int *bits, pos = 0, res = 0, curr = 0, currBit = 0;
void dfs(vector<string>& arr, int start = 0) {
// end case: max value achieved
if (res == 26) return;
res = max(res, curr);
// end case: no more combinations to check
if (start == pos) {
return;
}
for (int i = start; i < pos; i++) {
if (bits[i] && (currBit & bits[i]) == 0) {
// updating curr and currBits
curr += arr[i].size();
currBit ^= bits[i];
dfs(arr, i + 1);
// backtracking curr
curr -= arr[i].size();
currBit ^= bits[i];
}
}
}
public:
int maxLength(vector<string>& arr) {
// preparing bits
bits = new int[arr.size()];
for (auto &s: arr) {
int bit = 0, tmp;
for (char c: s) {
// updating the new bit flag
tmp = 1 << (c - 'a');
// checking if s has duplicate words
if (bit & tmp) {
bit = 0;
break;
}
bit |= tmp;
}
// writing bit into bits, if we found no duplicates
bits[pos++] = bit;
}
// comparing strings
dfs(arr);
return res;
}
};12. Largest K such that both K and -K exist in array
Given an array A of N integers, returns the largest integer K > 0 such that both values K and -K exist in array A. If there is no such integer, the function should return 0.
Example 1:
Input: [3, 2, -2, 5, -3]
Output: 3
Example 2:
Input: [1, 2, 3, -4]
Output: 0
Solution
This task is very easy. It is a bit more difficult than finding of a maximum value in given array. The only thing we have to add is check if this array contains the same value on the opposite side of zero. In other words we have to check all positive values in the array and check if there are values with the same absolute value but negative sign. There is the only data structure which has constant complexity for access to unsorted items, this is a hash table.
So at first we add all given values to a hash table.
Then pass through all items of the table and check if positive item has the same absolute value but with negative sigh.
Each time if we meet an absolute value bigger than already found maximum value keep it as a new maximum value.
Program C++:
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int solution(const vector<int>& input){
unordered_set<int> s(input.begin(),input.end());
int max_value = 0;
for(auto n : s){
if((abs(n) > max_value) && (s.count(-n) != 0) ) {
max_value = n;
}
}
return max_value;
}
int main() {
cout << solution({3, 2, -2, 5, -3}) << " Expected: 3" << endl;
cout << solution({1, 2, 3, -4}) << " Expected: 0" << endl;
return 0;
}Program Python:
def solution(arr):
arr = sorted(arr)
i,j = 0, len(arr)-1
while i < j:
if arr[i]+arr[j] == 0:
return arr[j]
elif abs(arr[i]) > arr[j]:
i += 1
elif abs(arr[i]) < arr[j]:
j-=1
return 0
print(solution([3, 2, -2, 5, -3]))Program Java:
public static void main(String[] s){
int[] arr = {-41,3,2,5,41};
System.out.println(largestNumWithNegPair(arr));
}
private static int largestNumWithNegPair(int[] arr){
HashSet<Integer> set = new HashSet<>();
int curMax = 0;
for (int a:arr) {
// if the negated counter part is already existing, consider the number for largestNum selection.
if(set.contains(a*-1))
curMax = Math.max(curMax,Math.abs(a));
else
//keep track of the numbers read so far.
set.add(a);
}
return curMax;
}13. Microsoft OA Min Adj Swaps to Group Red Balls
There are N balls positioned in a row. Each of them is either red or white . In one move we can swap two adjacent balls. We want to arrange all the red balls into a consistent segment. What is the minimum number of swaps needed?
Given string S of length N built from characters "R" and "W", representing red and white balls respectively, returns the minimum number of swaps needed to arrange all the red balls into a consistent segment. If the result exceeds 10^9, return -1.
Also See: Microsoft Online Assessment Questions and Solution
Example 1:
Input:WRRWWR
Output: 2
Explanation:
We can move the last ball two positions to the left:
swap R and W -> WRRWRW
swap R and W -> WRRRWW
Example 2:
Input:WWRWWWRWR
Output: 4
Explanation:
We can move the last ball two positions to the left:
swap R and W -> WWRWWWRRW
swap R and W -> WWWRWWRRW
swap R and W -> WWWWRWRRW
swap R and W -> WWWWWRRRW
Example 3:
Input:WR repeated 100000 times.
Output: -1
Explanation:
The minimum needed number of swaps is greater than 10^9. So return -1.
Example 4:
Input:WWW
Output: 0
Explanation:
There are no red balls to arrange into a segment.
Solution:
Probably the first idea you get after reading this task is to count all Ws surrounded by Rs and multiply them to number of Rs divided by Ws which we need to move. But if we will move Rs to left or to right side it may happens that the number of swaps will be not minimum. For example if we move RWRWWRRR from right to left we spend 10 swaps but if we will move from left to right we spend only 5 swaps.
The optimum way is moving Rs to the middle of the row.
So let’s process the row from the left and the right side simultaneously. We will move from the ends to the middle, find all pairs of Rs of the ends, count Ws between of them and add these counts to the result.
For example lets process the row: RWWWRWRWWR
We start from the sides and see that left and right sides are ending by Rs
R W W W R W R W W R
| |
left right
Number of Ws in between = 6, so in order to move two Rs from the ends to the middle we need to do 6 swaps. We add 6 to the result variable and continue.
Now we passing all Ws until we meet next pair of Rs
R W W W R W R W W R
| |
left right
Number of Ws in between = 1, in order to move two Rs from the ends to the middle we need to do 1 swap. We add 1 to the result variable and finish with the result = 7.
In order to calculate how many Ws we have between Rs we should count number of all Rs in the row before start of the main algorithm.
Program C++:
Description of the algorithm for similar task from Google
So we can solve this question by sliding window method. We always keep a window that contains k girls’ position and process the string char by char. If we encounter a boy, we do nothing; otherwise we move the window to contain the current girl and pop out the left most girl.
To solve the minimum swaps needed in the current window, one can find the median position of k girls in the window and calculate the distances from the other girls to the girl in the median position. For example, consider string = “B[GGGBBBBG]BBGGBGG”, the median position in the current window is 2 or 3 (indexed from 0). Let the median position be 2, the total distances from all the other girls is 1 + 1 + 6 = 8.
Then you minus the fixed adjust distance (1 + 1 + 2) = 4 and get the minimum number of swaps = 4. The fixed adjust distance here is because you move all girls into the median position, but the girls are sitting in a consecutive row instead of the same position.
Therefore we already have a O(kn)-time O(k)-space algorithm, k is for the time to solve the minimum number of swaps in the current window and n is for the time to scan the whole string. Of course you can improve the algorithm to be O(n) time. This is because when the window is sliding to the next one, the median position can be tracked easily if the window is implemented by a linked list. Regarding updating the distances to the median position, let the left_distance be the total distances from the girls to the left of the median girl and similarly for the right_distance.
Let m be the median position and m’ be the new median position. Consider the window slides to the next girl at position j and pops the most left girl at position i.
The the new left_distance = left_distance – (m – i) + (m’ – m) * ((k – 1) / 2)
and the new right_distance = right_distance + (j – m’) – (m’ – m) * (k / 2).
Therefore we can calculate the minimum number of swaps in constant time.
Here is the code:
int minSwapNum(string& s, int k) {
list<int> window;
int i = 0;
while ((i < s.size()) && (window.size() < k)) {
if (s[i] == 'G') {
window.push_back(i);
}
i++;
}
//No enough girls
if (window.size() < k) {
return -1;
}
auto med_it = window.begin();
advance(med_it, (k - 1) / 2);
int left_dist = 0;
int right_dist = 0;
for (auto idx : window) {
if (idx < *med_it) {
left_dist += (*med_it - idx);
} else {
right_dist += (idx - *med_it);
}
}
int adjust_dist = (k % 2 == 0) ? k * k / 4 : (k * k - 1) / 4;
int min = left_dist + right_dist - adjust_dist;
for (; i<s.size(); i++) {
if (s[i] == 'G') {
int head = window.front();
int tail = i;
int old_med = *med_it;
window.pop_front();
window.push_back(tail);
med_it++;
left_dist = left_dist - (old_med - head) + (*med_it - old_med) * ((k - 1) / 2);
right_dist = right_dist + (tail - *med_it) - (*med_it - old_med) * (k / 2);
if (left_dist + right_dist - adjust_dist < min) {
min = left_dist + right_dist - adjust_dist;
}
}
}
return min;
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> get_char_indices(const string & s, char c) {
int s_len = s.length();
vector<int> indices;
indices.reserve(s_len);
for (int i = 0; i < s_len; ++i) {
if (s[i] == c) {
indices.push_back(i);
}
}
indices.shrink_to_fit();
return indices;
}
int solution2(const string & s) {
auto reds = get_char_indices(s, 'R');
int mid = reds.size() / 2;
int min_swaps = 0, reds_num = reds.size();
for (int i = 0; i < reds_num; i++) {
// number of swaps for each R is the distance to mid, minus the number of R's between them
min_swaps += abs(reds[mid] - reds[i]) - abs(mid - i);
}
return (min_swaps > pow(10, 9)) ? -1 : min_swaps;
}
int solution(const string & s) {
int red_count = 0;
// count number of Rs in the string
for (char c : s) {
if (c == 'R') ++red_count;
}
// Init indexes to the ends of the string and the result
int left = 0, right = s.size() - 1, result = 0;
// moving from the ends to the middle
while (left < right) {
// if we meet pair of Rs on the ends
if (s[left] == 'R' && s[right] == 'R') {
// add the the result number of Ws between of these Rs
red_count -= 2;
result += right - left - 1 - red_count;
// and shrink the processing window
++left;
--right;
}
// pass all Ws we meet
else if (s[left] != 'R') {
++left;
}
else {
--right;
}
}
return result;
}
int main() {
cout << solution("RRRWRR") << " Expected: 2" << endl;
cout << solution("WRRWWR") << " Expected: 2" << endl;
cout << solution("WWRWWWRWR") << " Expected: 4" << endl;
cout << solution("RWRWWRRR") << " Expected: 5" << endl;
return 0;
}Program Java:
public static int minAdjSwapRedBalls(String s) {
List<Integer> redIndex = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'R') redIndex.add(i);
}
int res = 0, mid = redIndex.size() / 2; // mid is the point to get minimum swaps; greedy.
for (int i = 0; i < redIndex.size(); i++) {
res += Math.abs(redIndex.get(mid) - redIndex.get(i)) - Math.abs(mid - i);
}
return res;
}14. Maximum Length of a Concatenated String with Unique Characters
Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters. Return the maximum possible length of s.
Example 1:
Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".
Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
Constraints:
1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] contains only lower case English letters.
Solution:
We have a given array of strings. We have to find all possible combinations of these strings. We have one limitation — we can’t combine strings which have the same letters, in other words we can combine strings only with unique letters. It easy to see that we need to invent some way of fast check if two strings have the same letters. And it’s easy to see that length of any result string cannot exceed length of the alphabet, in our case 26 letters.
We can make a map where given strings will be the values and each string will have a sorted array of letters which used in this string as a key.
For example array of strings “coco”,”dodo”,”interactive” will have following look as a map:
Maximum Length of a Concatenated String with Unique Characters
It is easy to compare sorted letters and find if there are common letters in two strings.
But may be there is a way to speedup this comparison?
If each letter can appears only one time in the result string then maximum result string is the alphabet and has length 26 letters. We can reflect the alphabet into a bitset. If a letter appears in the string the corresponding bit is set to 1.
Word “interactive” as a bitset will looks like this:
Concatenated String Length with unique Characters
26 bits is less than a register of CPU, so in ideal case, we can compare two bitsets in one CPU command. Nothing can be faster.
Therefore the final algorithm should looks like this:
Iterate the input strings, skipping the strings that have duplicate characters.
For each string with unique chars, check if it has the same chars as the result string.
If they have intersection of characters, we skip it.
If not, we append this new combination to the result.
return length of the result string.
We should not work with the strings directly. We can convert them into the bitsets and work with the bits only. It significantly decrease memory consumption and increase speed of the program.
Program C++:
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
int solution(const vector<string>& v) {
// We will keep in this vector bitmaps of used letters
// for the processed words.
// Add one empty bitset for comparison with the first
// processed word. It makes the algorithm a bit shorter
vector<bitset<26>> char_bits_vector = {bitset<26>()};
int result = 0;
// for each string in the vector make a bitset where all
// bits corresponding to characters in alphabet are set.
for (auto& str : v) {
bitset<26> char_bits;
// set bits corresponding to chars in the string.
for (char c : str) { char_bits.set(c - 'a'); }
// How many bits were set.
int bit_num = char_bits.count();
// the string contains duplicate characters so don't process it
if (bit_num < str.size()) continue;
// Check if current word has common letters with already processed words
for (int i = char_bits_vector.size() - 1; i >= 0; --i) {
auto& c_b = char_bits_vector[i];
// if two bitsets have common 1 bits i.e.
// if two words have common letters don't process current word
if ((c_b & char_bits).any()) continue;
// if current word has unique letters add to the vector a bitset where
// all bits corresponding to letters of the current word are set to 1.
char_bits_vector.push_back(c_b | char_bits);
// add length of the current word to the result
result = max<int>(result, c_b.count() + bit_num);
}
}
return result;
}
int main() {
cout << solution({"co","dil","ity"}) << " Expected 5" << endl;
return 0;
}Program Python:
Explanation
Basic idea is to turn arr to [(set(word), len(word))] if word has no repeat letter
Then we can use union (&) operation to check whether length of set after union is same as the sum of two size
if (union_len:=len(union:=arr[i][0] | cur_s)) == arr[i][1] + cur_l]
if len(arr[i][0] | cur_s) == arr[i][1] + cur_l same as above
Due to the small data sacle (max length of arr is 16), use backtracking to try out all possbilities
Maintain a maximum length with ans
class Solution:
def maxLength(self, arr: List[str]) -> int:
arr = [(s, l) for word in arr if (l:=len(s:=set(word))) == len(word)]
ans, n = 0, len(arr)
def dfs(arr, cur_s, cur_l, idx):
nonlocal ans, n
ans = max(ans, cur_l)
if idx == n: return
[dfs(arr, union, union_len, i+1) for i in range(idx, n) if (union_len:=len(union:=arr[i][0] | cur_s)) == arr[i][1] + cur_l]
dfs(arr, set(), 0, 0)
return ansProgram Python: Code 2
from typing import List
def maxLength(arr: List[str]) -> int:
maxlen = 0
unique = ['']
def isvalid(s):
return len(s) == len(set(s))
for word in arr:
for j in unique:
tmp = word + j
if isvalid(tmp):
unique.append(tmp)
maxlen = max(maxlen, len(tmp))
return maxlen
if __name__ == "__main__":
word_list = input().split()
print(maxLength(word_list))Program Java:
import java.util.*;
import java.util.stream.Collectors;
class Solution {
public static int maxLength(String[] args) {
List<String> arr = Arrays.asList(args);
int maxLen = 0;
arr = arr.stream().filter(str-> isUnique(str)).collect(Collectors.toList());
Map<String,Integer> mem = new HashMap<>();
maxLen = dfs(arr, "", 0, maxLen, mem);
return maxLen;
}
private static int dfs(List<String> arr, String path, int i, int maxLen, Map<String, Integer> mem) {
if (mem.get(path) != null) return mem.get(path);
boolean pathIsUnique = isUnique(path);
if (pathIsUnique) {
maxLen = Math.max(path.length(), maxLen);
}
if (i == arr.size() || !pathIsUnique) {
mem.put(path, maxLen);
return maxLen;
}
for (int j = i; j < arr.size(); j++) {
maxLen = dfs(arr, path + arr.get(j), j + 1, maxLen, mem);
}
mem.put(path, maxLen);
return maxLen;
}
public static boolean isUnique(String str) {
char[] characters = str.toCharArray();
if (characters != null) Arrays.sort(characters);
for (int i = 0; i < characters.length - 1; i++) {
if (characters[i] == characters[i + 1]) return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] wordList = scanner.nextLine().split(" ");
scanner.close();
System.out.println(maxLength(wordList));
}
}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