Amazon Interview Question
Software Engineer in TestsCountry: India
Interview Type: In-Person
Heap is a good choice. If the mapping has to be stored as well, Priority queue can be used.
Maintain a services in use list.
Whenever a service is requested, scan the priority mapping and get the first free service not in the services in use list.
Add this service to the services in use list.
Whenever a service is no longer required, simply delete it from the services in use list.
a. What is the datastructure that you will use to store these services. You dont have to store the mapping. Mapping is already stored in the system.
---> Since the lest priority service is to be assigned to any user, a sorted collection is to be used. Best option would be to use a TreeSet
b. Can you write the code for it.
---> User is given the service mapping to first element of this TreeSet (also it is removed from the treeSet), on request for a service.
Make sure that you use synchronized block to synchronize this piece of code, because multiple users will try to access this TreeSet.
Add the service's priority back to the treeset once the user logs out.
c. How will you go about writing automation framework to test it
The above service has to be tested with multiple test cases spanning around no. of users, availability of service etc
I will use a min heap according to priorities in this case.
- DashDash May 31, 2013struct heap
{
int priority
int service
heap *left;
heap *right;
}
or best approach to use a heap is arrays