Amazon Data Structures & Algorithms Interview Questions

Getting a job at Amazon is a dream 💭 that you would love to achieve 🏆. Being an online retail giant, Amazon’s recruitment process is a tight race. You will need to solve their unique Data Structure and Algorithms questions to stand out from the competition 🙋.

This blog will take you through the Top 5 Data Structure and Algorithm questions asked in Amazon interviews. Though 5 is a small number, these questions cover a wide range of topics in DSA, which are explained using python codes for simplicity.

Enroll now in our Data Structure & Algorithms course for beginners

1. Jump game array

Question:- You will be given an array of non-negative integers, where each array element represents the maximum length of the jump from that position. By starting from the 1st element, you have to find out if you can reach the end of the array or not.

Here if you are in 1st position, you can jump 1 step ( from 1 to 2). For the 2nd position, the maximum length of the jump is 2 ( you can either jump 1 or 2 steps). For 3rd, it is one and so on.
Solution:-
Let us look at a few test cases and check if we are able to reach the end or not.

Since the first element itself is 0 here, we can’t jump anywhere. ( so we will just sit 🪑 there )
Apart from arrays that start with ‘0’, there are cases where we end up at zero from all the possible paths, as shown below.

What if there are no 0’s in the array? We can definitely reach the end 🏁. ( even for the minimum case [1, 1, 1, 1, 1] ).
Can you think of cases where there are 0’s, but we can still reach the end?
Here are a few:-

We can jump🦘 over zeroes if the number(s) before 0(s) can reach beyond them.
Hence we keep track of maximum reach, and if we encounter a zero thereafter, that means we can not move forward after that, so we return false.
Let’s implement the same logic:-

Sample input:- 2 2 0 1 2 0 1 1 4 Sample output:- True

Try debugging the code yourself and post your doubts through comments 💬 if any.

Pandas techniques used in Data Science...

2. Best time to buy and sell stocks

Question:- Say you have an array where each element represents the stock price for that day. Design an algorithm to find the maximum profit.
Note:- You can not engage in multiple transactions at a time (i.e., Complete one transaction before starting another).
Explanation:-

Consider the above array. Here, the stock price on day 1 is 100 ( whether you buy or sell it). For day two the price is 400, for 3rd day it is 500 and so on.

For example, if you buy the stock on day 1(for 100), sell that stock on day 2(for 400). Then the profit would be 300 (400 - 100). Similarly, if you buy a stock on day 4 and sell it on day 5, the profit would be 100 (300 - 200). What if we buy a stock on the 3rd day and sell it on the 4th day? It is a loss of 300 (500 - 200). Hence we do not perform such transactions.

Summing up all the facts together:-
Given an array ‘A’, we need to find the maximum value of A[j] - A[i] where j > i. We can achieve this simply by comparing the adjacent values.

Let us see how:-

If we buy a stock on the 1st day and sell on the 3rd day, the profit is 400 (500 - 100).

We will get the same profit by performing two transactions.

• Buy on day 1 and selling on day 2.
  

• Buy on day 2 and selling on day 3.
  The profit is (400 - 100) + (500 - 400) = 400.
  

Hence our approach is to check if we can obtain profit for all the adjacent prices. ( if the difference between a value and its previous one is greater than 0). If yes, we will add this profit to the total profit.

Now that we figured out what is expected out of the problem. Let’s start coding.

Sample input:- 100 400 500 200 300 Sample output:- 500
This is how we get 500:-
(400 - 100) + (500 - 400) + (300 - 200) = 500.

After seeing the code, try to guess the outputs for the following test cases:-

Output:- 865

Output:- 0 ( profit is not possible if the array is in decreasing order)

Output:- 350 (160 + 50 + 60 + 80)
Great job 🎉! Let’s move to the next question.

3. Clone a graph

Question:- If you are given a reference of a node in a connected undirected graph, return a deep copy (clone) of that graph.

In simple words, we just have to create the exact replica of the original graph.
If the original graph is:- The cloned graph is:-

Here each node in the graph contains a value and list of neighbors. We will be given the first node, and we must return the copy of the given node as a reference to the cloned graph.

