After solving a few problems for their Quora challenges, a recruiter emailed me to schedule a screen. The recruiter performed a basic screening, pitched me on the company, and was generally very nice. I then scheduled a phone screen with them, which I had a very poor experience with.

The interviewer mentioned he had been at the company for six months and that a person was reverse shadowing him. This led me to believe it might have been his first time conducting an interview. The experience later reinforced this belief.

The first problem given was fairly easy, and we went through it in around 15-20 minutes, including some follow-ups.

The interviewer did a very poor job on the second problem. After giving the question, he provided an example that was completely wrong, making it difficult for me to understand what he wanted. I was misled for quite some time before finally getting him to realize he had given an incorrect example.

After understanding the problem, I was confident I could solve it using recursion and later optimize by memoizing. However, midway through the interview, the interviewer told me I had made a mistake and pointed out the specific line. Later on, after the interview, I learned that I had the correct solution and he was incorrect. I verified my code with test cases and by checking with others, confirming he was wrong. Unfortunately, I didn't know better at the time, assuming he was trying to help.

In the end, we ran out of time and ended the interview because I could not reach the correct solution after deleting the line of code he indicated was wrong. I was determined that my solution was correct and later verified that it indeed was.

Since the problem can be solved both recursively and iteratively (using DP), I suspect he didn't know the recursive solution well and only knew the iterative one.

A DP/recursion problem that can already be found on Glassdoor.