There are languages - C and Go, and to a lesser extent, C++ - in which re-implementation of data structures and algorithms is not uncommon.
To your larger point, data structures and algorithms are popular in interviews for the same reason Project Euler is popular - it is very easy to ask a well defined, but interesting question about core CS or math.