Question

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

Answer 1

 

• We will create a lookup table that will store if any string has any char at index x or not.
• If we observe that multiple value fit at same position then we have our solution.

#include<bits/stdc++.h>
using namespace std;

vector<int> solve(vector<string> const& S) {
    const int n = (int)S.size(), m = (int)S[0].size();
    vector<vector<int>> lookup(m, vector<int>(26, -1));
    for(int j = 0; j < n; j++) {
        auto& w = S[j];
        for(int i = 0; i < m; i++) {
            auto& val = lookup[i][w[i] - 'a'];
            if(val == -1) val = j;
            else return {min(val, j), max(val, j), i};
        }
    }
    return {};
}

int main() {
    int n; cin >> n;
    vector<string> S(n);
    for(auto& e: S) cin >> e; 
    auto ans = solve(S);
    for(auto& e: ans) cout << e << ' '; cout << '\n';
    return 0;
}

Answer 2

This is one of the problems for Microsoft Online Assessements

 

You are given an array S consisting of N strings. Every string is of the same length M. Your task is to find a pair of strings in array S, such that there exists a position in which both of the strings have the same letter. Both the index in array S and the positions in the strings are numbered from zero.

 

For example, given S = ["abc", "bca", "dbe"], string 0 ("abc") and string 2 ("dbe") have the same letter 'b' in position 1. On the other hand, for strings "abc" and "bca" there does not exist a position in which they have the same letter.

 

Write a function that, given a zero-indexed array S of N strings, returns an array describing a pair of strings from S which share a common letter at some index. If there is no such pair, the function should return an empty array. If there is more than one correct answer, the function can return any of them.

 

The result should be represented as an array containing three integers. The first two integers are the indexes in S of the strings belonging to the pair. The third integer is the position of the common letter.

 

For S = ["abc", "bca", "dbe"], as above, the result array should be represented as [0, 2, 1]. Another correct answer is [2, 0, 1], as the order of indexes of strings does not matter.