Java Interfaces – Does It Always Make Sense to Program to an Interface?

I've seen the discussion at this question regarding how a class that implements from an interface would be instantiated. In my case, I'm writing a very small program in Java that uses an instance of TreeMap, and according to everyone's opinion there, it should be instantiated like:

Map<X> map = new TreeMap<X>();

In my program, I'm calling the function map.pollFirstEntry(), which is not declared in the Map interface (and a couple others who are present in the Map interface too). I've managed to do this by casting to a TreeMap<X> everywhere I call this method like:

someEntry = ((TreeMap<X>) map).pollFirstEntry();

I understand the advantages of the initialization guidelines as described above for large programs, however for a very small program where this object would not be passed to other methods, I would think it is unnecessary. Still, I'm writing this sample code as part of a job application, and I don't want my code to look badly nor cluttered. What would be the most elegant solution?

EDIT: I would like to point out that I'm more interested in the broad good coding practices instead of the application of the specific function TreeMap. As some of the answers have already pointed out (and I've marked as answered the first one to do so), the higher abstraction level possible should be used, without losing functionality.