Rules:-

• Do not return the original graph.
  
• No. of vertices and edges remain the same.
  
• Make the same connections as the original graph.
  
  

Solution:-
What comes to your mind🧠 when you think of graph traversals? It’s Breadth-First Traversal and Depth First Traversal right. Yeah, these are the most commonly used graph traversal techniques, and we’re gonna use one of them to tackle this problem.
We are using Depth First Traversal here as it is quicker and makes it easy to find child nodes in a graph. As we perform Depth First Traversal on the graph, we create a copy of each node and store it in a dictionary to avoid cycles.
This is how the keys are mapped to nodes (using a dictionary). And the node and list of neighbors are encapsulated (using class).

We only visit the nodes that are not present in the neighbors list. This helps in avoiding cycles and also storing nodes and their neighbors in sequential order.
Each node has a list of neighbors; this data is then used to create a replica of the original graph.
Here is the code that takes the node of the original graph as a parameter and returns the node of cloned graph:-

4. LRU Cache

Question:-
Design and implement LRU cache, which supports get and set operations.
Solution:-
Before we jump into the solution, let us understand every term in the question.
Assume that initially, we have many page requests and cache (memory) that can hold only some pages.
Let us say our cache size is ‘n’, which means cache can accommodate ‘n’ no. of pages. And initially, the cache is empty. Then we start adding one page after another.

After some point, the cache will be full, but the page requests still keep coming.

In that case, we need to replace the ‘least recently used’ page with the new page in the LRU cache. This is performed by set() operation.
Among all the elements, the least recently used is ‘1’. If we encounter another page, say ‘5’, remove ‘1’ and insert ‘5’.

When our cache is full, there are two possibilities for the new page, they are:-

• The new page is not present in the cache ( as shown above). We call this case a page fault. To handle this, set() operation is used.
• The new page is present. This case is known as a hit. get() operation handles hit.

Details of get operation:-
To check if the page is present or absent, we use the method get. If the page is not present in the cache, get returns -1. Then we call the function set to replace the least used page.
If the page is already present, we send the page to the end of the cache, by making it the most recently used page. Let us say our cache contains [ 1, 2, 3, 4], and then we encounter ‘2’. Then ‘2’ is sent to the end, making the cache [ 1, 3, 4, 2].

So whenever a get operation happens, we need to move that element to the end. To do that, we maintain an ordered map 📍 which stores the pages in the most recently used order.
Let us put this logic into code.

Now that we have seen questions from different concepts, let’s look at a question based on a math concept - permutation.

5. Kth permutation of a sequence

Question:-Let’s say we have a sequence of natural numbers from 1 to n. Given the value of n, find the kth permutation sequence.
Solution:- Sequence of natural numbers:-

For example, if n=3. 6 sequences are possible.
And if k=4, we have to find the 4th subsequence.

Our answer would be “231”.

How do we find the kth permutation?
Generating all permutations won’t help here because of the time complexity.
Instead, we use recursion and math to figure out the numbers depending on the position.

What is the role of position in finding kth permutation?
Let’s take the help of the above example to answer this question.
In the above example (n=3), the first two sequences start with ‘1’, the next two with ‘2’, and the last two with ‘3’.

If n is four, there would be six sequences ( (4-1)! i.e., 3!), each starting with 1,2,3, and 4.

Hence we can say that there are (n-1)! sequences that start with a specific number. What about the second number? Simple, it is (n-2)!.

In this way, we will find the position of the number using the formula k /(n-i)!, where i is the position and k is zero-based. And as we move from n-1 to 0, we keep removing the numbers which are already used.

For example, when n=3 and k=4. This is how the values change for each iteration.

Here👇 is the code that implements the above👆 logic:-

Sample input:- n = 5, k =16 Output:- 14352

Hope this blog helps you to understand the interview questions that have been asked for Data Structure and Algorithm for getting jobs on Amazon. Also, check out our YouTube channel.👉 where we post videos about Data Science, Python, Django and many more.

Also read - Top 5 DSA interview questions asked at Google