It's a symptom of a limitation in Java/C#'s module systems.
In principle, there's no reason you shouldn't be able to swap out one implementation of a class for another with the same constructor and method signatures. There are languages that allow this. However, Java and C# insist that every class have a unique identifier (the fully qualified name) and the client code ends up with a hard-coded dependency on it.
You can sort of get around this by fiddling with the file system and compiler options so that com.example.Foo maps to a different file, but this is surprising and unintuitive. Even if you do so, your code is still tied to only one implementation of the class. I.e. If you write a class Foo that depends on a class MySet, you can choose an implementation of MySet at compile time but you still can't instantiate Foos using two different implementations of MySet.
This unfortunate design decision forces people to use interfaces unnecessarily to future-proof their code against the possibility that they'll later need a different implementation of something, or to facilitate unit testing. This isn't always feasible; if you have any methods that look at the private fields of two instances of the class, won't be able to implement them in an interface. That's why, for example, you don't see union in Java's Set interface. Still, outside of numeric types and collections, binary methods aren't common, so you can usually get away with it.
Of course, if you call new Foo(...) you still have a dependency on the class, so you need a factory if you want a class to be able to instantiate an interface directly. However, it's usually a better idea to accept the instance in the constructor and let someone else decide which implementation to use.
It's up to you to decide if it's worth bloating your codebase with interfaces and factories. On the one hand, if the class in question is internal to your codebase, refactoring the code so that it uses a different class or an interface in the future is trivial; you could invoke YAGNI and refactor later if the situation arises. But if the class is part of the public API of a library you've published, you don't have the option of fixing the client code. If you don't use an interface and later need multiple implementations, you'll be stuck between a rock and a hard place.