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:-

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

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:-

Working of the code:-

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

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:-

Then k largest elements would be:-

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

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.

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

Popping k elements from the heap:-

Code to implement max-heap:-

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:-

Min-heap of first k elements:-

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

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

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

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

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

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.

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

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

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:-

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:-

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:-

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

Let us see how we can implement our logic:-

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

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

Output tree for the sample input is:-

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

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

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.

Then the total graph looks like this:-

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.

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:-

5. Wave Array

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

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:-

The wavy array is:-

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

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

And this is how the code looks:-

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

Enroll now in our Data Structure & Algorithms course for beginners

Also read: Top DSA Questions asked at Google