## Amazon Online Assessment

##### Amazon OA2 Questions

Name | Time | Online Judge | Experience Level | Platform | Difficulty |
---|---|---|---|---|---|

Utilization Checks / Autoscale Policy ⭐ |
2021 2020 | Online Judge | Experienced | HackerRank | Easy |

Cutoff Ranks ⭐ | 2021 2020 | Online Judge | New Grad/Intern | SHL | Easy |

Packaging Automation ⭐⭐ | 2021 | Online Judge | N/A | HackerRank | Medium |

Winning Sequence ⭐⭐ | 2021 2020 | N/A | Intern | SHL | Medium |

Rover Control ⭐ | 2021 2020 | N/A | Experienced | HackerRank | Easy |

Multiprocessor System ⭐⭐ | 2021 2020 | N/A | Intern | SHL | Medium |

Transaction Logs ⭐ | 2021 2020 | Online Judge | Experienced | HackerRank | Easy |

Five-Star Sellers ⭐⭐ | 2021 2020 | Online Judge | Experienced | HackerRank | Medium |

Shopping Patterns ⭐⭐ | 2021 2020 | N/A | Experienced | SHL/HackerRank | Medium |

Earliest Time To Complete Deliveries ⭐⭐ |
2021 2020 | N/A | Intern | SHL/HackerRank | Medium |

Count LRU Cache Misses ⭐⭐ | 2021 2020 | Online Judge | New Grad/Intern | SHL | Medium |

Nearest Cities ⭐⭐ | 2021 2020 | Online Judge | New Grad | SHL | Medium |

Fill the Truck ⭐ | 2021 2020 | Online Judge | New Grad | SHL | Easy |

Choose a Flask ⭐⭐ | 2021 2020 | N/A | Intern | SHL/HackerRank | Medium |

Throttling Gateway ⭐⭐ | 2021 2020 | N/A | Intern | SHL/HackerRank | Medium |

Slowest Key ⭐⭐ | 2021 2020 | N/A | Intern | SHL | Medium |

Labeling System ⭐⭐ | 2021 2020 | N/A | Intern | SHL | Medium |

Unique Device Names ⭐⭐ | 2021 2020 | N/A | Intern | SHL | Medium |

Turnstile ⭐⭐ | 2021 2020 | Online Judge | Experienced | SHL/HackerRank | Medium |

Debt Records ⭐ | 2021 2020 | Online Judge | New Grad | SHL | Easy |

Baseball Scorekeeping ⭐⭐ | 2021 2020 | N/A | N/A | N/A | Medium |

Find the Highest Profit ⭐⭐ | 2021 2020 | N/A | New Grad | SHL | Medium |

Items in Containers ⭐⭐ | 2021 2020 | N/A | Experienced | SHL/HackerRank | Medium |

Squared Shortest Distance ⭐ | 2021 2020 | N/A | New Grad/Intern | SHL/HackerRank | Easy |

Find the Max Available Disk Space ⭐⭐ |
2021 2020 | N/A | New Grad | SHL | Medium |

Split String Into Unique Primes ⭐⭐ | 2021 2020 | N/A | New Grad | SHL | Medium |

Fetch Items To Display ⭐⭐ | 2021 2020 | N/A | New Grad | SHL | Medium |

Count Teams ⭐ | 2021 2020 | N/A | New Grad | SHL | Easy |

Subtree: Maximum Average Node/ Highest Tenure ⭐ |
2021 2020 2019 | Online Judge | New Grad | SHL | Easy |

Secret Fruit List ⭐ | 2021 2020 | Online Judge | N/A | N/A | Easy |

Find Related Products ⭐⭐ | 2021 2020 | Online Judge | N/A | N/A | Medium |

Zombie Infection ⭐⭐ | 2021 2020 2019 | Online Judge | Experienced | SHL/HackerRank | Medium |

Top N Buzzwords ⭐ | 2021 2020 2019 | Online Judge | Experienced | SHL | Easy |

Load Balancer ⭐⭐ | 2021 2020 2019 | Online Judge | N/A | N/A | Medium |

