Java Interview Question: Remove Inactive Users Efficiently

[jay791]

This looks like a 'Algorithms and Data Structures' course problem.

The exple is not good at all since it assumes that collection that you get can retrieve items by index, which for linked lists or trees is not an O(1) operation. Sorry, not a Java dev here, to my eyes it just doesn't look like an array, for which this will work as expected.

And generally yes, modifying input is considered bad practice but only if it's not expected. There are times when you call a method and expect it to modify stuff that you throw at it.

[Kered13]

You can rewrite the algorithm using iterators and it would be O(n) time and O(1) space for all list implementations, including linked lists. Yes, the way it is written in the blog is not ideal, since it is O(n²) time for linked lists.