SDE - 1 Amazon interview experience | bhargavi sandur

Interview rounds

Round

Medium

Online Coding Interview

Duration150 minutes

Interview date24 May 2020

Coding problem2

We could attempt at any time out of the 3 given days.
The round was very time constrained and we could NOT go back to the question that we already attempted.

1. Merge two sorted linked list

Moderate

15m average time

80% success

0/80

Asked in companies

You are given two sorted linked lists. You have to merge them to produce a combined sorted linked list. You need to return the head of the final linked list.

Note:

The given linked lists may or may not be null.

For example:

If the first list is: 1 -> 4 -> 5 -> NULL and the second list is: 2 -> 3 -> 5 -> NULL

The final list would be: 1 -> 2 -> 3 -> 4 -> 5 -> 5 -> NULL

Problem approach

1. Compare the head of both linked lists.
2. Find the smaller node among the two head nodes. The current element will be the smaller node among two head nodes.
3. The rest elements of both lists will appear after that.
4. Now run a recursive function with parameters, the next node of the smaller element and the other head.
5. The recursive function will return the next smaller element linked with rest of the sorted element.
6. Now point the next of current element to that, i.e curr_ele->next=recursivefunction()

Try solving now

2. AWS Trucks

The problem statement involved the use of amazon trucks which had to deliver system requirements across an AWS region which contains N office buildings. The various location of buildings are given in a vector of (x,y) coordinates along with an adjacency matrix deniying tge connectivity. The head branch is located at (0,0). The truck starts at the head branch and after visiting other branches, returns back.Find the appropriate route so that each building is visited exactly ONCE. If you cannot visit them exactly once, print -1. Else print the route that should be taken in a vector of (x,y) coordinates.

Problem approach

1. It's basically a problem of visiting each node of a graph exactly once in a cycle. So its a Hamiltonian cycle which can be found out using backtracking
2. Create an empty path array and add vertex 0 to it.
3. Add other vertices, starting from the vertex 1. Before adding a vertex, check for whether it is adjacent to the previously added vertex and not already added.
4. If we find such a vertex, we add the vertex as part of the solution. If we do not find a vertex then we return -1
5. In the end, if it does contain a hamiltonian cycle, print all the elements in the path array, else -1

Round

Hard

Video Call

Duration60 minutes

Interview date26 Jun 2020

Coding problem5

Evening at 5:00 pm. It was held on Amazon Chime app
Face cam was to be kept on COMPULSARILY. You could however not see the interviewer.
Codepen type environment was also used for typing my code which could be edited by the interviewer also.
(Shared document kind of)
Interviewer was very professional and was trying to push me towards getting the most optimal solution. Each and every answer was asked a counter question as to why I made that choice

1. Missing Numbers

Easy

28m average time

85% success

0/40

Asked in companies

You are given an array 'ARR' of distinct positive integers. You need to find all numbers that are in the range of the elements of the array, but not in the array. The missing elements should be printed in sorted order.

Example:

If the given array is [4, 2, 9] then you should print "3 5 6 7 8". As all these elements lie in the range but not present in the array.

Try solving now

2. Maximum element between two nodes of BST

Easy

15m average time

85% success

0/40

Asked in company

Given a Binary Search Tree and two integers NODE1 and NODE2. You have to find the maximum element in the path from NODE1 to NODE2.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

Note:

1. The path from NODE1 to NODE2 does not include NODE1 and NODE2.

2. NODE1 and NODE2 are unique.

3. If there is no element in the path from NODE1 to NODE2, return -1.

Problem approach

1. Find the LCA or least common ancestor.
2. Apply binary seatch from LCA to find the greater out of A and B while keeping track of the largest node.

Try solving now

3. Compress the String

Moderate

32m average time

60% success

0/80

Asked in companies

Write a program to do basic string compression. For a character which is consecutively repeated more than once, replace consecutive duplicate occurrences with the count of repetitions.

Example:

If a string has 'x' repeated 5 times, replace this "xxxxx" with "x5".
The string is compressed only when the repeated character count is more than 1.

Note:

Consecutive count of every character in the input string is less than or equal to 9. You are not required to print anything. It has already been taken care of. Just implement the given function and return the compressed string.

Problem approach

1. Use a hashmap m to keep track of number of times a character has occured. Use a vector v to store the order of occurence
2. When you encouter a char, see if its present in m
If yes, the increase the count in m.
Else, make entry of char in m with count 1 and enter char in the vector
3. Print all the elements in the vector with the corresponding frequency by looking up the hashmap in O(1) time

Try solving now

4. OS Question

What is deadlock? (Learn)

How to recover from them? How to prevent them? (Learn)
Difference between thread and process? (Learn)

Problem approach

Tip 1 : Be very precise and to the point.
Tip 2 : Be extremely clear with the concept.
Tip 3 : Don't use fancy terms which you yourself don't know about.

5. DBMS Questions

What is ACID, explain with examples. (Learn)

Questions on join queries.

Problem approach

Tip 1: While giving examples, give short and relevant ones
Tip 2: Practice queries thoroughly
Tip 3: No need to learn very hifi concepts. STICK TO YOUR BASICS