Optimize Memory Usage/ Amazon Prime Air Route ⭐⭐ |
2021 2020 2019 | Online Judge | All | HackerRank | Medium |

Find Critical Servers ⭐⭐⭐ | 2021 2020 2019 | Online Judge | New Grad/Experienced | SHL/HackerRank | Hard |

Find Substrings ⭐⭐⭐ | 2020 2019 | Online Judge | N/A | N/A | Hard |

Partition String ⭐⭐ | 2020 2019 | Online Judge | Intern | SHL | Medium |

Maximum of Minimum Values I ⭐ | 2021 2020 2019 | Online Judge | Intern | N/A | Easy |

Maximum of Minimum Values II ⭐⭐ | 2021 2020 2019 | Online Judge | Intern | N/A | Medium |

Connect Ropes (/Merge Files) ⭐ | 2019 | Online Judge | N/A | N/A | Easy |

Min Cost To Add New Roads ⭐⭐⭐ | 2021 2020 2019 | Online Judge | N/A | N/A | Hard |

Min Cost to Repair Edges (Minimum Spanning Tree II) ⭐⭐⭐ |
2021 2020 2019 | Online Judge | N/A | N/A | Hard |

Data Center Critical Connections (Minimum Spanning Tree III) ⭐⭐⭐ |
2021 2020 | Online Judge | Intern | SHL | Hard |

Longest String Made Up Of Only Vowels ⭐⭐ |
2019 | Online Judge | N/A | N/A | Medium |

Movies on Flight/Music Pairs (Two Sum) ⭐ |
2021 2020 2019 | N/A | All | All | Easy |

Treasure Island I ⭐ | 2020 2019 | N/A | Experienced | N/A | Easy |

Treasure Island II ⭐⭐⭐ | 2020 2019 | N/A | Experienced | N/A | Hard |

K Nearest Post Offices ⭐⭐ | 2020 2019 | N/A | N/A | N/A | Medium |

Roll Dice ⭐ | 2020 2019 | N/A | N/A | N/A | Easy |

Min Cost to Connect All Nodes (Minimum Spanning Tree I) ⭐⭐⭐ |
2020 2019 | N/A | N/A | N/A | Hard |

Cell State After N Days ⭐ | 2020 2019 | N/A | N/A | N/A | Easy |

Shopkeeper Sale ⭐⭐ | 2020 2019 | N/A | N/A | N/A | Medium |

Favorite Genres ⭐ | 2020 2019 | N/A | New Grad | N/A | Medium |

Longest String Without three Consecutive Characters ⭐⭐ |
2020 2019 | N/A | N/A | N/A | Medium |

#### Movies on Flight

You are on a flight and wanna watch two movies during this flight.

You are given int[] movie_duration which includes all the movie durations.

You are also given the duration of the flight which is d in minutes.

Now, you need to pick two movies and the total duration of the two movies is less than or equal to (d - 30min).

Find the pair of movies with the longest total duration. If multiple found, return the pair with the longest movie.

e.g.

Input

movie_duration: [90, 85, 75, 60, 120, 150, 125]

d: 250

Output from aonecode.com

[90, 125]

90min + 125min = 215 is the maximum number within 220 (250min - 30min)

#### Treasure Island I

You have a map that marks the location of a treasure island. Some of the map area has jagged rocks and dangerous reefs. Other areas are safe to sail in.

There are other explorers trying to find the treasure. So you must figure out a shortest route to the treasure island.

Assume the map area is a two dimensional grid, represented by a matrix of characters.

You must start from the top-left corner of the map and can move one block up, down, left or right at a time.

The treasure island is marked as ‘X’ in a block of the matrix. ‘X’ will not be at the top-left corner.

Any block with dangerous rocks or reefs will be marked as ‘D’. You must not enter dangerous blocks. You cannot leave the map area.

Other areas ‘O’ are safe to sail in. The top-left corner is always safe.

Output the minimum number of steps to get to the treasure.

e.g.

Input

[

[‘O’, ‘O’, ‘O’, ‘O’],

[‘D’, ‘O’, ‘D’, ‘O’],

[‘O’, ‘O’, ‘O’, ‘O’],

[‘X’, ‘D’, ‘D’, ‘O’],

]

