Question

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

Answer 1

Took Microsoft OA yesterday: 2 coding and 10 MCQ

 

1.  

   Maximum possible value by inserting '5'
   examples:
   input: 1234 -> output: 51234
   input: 7643 -> output 76543
   input: 0 -> output 50
   input: -661 -> output -5661

    

2.  

   A string is considered balanced when every letter in the string appears both in uppercase and lowercase
   For example, CATattac is balanced (a, c, t occur in both cases). Madam is not (a, d only appear in lowercase).
   Write a function that given a string returns the shortest balanced substring of that string.
   Can this be solved with a sliding window approach?
   Update:
   More examples
   “azABaabza” returns “ABaab”
   “TacoCat” returns -1 (not balanced)
   “AcZCbaBz” returns the entire string

    

3.  

   MCQs mostly on the time complexity and theory.

    

 

Ques 1 is straight forward but Ques 2 took a lot of time :(

Answer 2

The cleanest way and fastest to do the second question is as follows.

 

1. Keep track of all the "most recent" matching intervals seen so far for each alphabet pairs. There should be up to 26 pairs. Here's what most recent means. Say you have a pattern like "abcdaA", you would never want to pick the interval (0,5) for the a/A pair when you can pick interval (4,5). There is never a situation where interval (0,5) would result in a smaller balanced substring. This is the greedy intuition that nets up at most 26 intervals at any given point and everything falls into place.
2. Loop from left to right, updating the list of most recent intervals for each alphabet.
3. For any overlapping intervals, merge them together. You have up to 26 intervals, and you can do this in O(26*log(26)) time: see https://leetcode.com/problems/merge-intervals/ for inspiration (essentially sort by start, then merge).
4. Loop through all 26 intervals, return the smallest value. Note that interval without a matching pair is infinity.

 

Time complexity: O(n * alphabet)
Space Complexity: O(alphabet)

 

pseudocode

 

int upper[26] = {INT_MIN};
int lower[26] = {INT_MIN};
int res=INT_MAX;
for(int i=0; i<arr.size(); i++) {
char c=arr[i];
if(isupper(c)) upper[c-'A']=i;
else lower[c-'a']=i;
map<int,int> m; //C++ ordered maps are sorted
for(int i=0; i<26; i++) m[min(upper[i],lower[i])]=max(upper[i],lower[i]);

 

// Now just find the smallest interval in a map, if you are confused, see https://leetcode.com/problems/merge-intervals/.
// for each interval, res=min(res,interval size);
}
return res;

 

Hope that helps since it looks like all the other posted solutions here have big edge cases and some are stupidly complicated. Honestly look me a bit to think of this. I can't imagine being able to come up with this in an time constrained situation.

 

Also - to all the people who says this is a simple sliding window problem / classic DP problem without providing a solution, screw you.

Answer 3

Question 2 : https://leetcode.com/problems/longest-nice-substring/

Answer 4

Second Question:

 

1. Define partner as the inverse-parity of the character, i.e. P(a) = A, etc
2. Loop over the string and create a map which maintains the index of the partner-character to its right for each character in the string (Imp: only look for partners to its right) => O(N)
3. Loop from each index(say sid, assuming our final result starts with this index) until its partner's index = eid (computed from the Map we created above) => O(N^2)
   a. Each character you pick up while in the loop, is either a partner of an existing character or a new character
   b. If its a new character, modify your eid = max(eid, parter-idx-of-curr-id); if there isnt a partner available to its right you can break early
   c. By the end of this loop, L = eid-sid+1 = length of the substring which has character and its partners = balanced-substring
   d. Maintain the minimum balanced substring

 

Complexity: T=O(N^2) ; S=O(N)

Answer 5

first question:

 

def MaximumValueAdding5(num):
    num = str(num)
    if num[0] !='-':
        for i in range(len(num)):
            if int(num[i])<=5:
                return str(num[:i]) + '5' + str(num[i:])
    else:
        for i in range(1,len(num)):
            if int(num[i])>5:
                return '-'+num[1:i]+ '5' + str(num[i:])

Answer 6

simple approach for q2:

 

// 10:23
class Solution {
private:
    bool checkBalanced(string& s, int start, int end) {
        unordered_set<char> chars;
        for (int i=start; i <= end; i++) {
            chars.insert(s[i]);
        }
        for (auto& c : chars) {
            if (c >= 'a' && c <= 'z') {
                if (chars.count(c-32) == 0) return false;
            } else if (c >= 'A' && c <= 'Z') {
                if (chars.count(c+32) == 0) return false;
            }
        }
        return true;
    }
public:
    string shortestBalancedSubstr(string s) { // 'bB'
        for (int len=2; len <= s.size(); len++) {
            for (int i=0; i <= s.size()-len; i++) {
                bool check = checkBalanced(s, i, i+len-1);
                if (check) {
                    return s.substr(i,len);
                }
            }
        }
        return "-1";
    }
};

int main() {
    Solution s;
    cout << s.shortestBalancedSubstr("bB") << endl;
    cout << s.shortestBalancedSubstr("CATattac") << endl;
    cout << s.shortestBalancedSubstr("azABaabza") << endl;
    cout << s.shortestBalancedSubstr("TacoCat") << endl;
    cout << s.shortestBalancedSubstr("AcZCbaBz") << endl;
    cout << s.shortestBalancedSubstr("Madam") << endl;
}