Amazon Interview Experience | Set 167 (SDE I for 1 year 6 months experience)

Round1: Online Coding Round
There were 4 coding question. Was asked to answer 2 out of 4.
1) Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S.
Example: Given coins with values 1, 3, and 5.
And the sum S is 11.
Output: 3, 2 coins of 3 and 1 coin of 5.

2) Given two rectangles, find if the given two rectangles overlap or not

3) Given two strings string1 and string2, find the smallest substring in string1 containing all characters of string2 efficiently.
For Example:
Input string1: “this is a test string”
Input string2: “tist”
Output string: “t stri”

4) I don’t remember the question.

Round 2: F2F Technical (Hyd)
1) Print zig zag of tree

2) Longest Palindromic subsequence of a given string.
Was asked to write complete code.

Round3: F2F Technical (hyd)
1) Lots of Question on my projects.
Since my project relates to multiprocessing, lots of questions were asked why multiprocessing/why not multithreading, difference, what is thread/process, producer consumer problem, etc.

2) Design a file structure in Linux.

3) I was asked to write flawless code for inserting an element in sorted linked list which should cover all corner cases.

Round3: F2F Technical (hyd)
1) Given an array of words, print all anagrams together.

2) You have an array which the ith value is the price of a given stock on day. You can buy only one share of the stock and sell one. Design an algo to find the best times to buy and sell. Also he asked me to give start date and end date.
3) Graph problem:
Critical node: If a node reaches another node only through one node.
Eg: A-C-B and A-E-B are critical nodes. (A reach B through one node which is C or E)
If A reaches B through more than one node, then they are not critical nodes.
1) A-C-B
A-D-E-B (A reach B thro c which might lead to critical node but A has another path to B thro D and E, so they are not critical nodes).
2) X-Y-Z
X-A-Z (X and Z are critical nodes)
Now find all critical nodes.

Round4: F2F Technical (hyd)
1) Many questions on my projects. He asked me to write pseudo code for one of my project.

2) Outlook:
A server receives meeting objects from multiple senders. Meeting object contains meeting time, sent time, recipient(s), sender id,etc. When recipient comes and checks the server, he/she should get requests based on meeting time and not based on sent time. Many discussions on space complexity and time complexity.
Eg:

12 PM      From: A  To: B,C,D   meeting time: 4 PM   meeting Id: 1
12.30 PM   from: A  To C,D      meeting time : 2 PM   meeting Id:2
1:PM       From B   To: C       meeting time: 1.30PM  meeting Id:3

When C requests the server, C should get ID3 as 1st, ID2 as 2nd and ID1 as 3rd meeting.

3) Many behavioural questions.

I would like to thank neveropen for helping me to crack the interview.

If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.