Your solution is less important than your process for getting there. The interviewer wants to determine how you think about problem solving. He wants to make su

Your solution is less important than your process for getting there. The interviewer wants to determine how you think about problem solving. He wants to make sure that you do not just hack at the code until it seems to work. The amount of time required is generally not important unless it becomes excessive. For a problem like this 10 to 15 minutes is probably reasonable, 30 minutes might be a red flag and 45 minutes might end the interview (these times are very rough estimates and might be longer depending on the amount of discussion that takes place). Once a working solution is developed it is common (in general, I do not work at Google) to ask an applicant how they might improve or optimize it without actually having them do the additional work.