But are you allowed to do that? The problem write-up makes it sound like you're supposed to be ingesting the interviewer's input. So, how did the interviewer code up sum types? With tons of nasty casting out of List<Object>, or with a slightly less terrible object hierarchy mimicking sum types?
That's what makes the question terrible. It implies you're supposed to be coding against an interface, but in the allowed language (Java) it's totally non-obvious what the interface is.
I'll submit this criteria for coding question: if a big chunk of your candidates can't write down the friggen type of the program you want them to implement -- and if two reasonable people could write down extremely different types for the same question -- then your question is bad and you should throw it out.
Is this even possible to do generically in Java or C#?
You can do it for objects so that it works for ALL types (i.e "object"), but you can't make it work generically for a type T for any T.
That's why this is such an excellent example of why sum types really are useful.
Writing the flatten interface without generics (Java List or c# IEnumerable) is not generic. If you do that it will accept a heterogeneous list - which we probably don't want.