Amazon | OA

Round 1

Questions:

Question

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 the given operation is performed any number of times.

Example:

n=5
fruits = [3, 3, 1, 1, 2]

Fruits 1 (banana) and 2 (pineapple) can be crushed first, followed by numbers 1 (banana) and 3 (orange). Only 3 (orange) remains in the array, hence the answer is 1.

Function Description: Complete the function getMinFruits in the editor below. getMinFruits has the following parameter(s): int fruits: array of n fruits

Returns: Int: the minimum possible count of fruits left

13/15 test cases solved

public static int getMinFruits(List<Integer> fruits) {
        Stack<Integer> stack = new Stack<>();

        for (int fruit : fruits) {
            if (!stack.isEmpty() && stack.peek() != fruit) {
                stack.pop(); 
            } else {
                stack.push(fruit);
            }
        }

        return stack.size();
    }

Candidate's Approach

The candidate used a stack to keep track of the fruits. For each fruit in the array, if the stack is not empty and the top of the stack is different from the current fruit, the candidate pops the stack (removing the two dissimilar fruits). If they are the same, the candidate pushes the current fruit onto the stack. The size of the stack at the end represents the minimum number of fruits left.

Interviewer's Feedback

No feedback provided.

---

Question

The team at an Amazon warehouse is given a task to optimize the packing of a set of boxes with different IDs. Each box is labeled with an ID, and these boxes are currently arranged in a single row from left to right, where the id of the ith box is represented by the string s_id consisting of digits from 0 to 9 inclusive. To make the packing more efficient, the team can perform the following operation any (possibly zero) number of times:

• Choose an index i and remove the digit s_id[i]. Then insert the box with ID min(s_id[i] + 1, 9) on any position at the beginning, at the end, or in between any two adjacent boxes in the row.

Given a string s_id, find the lexicographically minimal string of boxes using these operations. Note: A string X is lexicographically smaller than a string Y of the same length if and only if in the first position where X and Y differ, the string X has a smaller digit than the corresponding digit in Y.

Example: Given,

s_id = "26547"

Delete and insert in the 4th position of the string, resulting in "24677". Hence, the string returned is "24677". It can be proved that this is the lexicographically minimal string possible.

Function Description: Complete the function getMinimumString in the editor below. getMinimumString has the following parameter: string s_id: the ID of the boxes

Returns: string: the lexicographically minimal string.

15/15 test cases passed

import java.util.*;

public class Solution {
    public String solve(String s) {
        int n = s.length();
        int[] last = new int[10];
        int[] cnt = new int[10];
        
        Arrays.fill(last, -1);
        
        // Find the last occurrence of each digit in the string
        for (int i = 0; i < n; ++i) {
            last[s.charAt(i) - '0'] = i;
        }
        
        StringBuilder ret = new StringBuilder();
        int left = 0;
        
        // Process each digit from 0 to 9
        for (int i = 0; i <= 9; ++i) {
            int m = last[i];
            // Process the string from the left until the last occurrence of current digit
            while (left <= m) {
                int j = s.charAt(left++) - '0';
                if (i == j) {
                    cnt[i]++;
                } else {
                    cnt[Math.min(j + 1, 9)]++;
                }
            }
            
            // Append the required count of current digit to the result string
            char c = (char) (i + '0');
            for (int j = 0; j < cnt[i]; ++j) {
                ret.append(c);
            }
        }
        
        return ret.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String result = solution.solve("34892");
        System.out.println(result);  // Example test case
    }
}

Candidate's Approach

The candidate implemented a solution that tracks the last occurrence of each digit in the string. They used two arrays to count occurrences and to store the last index of each digit. The candidate processed each digit from 0 to 9, adjusting counts based on the digits encountered and ensuring the result string is built in a lexicographically minimal way.

Interviewer's Feedback

No feedback provided.

---