Google | Onsite | Longest Consecutive Sequence
Summary
I recently participated in an onsite interview with Google where I was tasked with solving the 'Longest Consecutive Sequence' problem, a classic algorithm challenge.
Full Experience
During my onsite interview at Google, the interviewer presented me with the problem of finding the longest consecutive elements sequence in an unsorted array of integers, emphasizing an O(n) time complexity requirement. I proceeded to discuss and implement a solution based on using a hash set to efficiently check for consecutive numbers. I also showed a slightly different approach during the discussion.
Interview Questions (1)
Problem Statement
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Examples
Example 1:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Explanation: The longest consecutive elements sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8]. Therefore its length is 9.
Constraints
- The array may contain duplicates.
- The array may contain negative numbers.