1 like 0 dislike
395 views
in Interview-Experiences by
recategorized by | 395 views

9 Answers

1 like 0 dislike
I got selected!!!

After the online coding test, I got shortlisted for virtual interview.

In the interview , I was asked 4-coding problems :

1)Find the minimum number of adjacent swaps needed for making a string palindrome.

2)A standard binary tree problem.

https://practice.geeksforgeeks.org/problems/left-view-of-binary-tree/1#

3)A standard hashing problem.

https://www.geeksforgeeks.org/longest-subarray-having-maximum-sum/

4)A standard dp-problem.

It was very similar to this : https://atcoder.jp/contests/dp/tasks/dp_c
by
0 like 0 dislike

Round 1:

  1.  Tell me about yourself.
  2.  Trapping Rain Water:Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
  3. Print left view of a binary tree.

    Discussion : I gave two approaches one with DFS and other with level order traversal.
    He asked to compare two approaches and implement the efficient one. DFS is the efficient one because in level order, you need to store all the nodes at each level, some of them may not be a part of the left view of BT.

Round 2:

  1.  Tell me about yourself.
  2.  Find sum of n elements after kth smallest element in BST. Tree is very large, you are
    not allowed to traverse the tree.
    Discussion : Since the array traversal is not allowed so we need to do some preprocessing over the tree, something like storing sum of all its predecessor nodes.For finding kth smallest element, use order statistics approach:
  3.  Given a sorted array which has been rotated n number of times. Find the value of n. It is similar to below post where you need to find only the pivot element. If you have the Index of pivot element, you can get the number of times the array is rotated.

Round 3:

  1. Count ways to reach nth stair.

    It is similar to fibonacci series. Interviewer asked various ways to implement the same -Recursion, 1-D array, with 3 variables and complexity of each.

  2. Design recommendation engine.
    It’s like auto suggestion. I gave the trie approach. The interviewer seemed fine with this approach and asked me to write full code with time and space complexities. Implementation of Tries:
    Trie | (Insert and Search)

Round 4(Managerial Round – Over video call)

  1. Tell me about yourself.
  2. Current work
  3. Which project you liked working the most.
  4.  Any case where you had conflict with your manager.
  5.  Any idea/technology suggested by you to your team which then got implemented and worked out.
  6.  Any case when you had to work out of your comfort zone.
  7.  The most critical feedback received from your manager/team members.
  8.  What do you do to enhance your technical knowledge apart from your project work.
    And many more.

Round 5(Final Round – Telephonic)

 

 

 

  1. Initially I was asked questions about the work I had done, the projects I did and some managerial questions.
  2. Then I was given a coding problem to solve. They use Collabedit tool in phone screen interviews where the same screen is shared by both interviewer and interviewee.
    Ques : Print all the non-repeating words out of two given sentences.
    Eg. Statement 1: I have a blue pen.
    Statement 2: I got a red pen.
    Output : have blue got red
    Discussion : I suggested the hashing approach. The interviewer asked to implement the same.

Points to take care:

  • You must know how to calculate time and space complexities
  • In each round they ask you about the project you recently did/ the project you liked working most/ most challenging work etc- so you should be prepared well for at least one project with in-depth details.
  • Start with the naive approach for each question asked and then proceed with solutions with better space and time complexities.
  • No need to waste time reading about Operating Systems, Networking, DBMS etc. They only care about the projects you did and your coding skills whether you cover all the edge cases while writing code, know time and space complexities, have better approaches for solving same problem and so on.
by
0 like 0 dislike

1st Round
Q1 – Clone a graph. ( Similar Question -> https://www.geeksforgeeks.org/clone-linked-list-next-arbit-pointer-set-2/)
Basically while cloning, when you create a new node in the cloned graph, have a hashmap which maps the old node to new node.
So in the hashmap key = old node, value = new node.

Q2 – Given an array of numbers, for each number print the first number to it’s left which is greater than the current number.

    Example
        Input -> 5,3,2,4,8,6
        Output-> -1, 5,3,5,-1,8
    Use stacks. Simple O(n) solution. 

2nd Round
Q1 – Find the row number according to the excel nomenclature –> (the opposite of this, https://www.geeksforgeeks.org/find-excel-column-name-given-number/)

 

 

 

    i.e given Z, Output -> 26
    Given AX, Output -> 50 

Q2 – Find the number of islands in a 2d Array -> https://www.geeksforgeeks.org/find-number-of-islands/

3rd Round(Hiring Manager)
Q1 – Given a number in words, print the number.

    Example 1) Input - "One Hundred and Five", Output should be "105" 
    Example 2) Input - "One Thousand and two hundred", Output should be "1200"
    Example 3) Input - "Twelve hundred", Output should be "1200"
    Example 4) Input - "Five Lacs", Output should be "500000"
    Example 5) Input - "Five Hundred Thousand", Output should be "500000" 

