Amazon Interview Experience by Amrith M Nair | On Campus - Jan 2019

New update is available. Click here to update.

SDE - 1

Amazon

5 rounds | 12 Coding problems

Amrith M Nair

Fresher | Jan 2019

Selected

65770 views

21 comments

999 upvotes

Interview preparation journey

Journey

I started my journey in coding from second year after being motivated from my seniors. I initially started my journey by learning basic programming languages. Later, I started giving contests on code forces and solving questions on it. I kept trying to be consistent in doing so. After 2-3 months I was able to solve some questions on code forces. Then in my third year, I studied core subjects like OS, DBMS, OOPS and CN in depth. In this manner, I was well prepared before the placement season.

Application story

I got this opportunity through campus placements. Amazon visited our campus for internships and placements. I applied through my resume on their portal.

Why selected/rejected for the role?

I was able to solve almost all the questions asked me during the selection process. I have done a lot of coding practise on Competitive programming sites and built a deep understanding of programming skills. My good communication skills are also one reason of my selection.

Preparation

Duration: 8 months

Topics: Data Structures and Algorithms, Operating System, Database Management System, Object-Oriented Programming System

Tip

Do lot of hard work and practice of Data Structures and Algorithms based questions. I personally recommend you Coding Ninjas and Geeks For Geeks for interview preparation.

Application process

Where: Campus

Eligibility: 7 CGPA

Resume tip

Make your resume short and try to make it of one page only and do mention all your skills which you are confident of in your resume.

Interview rounds

Round

Easy

Online Coding Test

Duration60 minutes

Interview date25 Jan 2019

Problems2

Tiling Problem

Given a “2 x n” board and tiles of size “2 x 1”, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.

Examples:

Input n = 3

Output: 3

Explanation:

We need 3 tiles to tile the board of size 2 x 3.

We can tile the board ...

Problem approach

I have done this problem earlier so got the DP based approach during the test and this approach passed all the test cases.

Try solving now

Find k’th character of decrypted string

Given an encoded string where repetitions of substrings are represented as substring followed by count of substrings. For example, if encrypted string is “ab2cd2” and k=4 , so output will be ‘b’ because decrypted string is “ababcdcd” and 4th character is ‘b’.

Note: Frequency of encrypted substring can be of more than one digit. For example, in “ab12c3”, ab is repeated 12 time...

Problem approach

I simply decrypt the string by reading substring and their frequency and append current substring to the decrypted string and after the end of traversal of given string our answer will be kth element of the decrypted string.

Try solving now

Round

Easy

Face to Face

Duration50 minutes

Interview date25 Jan 2019

Problems2

Count Positive-Negative Pairs

Given an array of positive and negative integers, print x if +x and -x are present in the array.

Problem approach

I asked for some clarifications whether I should print all distinct x‘s or if I should print an x if a pair of +x and -x is encountered. The first approach I told was to use a map and I was keeping a flag for +x and -x if it’s found once. Later he asked me to print all pairs, so I stored the frequencies of all the elements in the map and iterated through the negative elements and for each eleme...

Try solving now

Design the logic for minimising cash flow in an app like ‘Splitwise’.

Problem approach

Here the interviewer told me about an app called splitwise which i had used once. In the application each user adds the amount he spends and it’s shared equally among users of the app. The aim is to minimise the number of give and take operations. I initially thought of a very naive approach where I wanted to create classes for each person and expenditure and iterate through the expenditures of...

Round

Easy

Face to Face

Duration60 minutes

Interview date25 Jan 2019

Problems2

At the beginning of this round, the interviewer asked me about the data structures I knew. Linked lists, trees, graphs, arrays etc. was my answer. He asked me how well I knew Dynamic Programming. I said I wasn’t strong in that and he said that he would ask me a question on dynamic programming for sure.

Count Special Nodes in Generic Tree

Given a generic tree, find the count of all special nodes. A node is a special node if there is a path from root to that node with all distinct elements. The input was not a pointer to a tree. He’d give me an adjacency list and an array of values where the value of ith node in the adjacency list is the ith element in the values array. He asked me not a create a tree out of the given information...

