Google | OA Coding Questions and Solutions | Set - 1 | 2022

Question

All past online assesments of Google can be found using the tag "google_oa" in the search bar.

Here is the link :  https://www.desiqna.in/tag/google_oa

Answer 1

vector<string> split(string s, char c)
{
    vector<string> ans;
    int i = 0, j = 0;
    while (j < s.size())
    {
        if (s[j] == c)
        {
            ans.push_back(s.substr(i, j - i));
            i = ++j;
        }
        else
            ++j;
    }
    if (i != j)
        ans.push_back(s.substr(i, j - i));

    return ans;
}

int countSmallestCharCount(string s)
{
    char c = *min_element(s.begin(), s.end());
    return count(s.begin(), s.end(), c);
}

int lower_bound(vector<int> &arr, int n)
{
    int size = arr.size();
    int l = 0, r = size - 1;
    int ans = size;
    while (l <= r)
    {
        int mid = l + ((r - l) / 2);
        if (arr[mid] >= n)
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return ans;
}

auto solve = []()
{
    string s1, s2;
    cin.ignore();
    getline(cin, s1);
    getline(cin, s2);
    vector<string> a(split(s1, ' '));
    vector<string> b(split(s2, ' '));
    vector<int> countA, countB;
    for (string s : a)
    {
        countA.push_back(countSmallestCharCount(s));
    }
    sort(countA.begin(), countA.end());
    for (string s : b)
    {
        cout<<s<<endl;
        countB.push_back(countSmallestCharCount(s));
    }
    vector<int> ans;
    for (auto x : countB)
    {
        ans.push_back(lower_bound(countA, x));
    }
    for (auto &x : ans)
        cout << x << " ";
    cout << endl;
};

Answer 2

Compare Strings

A string is defined to be "strictly smaller" than another string when the number of occurrences of the lexicographically smallest character in the string is less than that of the other. For example, "abcd" is strictly smaller than "aaa" because the smallest character in "abcd", "a", appears 1 time, whereas the smallest character in "aaa", "a", appears 3 times.

In another example, "d" is strictly smaller than "ff" because the smallest character in "d", 'd', appears 1 time, and the smallest character in "ff", 'f', appears 2 times.

Given a list of strings str1 with m elements, and another list of strings str2 with n elements, return an array A of n integers. For 0 <= i < n, A[i] is the number of strings in str1 that are strictly smaller than the comparison i-th string in str2. Focus on correctness instead of performance in your solution.

Input

• str1: a list of strings with m elements.
• str2: a list of strings with n elements.

Output

An integer array of size n

Examples

Example 1:

Input:

1str1 = "abcd aabc bd" 2str2 = "aaa aa"

Output: [3, 2]

Explanation:

All the strings in str1 are strictly smaller than "aaa", and strings "abcd" and "bd" are strictly smaller than "aa".

Constraints

• 1 <= n, m <= 10000
• 1 <= length of any string in str1 or str2 <= 10
• All the input strings are made up of lowercase English alphabets (a-z)