Microsoft Interviews · 1

The first 5 mins were introductions then we spent another 10-15 minutes talking about my past experiences and project. Then we jumped into a leetcode type coding problem.

Behavioral Question:

Tell me about a project you lead in the past.

Technical Problem:

Given an array of unsorted integers, determine the length of the longest sequence of consecutive integers that can be formed. The solution must run in linear time complexity.

Input: [100, 4, 200, 1, 3, 2]
Output: 4 # longest consecutive sequence is [1, 2, 3, 4]

Input: [-1, -2, 0, 1, 2, 3]
Output: 5 # sequence [-2, -1, 0, 1, 2, 3].

Input: [0, 0, 1, 2, 2, 3, 4, 5]
Output: 6 # sequence [0, 1, 2, 3, 4, 5]

Solution:

public class Solution
{
    public int LongestConsecutive(int[] nums)
    {
        var numSet = new HashSet<int>(nums);
        int longestStreak = 0;

        foreach (int num in numSet)
        {
            if (!numSet.Contains(num - 1))
            {
                int currentStreak = 1;
                while (numSet.Contains(num + currentStreak))
                {
                    currentStreak++;
                }
                longestStreak = Math.Max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }

    public static void Main()
    {
        var solution = new Solution();
        int[] nums = { 100, 4, 200, 1, 3, 2 };
        Console.WriteLine(solution.LongestConsecutive(nums));  // Outputs 4
    }
}

Both time and space complexity is O(n)