DevMan прав - по парадигме всегда!
На практике - любой написанный код (класс или интерфейс) требует расходов времени на создание и сопровождение. Сопровождать примитивный класс проще, чем примитивный класс и его интерфейс.
Поэтому на практике, обычно, пишут интерфейсы:
1. Как необходимую часть паттернов;
2. Если "интерфейс - это контракт взаимодействия": разрабатывается библиотека или компонент, здесь интерфейсы - это часть неизменяемого контракта;
3. Хорошая практика - все сервисы делать с интерфейсами. К этому подталкивают многие фреймерки JAVA, как пример:
Spring и OSGi (
Apache Felix);
4. Для JUnit тестировая. Пример: при тестировании бизнес логики, реальные сервисы заменяются тестовыми заглушками. Соотвественно класссы бизнес логики должны использовать интерфейсы, которые при реальной работе земеняются реальными имплементациями, а в тестовом окружении - тестовыми заглушками.