There were a lot of edge cases, and discussion with regards to this. ( I took a lot of time and the manager did not seem to pleased.  )

Q2- In a sorted array, find two numbers who’s difference is k.

Given -> 1,2, 3,4,7,8,9,11 and k=7
Ouput -> 1,8 or 2,9, or 4,11 (Print any one) 

https://www.geeksforgeeks.org/find-a-pair-with-the-given-difference/

A lot of questions as to Why Amazon, Why do you want to leave so early.

4th Round(Bar Raiser)
Q1 – Given a sorted array find a number. (Simple Binary Search)
Now consider repetitions and find the left most occurrence. (Binary Search to first find number, then again Binary Search to find left most occurrence)
Similarly find the right most occurrence. (Binary Search to first find number, then again Binary Search to find right most occurrence)
Now using the above two functions, find the number of times the element is present.
Note – Cases like where number is NOT present,

Q2- Assembly Line Scheduling. (Very Simple DP.)
https://www.geeksforgeeks.org/dynamic-programming-set-34-assembly-line-scheduling/

Result
After three weeks, I got a generic email saying that I could not clear it. I had a really irresponsible recruiter who did not have the courtesy to give me a call and just convey some feedback. Eventually, I think I took too much time with the first question in the manager round.

by
0 like 0 dislike

Round 1: (Paper Coding)

Q1. A person is standing at the center(0, 0). He is facing north(N). There can be 4 possible commands – Turn left, Turn right, Move ahead, Move back. Find the final coordinates after a set of instructions. This is an easy implementation problem.
Q2. Find longest palindromic sub string in a given string. This can be approached top-down or bottom-up (DP).

I had to wait 3 hours for the result of this round. Every round was an elimination.


 

Round 2:

Q1. Given a binary tree. Find if there is path from root to leaf with given sum X. After I answered the question, interviewer asked me to print all possible paths for the previous problem.
Q2. Given a binary tree. Add links in binary tree in such a way that all the nodes on a level form a linked list.
Interviewer asked me if I have any questions.

Round 3:

I was given a brief overview about the team for which hiring is going on – Amazon Payments Team.

Q1. This was somewhat related to modified spiral traversal. I can vaguely describe the problem as printing even level nodes (starting node 0) right to left and odd level nodes left to right. Also, the order of printing levels is – 0, 2, 1, 4, 3 …

Q2. This was a question related to data structure design where interviewer told me that I just need to explain different approaches. Lets say DJ is using an application (something like Amazon Music) where he is getting requests from people and then he is picking Nth popular song among current requests. There are two functions – GetRequest() and NthPopular(). Discussed different approaches to store song requests and then ways to retrieve Nth popular by checking count. In these types of questions, it is very important to clarify the requirements and then start discussion.

I must say that interviewer was very supportive.

Round 4:

 

 

 

Brief introduction about myself.

Q1. Given a binary tree, a node N and distance K. We need to find count of all nodes which are at distance K from N.
Q2. A matrix is sorted row-wise and column-wise. We need to find if a number N exist in this matrix. I gave a O(MlogN) solution. We were already running out of time, so she hinted me and then I was able to come up with O(M+N) solution.

Round 5:

The person interviewing me was senior development manager of some other team. Also, I had a feeling that this is a bar-raiser round.

I was asked to introduce myself. Then he asked me about projects in my current company. There were few questions like – Tell me about your most challenging work. Was there a situation where you faced any conflict and how did you resolve it? Was there a situation where you took initiative to do something? These questions are asked to examine Amazon’s principles. Also, in this round, you are the one who is actually driving the interview. The moment you use a term, you can be asked different questions on it. The entire discussion took 1 hour.

