Brain-numbing theoretical question not grounded in practicality at all. Interviewer seems disinterested and playing with his phone most of the time and was hard to understand at times. If you will like to work in a company that values how to implement a trivial algorithm over how to actually apply it, then this is for you - and if you could really implement it off the top of your head, I suggest you try for Google.