Company: Amazon
Number of Rounds: Apti/Coding test + 4 interviews
Questions:
Apti/Coding Test (14 shortlisted after the test)
Total time was 90 minutes, 20 questions for Apti, +1 for correct answer -0.25 for wrong. Had 5-6 quant sums and remaining were technical questions.
Coding Questions
- Write a function that accepts pointers to 3 Linked lists. Each list represents a number and each node holds a single digit. Eg: 2->9->0->7 represents 2907.You need to add the 3 linked lists together and return a pointer to a new list that contains the sum.
- Given an array with positive and negative numbers, arrange(in place) it such that there are alternating positive and negative numbers. You have to maintain the order of the positive numbers as well as the order of the negative numbers. If there are any extra positive or negative numbers just pad them at the end of the array.Eg: 1, -4, -3, 2, 6, -5, -1, -10, 8Ans: 1, -4, 2, -3, 6, -5, 8, -1, -10
Interviews
All the interviews were primarily technical, with little bits of HR stuff mixed in. Overall the interviewers were very informal and friendly and gave hints for the tougher problems as long as you were trying hard and thinking in the right direction. You can code in any language you are comfortable with.
1st Interview (2 shortlisted after 1st interview)
- Asked me about the apti and the coding test, what questions I got wrong and how I coded the 2 questions. Also asked some questions on my projects.
- Given a binary search tree and the value of a node. Find the value of the node that is just larger than the given node. Account for all test cases
- Given a linked list, swap its nodes pair-wise. (I told him I knew this problem, so he moved on)
- Given a linked list and an integer k swap its nodes k-wise. (So above problem is a special case where k=2)
- Obtain two numbers from array such that their sum is K.(Gave him one solution he wanted more so I gave him two more).Then he asked several questions on my all solutions.Asked me to calculate complexity of every solution step wise (showing proper addition calculations for the steps)
- Then he asked me to write a program for finding pythagorean triplets (a^2 +b^2 = c^2 ) array.This was like modification of the above question. So he asked me to use all the approaches that I mentioned in second question and use it here. Again he asked all the complexities in detail.
2nd Interview
- Asked me some questions about myself, family background, where I would prefer to work and why, and the projects in my resume.
- Given a stack of integers. You have to write 3 functions, push(), pop() and minimum(). Minimum() should return the smallest value in the stack. All three functions should operate in constant time only. (You can use space)
- You are given a binary tree. Every node has a pointer Node *inordersuccessor that points to NULL. You have to make each node point to its inorder successor. (He wanted a linear time solution)
- His first few questions related to some web projects I had on my resume.
- Then 1-2 in general questions like tell me about yourself and all.
- A frog has to cross a river. There are n elements in between. Those elements can be 1 or 0.Frog can land only on a 1. If frog lands on 0 then he dies. The frog has initial speed of 1.This means that he can jump by one element. At any point the frog can either increase his speed or decrease his speed. If the frogs speed becomes 0 then also he dies. The aim was to find a path till the end of the river.(Gave him several solution but he settled for a solution that he had in his mind about making a decision tree).Then he asked me to write a code for the whole solution.Again asked me regarding the complexity of all the solution.
- Given a pattern I was asked to find the maximum substring containing unique characters.Different scenarios were discussed regarding the solution and again was asked to write a full fledge code for the solution which was followed by a code complexity session.
3rd Interview
- Asked me to explain my internship in detail.
- You are given a singly linked list. In addition to the next pointer, each node also has a random pointer. This random pointer can point to anything such as the node itself, NULL, or to any random node in the list. The integer values of the nodes need not be unique. You have to create a new list that is a perfect replica of this list. (He wanted a solution in linear time)
- Write an algorithm that takes any positive integer value as input and returns the least significant non-zero digit of its factorial. Eg: 6 as input, factorial is 720, answer is 2.(Obviously you cannot calculate the factorial, as the input could be any integer, like 50,000)
- He started with questions about the different android applications I had on my resume.
- Draw a diagram about what happens when a user hits a url in a browser.He also wanted the function names that are used in http protocol. The diagram started from a superficial level and asked me go in deep in every aspect of the diagram. Every detail was asked.
- What is a AVL tree? Why is it used? In which case is it bad? And some more questions regarding it.
- There is a textfield and somewhere there are stored several names of functions.I was asked to implement auto suggest functionality. What data structure would I use?What algorithm would be followed? What is the complexity in each case? Asked me to list all the data structures that I know and asked me to implement it using every thing I listed.Then after he was happy with one solution he asked me to write a proper working code for it. After the code he asked me to write the following functions- add(), delete(), find() on that structure. And step by step complexity was asked.
4th Interview (Final) (1 selected after 4th interview)
There was no actual coding in this round, he just wanted me to explain my algorithms and check test cases.
- Went through my resume, asked me about my favourite project and why it was my favourite.
- Asked me a few simple questions on data structures, what is a BST, what are the different ways of traversing it? Etc.
- There is a BST. You are not provided with the BST, but are given a linked list that represents the nodes of the BST as they would appear in a pre-order traversal. Write a function to analyse the list and return false if there exists any node which has both a left child as well as a right child. If no such node exists return true. You should not try to rebuild the BST from the linked list. (I provided an n^2 solution which he wanted me to optimize. He hinted that I should use dynamic programming but I couldn’t find any way so he moved on to the next question)
- There is a telescope stationed in India. This telescope is continuously calculating distances between stars and earth. As soon as it calculates one value it sends it to your program and starts calculating the distance to another star. You need to handle this data in a manner such that you can efficiently request the distances of the 100(or some other fixed value n) closest stars at any given point in time.
- Write an algorithm that takes a BST as input and returns the number of vertical lines that would be required to cut through all the nodes of the BST. For this problem, you have to assume that the BST nodes are arranged in a grid like format. For example, the right child of the left child of the root, will be in the same line as the root itself. Similarly, the left child of the right child of the root will also be in the same line.
- You are given an N*M array(N may or may not be equal to M). The elements of each row are sorted in ascending order. Similarly the elements of each column are sorted in ascending order. Devise an efficient algorithm that will take an integer value as input and return true if the value exists in the array, else return false. (You don’t need to find out the position of the value, just return true if it exists. Obviously he doesn’t want an n^2 solution)
Company: Amazon
Aptitude tests: Already been posted
1st Technical interview:
1. Tell me about your self.
2. Favourite data structure.
3. Given a tree wherein each node, in addition to left and right pointers, has a next pointer. All the next pointers are initialized to null initially. How will you make the next pointer of each node point to the next node on the same level? He asked me to explain the logic and code it, which I did using level order traversal using a queue. He then asked me to do it without using stack/recursion/queue using constant extra space. Also asked me to code the optimized version.
1st Technical round:
1. Given a tree, how will you check if it is a BST or not
2. Given two linked lists, check if they merge in the end.
About the Author
