В вашем примере все выглядит хорошо.
Помните, что в java есть пакеты, и в приведенном выше примере вы не указываете пакет, поэтому интерфейс и класс находятся в пакете по умолчанию. Вы должны поместить эти файлы в какой-то каталог, а затем скомпилировать файл класса.
Для компиляции используйте:
javac ExampleImplementation.java
Или лучше, используйте некоторую IDE (Eclipse или Netbeans), тогда, если что-то будет не так, IDE уведомит вас и сообщит, с какой ошибкой вы столкнулись.