DataStructure to use to store elements and sorted them in the order of their usage frequency/timestamp

Question

I have one problem statement: Suppose there is Employee class and a class has to be designed which provides get and put methods to access and add employees. Employee class is a third party class so we can't make changes in it. There is a memory limit like max 50k employees can be stored. Now if while adding employee if memory limit is reached then remove one employee by following any of the below approaches and add the new employee:

1. on the basis of access frequency
2. on the basis of timestamp. one with the old timestamp should be removed

I can think of taking two hashmaps: - one for storing employee objects and one with the employees with key and timestamp or frequency as value.

But this is not the optimal solution. Please provide the valuable suggestions on which data structure can be used to solve this problem.

Answer 1

Just use a normal collection for storing your Employee. When adding a new employee and you detect that the memory is full, you just determine the employee with the smallest sort order criteria and remove it from the database.

Since you did not provide the Employee class I declare here an example:

class Employee {
    int frequency;
    Instant lastAccess;
}

Your database (can also be LinkedList):

private List<Employee> myDatabase = new ArrayList<>();

The comporator for evaluating the employee with the smallest criteria (first frequency is compared, if equals the lastAccess is compared:

public int compare( Employee emp1, Employee emp2 )
{
    int result = emp1.frequency - emp2.frequency;
    if ( result == 0 )
    {
        result = emp1.lastAccess.compareTo( emp2.lastAccess );
    }
    return result;
}

And here the 'main' method which inserts a new employee into your database (the implementation of isMemoryFull is left to you):

private void insertEmp( Employee emp)
{
    if ( isMemoryFull() )
    {
        Employee minEmp = myDatabase.stream().min( this::compare ).get();
        myDatabase.remove( minEmp);
    }

    myDatabase.add( emp );
}

Note: This works with Java8 lambdas and streams. For java < 8 you have to implement the compare method formally as Comparator and use Collections.sort instead the stream().min() method.