I submitted my resume and communicated with HR a few times before an online interview was set up. The interview problem was not hard. I quickly gave a solution, but the interviewer pushed for a better one – one with improved time and space complexity. This was a very reasonable request. Unfortunately, I did not perform well enough to secure an on-site interview.

Given an array of integers, find the length of the longest subsequence such that elements in the subsequence are consecutive integers.