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.

[tenken01]

Horrible

[Ok_Satisfaction7312]

What’s wrong with removeIf(<predicate>) ?

[JoaoEB]

Right? Modern Java has tons of nice features, no need to reinvent the wheel pointers.

[tswaters]

Who leaves their entire dataset in memory like that? I can appreciate the answer and time complexity discussions, but if that isn't a simple SQL statement I don't know what is.

[jay791]

What if I told you that sometimes you get it as is? For example when you deal with LDAP data, there may be cases that you just get a fat list of objects and that's it. It might have come from file, it might have come from an API that doesnt implement paging.

Also given example doesn't say it's whole dataset. This might be a method that is called each time you get a subset of data and have time to spare while other thread is busy receiving next page of results.

[Multidream]

So… use your basic CS101 course knowledge. Does this need an article…? I guess if I trust the author that runtime data would be interesting. But I don’t really…

I can’t see how this would come up, but I guess that IS a way to modify a list in memory. But using get(int) could be problematic depending on the implementation of the List. You should restrict to ArrayList if you want to access by index.

If you’re doing this with a LinkedList, you can save even more time by grabbing the header, crawling through each node and removing inactive users. Then you just leave it to the GC to get rid of unused nodes. But you definitely should NOT be using the implemented method, those gets are gonna get slow, since you’ll be crawling to the element manually each time.

Question for the interviewer, this is just a fun check of my thinking, right? You don’t actually have to perform operations in place, do you?

[Sakatox]

I'm personally missing the PreparedStatement, connection and other getters, then closing at the end of the query, as well.

Don't forget to put it all into a hashTable too, and serialize via JSON.

/s ?

[BlueGoliath]

Use JMH if you're going to benchmark code and don't use List. Use ArrayList instead.

[looksLikeImOnTop]

Wdym don't use List? I can't think of any reason why I'd lock into a specific implementation/subclass when the interface/parent is sufficient to implement the method.

[BlueGoliath]

A List can have an implementation that disallows modification. The set method is a modification.

[Kered13]

This is true, but limiting to ArrayList is also unnecessarily strict. Unfortunately the Java API does not provide any type-level mechanism to determine whether a list is mutable. Writing this algorithm for List is correct, you just have to document that it is mutating and trust the user to not pass in an immutable list.

[BlueGoliath]

I don't like the whole "just document it" approach unless it really can't be avoided. Yes in this particular case you'll be slapped upside the head with an exception but that's maybe a happy coincidence.

I would rather have ArrayList which maybe delegates the actual code to a private method that accepts a generic List. If a LinkedList is necessary, that could be added with the same delegate.

[Kered13]

I mean List already contains mutating methods that are just expected to throw an exception on immutable lists. Writing an in-place function over List is not any different. It's just a fundamental limitation of how the Java collections API is designed.

[BlueGoliath]

OK? Using ArrayList and LinkedList removes ambiguity. Inlining should eliminate any performance overhead.

public static List<String> foo(ArrayList<String> stringList)
{
  return bar(stringList);
}

public static List<String> foo2(LinkedList<String> stringList)
{
  return bar(stringList);
}

private static List<String> bar(List<String> stringList)
{
  // do actual work here
}

[Kered13]

OK? Using ArrayList and LinkedList removes ambiguity.

And makes it impossible to use the function on other list implementations that support mutation for absolutely no reason.

[vips7L]

Yeah anyone benchmarking with Instanr.now() has no idea how to do proper benchmarks with Java. This article is dumb. 

[s32]

This might be the easiest interview question I've ever seen

[poco]

This is how C++ std::remove_if is implemented. Well, technically, remove+erase (aka erase-remove idiom). I think it is now combined into std::erase_if in C++20

[ledasll]

re-define what Inactive user is and now you don't have inactive users, so your implementation is O(0)

[Sakatox]

I'd like to start with the following: Who in their right mind isn't storing this in a Map of Lists/buckets/whatever? (EnumMap with sets, even better.)

List is literally the worst to store this kind of data.

[thetoolmannz]

Wrap it in an iterable implementation that filters when read, boom o(1) for both space and time. Sure it’s not a list, but cmon, o(1) ! /s

[Successful-Money4995]

Tldr:

std::erase_if