Output from aonecode.com

Route is (0, 0), (0, 1), (1, 1), (2, 1), (2, 0), (3, 0) The minimum route takes 5 steps.

#### Treasure Island II

You have a map that marks the locations of treasure islands. Some of the map area has jagged rocks and dangerous reefs. Other areas are safe to sail in.

There are other explorers trying to find the treasure. So you must figure out a shortest route to one of the treasure island.

Assume the map area is a two dimensional grid, represented by a matrix of characters.

You must start from one of the starting point(marked as 'S') of the map and can move one block up, down, left or right at a time.

The treasure island is marked as ‘X’ in a block of the matrix.

Any block with dangerous rocks or reefs will be marked as ‘D’. You must not enter dangerous blocks. You cannot leave the map area.

Other areas ‘O’ are safe to sail in.

Output the minimum number of steps to get to any of the treasure.

e.g.

Input

[

[‘S’, ‘O’, ‘O’, 'S', ‘S’],

[‘D’, ‘O’, ‘D’, ‘O’, ‘D’],

[‘O’, ‘O’, ‘O’, ‘O’, ‘X’],

[‘X’, ‘D’, ‘D’, ‘O’, ‘O’],

[‘X', ‘D’, ‘D’, ‘D’, ‘O’],

]

Output

3

Explanation

You can start from (0,0), (0, 3) or (0, 4). The treasure locations are (2, 4) (3, 0) and (4, 0).
Here the shortest route is (0, 3), (1, 3), (2, 3), (2, 4).

#### K Nearest Post Offices

Find the k post offices located closest to you, given your location and a list of locations of all post offices available.

Locations are given in 2D coordinates in [X, Y], where X and Y are integers.

Euclidean distance is applied to find the distance between you and a post office.

Assume your location is [m, n] and the location of a post office is [p, q], the Euclidean distance between the office and you is SquareRoot((m - p) * (m - p) + (n - q) * (n - q)).

K is a positive integer much smaller than the given number of post offices.
from aonecode.com

e.g.

Input

you: [0, 0]

post_offices: [[-16, 5], [-1, 2], [4, 3], [10, -2], [0, 3], [-5, -9]]

k = 3

Output from aonecode.com

[[-1, 2], [0, 3], [4, 3]]

#### Roll Dice

Given N dices each face ranging from 1 to 6, return the minimum number of rotations necessary for each dice show the same face.

Notice in one rotation you can rotate the dice to the adjacent face. For example you can rotate the dice shows 1 to show 2, 3, 4, or 5. But to make it show 6, you need two rotations.

Example:

Input: [6, 5, 4]

Output: 2

Rotate 6 to 4, then rotate 5 to 4.

Input: [6, 6, 1]

Output: 2

Rotate 1 to 6, which needs two rotations.

Input: [6, 1, 5, 4]

Output: 3

Rotate 6 to 5, rotate 1 to 5, then rotate 4 to 5

#### Min Cost to Connect All Nodes (Minimum Spanning Tree I)

Given an undirected graph with n nodes labeled 1..n. Some of the nodes are already connected. The i-th edge connects nodes edges[i][0] and edges[i][1] together. Your task is to augment this set of edges with additional edges to connect all the nodes. Find the minimum cost to add new edges between the nodes such that all the nodes are accessible from each other.

**Input**:

n, an int representing the total number of nodes.

edges, a list of integer pair representing the nodes already connected by an edge.

newEdges, a list where each element is a triplet representing the pair of nodes between which an edge can be added and the cost of addition, respectively (e.g. [1, 2, 5] means to add an edge between node 1 and 2, the cost would be 5).

**Example**:

Input:

n = 6, edges = [[1, 4], [4, 5], [2, 3]], newEdges = [[1, 2, 5], [1, 3, 10], [1, 6, 2], [5, 6, 5]]

Output: 7

Explanation:

There are 3 connected components [1, 4, 5], [2, 3] and [6].

We can connect these components into a single component by connecting node 1 to node 2 and node 1 to node 6 at a minimum cost of 5 + 2 = 7.

hint: what’s the time complexity of your algorithm? Can you make the running time O(E * log(E)) by using Union Find?

#### Min Cost to Repair Edges (Minimum Spanning Tree II)

There's an undirected connected graph with n nodes labeled 1..n. But some of the edges has been broken disconnecting the graph. Find the minimum cost to repair the edges so that all the nodes are once again accessible from each other.

**Input**:

n, an int representing the total number of nodes.

edges, a list of integer pair representing the nodes connected by an edge.

edgesToRepair, a list where each element is a triplet representing the pair of nodes between which an edge is currently broken and the cost of repearing that edge, respectively (e.g. [1, 2, 12] means to repear an edge between nodes 1 and 2, the cost would be 12).

**Example 1**:

Input:

n = 5, edges = [[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]], edgesToRepair = [[1, 2, 12], [3, 4, 30], [1, 5, 8]]

Output: 20

Explanation:

There are 3 connected components due to broken edges: [1], [2, 3] and [4, 5].

We can connect these components into a single component by repearing the edges between nodes 1 and 2, and nodes 1 and 5 at a minimum cost 12 + 8 = 20.

**Example 2**:

Input:

n = 6, edges = [[1, 2], [2, 3], [4, 5], [3, 5], [1, 6], [2, 4]], edgesToRepair = [[1, 6, 410], [2, 4, 800]]

Output: 410

**Example 3**:

Input:

n = 6, edges = [[1, 2], [2, 3], [4, 5], [5, 6], [1, 5], [2, 4], [3, 4]], edgesToRepair = [[1, 5, 110], [2, 4, 84], [3, 4, 79]]

Output: 79

#### Favorite Genres

Given a map Map<String, List<String>> userMap, where the key is a username and the value is a list of user's songs. Also given a map Map<String, List<String>> genreMap, where the key is a genre and the value is a list of songs belonging to this genre. The task is to return a map Map<String, List<String>>, where the key is a username and the value is a list of the user's favorite genres. Favorite genre is a genre with the most song.

Example :

Input:

```
userMap = {
"David": ["song1", "song2", "song3", "song4", "song8"],
"Emma": ["song5", "song6", "song7"]
},
genreMap = {
"Rock": ["song1", "song3"],
"Dubstep": ["song7"],
"Techno": ["song2", "song4"],
"Pop": ["song5", "song6"],
"Jazz": ["song8", "song9"]
}
```

Output: ```
{
"David": ["Rock", "Techno"],
"Emma": ["Pop"]
}
```

Explanation: David has 2 Rock, 2 Techno and 1 Jazz song. So he has 2 favorite genres.

Emma has 2 Pop and 1 Dubstep song. Pop is Emma's favorite genre.

#### Longest String Without 3 Consecutive Characters

Given A, B, C, find any string of maximum length that can be created such that no 3 consecutive characters are same. There can be at max A 'a', B 'b' and C 'c'.

Example 1:

Input: A = 1, B = 1, C = 6

Output: "ccbccacc"

Example 2:

Input: A = 1, B = 2, C = 3

Output: "acbcbc"

#### Longest String Made Up Of Only Vowels

Given a string of lower charasters, remove at most two substrings of any length from the given string such that the remaining string contains vowels('a','e','i','o','u') only.

Your aim is to maximise the length of the remaining string. Output the length of remaining string after removal of at most two substrings.

NOTE: The answer may be 0, i.e. removing the entire string.

Example1:

Input:

earthproblem

Output:

2

Example2:

Input:

letsgosomewhere

Output:

3

**More Amazon OA Questions**:

Cell State After N Days

Move The Obstacle

Optimize Memory Usage

Connect Ropes

Prioritize Orders

Shopkeeper Sale

Longest String Made Up Of Only Vowels

Longest String Without 3 Consecutive Characters

Min Cost To Add New Roads

...

#### Get one-to-one training from Google Facebook engineers

##### Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.

Most recent interview questions and system design topics gathered from aonecode alumnus.

One-to-one online classes. Get feedbacks from real interviewers.

##### Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.

New to the ground? - Develop basic coding skills with your own designated mentor.

Days before interview? - Focus on most important problems in target company question bank.