At top-tier software companies, expect all of the (applicable) questions to be accompanied by the "and what is the runtime complexity of your solution" followup

At top-tier software companies, expect all of the (applicable) questions to be accompanied by the "and what is the runtime complexity of your solution" followup question. Depending on your abilities, the interviewer will try to lead you towards an optimal solution.