Google has a long and slow hiring process. I was contacted by a Google candidate review associate, who sent my information to a recruiter. Finally, I was contacted by a coordinator who scheduled the interview.

I appeared for the first phone screen. It had one coding question.

Given a doubly linked list such as:

1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6

And an input sequence (1, 2, 4, 3, 6):

Find the longest subsequence within the doubly linked list that contains the maximum number of elements from the input sequence. Return the last number of this subsequence.

For the above input, 1-2-3-4 is the longest subsequence according to the given input. The last number is 4.

For the input (1, 2, 4, 7):

The answer should be 1-2, and 2 is the last element.