Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
The oldest friend will be the 1st friend added unless it gets removed. So I think an "ID" and "Valid" column in relationship database will be able to get the answer, right? In Rails, it could look like this:
user.friends.find_by_valid(true) #it will return the 1st valid friends ordered by ID.
we can use a graph representation. Now on a avg each user has around 200 friends(max is like 5k-10k). we can put them into a heap as the unfriend operation happens very rarely and find oldest will be happening frequently.
Solution lot depends on the conditions and the frequency of different operations and space constraints. That will be part of followup questions.
Another thing that can be done here is that we can have a doubly linkedlist of graph nodes based on order of time when the friend was added. this will optimize all get, delete and add operations but at cost of memory.
I think this can be implemented by constructing a min-heap. The heap property can consider friendship timestamp for sorting order while insertion. At any given time the root node will have the minimum timestamp value, and hence the oldest friend.
The deletion operation for min-heap will take care of popping up lowest timestamp (i.e. newer than oldest friend, but older than others) node in root position.
Can the oldest friend change in the case of current oldest friend gets removed from friend list,
- ashi January 29, 2014If so,
need to maintain timestamp or some counter like # of friends along with list of friends.
Otherwise, it is oldest friend is like a primary key for a person, can be stored.