## Amazon Online Assessment

##### Amazon OA2 Questions

Zombie Infection ⭐⭐ Online Judge MediumOptimize Memory Usage ⭐⭐ Online Judge NEW Medium

Find Substrings ⭐⭐⭐ Online Judge Hard

Partition String ⭐⭐ Online Judge Medium

Top N Buzzwords ⭐ Online Judge Easy

Load Balancer ⭐⭐ Online Judge Medium

Find Cirtical Servers ⭐⭐⭐ Online Judge Hard

Maximum of Minimum Values I ⭐ Online Judge Easy

Maximum of Minimum Values II ⭐⭐ Online Judge Medium

Longest String Made Up Of Only Vowels ⭐ ⭐ Online Judge Medium

Subtree: Maximum Average Node ⭐ Online Judge Easy

Connect Ropes (/Merge Files) ⭐ Online Judge Easy

Min Cost To Add New Roads ⭐ ⭐ ⭐ Online Judge Hard

Min Cost to Repair Edges (Minimum Spanning Tree II) ⭐ ⭐ ⭐ Online Judge Hard

Data Center Cirtical Connections (Minimum Spanning Tree III) ⭐⭐⭐ Online Judge Hard

Movies on Flight ⭐

Treasure Island I ⭐

Treasure Island II ⭐ ⭐ ⭐

K Nearest Post Offices ⭐ ⭐

Roll Dice ⭐

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

Cell State After N Days ⭐

Move The Obstacle ⭐

Shopkeeper Sale ⭐ ⭐

Favorite Genres ⭐

Longest String Without 3 Consecutive Characters ⭐ ⭐

(⭐ - difficulty)

#### 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.