Google Interview Question: Find the length of the longes... | Glassdoor

Interview Question

Software Engineer Intern Interview(Student Candidate)

Find the length of the longest chain of consecutive

  integers in an unsorted set in linear time.
Answer

Interview Answer

5 Answers

3

int l = 1;
int max = 1;

for( int i = 0; i max ) max = l;
             l = 1;
      }
}

Negin on Mar 12, 2013
1

This finds the max length in a sorted array, not an unsorted set. I believe you'd need to iterate the set and call contains(), perhaps removing from the set after getting a result for contains() so it would be linear.

Ben H on Jul 29, 2013
0

public static int findMaxLengthConsecutive(Set input) {
        Iterator iter = input.iterator();
        int maxLength = 0;
        Set copySet = new HashSet(input); // Since I can't modify the original due to the iterator
        while (iter.hasNext()) {
            Integer i = iter.next();
            if (copySet.contains(i)) { // We haven't counted i in another list
                int tmpLength = 1;
                for (int k = i+1; input.contains(k); k++) {
                    tmpLength++;
                    copySet.remove(k); // We've counted k, remove it so we don't need to visit again
                }
                for (int k=i-1; input.contains(k); k--) {
                    tmpLength++;
                    copySet.remove(k);
                }
                if (tmpLength > maxLength) {
                    maxLength = tmpLength;
                }
            }
        }
        return maxLength;
    }

Ben H on Jul 29, 2013
0

public static int longestConSub(int[] arr) {
        int longestCount = 1;
        int currCount = 1;
        int end = 0;

        for(int i=0; i

Hao Q on Oct 28, 2013
0

Here's a Python solution. Unsure about the time complexity, but I believe it's linear.
def longestConsectutive(lst):
    curr = 0
    max = 0
    for i,v in enumerate(lst):
        tmp = lst[i]
        while(tmp in lst):
            curr += 1
            tmp += 1
        if curr > max:
            max = curr
        curr = 0

    return max

A. S. on Nov 6, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.