Amazon | Loop interview | SDE-1

Online Assessment

Questions:

1. Question 1 (Easy): You will have a stream of numbers as input and you have to print output in sequence if all the prior numbers exist in the input stream.

   • Example:
     • Input: 3 1 2 6 5 4
     • Output: [[1],[2,3],[4,5,6]]
   • Solution: Use a set to keep track of numbers that have already been received and use another variable called start = 1. If start is present in the set, keep adding it into the output and increase start by 1.
   • Verdict: All test cases passed.

2. Question 2 (Medium): You are given an array of integers. You have to make packets from its elements. A packet can contain at most 2 elements and cannot be empty. You have to tell the maximum number of packets that can be created where the sum of elements in each packet is equal among all packets.

   • Example:
     • Input: 1 4 3 2 2 6
     • Output: 3 (Packets: [4], [2,2], [1,3])
   • Solution: Sort the input array. The maximum sum of two elements cannot exceed 2 * max_element of the array. Check for every sum starting from 2 * max_element. Use upper bound to find that sum in the array and use an approach like two-sum to find how many pairs you can make out of it.
   • Verdict: All test cases passed.

Round 1

Questions:

1. Question 1 (Easy): Find Next Greater Element

   • Follow-up: What if the array is circular?
   • Solution: This is a standard question. We can solve it using a stack while traversing the array from reverse. For the follow-up, we can append the array to itself and then apply the same algorithm.
   • Complexity: Discussed with the interviewer.

2. Question 2 (Easy): Number of Islands

   • Follow-up: There are two matrices given, A and B. An island in B counts as a valid island only if it is entirely within an island in A.
   • Solution: This is also a standard question. We can solve it using DFS and BFS. For the follow-up, check if there is any i,j where B[i][j] == 1 and A[i][j] == 0. Use BFS or DFS traversal on B to mark that island as 0, then apply the original algorithm in the second pass.
   • Complexity: Discussed with the interviewer.

Round 2

Questions:

1. Question 1 (Medium): Implement a class named NumberPool which consists of two methods: checkout() and checkin(). checkout() will give the minimum number present in the pool and pop it out, while checkin() will insert the given number back into the pool.

   • Solution: Initially provided a brute force solution using a min priority queue. Suggested an optimization using a set to track numbers that have been popped out and iterating from 1 to INT_MAX to find the next available number.
   • Follow-up: Discussed another approach using a doubly linked list.

2. Question 2 (Medium): Reorganize String

   • Solution: Used a priority queue approach to append the character with the maximum frequency and reduce its frequency by one, pushing it back into the queue while blocking the last appended character.
   • Complexity: Initially stated as O(N log N) but corrected to O(N log(26)) due to the limited number of characters. The interviewer challenged the candidate to find a linear time complexity solution, which the candidate could not provide.