Then, there was a programming question – counting all pairs in an array whose sum is X. I answered an approach which stores count (maps) of all numbers and checking the count of (X-num) where num is an array element and then doing calculations. It appeared to me that he was not expecting this answer. Then I answered the approach of maintaining two pointers – start and end. He said I could code any of the approaches. I coded the second approach but missed one test case.

by
0 like 0 dislike

Round 1( Technical):
1.)I was straight away asked to write code for detecting loop in a linkedlist without any formal introduction and all .
After telling my approach he asked me to give a proof of it to which I got shattered but then he gave me a hint and later discussing it we got to the proof but it wasn’t a full-valid proof. But later on it I found http://math.stackexchange.com/questions/412876/proof-of-the-2-pointer-method-for-finding-a-linked-list-loop
After it he asked me to detect starting point of the loop. Again which is geeksforgeeks. I wrote the full code on a paper and understand him my approach which is very similar to geeksforgeeks one.
2.)He gave me another question from g4g which I haven’t read before
Sort one matrix based on another matrix. I gave him one brute force approach, then he asked me to optimise it and then we discussed a bit an finally I came up with O(nlogn) approach.

I was a bit hesitant after 1st round as I’ve mumbled upon the proof of detecting loop in linkedlist until he gave me some hint. However, I was called after 2-3 long hours of waiting for my 2nd round of interview.

Round 2(Technical):
He was a very senior guy and a very cool and calm personality. He entered the room and said sorry to me for such a long wait and then started with formal introduction as to What you do in your present company and why do you want to leave it at such an early stage.

1.)He asked me to check whether a given tree hold children sum property or not.
As soon as I heard the problem, I tld him my approach and coded it on a paper. He then to calrify if I haven’t crammed it asked me to explain him the recursion and dry run it on different examples. I did that explaining him completely the edge cases and every aspect of that recursion. He was impressed 


 

Then he started telling about his experience of startups and that of Amazon

2.) He asked me another question :
Given a stock market price for each day in an array. Give the ans as to when you will buy stocks and when you will sell so as to make the maximum profit.
I think for a while and gave him my approach which he was quite impressed.

After that HR asked me to leave and said that you’ll be informed about the result and further rounds.I got a call and was asked to come for Hiring manager Round

Round 3 (Hiring Manager):
He is the manager of the team for whose team interviews are going. So he started of with the formal discussion as to what are my technical interests and what did I learn in my previous jobs. Then he starts discussing my CV and asked e t pick any 2 projects at which I’m confident enough.
As I wrote technical paper on the work I did in my last job, so he started discussing over that and asked me different ways of solving that problem and hw could I optimize it further. Then he asked me some of the behavioral questions as of why are you leaving when such a good work is there. I told him the concern about salary. It went fine and I thought that I impressed him.

Later on HR told me to wait for another 4 hrs for Sr Manager round.

Round 4 (Sr Manager):
He is a very senior person in the Amazon. probably their head of some main division. He started off with very behavioural questions as to why leaving so early and why Amazon. It was very hard t convince him as his expressions were not changing at that time. He fired me a series of such questions as to what is the most difficult task I have performed till yet technically. He was hoping for answers specific to work related. What are your weakness and strengths and what are you doing to improve yourself.

Then he jumped to my CV and asked me for each and every single detail written in my CV( so please make your CV as small and as specific to your strong pints as you can). He asked my role in different projects I have done and in the technical paper I have written along with others. he even asked my college projects(even the 2nd sem project which I forgot to take off from my CV) to the depth and asked for the specific details( He knew about everything regarding my projects ).

Then after this discussion I thought it would get over, but he has some other plans. He asked me to give a solution to some coding problems:
1. Check how many Parenthesis are balanced in an array of parenthesis.This was easy but then he asked me to scale it such that your array can’t reside it on one memory. To this I said do parallel processing, he gave me freedom of number of clusters on which I can store and compute and then it took some time to me to come up with scaled algorithm. That was quite interesting and energetic enough. All my tiredness went off.

 

 

 

2. In a string detect the smallest window length with highest number of distinct characters. For eg.
A = “aabcbcdbca”, then ans would be 4 as of “dbca”

