Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
1. create a queue to hold the calls for last x seconds. and create a counter.
2. when the service is called:
if the queue is filled then remove the oldest call and if that has returned true then count--
if count < N then increment counter, add the call to the queue and return true
else add the call to queue and return false without incrementing counter
Approach 1:
- iictarpit December 19, 2012Use a circular linked list, for the first N calls keep adding items to the LL.
Maintain pointer to currently added element. From N+1th call see if the oldest item (currentElement.next) timestamp is less than current item – X. if it’s the case replace the timestamp and move the currentElement pointer to this element. If it’s not the case return false.
Time Complexity O(1)
Space Complexity O(N).
Approach 2:
If we take first call time as a reference (t0) then in idealistic case when events are generated with N/X frequency then function should return all true.
From this reference, suppose last event occur in interval t0 + (N/X)x, then if next occur after t0 + (N/X)x + N/X return true else false.
So we need to store interval of only last event, thus space complexity O(1)
Time Complexity O(1)