So I was interviewing today with one of the Big 4 tech giants and I was asked an algorithmic question. Before I start explaining my solution, I ran through all the famous data structures in my head and had a very clever idea of using a Map which reduced my naive solution from O(N^2logN) to O(N). I proceeded to explain my solution clearly and coded it up. The interviewer asked some followup questions about them and he said that this was indeed the optimum solution.
Now after I finished the interview, I started getting worried because I am wondering if the interviewer would think that I knew this question from before and just wrote down the answer I know. Do interviewers generally think that anybody who gets the optimum solution from the start has most likely seen this question before?
EDIT: I got the internship :). I guess I got my answer.