Finally I gave him some solution which was incomplete, he asked me to relook at my solution and I found the mistake but didn’t asked me to code it.

 

by
0 like 0 dislike

Round 1:
Online coding test comprising of two coding questions and 20 MCQs. The coding problems were:

  • Rotate a matrix by 90 degrees.
  • Longest increasing subsequence.

Round 2: Technical 1, he asked me two questions:

  • If a number is written on a paper and that paper is rotated by 180 degrees, will the number remain the same?
  • Merge two sorted arrays to get a resultant sorted array. Sub questions were to get the resultant array into increasing as well as decreasing order.

Round 3: Technical 2, he also gave me two questions. He first asked me about my strong areas. I accidentally told him my weak areas too. That was my blunder. Don’t ever do that.

  • If there are files that are dependent on each other and I need to compile them. In what order should they be executed that all of them would get successfully compiled? This was basically topological sort.
  • 2x+3y+7z = n –> Find all possible combinations of x, y, z such that they satisfy above equation. I had suggested two approaches but he wanted the solution of lesser complexity. The optimized solution is obtained by dynamic programming. I couldn’t answer it using DP.
by
0 like 0 dislike

I got a call from amazon for opening in SDE – I. It started with a online screening round and followed by one telephonic and then 3 face to face interview and again a telephonic interview.

Online screening :
There were 20 multiple choice questions from Computer science fundamentals (OS, DS, DBMS, Networks etc.) and basic input/output questions, some aptitude questions and 2 coding questions:-
1. Given an array find the minimum difference between any pair.
2. Write a function that returns true if a given undirected graph is tree and false otherwise. http://geeksquiz.com/check-given-graph-tree

Telephonic Interview :
Interview started with brief introduction about me and my projects, then started with coding questions.
1. Given two trees return yes if the order of leaves in tree are mirror image of each other.
2. Given an array of n numbers. another array with same elements but numbers are shuffled and one element is removed. Find the missing element.(without using any extra space and in O(n) ).
Then if both the array are sorted then how to find the missing element. (without extra space and in O(log n)).
Then they called me for onsite interview and 3 face to face interview were conducted there.

Face-to-Face Interview 1 :
He started with a brief introduction and asked me my about my projects in detail.
then moved to coding questions:-
1. Arrange Linked List elements in zig-zag pattern such that a < b > c < d > e ……

(without using extra space and Time complexity O(n)).
Don’t forget to handle edge cases.
(This is array implementation of same question).

 

 

 

2. Given a binary tree. return sum of all Left Leaf nodes.
Left leaves meaning leaf node which is left child of his parent.


Face-to-face Interview 2 :
1. Given two nodes of a binary tree,check they are cousins or not. (Both Iterative and recursive solution).
https://www.geeksforgeeks.org/check-two-nodes-cousins-binary-tree
2. Given an array with N elements (numbers from 0 to N-1). Find all duplicate elements.
I gave a solution with hashing, he asked me to do without extra space.
Then I gave solution with sorting the array, he asked me to do with only single traversal and without extra space.


Face-to-face Interview 3 :
Started with brief introduction and some questions from my projects and CS fundamentals (OS,Networks).
1.Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.


Telephonic Interview :
The interviewer asked me to introduce myself, and after that he asked some behavioural question like-
Have you got offer from any other company ?
Why are you intersted in joining AMAZON ?
1. Design a Elevator. How you store the input from users inside the elevator, outside the elevator. How the elevator will take decision whether to go up,down or stop.

2. There is an event in the auditorium and Given capacity of the auditorium (NxM). every group of person booked ticket and all the tickets are booked, Now you have to assign seat number to all of them such that minimum number of group split.

by
0 like 0 dislike

Written Test (on Hackerrank)
20 MCQ’s and 2 Coding Questions to be solved in 90 minutes
1) NEXT PERMUTATION: Next Largest Number with same set of digits.
For Ex: I/P: 123, O/P: 132
2) DFS + DP Standard Question. I don’t remember the exact problem statement, but it was pretty standard one and required a DFS+DP solution.

Round One (Telephonic)
1) Given an array of zeroes and ones. You are allowed to flip any one 0 so as to maximize the continuous number of one’s.

