Pick Up Coupons Google OA 2023 Solution
Several coupons are placed in a row, and to win the prize you need to pick at least 2 coupons of the same value. You can only pick consecutive coupons from the row. Each coupon costs 1 coin, find the minimum number of coins needed to obtain the prize or, -1 if it’s not possible.
Example 1:
Input: coupons = [5, 3, 4, 2, 3, 4, 5, 7]
Output: 4
Explanation:
Because you can buy coupons with values [3, 4, 2, 3] or [4, 2, 3, 4]
Example 2:
Input: coupons = [3, 6, 1, 9]
Output: -1
SOLUTION
Program: Pick Up Coupons Google OA Solution in Python
def min_cost_to_win(coupons):
output = len(coupons) + 1
di = collections.defaultdict(int)
basket = []
for i in range(len(coupons)):
itm = coupons[i]
if itm not in basket:
basket.append(itm)
di[itm] = i
else:
crnt = i - di[itm] + 1
output = min(output,crnt)
di[itm] = i
if output>len(coupons):
output = -1
return outputProgram: Pick Up Coupons Google OA Solution in Python
def min_cost_to_win(nums):
last_seen_idx = {}
ans = len(nums) + 1
for i, num in enumerate(nums):
if num in last_seen_idx:
ans = min(ans, i - last_seen_idx[num] + 1)
last_seen_idx[num] = i
return ans if ans < len(nums) + 1 else -1Program: Pick Up Coupons Google OA Solution in Java
private static int findPrice(int[] coupons) {
Map<Integer, Integer> hmap = new HashMap<>();
int price = Integer.MAX_VALUE;
for(int i=0;i<coupons.length;i++) {
if(hmap.containsKey(coupons[i])) price = Math.min(price, i - hmap.get(coupons[i]) + 1);
hmap.put(coupons[i], i);
}
return price == Integer.MAX_VALUE?-1:price;
}Related:
- Amazon OA Online Assessment 2022 Questions and Answers
- Microsoft Online Assessment 2021 Questions and Solution