Problem approach

I suggested to do a depth first search keeping a set which contains all elements upto a given node. Once I reach a particular node, I check if it’s already in the set. If its already in the set, I return because that element has already been visited and is not a special node. Otherwise, I increase the count of a global variable by 1 and push that element to the set. Then I go through the adjace...

Try solving now

Common Digit Longest Subsequence

Given an integer array, find the longest subsequence with adjacent numbers having a digit in common. Eg: 1 12 44 29 33 96 89 . The longest subsequence here is { 1 12 29 96 89} and the answer is 5.

Problem approach

I initially tried a 2D DP solution where dp[i][j] indicates the length of the longest sequence with ending at i containing j as a digit. It’s a N X 10 DP matrix. The interviewer asked me why I needed a 2D DP solution and I struggled to convince him. I wrote the code for it. I...

Try solving now

Round

Easy

Face to Face

Duration40 minutes

Interview date11 Feb 2019

Problems2

The interviewer asked me if I was comfortable with the interview process so far and how the previous interviews were. I said it was good and he gave me the first problem to solve.

Given a binary tree, modify the tree satisfying the following constrains :

Value at root must be the sum of left child and right child (not subtrees).

You can’t reduce the value at any node. You can only increase it.

Value of root node must be minimum

Problem approach

I drew a few trees and asked him the output for those examples. He asked me to say it myself and I did. I thought of doing a post-order traversal as we need to visit the root’s left and right child before visiting root. In the post-order traversal, we keep the sum of root’s left and right child in a variable sum. We take the difference of this sum and root data. If the sum is greater than root’...

Sort 0 1 2

Given an array A of size N containing 0s, 1s, and 2s; you need to sort the array in ascending order. You can scan the array only once.

Problem approach

I solved this question using three-pointers and this problem was a variation of dutch national flag problem. The interviewer was satisfied by my approach as this was the most optimal approach.

Try solving now

Round

Easy

Face to Face

Duration60 minutes

Interview date11 Feb 2019

Problems4

The interviewer asked me some Computer Science‍ fundamentals in this round as well as some behavioural questions.

Difference between threads and processes.

Problem approach

This is most basic question of OS and I explained it very well using a tabular representation.

Deadlocks and its prevention.

Problem approach

I firstly told him necessary conditions for deadlock and then explained him that if we don’t let all conditions fulfilled for deadlock then it may be prevented.

Trie data structure

Implement a Trie data structure and write functions to insert and search for a few words in it.

Problem approach

I wrote a class to implement a character Trie using a vector of nodes as children. He asked me to improve on space. So I used a hashmap to store the child nodes only if a child exists. I wrote the code for insertion and finding a word and walked him through.

Try solving now

Anagram Pairs

Given two strings a and b consisting of lowercase characters. The task is to check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains same characters, only the order of characters can be different. For example, “act” and “tac” are anagram of each other.

Problem approach

I implemented it first by sorting two strings and comparing them. He asked me to write a better approach. So I used a hashmap to do it.

Try solving now

Join the Discussion

21 replies

Abhishek Rohit |Level 4

27 Apr 2022

#include <unordered_map>

bool isAnagram(string str1, string str2)
{
   unordered_map<char, int>mp;
	if(str1.length()==str2.length())
	{
     for(int i=0;i<str1.length();i++)
	{
		mp[str1[i]]++;
		 mp[str2[i]]++;
	}
		for(auto i:mp)
		{
			if(i.second ...

9 upvotes

1 reply

Gautam Mishra |Level 2

12 Nov 2020

Edited

Thank You So much. For the splitwise question DP something like subset sum will work.

8 upvotes

0 replies

Victim |Level 2

3 Feb 2021

Comment Removed

2 upvotes

0 replies

AkashDebbarma |Level 7

11 months ago

Count special nodes in Generic tree Solution

void dfs(TreeNode<int> *root, unordered_set<int> &pathElements, int &count){
    if(!root){
        return;
    }
    int currVal = root->data;
    if(pathElements.count(currVal) != 0){
        retur...

1 upvote

0 replies