I proposed an O(n) SOlution. But this interviewer was not interested he gave me disgusting look as if i have given exponential solution. He then boasted that he could have done lower then O(n). FInally i confronted him and ask him to do it. To my surprise this guy couldnt do. He was just writing something on board but cudnt do anything. Finally to save his ego he said that he was working for Microsoft and he doesn't remember solution.Dude then you shouldn't ask this question.