Google | Onsite | Longest Consecutive Sequence

Location
onsite
Posted
21 May 2024
382 reads

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.

How it went

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.

Questions asked (1)

  1. 01

    Longest Consecutive Sequence

    Data Structures & Algorithms · Medium

    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.

    Function Definition

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!