Amazon

Maximum Teams can Form.

Q1 was about given an Array of numbers, for example {5, 1, 2, 1, 4, 5} which represent skills of employees..(Skills[i])
How many teams you can form, given the Teamsize = 3 and MaxDiff = 2 which is the maximum difference allowed in skills

Example 1 = With {5, 1, 2, 1, 4, 5} and given Teamsize = 3 and MaxDiff = 2. You can form 2 teams [2, 1, 1] and [4, 5, 5].
Example 2 : 0 teams can be formed with [9, 3, 5, 7, 1] and int teamSize = 2; int maxDiff = 1

Time O(nlogn) Space O(n)

#include <algorithm> // copy
#include <iostream> // cin, cout, streamsize
#include <iterator> // back_inserter, istream_iterator
#include <limits> // numeric_limits
#include <sstream> // istringstream
#include <string> // getline, string
#include <vector> // vector

int teams(std::vector<int> skill, int size, int diff) {
    sort(skill.begin(), skill.end());
    if (skill.size() < size) {
        return 0;
    }
    
    int maxCnt = 0;
    auto N = skill.size();
    for (int i = 0; i <= N - size; ) {
        if (skill[i + size - 1] - skill[i] <= diff) {
            maxCnt++;
            i += size;
        } else {
            i++;
        }
    }
    return maxCnt;
}

template<typename T>
std::vector<T> get_words() {
    std::string line;
    std::getline(std::cin, line);
    std::istringstream ss{line};
    std::vector<T> v;
    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
    return v;
}

void ignore_line() {
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

int main() {
    std::vector<int> skill = get_words<int>();
    int size;
    std::cin >> size;
    ignore_line();
    int diff;
    std::cin >> diff;
    ignore_line();
    int res = teams(skill, size, diff);
    std::cout << res << '\n';
}

Link: post, test

Find Minimum Cost to Purchase m Items

In Amazon Go Store, there are n items, each associated with two positive values a[i] and b[i].
There are infinitely many items of each type numbered from 1 to infinity and the item numbered j of type i costs a[i] + (j-1) b[i] units.
Determine the minimum possible cost to purchase exactly m items.

Example
Given n = 3, a = [2, 1, 1], b=[1, 2, 3], m = 4
The optimal types to buy are-

Choose i = 1. This is the first purchase of this type of item, so j = 1.The first item costs a[1] + (1-1)*b[i] = 1 + (1-1)*2=1.
Choose i = 2. Again, it is the first purchase of this type so j = 1. The
second item costs 1+ (1-1)*3=1.
Choose i = 0 which costs 2 + (1-1)* 1 = 2.
When a second unit of any type is purchased, j = 2 for that transaction. The costs of a second units of each item are:
a[0] costs a[0] + (2-1)* b[0] = 2 + 1*1=3
a[1] costs 1 + 1*2=3
a[2] costs 1 + 1*3=4
Choose either a[0] or a[1] since they cost less.
The total cost to purchase is 1 + 1 + 2 + 3 = 7.

Constraints

1<=n<=10^5
1 <= a[i], b[i]<= 10^5
1<= m<=10^5

Solution

long long solution(const vector<int> &a, const vector<int> &b, int m) {
    priority_queue<pair<long long, int>> q;
    const int n = a.size();
    for (int i = 0; i < n; ++i) {
        q.push({-a[i], i});
    }
    long long r = 0;
    for (; m; --m) {
        const int i = q.top().second;
        const long long p = -q.top().first;
        r += p;
        q.pop();
        q.push({-p - b[i], i});
    }
   
    return r;
}
 
int main() {
    printf("%lld\n", solution({2, 1, 1}, {1, 2, 3}, 4));
    return 0;
}

Link: post