Longest Consecutive Sequence

Python data engineering interview problem. Difficulty: beginner. Pattern: Hashing. About 10 minutes. Free to practice.

Length of the longest run of consecutive integers. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

You have a list of whole numbers in any order. A consecutive sequence is a group of numbers that follow each other with no gaps, like 1, 2, 3, 4. Your task is to find how long the longest such sequence is. Write a function longest_consecutive(nums) that returns the length of the longest consecutive sequence of numbers that can be formed from the values in the list. The numbers do not need to be next to each other in the list, and the list may have duplicates. For [100, 4, 200, 1, 3, 2] the longest sequence is 1, 2, 3, 4, so the answer is 4. Keep the print lines in the editor.

Requirements

• Return the length of the longest run of consecutive integers, such as 5, 6, 7.
• The numbers can be anywhere in the list, in any order.
• A duplicate value counts only once.
• Return 0 for an empty list.

Constraints

• nums can be unsorted and can contain duplicates.
• Numbers can be negative.
• Aim for O(n) time. Sorting the list works too, but it takes O(n log n).

Examples

Input: longest_consecutive([100, 4, 200, 1, 3, 2]) Output: 4 1,2,3,4 form a run.

Topics: lakebench, python, set, sequence.

More Python interview questions · All interview problems · Learn data engineering