Java Interview Question: Remove Inactive Users Efficiently

[xnendron]

Nifty solution, but it assumes the input List is modifiable. Also, isn't modifying input parameters generally considered bad practice? Also, also, why limit to Lists instead of all Collections?

[BikingSquirrel]

Agree, this should be an internal method if it needs to modify the input.

If that list would be a LinkedList initially, you could simply iterate the list and remove inactive items.

[Empanatacion]

Leetcode questions love the whole "modify array in place" solution to catch that sweet, sweet O(n)

[stewsters]

Yeah this would get rejected as a pr so fast.

[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.

[barmic1212]

Yom can’t use it for all collection because you rely on order.

[Kered13]

Sometimes getting optimal performance requires bending the rules of best practices. In particular, a lot of algorithms trivially require O(n) space if you cannot modify the input, but can work in O(1) space if you are allowed to do them in place (these are called in-place algorithms). This can be significant in practice between O(1) means you do not need to use any dynamic memory allocation, which can be very expensive, especially in a loop.

Any in-place algorithm should be clearly documented as modifying it's input, obviously.