Amazon | Seattle | SDE-2 | 4YOE | Screening | Reject
Anonymous User
913
Heap (Priority Queue)AmazonSortingPhone ScreeningInterview

Company: Amazon
Location: Seattle
YOE: 4 years
Position: SDE-2
Round: Technical Screening

I was asked this question in Amazon Screening round.

You are given the a List of warehouses and their open year and close year.
Find out the year in which maximum warehouse were open? (If there are multiple return the earliest year).

ex:

consider Input:
{ 
  "wareHouse1": [2000, 2019], // This indicates that warehouse1 was opened in year 2000 and was closed in year 2019.
  "wareHouse2": [1995, 2002],
  "wareHouse3": [2001, 2001],
  "wareHouse4": [1999, 2004]
};

For this The output will be: 2001. As all the 4 warehouses were open in that year.

I identified that this problem is similar to meeting room - 2 and cosidered using minHeap with Sorting.

Algorithm:

* Get Min of year_open and max of year_closed
* Sort the durations in the ascending order of year_of_opening
* Initiate a minHeap
* starting from minYear to maxYear: for every year
		* Put all the closeYears from the durations which started on or before this year in the heap
		* remove all the durations (close_years) which are lesser than this year (minHeap.peek() and poll())
		* get the size of the heap  and keep track of maximum size and maximum year
* return maxYear  

Complexity: 
TC: O(NLogN) Sorting + O(D) where D=|maxYear - minYear| ~ O(NLogN)
SC: O(N) constructing heap.
Example1:

		{
		"w1": [1991, 2021],
        "w2": [2000, 2010],
		"w3": [2005, 2007],
		"w4": [1996, 2005],
		"w5": [2004, 2006]
		}
		
		answer: 2005 (As all the warehouse were open in that year).

Code:
https://leetcode.com/playground/epja2f98

Even After I solved this, I got a Rejection in 3 days.

Hoping that it'll help others and if you folks have better approach, feel free to comment and share.

Comments (4)