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.

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 &gt; 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 &gt; max:
max = curr
curr = 0

return max

A. S. on Nov 6, 2013