AI Probably
AI Probably's Blog

AI Probably's Blog

Top 5 DSA Interview Questions asked at Amazon - Part II

Top 5 DSA Interview Questions asked at Amazon - Part II

A walk-through to the most important DSA questions asked in tech giant Amazon (part 2)

Hello!!!
Once again, here we are with the 5 more DSA interview questions asked in Amazon to take you one step ahead in your learning💡 journey. This is the second part of important DSA questions asked at Amazon. If you haven't read Part 1 of Amazon interview questions - Read here first.

1. Loop in Linked List

Question:- Given a linked list, determine if there is a loop or not.
A linked list without a loop looks simply like this:-

ll 11.PNG

While a linked list with loop➰ looks like this:-

ll loop 11.PNG

All that we have to do is to determine the presence of a loop. It is very easy😄 with a dictionary in python . Let us see how:-

pseudo 11.PNG

Working of the code:-

linked list loop dictionary

Writing the code for this question is as easy as understanding the logic:-

loop in linked list

Can you guess the time complexity? Yess!👍 It is O(n).

2. K Largest Elements

Question:- You will be given an array of integers where you have to find the largest k elements in the array.

For example, let us say the array is:-

arr 21.PNG

Then k largest elements would be:-

arr 22.PNG

You might ask, “Sorting works, right?”. Yes, It definitely works.

arr 23.PNG

But what if I say there is a better solution. By saying better, I mean better time complexity.
We know sorting takes O(nlogn) time. But we can use heaps to reduce time⏳ complexity. So let’s dive into the solutions.

Max-heap for finding largest k elements:-
Basically, max-heap is a tree where a parent is always greater than its children. So the root of the tree is the greatest element. pseudo 21.PNG

Let us see how this works for an example:-
After construction of max-heap:-

maxheap

Popping k elements from the heap:-

max heap pop ans 21.gif

Code to implement max-heap:-

k largest max heap sample 21.PNG

We have reversed the sign➖ of elements because the default heap in python is min-heap.
Now let us look at the min-heap. You might be wondering why min-heap. But min-heap makes the job of finding k largest elements faster⏲️.
Let us see the steps involved in this method followed by an example:-

pseudo 22.PNG

Min-heap of first k elements:-

minheap 21.PNG

Once the min-heap is built, we start comparing each element with root as shown:-

min heap 22.gif

To give you an idea, why we are doing this, let us consider one instance in the above simulation of the heap:-

minheap 23.PNG

In our heap, there are k elements, and we know the minimum element among them (3). Now we found another element (8) that is greater than the root, so there are no chances for the root to be among the k largest elements; hence we replace it.
In this way, we build the heap that contains the k largest elements. And the root of the heap is the kth largest element of the array. :-

minheap 24.PNG

The final step is to pop all the elements from min-heap:-

min heap

It is interesting🤩, right? Let us write the code for it.

k largest min heap sample 22.PNG

Which method do you think is easy? (min or max heap?) Let us know in the comments.

3. Construct Binary Tree From Inorder And Preorder

Question:- If you have inorder and preorder traversals, construct the binary tree Firstly what are inorder and preorder traversals? They simply define the order in which the nodes have to be displayed. There are three such traversals.

tree traversals

Before jumping into the code, let us try to guess the inorder and preorder of different Binary Trees.
Example Binary Tree 1:-

binary tree example

Preorder:- 5 2 1 3 4
Inorder:- 1 2 5 4 3
Example Binary Tree 2:-

binary tree example

Preorder:- 5 2 1 3 4
Inorder:- 1 2 5 3 4
Did you observe that the preorder for the above two trees is exactly the same, yet the trees are different? Hence we can not form a tree only based on preorder.
Example Binary Tree 3:-

binary tree example

Preorder:- 1 2 4 3 5
Inorder:- 4 2 1 5 3
Now we are ready to reverse the process, i.e., we are going to construct the binary tree based on traversals.
Recursive steps involved in the construction of tree:-

pseudo 31.PNG

Explanation:-

  • The first element of preorder is the root

  • In inorder, the left part of the root is the left subtree, and the right part is the right subtree

  • Now, we call the function recursively by passing both inorder and preorder of left and right subtrees as parameters.

Recursion is easy once we understand the depth of recursion. Let us build the recursive function in the following steps:-

logic 31.PNG

Given preorder and inorder, we should be able to convert it into a tree:-

preorder inorder tree

Let us see how we can implement our logic:-

ex 32.PNG

First, we search for 1 (1st element in preorder) in inorder and divide inorder into left⬅️ and right➡️ subtree, and then according to the number of elements left side in inorder, we also divide the preorder (3 each) .

ex 33.PNG

Now we repeat🔁 the process for the left and right subtrees.
Putting all this together will give us the code:-

tree preorder inorder

sample 31.PNG

Output tree for the sample input is:-

ex 34.PNG

What next? We have covered linked lists, heaps, trees. Yeah! Its graphs, one of the topics every student preparing for Amazon must know.

4. Word Search Board

Question:- Given a matrix and word, find out if you can form the word from sequentially adjacent characters of the matrix

note 41.PNG

Let us examine the question carefully.
If the given matrix is:-

mat 41.PNG

Word search:-

matrix word search

If the word given is “RABS”, our answer would be yes.
Similarly, we can find words like “AIPROBABLY”, “BLOG”, “DLIP”, “ROB” etc.
And we can not form words like “BAG”, “BOAS”, etc
Our approach:-
We are going to build a graph with each character as a node, and the possible moves (up, down, right, left) from that character will be the edges of the graph.

mat 43.PNG

Then the total graph looks like this:-

mat 44.PNG

Now that we formed the graph, each path in the graph is a possible string. So for the word given, we will find🔍 whether there is such a path in the graph or not.

mat 45.gif

This can be done recursively by starting from the node that matches with the first1⃣ character of the word. Then, we will move character by character to form the string using the possible moves.
Here is the code that implements the above logic:-

search matrix word sample 41.PNG

5. Wave Array

Question:- Given an array of integers form a wavy array A wavy array is similar to:-

wave.PNG

The array should increase⬆️ from 1st to 2nd, decrease⬇️ from 2nd to 3rd and then increase⬆️ from 3rd to 4th element and so on.
For example, if the given array is:-

arr 51.PNG

The wavy array is:-

wave array

Let us see how we can obtain this wavy array:- Initially, let us sort the array:-

arr 53.PNG

Now we simply exchange the adjacent values, and that gives us the wavy array as shown:-

wave 51.gif

And this is how the code looks:-

wave array code sample 51.PNG

We are delighted to extend our support and hope your efforts get paid off👍. All the best!!

Also read: Top DSA Questions asked at Google

 
Share this