2) Given only a Node of a Binary Tree, Find the next in-order successor in O(1) space. Root of tree is unknown.
As he told to assume anything except the position of root, To solve the problem I assumed that the Treenodes also contain parent pointers to their respective parent.

Round Two (F2F)
1) Given a Binary Tree. Print its elements vertically. Solved it using Horizontal Distance concept and hashmap.

2) Variation of above question, you are not allowed to use Hashmap. Discussed many approaches. He applied a constraint of not using any Hashing, after a lot of discussion and variations came up with the solution as a Doubly Linked List of List of Nodes. Since I was not allowed to use hashing, the variation I did to solve was to maintain a global pointer to the doubly linked list, moved it left in doubly linked list for the left child of current treenode and move right for right child of current tree-node.


 


Round Three (F2F)
Introduction and Internship related discussion followed by these technical problems
1) Given a Stream of sorted integers. Size of input vector is unknown. Find a given integer. Expected Complexity; Log(n)
Hint: Used Perfect Square’s as the start index and end index in binary search approach.
2) Variation in above problem, as we do not know the end point. Lets assume we have a function which returns NULL if the threshold index (Size of input vector)
had crossed. Now improve above solution to handle the case.
Ex: Lets assume that the array size is
3) Subject Related Questions: TCP v/s UDP, Virtual memory, Cryptography etc
4) Design a Music Player which plays songs in random order without repeat. Came with O(n) Time and O(1) space solution.

Round Four (F2F)
Introduction, Project related questions followed by:
1) Given k sorted Linked Lists. combine those into one sorted list.
Used custom Min heap approach to do the same.
2) Implement Custom Min Heap for above problem.
3) Print Nodes at distance “k” from a given node in a binary tree.

Round Five (Telephonic)
1) Introduction and Project discussion.
2) Convert given integer into Roman Number format but by using minimum number of conditional statements. Came up with lot of approaches,
he was not satisfied with any approach and asked to remove as much conditional statements as I can.
3) Given an array of zeroes and ones. find the maximum size of subarray with equal number of zeroes and ones. Came up with O(n) time and O(n) space solution.

by
0 like 0 dislike

Round 1: Online coding + MCQs

MCQ consisted of Data Structures, Algorithms, Code Output of C/C++ snippets (Pointers).

Coding questions:

  • Count trailing zeroes in factorial of a number
  • Find the minimum height of Binary Tree for a given inorder and level order traversals

Round 2: F2F Problem Solving

Initially, Interviewer asked current job role and introduction and then start coding questions. In this round, they asked two questions


 

  • Find the square root of number up to 3 precision
  • Design queue using stack

Round 3: F2F Problem Solving

In this round also Interviewer asked two coding questions. For the second question, he gave some used cases and explained thoroughly and asked to write production-ready code and some technical questions from Java since I mentioned Java in my resume

  • Clone a Linked List with next and random pointer
  • Minimum Heap tree
  • What is Polymorphism,
  • Explain real-life case of Function overloading and overriding
  • What are virtual destructor and a private constructor

Round 4:  Video call on Amazon Chime App

The interviewer asked me to introduce myself and brief him about my job role and contributions. Some questions he asked regarding my company project on which I am working. Later he starts some generic questions like:

  • Why do you want to change job?
  • Why only Amazon?
  • Anything that you had taken lead or gave your ideas to your Lead or Manager

He shared a live screen to write code. He asked me to explain the approach first and time and space complexity

Coding question:

I explained him using Insertion sorting but due to its worst time complexity, he asked to think some other way. He helped me in writing code using binary search tree and coding round went well.

Round 5: Bar Raiser


 

In this round Interviewer checked how technically strong and capable enough to handle any sorts of challenging tasks based on our past works. He asked some generic questions like:

  • Why do you want to change job?
  • He asked some questions  seeing my resume
  •  Any critical issues have you resolved? If yes, then how were your approach, resolve, and impacts
  • He asked many questions related to Automation Framework that I created using java and Selenium

He asked to solve one code on the live share screen. Firstly, he asked to tell him the approach and what will be time and space complexity and what kind of Data Structure will you prefer.

Coding question:

I explained to him and write code using BFS. Although, it was not the best solution but he convinced.

Result: Hard luck not selected. This was my first interview experience with Amazon. Although, not selected in the first attempt but gain enough confidence for a future interview.

by