Documentation and analysis for the programming questions asked during Amazon ML Summer School 2022 (Edition 2).
Important
These are the programming questions from Amazon ML Summer School 2022 – Edition 2. ⭐ Star the repository and jump into some practice questions on LeetCode.
Amazon ML Summer School assessments emphasize:
- Problem solving
- Greedy algorithms
- Data structures
- Mathematical reasoning
- Time and space complexity analysis
This repository serves as concise documentation for the questions from Edition 2.
| No. | Question | Primary Topic |
|---|---|---|
| 1 | Three Robots | Greedy, Stack, Lexicographical Ordering |
| 2 | Mean, Median and Mode | Arrays, Sorting, Frequency Counting |
Note
Primary Topics
- Greedy Algorithm
- Stack
- Lexicographical Ordering
- String Processing
There are three robots named Ray, Ben, and Kevin.
Initially:
- Ray contains a string S of length N.
- Ben contains an empty string.
- Kevin contains an empty string.
Two operations are allowed.
Remove the first character from Ray and append it to the end of Ben.
Remove the last character from Ben and append it to the end of Kevin.
The operations continue until both Ray and Ben become empty.
The objective is to obtain the lexicographically smallest possible string in Kevin.
Initially
Ray : abcxyz
Ben :
Kevin :
Move 1
Ray : bcxyz
Ben : a
Kevin :
Move 2
Ray : bcxyz
Ben :
Kevin : a
The order of operations determines the final string, making the problem an optimization task rather than a simple simulation.
Key Observation
Ben behaves exactly like a stack.
- Characters are inserted only at the end.
- Characters are removed only from the end.
At every step, the decision is whether to:
- Continue pushing characters into the stack, or
- Pop characters immediately into Kevin.
The optimal decision depends on whether a smaller character still exists later in Ray.
Therefore, keeping track of the minimum remaining character in every suffix allows optimal greedy decisions.
Approach
The solution combines two ideas.
Always output the smallest possible character as early as possible.
Ben naturally behaves like a stack.
Before processing the string, compute the minimum character available from every suffix.
This allows each decision to be made in constant time.
The overall algorithm performs only one traversal while maintaining optimal lexicographical ordering.
Algorithm
- Compute the smallest character for every suffix of the string.
- Traverse the string from left to right.
- Push every incoming character onto Ben.
- Compare the top of Ben with the smallest remaining character in Ray.
- Pop whenever doing so cannot make the answer larger.
- Continue until Ray becomes empty.
- Finally, pop all remaining characters from Ben.
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(N) |
Tip
Although the problem involves three different strings, the effective data structure is simply a stack, making the solution linear in both time and space.
Using a Robot to Print the Lexicographically Smallest String
https://leetcode.com/problems/using-a-robot-to-print-the-lexicographically-smallest-string/
Note
This LeetCode problem follows the same underlying greedy and stack-based concept and is excellent practice for understanding the optimization strategy used in this Amazon question.
Note
Primary Topics
- Arrays
- Sorting
- Mathematical Computation
- Frequency Counting
Given an integer input1 representing the number of elements and an integer array input2, compute the following statistical values:
- Mean
- Median
- Mode
The returned values for mean and median must be accurate up to six decimal places.
If multiple numbers share the highest frequency, the smallest value must be selected as the mode.
Mean
The mean represents the arithmetic average of all elements.
Mean = (Sum of all elements) / Number of elements
Example
Input
1 2 3
Mean
(1 + 2 + 3) / 3 = 2
Median
The median represents the middle value after sorting the array.
If the number of elements is odd,
Median = Middle Element
If the number of elements is even,
Median = Average of the two middle elements
Example
Input
9 3 5 1 7
Sorted
1 3 5 7 9
Median
5
Mode
The mode is the value that appears most frequently.
When multiple values have the same maximum frequency, choose the smallest value.
Example
Input
5 4 5 3 3
Frequency
3 → 2
5 → 2
4 → 1
Mode
3
Approach
The solution is divided into three independent computations.
- Traverse the array once.
- Compute the total sum.
- Divide the sum by the number of elements.
- Sort the array.
- Return the middle element for odd-sized arrays.
- Return the average of the two middle elements for even-sized arrays.
- Count the frequency of every element.
- Identify the highest frequency.
- If multiple elements have the same frequency, return the smallest one.
Algorithm
- Read the array.
- Compute the sum of all values.
- Calculate the mean.
- Sort the array.
- Calculate the median.
- Count the frequency of every element.
- Select the smallest element having the highest frequency.
- Return the three computed values.
| Metric | Complexity |
|---|---|
| Mean | O(N) |
| Median | O(N log N) |
| Mode | O(N) |
| Overall | O(N log N) |
Tip
The sorting step dominates the overall complexity, making the complete solution O(N log N).
Example 2
N = 5
Array = {41, 18467, 6334, 26500, 19169}
Mean = 14102.200000
Median = 18467.000000
Mode = 41
Important
Amazon did not publish official editorials for these questions. The following LeetCode problems cover the same concepts and are recommended for additional practice.
| Problem | Difficulty |
|---|---|
| Using a Robot to Print the Lexicographically Smallest String | Hard |
| Topic | Practice |
|---|---|
| Sorting | Sort an Array |
| Frequency Counting | Top K Frequent Elements |
| Arrays | Majority Element |
| Mathematical Operations | Find the Pivot Integer |
This repository is intended for educational purposes only.