One hot encoding of target space
For certain models, it can be important to make sure the inputs are linearly independent. I'm pretty sure this is never the case for the outputs. If we have more than two classes, it's extremely difficult if not impossible to output class-probabilities if we don't have a specific dimension for each class in the output vector. In other words, your suggestion has much more explanatory power than what was suggested by your interviewer, which is solving a problem that exists on the inputs for some models but not for the outputs.

In multi-class problems, it is indeed the norm that each class has their own dimension in the output vector as you suggested. Either the interviewer was trying to look smart and confused input and output encoding (which still would only apply to certain families of models), or you aren't remembering the events of the interview properly. If you're confident that the interview went as you described, you should consider complaining to your point of contact that you were criticized for giving a correct answer. 

Feel free to cite the following as popular/canonical examples of multi-class classifiers:


http://scikit-learn.org/stable/modules/generated/sklearn.ensemble.RandomForestClassifier.html#sklearn.ensemble.RandomForestClassifier.predict_proba



  Returns: array of shape = [n_samples, n_classes]



https://keras.io/losses/#categorical_crossentropy



  when using the categorical_crossentropy loss, your targets should be in categorical format (e.g. if you have 10 classes, the target for each sample should be a 10-dimensional vector that is all-zeros expect for a 1 at the index corresponding to the class of the sample)