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 one 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 of the class ends up with a hard-coded dependency to it.
You can kinda get around this by messing with the file system and compiler options so that com.example.Foo maps to a different file, but the users of your code will hate you for it, and your code is still hard-coded to one implementation of the class. e.g. If class Bar uses some class Foo, you can play file system tricks to choose a Foo at compile time, but you won't be able to have two Bars using two different implementations of Foo.
This unfortunate design decision means people need to lean on 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 binary methods that look at the private fields of two instances of the class, you're screwed. That's why you don't see union in Java's Set interface. But most of the time, you can get away with it.
Of course, if you call new Foo you still have a hard-coded dependency on the class, so you need a factory or a dependency injection framework to pass you an unknown implementation of the interface.
It's up to you to decide if it's worth bloating your codebase with all these 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 fairly trivial. But if it's part of the public API of a library you've published, you don't have the option of fixing the client code, so you may want to future-proof the code.