I came up with my own solution quickly that worked quite well (I missed one corner case) and overall did really well. However, I got a rejection because my solution was 'too simple' and 'did not work'. The interviewer kept pushing me towards the text book answer (probably the only thing they know) and they seem to expect the candidate to have the solution memorised and to just produce a text book answer. I think it was an extremely poor interview, as they didn't appreciate I managed to create an excellent solution on the spot without prior knowledge of this algorithm. Instead they were looking for someone who might not be a great problem solver but has memorised a bunch of useless algorithms that are never used in real life. The interview was called pair programming but it was just me coding, so it was not what I'd call pair programming which some other companies do really well.