CareerCup

Can the oldest friend change in the case of current oldest friend gets removed from friend list,
If 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.

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.

Adjacency list representation of the friendship graph is good enough for this problem. The first one in the list is your first friend, delete him then second guy comes to the front.

Adjacency list representation of the friendship graph is good enough for this problem. The first one in the list is your first friend, delete him then second guy comes to the front.

Adjacency list representation of the friendship graph is good enough for this problem. The first one in the list is your first friend, delete him then second guy comes to the front.

Adjacency list representation of the friendship graph is good enough for this problem. The first one in the list is your first friend, delete him then second guy comes to the front.

Adjacency list representation of the friendship graph is good enough for this problem. The first one in the list is your first friend, delete him then second guy comes to the front.

Keep friends in

Nodes

in a

Graph

and have a property in the Node for when added. Then do a breadth-first-search to find a node which has the oldest date.

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.