Round 1
Questions:
Question 1
Amazon recently launched a new game, Fruit Crush! In this game, you are allowed to choose two dissimilar fruits and crush them. Each type of fruit is represented as an integer in an array. Formally, you can choose any two unequal integers in the array and delete them.
Given an array fruits of size n, return the minimum possible number of fruits left after performing the given operation any number of times.
Example
- Input: n = 5,
fruits = [3, 3, 1, 1, 2] - Explanation:
- Crush fruits 1 (banana) and 2 (pineapple) first.
- Then crush fruits 1 (banana) and 3 (orange).
- Only fruit 3 (orange) remains in the array.
- Output: 1
Function Description
Complete the function getMinFruits in the editor below.
- Parameters:
int fruits[n]: an array of integers representing the fruits.
- Returns:
int: the minimum possible count of fruits left after performing the operations.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ fruits[i] ≤ 10^5
Question 2
Amazon Games has recently launched a new game involving dominoes. The game consists of n dominoes, where the i-th domino has a size domino[i]. The order of the dominoes is defined as the length of the longest strictly increasing subsequence (LIS) of the sizes of the dominoes.
An associated array, remove, contains n integers from 0 to n-1. In the i-th move, the player can remove the domino numbered remove[i].
Given the arrays domino and remove, find the maximum number of moves that can be made such that the order of the remaining dominoes is at least equal to a given integer min_order.
Example
- Input:
- n = 6
domino = [1, 4, 4, 2, 5, 3]remove = [2, 1, 4, 0, 5, 3]min_order = 3
- Explanation:
- Move 1: Drop domino[2] (size 4). Remaining dominoes: [1, 4, 2, 5, 3]
- Move 2: Drop domino[1] (size 4). Remaining dominoes: [1, 2, 5, 3]
- Move 3: Drop domino[4] (size 5). Remaining dominoes: [1, 2, 3]
- Move 4: Drop domino[0] (size 1). Remaining dominoes: [2, 3]
- Move 5: Drop domino[5] (size 3). Remaining dominoes: [2]
- Move 6: Drop domino[3] (size 2). No dominoes left. The longest increasing subsequence (LIS) after each move is:
- After Move 1: LIS = [1, 2, 5] (length 3)
- After Move 2: LIS = [1, 2, 3] (length 3)
- After Move 3: LIS = [1, 2, 3] (length 3)
- After Move 4: LIS = [2, 3] (length 2)
- After Move 5: LIS = [2] (length 1)
- After Move 6: No dominoes left. The maximum number of moves that can be made while keeping the order (LIS) at least 3 is 3.
- Output: 3
Function Description
Complete the function getMaxPoints in the editor below.
- Parameters:
int domino[n]: an array of integers representing the sizes of the dominoes.int remove[n]: an array of integers representing the dominoes to be removed in each move.int min_order: the minimum required order (LIS length) of the remaining dominoes.
- Returns:
int: the maximum number of moves that can be made while maintaining the order of the remaining dominoes at least equal to min_order.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.