Java Interview Question: Remove Inactive Users Efficiently

Efficient User Cleanup in Large Datasets

Problem Description

Imagine you’re working on a user access control system for an application, and you need to clean up a list of users who have been marked as inactive. Your goal is to remove all inactive users (status = INACTIVE) from the list while keeping the operation efficient and minimizing memory usage.

The current solution creates a new list to store active users, which is memory inefficient for large lists.

• How would you modify the solution to improve memory usage by operating in place?

• What is the time complexity of your proposed solution, and how does it compare to the existing approach?

Existing Approach

• The existing approach Iterates over each customer filters only the active ones and then maps it to a new array list.

Time complexity: Since we are iterative over each element, time complexity is O(N)

Space complexity: Since we are creating a new array list to store active customers, space complexity is. O(N)

Solution

• One of the major problems with the existing approach is that it takes an additional list to store the active customer.

• So if we can find an approach to filter inactive customers in place, we can save memory from O(N) to O(1).

• Left Pointer (leftPointer): This pointer keeps track of the position in the list where the next active customer should be placed.

• Right Pointer (rightPointer): This pointer iterates through all customers in the list and checks if each customer is active or inactive.

• If rightPointer finds an active customer, it places that customer at the current position of leftPointer and then increments leftPointer to the next position. This ensures that the active customers are moved towards the front of the list.

• If rightPointer finds an inactive customer, it simply skips that customer and continues moving rightPointer forward. No modification is made to the list in this case.

• The line customers = customers.subList(0, leftPointer); creates a view of the original list from index 0 to leftPointer (exclusive). It doesn't modify the original list directly, but instead creates a new list backed by the original list, containing only the active customers.

Time Complexity: Since we are iterative over each element, time complexity is O(N)

Space Complexity: Since we are replacing elements in-place we do not need any extra memory and hence memory usage is O(1).

Benchmarking the solutions

• Let's create a nice little helper method benchmark that takes a runnable task as input and calculates total memory usage and execution time for the task.

Output:

After running both approaches through the benchmark method, we can see a lot of savings in terms of memory and total execution time.

existing approach:
exec time in milliseconds: 8330
total memory used (mbs): 466.0

efficient approach:
exec time in milliseconds: 5213
total memory used (mbs): 1.0

The source code is available here.

Check out more Java coding questions here.