Amazon Interview Experience

Amazon Interview ExperienceRound 1(Coding on Hacker Rank platform):Given an array of Strings, Each string has an id and version associated with it. string with alphabetic versions are the older versions and the string with numerical versions are the new version. We need to line up the strings for renovation such that older version strings (strings with alphabetic version) need to be put first in lexicographical order. If any clashes in arrange, then arrange them as per the lexicographical order of the id. The renovated strings need to be kept as in the input order.Example:
Input:{a a , c b , b b, a 1, b 2}
Output:{a a , b b , c b, a 1, b 2}Expected time complexity O(N* log(N)). I was able to solve it with Heap (priority queue in c++).Given a 2 D array with each cell having values 1, 0, 9 where 1-> land , 0-> sea , 9->obstacle, we can only traverse in land (1).Need to find the Minimum number of steps required to reach the obstacle (9).we are allowed to traverse only to right, left, down and up.Expected Time Complexity: O(M * N) . I was able to solve it with BFS (Breadth-First Search)Round 2(Amazon chime paired Coding F2F):Given a list of contacts containing name and phone number , we need to group the contacts which either have the same name or same phone number together.Example:
Input :{{abc ,9987},{xyz,9986},{dfg,9987}}
Output:{{{abc ,9987},{abc ,9987}},{{xyz,9986}}}Union Find Algorithm or Depth First search Algorithm was applicableGiven a Sorted array, such that each number repeats exactly twice except one number, we need to find that numberExample:
Output: 3Expected Time Complexity :O(log(N)) Binary search was applicableDifference between thread and ProcessDNS Server mechanismRound 3(Amazon chime paired Coding F2F):Given the Process ids in array and the parent of these Process ids in separate array, and the process id we need to kill. Find the List of the process which would get killed on killing the given process.Example:pid{1,2,3,4,5,6,7,8,9}
Killing Process: 3
Output :{4,5,6,7,8,9} Create a Directed Graph between the parent and Child process and perform BFS (Breadth First search)Given a Linked Link, Alter the Linked list as the belowInput:l1->l2->.. ln-2->ln-1->ln
Output: l1->ln->l3->ln-2…Separate out the Linked List by alternate nodes, we get two linked lists, reverse the second list and then join them.Discussion on LRU Cache Implementation. (Double Linked List and HashMap)Amazon Leadership Principles Questions. 4(Bar Raiser Round F2F-Amazon chime):Few Questions on Amazon leadership principlesGiven a string that represents covid patients we need to isolate(remove) each character in string in lexicographical orderCost of each isolation is equal to the index value of the characterExample 1:
Input : aacb
Output : 1+1+2+1=5Use Double linked list for altering and the hashmap for character frequency.Round 5(Hiring Manager-Amazon Chime):Few Questions on Amazon leadership principlesGiven an array of Integers find the pair whose sum is farthest from zero.some variations on the above questionFinally, After 5 Rounds I got a Mail from HR stating my Selection.Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course. In case you are prepared, test your skills using TCS, Wipro, Amazon and Microsoft Test Serieses.