Due to Confidentiality Clause questions are not the exact same as the real interview but with similar difficulty level
I applied at Amazon Off Campus
through an Online Coding Cotest
named Amazon WOW
The Contest consisted of 20 MCQs
and 2 Coding Questions
After clearing that round
I got an Interview call from Amazon
And following is going to be my interview experience with Amazon
Good Morning Anshika!
Good Morning Sir!
So give me your introduction
Sir I am currently doing B.Tech
from Madan Mohan Malviya University of Technology
in Computer Science Engineering
Sir apart from my curriculum
I have done various courses in Machine Learning
And also I worked at Coding Ninjas
as a Teaching Assistant
My job there was
to debug the code of students
as well as to help with their projects
I have also done  a certification programme
from NPTEL
which was conducted by IIT Madras
in design & analysis of Algorithms
I was in top 5 Percentile
of the students who did that course
Sir apart from studies I am pretty much
interested in sports
Okay, that's cool which sports do you play?
Sir I am very much into athletic sports
like Races, Short put, Long jump
All of this
Okay so now,
I have pasted the question in the Code Editor
Can you see that?
Sir there is a confusion
Like what we will be printing
when there is no greater element in the right side
Good question, Print -1
Sir I can do it easily with N Square approach
Should I say that?
Do it using O(N)
Okay
Sir I can use stack data structure here
to implement it
Like what I will be doing is
I will start iterating from forward
like from i = 0
And I will push the element in the stack
Like initially we will push element 4
for input 1 I am explaining here
We will push element. 4 in the stack
Then when it comes to 5
We will just compare it with top of stack
Like we can see this number 5 is greater than 4
So what I can do is I can pop my 4
And I can just write there 4 corresponding
element is 5
and now in my stack there will be 5
Now when it comes to 2
I compare 5 and 2. 2 is smaller than 5
So I will just push it in the stack, 2 also 1 also
Now when it comes to 25
When we compare it with 1
We just see that 25 is greater than 1
So we pop out 1 and write 25
Again pop out 2 and write 25
Similar with 5
And now the stack will only be left with 25
For that we can write -1
Sir will this work
It's necessary to maintain the order
Okay
We can use the same stack
And we can start iterating from backwards
Sir what I will be doing is
I will be inserting my last element in the stack
And then what I can do is I can always
compare my top element with arr(i)
If my arrow 5 is greater than top element
than I can simply pop the stack
Once this whole process will be done inside while
Once when it is done
We can check that if our s is empty
I mean if stack is empty we can write
We can write answer to be -1
Else the answer will be stack top;'
And after doing all this operation
we can simply go and push
our arr(i)
Okay so just code it
Sure Sir
I am done, now it will work fine
So I have put another question in the
code editor, Please look into it
Yes Sir
Okay
Sir in which all directions
we can traverse like that is not mentioned
in the question
Okay all 8 Directions
Left, Right, Up, Down & Diagonally
Okay Sir
Sir I can do this question using either DFS or BFS
Which one are you comfortable to write?
Sir DFS
So let's write using BFS
Okay Sure Sir
Sir should I code it?
Or discuss the approach with you
Okay code it
Okay Sir
Yes Sir its. done
Okay you have not written the bounding condition
properly
Okay
Yes Sir Yes Sir you are right
I forgot to mention all the bounding conditions here
I am just writing it down
Yes Sir it's done. Can you see that now Sir
Ya
Okay What is the Space Complexity?
Sir it will be O (N^2)
Okay
I am done for this round
Any question you would like to ask?
Yes Sir Any feedback if you can give me
based upon today's interview
Sorry we cannot
The HR will mail you the feedback
once your interview is done
Its Okay, Thank you Sir
Hi Anshika! Please tell me about your projects
Sir I have made various projects in Machine Learning
Some of my projects are
Facial recognition using Neural Network
And text classification using self implemented
Naive Bayes Classifier
Alright!
So Let's discuss your second project
Sir in this project I have used
20 Newsgroup Dataset
And I have cleaned & processed them using NLP
As well as Sir, I have implemented
my own Naive Bayes Classifier
And have compared the result
with the Naive Bayes Classifier implemented in SKlearn
with my own
And also
have shown through the output
that my classifier is working
as good as the actual Sklearn Classifier
Okay
Can you tell me the difference between Stemming & Lemmatisation
Yes Sir
Both are used to give us root words
But Lemmatisation based upon
part of speech is more powerful than Stemming
which is actually rule based
And what are the difficulties you faced while implementing it
Sir the first difficulty I faced during the
implementation was, while i was trying to
multiply various features independent results together
My answer actually tended to become zero
Like what was happening was the numbers were very small
So the answer was becoming zero
So this was one difficulty was there
So what I did was
I removed that multiplication to Log Addition
And then
Like if my answer is 0.001
Then I was getting that perfect answer
Not perfect like
It was okay I was getting that
0.001 or  0.012 like
The second thing which I implemented was Laplace correction
It was 1 difficult part because
While I was trying to actually figure out
there were some cases
which were not in the training data
When that cases came in testing data
my outputs were getting wrong & wrong
So here I did Laplace correction
And automatically now my outputs are coming correct
We are done with the projects Anshika
Can you tell me what is Deadlock?
Sir Deadlock is a situation
when 2 or more processes wait for each other to finish
And none of them actually get finished
Like an example of 2 trains which are approaching towards each other
This is an example of Deadlock
So the necessary conditions for Deadlock are
Mutual Exclusion, Hold & Wait
Circular Wait & No Preemption
And what is thrashing
Sir thrashing is a condition
when the number of page faults are more than
actually the executing transactions
Heard about Balady's Anomaly
Sir when we increase the number of page frames
Usually the page faults decreases
But in this Anomaly what happens that
when you increase the page frames
still the number of page faults are getting increased
It happens in First In First Out replacement algorithm
Okay Anshika Let's code now
So I am going to paste a code in front of you
Okay Sir
Can you see this?
Yes Sir I can see the code
Alright Go for it
Sir 1 idea is coming to my mind
We will be doing the inorder traversal of BST
And we will store that in order
traversal in an array and then we can print the Kth element from that
Also if you want to avoid the array
We can go for just the count
And from that count only we can print the Kth Element of the array
Space & Time Complexity
Sir Time will be O(n)
And if use count then space can be O(1)
So optimise it
Okay Sir
Sir is it allowed to change the structure of the tree
Yes you can do that
Okay Sir
So what I will be doing is
I will be storing the left count
Already in the node like we can make the
class structure like that and we can store the left count
And then I will be going to a node I will just check
that whether this is the. Kth node or not
If it is Kth node we can print it
And otherwise we can take these both cases
One case it will go to root right
and the other case it will go to root left
Alright Go ahead and code it
Sure Sir
Sir it is Done
Sir should I need to write the insert function here
No just write the structure of the tree
Okay Sir
Sir is this fine now
This is fine
So let us move to the next question
Can you see this Anshika?
Yes Sir I can see the question
Alright! So go for it
Sir I can solve this question using O(N^2)? approach
No optimise it
Okay Sir
Sir what we can do here is
We can convert 0 to -1
And this question will become same as
the largest contiguous Sub Array having
sum equal to 0
And Sir for that
we can use HashMap
which will be storing the sum
And corresponding index in it
Can we do it like that Sir?
With the help of that method
Out time complexity will be obviously optimised to O(n)
Alright Go ahead
Sir should I explain you the approach or directly code it?
Directly code it
Okay Sure Sir
Sir I have written the code
I think you will get a wrong answer because you
missed out a very important part in it
Okay Just give me some time sir, I am just figuring it out that
what mistake I have done here
Just a hint you have not taken into consideration
Sub Array which will start from the initial position
Okay you are right Sir
I have just missed out this ver y important part
in my code
Like I have not written this part
m(0) = -1 like for my HashMap
Obviously the first sum = 0 should be -1
Now it is correct Sir now it will work fine
Alright Thank you Anshika, we are done with this round
Thank you Sir, Thank you So much
Hi Anshika!
Hello M'am
Let's get started, what are ACID Properties
Okay
M'am from ACID Properties
A actually stands for Atomicity
which means
that wither the transaction takes place once
Or does not happen at all
consistency means that the data should be consistent
before & after the transaction runs
Similarly I is for Isolation that means
that at a time
there could be multiple transactions running
But they should not
affect the working of each other
Similar is with Durability which means
that the changes which we have made
on the database should be permanent
It cannot be revoked by itself
Anshika I have pasted the question can you see it?
Yes M'am I can see the question
M'am one approach which is coming to my mind is that
What I will be doing
I will compare every K Node
that is head of every linked list
and get the node with the smallest value
Then the node with the smallest value
for that what I will do is head = head.next
Like this I will extend my final sorted
Linked List with the selected nodes
Keep on taking nodes one by one
And like that we will be getting the FInal sorted Linked List
This approach
will be M'am taking n,k approach
where n is the total elements in the Linked List
and k =  the given number of Linked List
Okay so is their any other approach
M'am I can also do one thing
Like for the comparison of every K Node
I can directly use priority queue
And that will give me the short I mean the
smallest node in Log(k)
So my complexity will also become n Log(k)
Okay Code it
Okay M'am
Yes M'am Now I have done the code
By default what is the Priority Queue
Min or Max heap
Min Heap
Okay yes I need to add here
I just forgot to write down a very important condition
Just a minute M'am I am adding it here
Okay
It's wrong Anshika
Okay
Okay Yes M'am how can I forget that we need
to make a comparator class
and not greater
M'am I am doing it, I am correcting my code
Yes M'am I have coded now
Ya, this is correct
Okay I am done now. Any question?
Yes M'am
I wanted to know
How has your role changed
since you have joined Amazon?
I joined as a Developer
And now I am a Senior Manager here
The journey with Amazon has been awesome
Great to know M'am, Great to know
Thank you Anshika
Thank you so much M'am
Hi Anshika!
Hello SIr!
And why do you want to join Amazon?
Sir I am much influenced
by the vision of Amazon
to be the most customer obsessed company in the world
like I personally believe it a lot
And also I have seen the results of this
Like how at my personal level
Amazon has lived upto that
customer obsessed policy
So what I feel like joining company like this
and helping them in their vision
Like this would be one thing
I personally would like to contribute
As well as Sir, I have talked to
with my Alumnis and other Networks I have around
about the working culture, about the learning curve
at Amazon
And I am like
very much excited & happy to see that
How they have personally grown
and as well as how the company
And how other work culture is around in the company
And how is your experience as Teaching Assistant at Coding Ninjas?
Sir it was great
like I learnt very minute details
while debugging the codes of the students
which i could have not done
without this TAship
Any specific instance you can give?
Like a very minute detail
a student once asked me a doubt
And with the help of that doubt I realised
that arrays are actually passed by reference
in our code
but vectors are not
For vectors to be passed by reference
we have to use that ampersand
Do you know LRU Cache?
And can you explain?
Yes Sir
Sir LRU Caching Scheme is used to remove
the least recently used frame
when the cache is full
And when a new page is referenced
And that is not there in cache
And can you tell me how to implement it
Yes Sir!
Sir we can use here a Queue
which can be accessible from both front & rear
For that we can either use D queue
or we can use Queue using doubly Linked list
Implemented using doubly linked list
Sir this queue the size of queue
will basically tell us the number of frames
which are currently in our memory for now
And the second data structure we will use is Hash Map
In that
the key will be page number
and the corresponding value will be
the address of that page
in the corresponding Queue Node
Sir what we will do basically is
suppose a page is referenced
And that page is actually present in that queue
How we can find it?
We can find it using directly HashMap
If it is not present in the queue
then we can see  that whether the size of Queue
is full or not
If size of Queue is not full
we can simply insert it  in the queue
and correspondingly we can make changes in the HashMap
But if it is already inserted in the Queue
then we can remove it from the Queue
like we can take front end for the insertion
and rear end for the deletion
And then we can also update this change
inside our HashMap
Alright can you code this for me?
Yes Sure sir. i will code it
Yes sir I have written the code now
Okay
I am done with the interview
and you can wait for the results now
Okay Sir till when can i expect my final results
In the next 5 working days
Okay Thank You so much Sir
Thank you
Hope you like this video
and got an insight of
how the actual interview looks like
So in order to get more valuable content like this
you can follow the channel of RU buZZIng
as well as to get more technical contents
You can follow me over LinkedIn or Instagram
My LinkedIn & Instagram Handles are given in the description page
Thank you
