Google Interview Question for Software Engineer in Tests Software Engineer / Developers


Country: -
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
14
of 14 vote

"""Given an int array which might contain duplicates, find the largest subset of it which form a sequence.
Eg. {1,6,10,4,7,9,5}
then ans is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time"""
def find(arr):
    table = {}
    first = 0
    last = 0
    for i in arr:
        beg = end = i
        if i in table:
            continue
        table[i] = 'EXISTED'
        if i - 1 in table:
            beg = table[i-1]
        if i + 1 in table:
            end = table[i+1]
        table[beg] = end
        table[end] = beg
        if end - beg > last - first:
            first = beg
            last = end
    return list(range(first, last + 1))

arr = [1,6,10,4,7,9,5, 5,8]
            
print(find(arr))

O(n) time and space
In Python, dict is a hash with O(1) time to retrieve an item.

- Anonymous October 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

dunt you think ; n means number of element;
what could be your space complexity for having only 2 number {1,100}??

- skg December 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 Probably some explanation would get you some upvotes :-) That's very clever, on every iteration the dictionary keeps, for each value, the starting point of the range (seen so far), except if it's the first element in the range, then it keep where it ends. O(n) space, O(n) time, nice.

- tokland October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
6
of 6 votes

nice algorithm!

java codes below

public int[] longestConsecutiveSequence(int[] a) 
        {
                int first = Integer.MAX_VALUE; // the first number of the maximum consecutive sequence
                int length = 0; // the length of the maximum consecutive sequence
                Map<Integer, Integer> table = new HashMap<Integer, Integer>();
                for(int i: a) {
                        if(!table.containsKey(i)) {
                                int start = i;
                                int end = i;
                                if(table.containsKey(i + 1) && table.get(i + 1) >= i + 1) {
                                        end = table.get(i + 1);
                                        table.remove(i + 1);
                                        table.remove(end);
                                }
                                if(table.containsKey(i - 1) && table.get(i - 1) <= i - 1) {
                                        start = table.get(i - 1);
                                        table.remove(i - 1);
                                        table.remove(start);
                                }
                                table.put(start, end);
                                table.put(end, start);
                                if(end - start + 1 > length) {
                                        first = start;
                                        length = end - start + 1;
                                }
                        }
                }
                System.out.println(table);
                System.out.println(length);
                int[] s = new int[length];
                for(int i = 0; i < length; i++) s[i] = first + i;
                return s;
        }

- dgbfs December 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And here is the c# implementation of the same thing

{{public static void LongestContiguousSubArr(int[] arr)
{
Dictionary<int, int> map = new Dictionary<int, int>();
int f = 0;
int l = 0;
for (int i = 0; i < arr.Length; i++)
{
int num = arr[i];

int beg = num;
int end = num;

if (map.ContainsKey(num))
continue;//already processed

map[num] = num;

int numm1 = num - 1;
int nump1 = num + 1;

if (map.ContainsKey(numm1))
beg = map[numm1];
if (map.ContainsKey(nump1))
end = map[nump1];

int temp = map[beg];
map[beg] = map[end];
map[end] = temp;

if (f - l <= end - beg)
{
f = beg;
l = end;
}
}

for (int i = f; i < l; i++)
{
Console.WriteLine(i);
}
}}}

- bp September 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Reposting with formatting

public static void LongestContiguousSubArr(int[] arr)
        {
            Dictionary<int, int> map = new Dictionary<int, int>();
            int f = 0;
            int l = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                int num = arr[i];
                
                int beg = num;
                int end = num;

                if (map.ContainsKey(num))
                    continue;//already processed

                map[num] = num;

                int numm1 = num - 1;
                int nump1 = num + 1;

                if (map.ContainsKey(numm1))
                    beg = map[numm1];
                if (map.ContainsKey(nump1))
                    end = map[nump1];
                
                int temp = map[beg];
                map[beg] = map[end];
                map[end] = temp;

                if (f - l <= end - beg)
                {
                    f = beg;
                    l = end;
                }
            }

            for (int i = f; i < l; i++)
            {
                Console.WriteLine(i);
            }

}

- bp September 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can someone post an explanation?

- ankeshanand1994 October 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

okay here is an explanation:
Logic here is that each element in the hashtable keeps track of the sequence. So boundary elements of the sequence are important as the end element of the sequence points to beginning element of the sequence and beginning element of the sequence points to the end element. So whenever a new element is to be added to the sequence it picks up the boundary value and becomes the new boundary. Check how 8 is added to the table below:

Array a:      [1, 6, 10, 4, 7, 8]

i: 1 	 Table: {1=1}
i: 6 	 Table: {1=1, 6=6}
i: 10 	 Table: {1=1, 6=6, 10=10}
i: 4 	 Table: {1=1, 4=4, 6=6, 10=10}
i: 7 	 Table: {1=1, 4=4, 6=7, 7=6, 10=10}
i: 8 	 Table: {1=1, 4=4, 6=8, 7=6, 8=6, 10=10}

- Yash May 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I believe the sequence here in the problem does not only means an arithmetic sequence with a common difference of 1. So with an input of {1,2,3,4,6,8}, the output of this solution will be {1, 2, 3}. However the correct answer should be {2, 4, 6, 8}

- bsw August 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
10
of 10 vote

Here's a in-place algorithm with O(n) time and O(1) extra-space
Given array 'A' of size 'n', the goal is to reorder elements in the given array so that they are in their correct positions i.e. A[i]-min(A) is at A[0] when A[i]==min(A)
and A[j]-min(A) is at A[1] if A[j] = min(A)+1
and A[k]-min(A) is at A[2] if A[k] = min(A)+2 ..... so on....

1. Pass1: Find max(A) and min(A)
   if ( max(A)-min(A) > n ) then return false //i.e. you cannot have a sequence greater than n
2. Pass2: For every element 'i', 
              a. if A[i] == A[A[i]-min(A)] //already at the right position
                    if i != arr[i]-minArr then set A[i]=-Inf //this is a duplicate
                    else continue next iteration
              b. else //swap to move it to the right position
                     swap A[i] with A[A[i]-min(A)]
                     after swapping if A[i] != min(A)+i repeat from step 'a'
3. Pass3: For every element 'i', check if next element == A[i]+1,
              if not then return false.

An example with duplicates: {45,50,47,45,50,46,49,48,49}
Pass1: max(A) = 50, min(A) = 45
Pass2: modified Array:
[45,50,47,45,50,46,49,48,49] //45 already at A[A[0]-min(A)]
[45,46,47,45,50,50,49,48,49] //swap 50 & 46
[45,46,47,45,50,50,49,48,49] //47 already at A[47-45]
[45,46,47,-Inf,50,50,49,48,49] //A[3] = -Inf since it is a duplicate
[45,46,47,-Inf,-Inf,50,49,48,49]
[45,46,47,-Inf,-Inf,50,49,48,49]
[45,46,47,-Inf,49,50,-Inf,48,49]
[45,46,47,48,49,50,-Inf,-Inf,49]
[45,46,47,48,49,50,-Inf,-Inf,-Inf]
Pass3: return true

//Note : instead of -Inf you can use some other marker such as min(A)-2

ok, since many of you are disagreeing, I've posted the code below

- archioliis October 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a good solution. I have one more idea.

Step 1: Find the min and max
Step 2: Subtract each element from Max. k = Max - A[i]. keep adding and multiplying this k to a variable Sum and Product.
Sum += k
Product = Product *k;
Step 3: n = max-min. Find sum on 0+1+..+n and product 1*2*...n. This sum and product much be equal to the Sum and Product found in step 2.

Let me know if I am doing something wrong in this solution.

- Anonymous October 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will not handle duplicate elements....

- cyril October 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it wont work

- sinvija November 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Find min and max
if (max-min != n-1) return false;
for i=0:n
if(A[A[i]-min] is visited)
return false;
else
set visited A[A[i]-min];
return true;

To set the highest bit of A[i] as the mark to indicate whether the element is visited or not.

- Anonymous November 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

//ideone.com/Sa2Xz

#include <vector>
#include <iostream>
#include <algorithm>
#include <limits>
using std::vector;
using std::cout;

bool HasSequence (vector <int>& arr)
{
	int maxArr, minArr;
	bool success = true;
	if (arr.empty())
	{
		return !success;
	}

	//Step-1:
	maxArr = *std::max_element (arr.begin(), arr.end());
	minArr = *std::min_element (arr.begin(), arr.end());
	if (maxArr - minArr >= arr.size())
	{
		return false;
	}

	//Step 2:
	//For every element 
	for ( int i = 0; i < arr.size() ; ++i)
	{
		bool swappedProperly = false;
		while (!swappedProperly) //DONT GET DECIEVED BY THIS WHILE LOOP FOR O(N^2) complexity.// This algo is stil O(n)
		{
			if (minArr > arr[i]) //Duplicate
			{
				break;
			}
			// a. if A[i] == A[A[i]-min(A)] 
			if (arr[i] == arr[arr[i]-minArr]) //already at the right position
			{
				if (i != arr[i]-minArr) //this is a duplicate
				{
					arr[i] = minArr - arr[i];	//mark it less than min(A) so that it can be identified as dup
				}
				swappedProperly = true; //next iteration
			}
			// b. swap to move it to the right position
			else
			{
				// swap A[i] with A[A[i]-min(A)]
				std::swap (arr[i], arr[arr[i]-minArr]);
				// after swapping if A[i] != min(A)+i repeat from step 'a'
				if (arr[i] == minArr+i) 
				{
					swappedProperly = true;
				}
			}
		}
	}

	//Step 3: //For every element 'i', 
	vector<int>::iterator itr = arr.begin();
	++itr;
	for ( ; arr.end() != itr ; ++itr)
	{
		if (*itr < minArr)
		{
			//traverse until the end to see that there are no gaps in the sequence
			for ( ; arr.end() != itr; ++itr)
			{
				if (*itr >= minArr)
				{
					success = false;
					continue;
				}
				*itr = minArr + *itr;	//revert change done for marking as dup
			}
			break;
		}
		if ((*(itr-1))!= (*itr)-1) //check if current element == previous element - 1,
		{
			success = false;
			break;
		}
	}
	return success;
}

int main()
{
	int arr[] = {45,50,47,45,50,46,49,48,49};
	std::vector<int> inputArray (arr, arr + sizeof(arr)/sizeof(int));
	if (!inputArray.empty() && HasSequence (inputArray) )
	{
		std::cout << "Contains a Sequence :\t [" ;
		int prevVal = inputArray[0];
		for (std::vector<int>::const_iterator itr = inputArray.begin();
			inputArray.end() != itr; ++itr)
		{
			if (*itr < prevVal)
			{
				break;
			}
			std::cout << *itr << "'";
			prevVal = *itr;
		}
		std::cout << "]" << std::endl;
	}
	else
	{
		std::cout << "Doesn't contain a sequence" << std::endl;
	}

}

- archioliis November 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Solution posed is correct. In words -
Find min of array. We mark a[i-min] –ve, if a[i] is –ve we mark its absolute position value –ve. If index is out of range or we already see the marked –ve value while marking then no sequence. At the end of the iteration all array elements should be –ve.

- yogesh March 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Solution posed is correct. In words -
Find min of array. We mark a[i-min] –ve, if a[i] is –ve we mark its absolute position value –ve. If index is out of range or we already see the marked –ve value while marking then no sequence. At the end of the iteration all array elements should be –ve.

- yogesh March 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Solution posed is correct. In words -
Find min of array. We mark a[i-min] –ve, if a[i] is –ve we mark its absolute position value –ve. If index is out of range or we already see the marked –ve value while marking then no sequence. At the end of the iteration all array elements should be –ve.

- yogesh March 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Solution posed is correct. In words -
Find min of array. We mark a[i-min] –ve, if a[i] is –ve we mark its absolute position value –ve. If index is out of range or we already see the marked –ve value while marking then no sequence. At the end of the iteration all array elements should be –ve.

- yogesh March 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How would this work if the set is {45,50,47,45,50,50,49,48,46,49}?

Would your step 2 in the example be an infinite loop as you are switching 50 in position 2 with 50 in position 5 and keep looping?

Moreover, this seems like O(n^2) solution as you keep going back to step a. Or did I miss something in understanding your example?

- Prash September 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
6
of 6 vote

One run with one hash table:

Keep in hash table using the numbers as keys of a structure containing two numbers: the first (F) and the last (L) element of a possible chain. Only first and last element of the chain need to be properly updated. When you insert an element N in the table check also for the neighbors (N-1 and N+1). We will call '(N)->F' The number stored as first of a possible chain in the Nth position and '(N)->L' the number stored as last of the chain. Possible cases are:

- The number is already there => Do nothing.

- No neighbors => make a single-node chain storing the number as first and last in its own position:
(N)->F = N
(N)->L = N

- Only the left neighbor is present => The number becomes the last element in the chain. Get the first element of the chain from the left neighbor and update the chain info:
(N)->L = N
(N)->F = (N-1)->F
((N-1)->F)->L = N

- Only right neighbor is present => Similar to previous
(N)->F = N
(N)->L = (N+1)->L
((N+1)->L)->F = N

- Both neighbors are present => Link two chains updating the first of the left and last element of the right:
((N-1)-F)->L = (N+1)->L
((N+1)->L)->F = (N-1)-F

Each time you update a chain you can easily compute the length. Keep track of the largest one storing in a couple variables its length and its first element and updating as required.

- juando.martin July 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

seems good..

- Anonymous July 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

When left neighbour is present, instead of just updating (N-1)->F->L, you should update the L value for every number between (N-1)->F and N. For instance, suppose 1, 2, 3 are present in the hashtable and now 4 is inserted, you need to update the L value for all 1, 2, 3 to 4.

Thus the time complexity is O(nL) with L being the maximum length of consecutive numbers.

- alphayoung August 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Like

- jiangok2006 July 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have implemented the idea in Java. It looks good.

import java.util.HashMap;

class Node {

	Integer first;
	Integer last;

	Node(Integer first_int, Integer last_int) {

		this.first = first_int;
		this.last = last_int;

	}

}

public class ConsecutiveString {

	public static void main(String[] args) {
		Integer max_length = 0;
		String max_string = "";

		HashMap<Integer, Node> table = new HashMap<Integer, Node>();

		Integer[] numbers = { 101, 2, 3, 104, 5, 103, 9, 102 };
		for (Integer number : numbers) {

			if (table.containsKey(number)) {
				continue;
			} else {
				Integer first = number;
				Integer last = number;
				if (table.containsKey(number - 1)) {
					first = table.get(number - 1).first;
				}
				if (table.containsKey(number + 1)) {
					last = table.get(number + 1).last;
				}
				// update all consecutive nodes

				String consecutive = number.toString();

				int i = 1;
				while (table.containsKey(number - i)) {
					table.get(number - i).first = first;
					table.get(number - i).last = last;
					consecutive = ((Integer) (number - i)).toString() + ","
							+ consecutive;
					i++;
				}

				i = 1;
				while (table.containsKey(number + i)) {
					table.get(number + i).first = first;
					table.get(number + i).last = last;
					consecutive = consecutive + ","
							+ ((Integer) (number + i)).toString();
					i++;
				}

				Node new_node = new Node(first, last);
				table.put(number, new_node);

				int length = last - first + 1;
				if (length > max_length) {
					max_length = length;
					max_string = consecutive;
				}

			}

		}

		System.out.println(max_string);

	}
}

- Another Humble Programmer October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well that is not exactly my idea. Than does not run in O(n) as you update nodes in the table that need not. Take into account that once a node is stored it will never be checked again unless a neighbor is checked in too for the first time, so you only need to keep updated the extremes of a chain.

The code would be for the node class just the same:

import java.util.HashMap;

class Node {

	Integer first;
	Integer last;

	Node(Integer first_int, Integer last_int) {

		this.first = first_int;
		this.last = last_int;
	}
}

But for the Consecutive string class:

import java.util.HashMap;

public class ConsecutiveString {

	public static void main(String[] args) {
		Integer max_length = 0;
		Node max_chain = null;

		HashMap<Integer, Node> table = new HashMap<Integer, Node>();

		Integer[] numbers = { 101, 2, 3, 104, 5, 103, 9, 102 };
		for (Integer number : numbers) {

			if (table.containsKey(number)) {
				continue;
			} else {
				Node here;
				if (table.containsKey(number - 1)) {
					Node left = table.get(number - 1);
					if (table.containsKey(number + 1)) {
						Node right = table.get(number + 1);
						// We have both left and right. Link them and
						// store in both sides
						left.last = right.last;
						right.first = left.first;
						here = left; // Or right, it's the same
					} else {
						// there is a node at our left, but not at the right.
						left.last = number;
						table.put(number, left);
						here = left;
					}
				} else if (table.containsKey(number + 1)) {
						// We have only a node at our right
						Node right = table.get(number + 1);
						right.first = number;
						here = right;
				} else {
						// No other node around
						here = new Node(number, number);
					}
				table.put(number, here);
				int length = here.last - here.first + 1;
				if (length > max_length) {
					max_length = length;
					max_chain = here;
				}

			}

		}

		System.out.println(max_chain.first.toString() + " - " +
		                   max_chain.last.toString());

	}
}

- juando.martin October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@juando.martin Yes. I think you are right :-) Good idea. Thank you so much. What I implemented is what alphayoung suggests.

- Another Humble Programmer October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I also think the idea of juando.martin is incorrect, as doubted by alphayoung.
For example, if we set:
Integer[] numbers = { 1, 3, 5, 7, 9, 4, 6, 2, 8 };
The the result of the code of juando.martin is:
3 - 9
while the correct answer should be:
1 - 9

- Alva0930 February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Well, it was not the idea that is wrong, but the code. I did not realize that cannot get the ends of the chain through the nodes, but rather through the table. As I said you don't have to modify all the nodes, only the ends. Here is the (hopefully) right code. Only a couple of indirections added to my previous.

import java.util.HashMap;

public class ConsecutiveString {

	public static void main(String[] args) {
		Integer max_length = 0;
		Node max_chain = null;

		HashMap<Integer, Node> table = new HashMap<Integer, Node>();

		//Integer[] numbers = { 101, 2, 3, 104, 5, 103, 9, 102 };
		Integer[] numbers = { 1, 3, 5, 7, 9, 4, 6, 2, 8 };
		for (Integer number : numbers) {

			if (table.containsKey(number)) {
				continue;
			} else {
				Node here;
				if (table.containsKey(number - 1)) {
					Node left = table.get(number - 1);
					left = table.get(left.first);
					if (table.containsKey(number + 1)) {
						Node right = table.get(number + 1);
						right = table.get(right.last);
						// We have both left and right. Link them and
						// store in both sides
						left.last = right.last;
						right.first = left.first;
						here = left; // Or right, it's the same
					} else {
						// there is a node at our left, but not at the right.
						left.last = number;
						table.put(number, left);
						here = left;
					}
				} else if (table.containsKey(number + 1)) {
						// We have only a node at our right
						Node right = table.get(number + 1);
						right = table.get(right.last);
						right.first = number;
						here = right;
				} else {
						// No other node around
						here = new Node(number, number);
					}
				table.put(number, here);
				int length = here.last - here.first + 1;
				if (length > max_length) {
					max_length = length;
					max_chain = here;
				}

			}

		}

		System.out.println(max_chain.first.toString() + " - " +
		                   max_chain.last.toString());

	}
}

- juando.martin February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well, I misunderstood the idea of juando.martin because I looked the code, which has bugs, to get the idea.
It seems to be correct now.

- Alva0930 February 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

same idea, implemented in C++

struct range {
	int start;
	int end;
	range(int s, int e) {start=s; end=e;}
};

void find_longest_consecutive_numbers(vector<int>& N)
{
	unordered_map<int,range> hash;
	unordered_map<int,range>::iterator left, right;

	range max_range(0,0);
	int max_length=0;

	for(int i=0; i<N.size(); i++) {		
		range r(N[i],N[i]);

		left = hash.find(N[i]-1);
		right = hash.find(N[i]+1);

		// update range r
		if( left!=hash.end() ) 
			r.start = left->second.start;
		if( right!=hash.end() )
			r.end = right->second.end;

		// update hash table
		if( left!=hash.end() ) 
			left->second.end = r.end;
		if( right!=hash.end() )
			right->second.start = r.start;

		// insert range r
		hash.insert(make_pair(N[i],r));

		// check if this range was the longest
		if( r.end-r.start+1 > max_length ) {
			max_length = r.end-r.start+1;
			max_range.start = r.start;
			max_range.end = r.end;
		}
	}

	printf("longest range = %d : %d\n", max_range.start, max_range.end);
}

- Anonymous February 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 11 vote

so from the example I undertand that the question is : given an unsorted array, find the longest consecutive sequence if the array was sorted? in O(n) time?
This can be done in O(max(array)) time with O(max(array)/8) space.
1. Find the max of array. Create a bitset of size=MAX
2. As we traverse the input array set the position in the bitset to 1.
3. Now traverse the bitset for the consecutive 1's.

Not sure if this can be done in O(n)

- chennavarri February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

slight modification I suggest:
You can calculate (max-min) and this can be used as size of the bit map. then we can scan from left, subtract (element-min), put 'true' at (element-min)th index.

- BVarghese December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

isn't finding the max of an array require to travel once ? and then we also need to traverse through array to add elements to the bitmap ?

- orhancanceylan June 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

We need 2 passes, one Hashtable, and one BitVec. The first pass was meant to put all elements into the HT. The second pass loops to your original array to retrieve the longest sequence a give element has become parted with. At the same time, we need to mark other elements "explored" so that you don't need to repeat the longest sequence again and again. This will give you an approximately O(n) complexity with a huge space required.

public static void findLongestSeq(int[] array){
		Hashtable<Integer,Integer> HT = new Hashtable<Integer,Integer>();
		//First pass put every thing in the HT.
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]+" ");
			if(HT.get(array[i]) == null)
				HT.put(array[i],i);
		}//endfor
		System.out.println();
		//Second pass findLongestSeq
		int max_cnt=0;int lb=0;int ub=0;
		//use isExplored boolean to skipping all interval numbers. Reducing redundancy.
		boolean[] isExplored = new boolean[array.length];
		for(boolean cell:isExplored) cell = false;
		
		for(int i=0;i<array.length;i++){
			//base case ignore the number in the interval
			if(!isExplored[i]){
				int cnt=1;
				isExplored[i] = true;
				//retrieve lower bound
				int key1 = array[i]-1;
				while(HT.get(key1)!=null){
					isExplored[HT.get(key1--)] = true;
					cnt++;
				}
				//retrieve upper bound
				int key2 = array[i]+1;
				while(HT.get(key2)!=null){
					isExplored[HT.get(key2++)] = true;
					cnt++;
				}
				//update longest seq.
				if(cnt > max_cnt){
					max_cnt = cnt;
					lb = key1+1;ub=key2-1;
				}
			}//endif
		}//endfor
		//print out
		while(lb <= ub)
			System.out.print((lb++)+" ");
	}

- Saimok February 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Salmok: a small modification. you could just set the value of the key in the hashtable instead of using a separate bitset. That should reduce some space. but ya, as u mentioned hashtable could take space more than O(n)

- chennavarri February 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome solution dude.. It works!

- Jagadish July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question clearly states: "do it in one go", and you went through the array twice.

- Anonymous May 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

Nice code in C#. Complexity O(n)

onestopinterviewprep.blogspot.com/2014/04/longest-consecutive-sequence-of-numbers.html

- codechamp April 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. Put the elements into a hash list = 0(n) (I am assuming 0(1) insertion here, which can be done at the expense of memory).
2. Maintain 2 variables say longestSeqLength = curSeqLength;
3. Run the following loop,

longestSeqLength = curSeqLength = 0;
   for ( iterator itr = list.begin(); itr != list.end(); ++itr) {
       curSeqLength++;
       //Find all consecutive numbers greater than the current element 
       int offset = 1;
       for (iteator j = list.find(*itr) + offset); j != list.end(); 
            ++offset, ++curSeqLength) {
          list.erase(j);
       }
       //Find all consecutive numbers less than the current element 
       offset = -1; 
       for (iteator j = list.find(*itr) + offset); j != list.end(); 
            --offset, ++curSeqLength) {
          list.erase(j);
       }
       if (curSeqLength > longestSeqLength) 
           longestSeqLength = curSeqLength;
        curSesLenght = 0;
   }

caveat: I am assuming its safe to erase elements from a hash list while iterating over it. In some implementations (eg C++ stl) you have to take special precutions for this. In the interest of clarity I have not added the code to cater to iterator invalidation.
4. Note that for each number we find the longest sequence that this number could be a part of in the input. We do this by progressively finding the numbers greater than and less than the current number such that the combined result is part of a sequence. When we find such a number we erase it from the list so we will never visit this again. If we don't find any such numbers we move onto the next number.
5. In the loop above we only hit a number once, making this a O(n) loop.
Total time = n (hashing) + n (loop in step 3) = 2n = O(n)

Jasmeet

- Jasmeet Bagga February 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Jasmeet: a hashtable is not sorted so 3,4,5 need not be in a consecutive order. So if you insert 3,1,6,2,8,9,10, into hashtable and traverse the table. you could get some order depending on the hash function n definitely not sorted

- Anonymous February 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous
I know that a hashtable is not sorted. Please look at the solution, it does not require a sorted order. On each element I am searching to its right (in increments of 1) and left (in decrements of 1) and eliminating the numbers so found. Find in a hash table is 0(1). In each pass around any of the 3 loops above I eliminate a number, thus requiring n passes.

- Jasmeet Bagga February 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this solution works fine..good work.

- neo April 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this solution won't work. You can't check increasing numbers and decreasing numbers separately while erasing them in each step.

- Anonymous April 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Here is a solution in c#. The java solution should not be much different

private static String MaxConsecutiveSequence(int[] data)
        {
            if (data == null)
            {
                return null;
            }
            if (data.Length < 2)
            {
                return data[0].ToString();
            }

            // find the largest value in the array - O(n)
            int maxValue = Int32.MinValue;
            for (int idx = 0; idx < data.Length; idx++)
            {
                if(data[idx] > maxValue)
                {
                    maxValue = data[idx];
                }
            }

            bool[] markers = new bool[maxValue+1];
            // Set a marker for where the value occurs - O(k)
            for (int idx = 0; idx < data.Length; idx++)
            {
                markers[data[idx]] = true;
            }
            markers[maxValue] = false;


            // Traverse the marker array looking for max sequence - O(k)
            int sequence = 0;
            int start = 0;
            int maxSequenceStart = 0;
            int maxSequence = 0;
            bool inSeq = false;
            int j = 0;
            while(j < markers.Length)
            {
                if(markers[j])
                {
                    if (!inSeq)
                    {
                        start = j;
                    }
                    sequence++;
                    inSeq = true;
                }
                else
                {
                    if (sequence > maxSequence)
                    {
                        maxSequence = sequence;
                        maxSequenceStart = start;
                    }
                    sequence = 0;
                    inSeq = false;
                }
                j++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = maxSequenceStart; i <= maxSequenceStart + maxSequence; i++)
            {
                sb.Append(i);
                sb.Append(" ");
            }
            return sb.ToString();
        }

- Anonymous October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I'm pasting my code here for this problem.
The idea is to use merging small consecutive pieces:

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Sequence {
public:
    int start;
    int end;
    Sequence(int _start, int _end) {
        start = _start;
        end = _end;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int, Sequence*> map;
        for (int t = 0 ; t < num.size() ; t++) {
            int i = num[t];
            if (map.find(i) != map.end()) {
                //found, ignore
            } else {
                //not found
                bool f1 = (map.find(i - 1) != map.end());
                bool f2 = (map.find(i + 1) != map.end());
                if (f1 && f2) {
                    map[map[i - 1]->start]->end = map[i + 1]->end;
                    map[map[i + 1]->end]->start = map[i - 1]->start;
                    map[i] = map[map[i - 1]->start];
                } else if (f1 && !f2) {
                    map[map[i - 1]->start]->end = i;
                    map[i] = new Sequence(map[i - 1]->start, i);
                } else if (!f1 && f2) {
                    map[i] = new Sequence(i, map[i + 1]->end);
                    map[map[i + 1]->end]->start = i;
                } else {
                    //!f1 && !f2
                    map[i] = new Sequence(i, i);
                }
            }
        }
        
        int max = 0;
        for (auto it = map.begin() ; it != map.end() ; it++) {
            if (it->second->end - it->second->start + 1 > max) {
                max = it->second->end - it->second->start + 1;
            }
        }
        
        return max;
    }
};

/*
int main(int argc, const char* argv[]) {
    Solution s;
    vector<int> num;
    num.push_back(100);
    num.push_back(4);
    num.push_back(200);
    num.push_back(1);
    num.push_back(3);
    num.push_back(2);
    cout << s.longestConsecutive(num) << endl;
    return 0;
}//*/

- Junxian.Huang February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is the solution c++...!!!

#include<iostream>
#include<vector>
#include<unordered_map>

void getMaxSequence(vector<int>& vec){

	unordered_map<int, int> hash;
	unordered_map<int, int>::iterator it, prev, next;

	for (int i = 0; i < vec.size(); ++i){
		it = hash.find(vec[i]);
		if (it == hash.end()){

			prev = hash.find(vec[i] - 1);
			next = hash.find(vec[i] + 1);

			if (prev != hash.end() && next != hash.end()){
				int temp = prev->second;
				hash[prev->second] = next->second;
				hash[next->second] = temp;
				hash[vec[i]] = prev->first;
			}
			else if (prev != hash.end()){
				int temp = prev->second;
				hash[temp] = vec[i];
				hash[vec[i]] = temp;
			}
			else if (next != hash.end()){
				int temp = next->second;
				hash[temp] = vec[i];
				hash[vec[i]] = temp;
			}
			else{
				hash[vec[i]] = vec[i];
			}
		}
	}
	int max = 0;
	int start = 0, end = 0;
	for (it = hash.begin(); it != hash.end(); it++){
		int result = it->first - it->second;
		if (result > max)
		{
			start = it->second;
			end = it->first;
			max = result;
		}

	}

	for (int i = start; i <= end; i++)
		cout << i << " ";
	cout << endl;
}

int main(){
	int arr[9] = { 1, 12, 10, 4, 7, 9, 5, 5, 8 };
	vector<int> vec(arr, arr + 9);

	getMaxSequence(vec);
	return 0;
}

- AndyC April 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the array and scan it once counting the largest possible subsequence. O(nlogn + n) = O(nlogn) time and O(1) space if we can destroy the array, else O(n) space.

- maverick February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the solution should be O(n). O(n log n) is too simple...

- Alec February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I gave the same solution that sort the array and traverse the array will take nlogn+n time and 2n space to store the latest longest sequences. BST also takes nlogn and ascending order linked list also take nlongn...

ONLY left is Hash tables. Solution is O(n) time.

- Anonymous February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Traversing hash tables might be O(n) but traversing doesn't happen in sorted order i.e. if 13,4,25,6,5,7 are inserted into the hash table then while traversing it doesn't traverse 4,5,6,7 in consecutive order.

- chennavarri February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Use a treeMap

- noMAD November 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

where have you had the interview?

- Alec February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hyderabad, India

- Anonymous February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hyderabad sux, Google sux even more. They are after me to join them, but I don't want to give them a damn chance.

- Anonymous August 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another approach:

1. startIndex = 0, maxIndex = 0, count = 1;
2. start traversing the array.
3. if the count becomes zero
a. reset the array counter to maxIndex+1
b. startIndex = maxIndex = array counter
c. count = 1
4. if current array element is less than element at maxIndex then decrease count.
5. else increment count and set maxIndex to array counter.

6. once the loop finishes we'll get the start position of the sequence, then its easy to find the sequence in one pass.

not O(n) solution :(

int FindLongestSum(int a[], int length)
{
	if(length <=1)
		return length-1;
	int start = 0, currentMax = 0, count = 1;
	
	int i = 1;
	while(i<length)
	{
		if(count == 0)
		{
			if(i == length-1)
				break;
			else
			{
				i = currentMax + 1;
				start = i;
				currentMax = i;
				count = 1;
			}
		}
		else if(a[i] < a[currentMax])
		{
			count--;
			i++;
		}
		else
		{
			count++;
			currentMax = i;
			i++;
		}
	}
	return start;
}

- Paras February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

srry I interpreted the question as find the longest increasing sequence in the same order in which they appear in array.

- paras February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is in O(n) time complexity.

- asetech February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't work, try on this 5,12,3,13,10,9,4,6,23,8,7. The answer should be 3,4,5,6,7,8,9,10.
A simpler example would be 3,1,4,2,5. answer 1,2,3,4,5

- chennavarri February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is longest consecutive elements sequence..
in 3 1 4 2 5... 4 and 2 r not consecutive..neither do 1 ans 4 dn how it is 1 2 3 4 5

and in 5,12,3,13,10,9,4,6,23,8,7 .. 3,13 r not consecutive..

the answer should be 10,9 or 8,7.. not 3,4,5,6,7,8,9,10

- asetech February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@asetech: I think @chennavarri is right.
u r talking about longest subsequence for which there are elegant solutions using dynamic programming. The question is about finding a longest sequence if the array was sorted. The question states"Ex: 5 7 3 4 9 10 1 15 12 Ans: 3 4 5 (longest with 3 elements)". Do you see, 5 appears before 3 4 but the answer is 3 4 5. i.e. longest consecutive sequence if the array was sorted

- Anonymous February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

in that case..sort it..and scan the sorted array to find d longest subsequence... as stated earlier in here by maverick.. :)

- asetech February 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The only approach is to sort it using quick sort O(n log n), and iterate through the sort list.

This approach is the easier to implement with optimal run time.

- Paul February 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Epic fail ...

- Anonymous July 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <hash_map>
typedef stdext::hash_map<int,int> HII;
typedef HII::iterator HII_iter;

vector<int> longest_consecutive(vector<int> const &v){

HII min_max,max_min;
HII_iter min_max_it,max_min_it;

for(int i=0;i<v.size();++i){
min_max_it=min_max.find(v[i]+1);
max_min_it=max_min.find(v[i]-1);
int high=v[i],low=v[i];
if(min_max_it!=min_max.end()){
high=(*min_max_it).second;
max_min.erase(high);
min_max.erase(min_max_it);
}

if(max_min_it!=max_min.end()){
low=(*max_min_it).second;
min_max.erase(low);
max_min.erase(max_min_it);
}
min_max.insert(make_pair(low,high));
max_min.insert(make_pair(high,low));
}

int max_range=0;
int max_low,max_high;
for(HII_iter it=min_max.begin();it!=min_max.end();++it){
if((*it).second-(*it).first>max_range){
max_range=(*it).second-(*it).first;
max_low=(*it).first;
max_high=(*it).second;
}
}

vector<int> rtn;
rtn.push_back(max_low);
rtn.push_back(max_high);

return rtn;
}

- Anonymous February 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <hash_map>
typedef stdext::hash_map<int,int> HII;
typedef HII::iterator HII_iter;

vector<int> longest_consecutive(vector<int> const &v){

	HII min_max,max_min;
	HII_iter min_max_it,max_min_it;

	for(int i=0;i<v.size();++i){
		min_max_it=min_max.find(v[i]+1);
		max_min_it=max_min.find(v[i]-1);
		int high=v[i],low=v[i];
		if(min_max_it!=min_max.end()){
			high=(*min_max_it).second;
			max_min.erase(high);
			min_max.erase(min_max_it);
		}

		if(max_min_it!=max_min.end()){
			low=(*max_min_it).second;
			min_max.erase(low);
			max_min.erase(max_min_it);
		}
		min_max.insert(make_pair(low,high));
		max_min.insert(make_pair(high,low));
	}

	int max_range=0;
	int max_low,max_high;
	for(HII_iter it=min_max.begin();it!=min_max.end();++it){
		if((*it).second-(*it).first>max_range){
			max_range=(*it).second-(*it).first;
			max_low=(*it).first;
			max_high=(*it).second;
		}
	}

	vector<int> rtn;
	rtn.push_back(max_low);
	rtn.push_back(max_high);

	return rtn;
}

- Anonymous February 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about variation of MergeSort? Once we have two sorted subsets, instead of merging Build consecutive elements sequence using dynamic programming technique. This will be O(nlogn) but slightly better than sorting and then building the sequence.

- Kalyan February 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

build the bitmap O(n) + find the consecutive sequence based on bitmap O(n) = O(n)

def find_longest_subarr(arr):
    # build the bitmap
    bitmap = 0
    for x in arr: bitmap = bitmap | ( 1 << (x-1) )
    # loop the bitmap
    subarr, temparr = [], []
    x = 1
    while bitmap>0:
        bitmap, bitmark = divmod(bitmap, 2)
        print x, bitmap, bitmark
        if bitmark == 1: temparr.append(x)
        elif len(temparr)>len(subarr): subarr = temparr; temparr = []
        else: temparr = []
        x += 1
    # remember the last temparr is not included in the loop
    if len(temparr)>len(subarr): subarr = temparr
    return subarr

- ll March 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <vector>
using namespace std;

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
vector<int> p(a.size());
int u, v;

if (a.empty()) return;

b.push_back(0);

for (size_t i = 1; i < a.size(); i++)
{
// If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
if ((a[b.back()] < a[i])&&(a[i]-a[b.back()]==1))
{
p[i] = b.back();
b.push_back(i);
continue;
}

// Binary search to find the smallest element referenced by b which is just bigger than a[i]
// Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.
for (u = 0, v = b.size()-1; u < v;)
{
int c = (u + v) / 2;
if (a[b[c]] < a[i]) u=c+1; else v=c;
}

// Update b if new value is smaller then previously referenced value
if (a[i] < a[b[u]])
{
if (u > 0) p[i] = b[u-1];
b[u] = i;
}
}

for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}

/* Example of usage: */
#include <cstdio>
int main()
{
int a[] = { 10, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };

vector<int> seq(a, a+sizeof(a)/sizeof(a[0])); // seq : Input Vector
vector<int> lis; // lis : Vector containing indexes of longest subsequence
find_lis(seq, lis);

//Printing actual output
for (size_t i = 0; i < lis.size(); i++)
printf("%d ", seq[lis[i]]);
printf("\n");

return 0;
}

- rai March 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it prints only numbers after the initial number in the series positions though

- rai March 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution uses a Hashtable and perhaps is similar to the answer above, but I think its a bit simpler. Where hash[n] stores the number of consecutive from elements {x,...,n}. For simplicity we'll assume no duplicates.

1) Create cache variables maxCounts and startIndexOfMax

2) Now as we add numbers n:

//We either have someone behind us, or we dont. If so, we are 1 longer.
hash[n] = hash[n-1] > 0 ? hash[n-1]+1 : 0;
//now check & update people ahead of us. We may have connected two sub sequences.
int i = 1;
while(hash[n+i] != null)
{
hash[n+i] = hash[n+i-1] + 1;
i++;
}
3) Of course update maxCounts and startOfMax if necessary.

Worst case performance is if values are in reverse order (5,4,3,2,1). In which case shuffle or start reading from the tails.

R

- Rob Leclerc March 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Java, we can use a TreeMap that guarantees that the keys are in the ascending sorted natural order. TreeMap is implementation of RB trees and you can see further details about it on other sites.

So the problem could be solved by
1) Scan the array once, put every element of the array into the treemap with value as 1. The value for every key would denote the maximum length of the sequence that could end in that element.
2) Iterate over the elements of the TreeMap:
For every element in the TreeMap
if(element-1) exists then value(element)=value(element-1)+1
3) Keep another variable max to keep track of the max sequence obtained after every iteration.

This will require O(n) time but extra storage. And I am not sure if using of a data structure like TreeMap would trivialize the problem.

- Anonymous April 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Aren't insertions into a Red Black Tree

O(log n)

?

- Anon July 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes they are

O(log n)

. This would be as good as sorting which has been discussed earlier.

- Ano October 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

One way is sort the array and find the maximum increasing sequence. But he was looking for O(n)[One Go] solution using hashtable. any idea?

- Neo July 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

where did u attend this interview?

- Anonymous July 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you can use something similar to counting sort
Find max and min in the array
create a bit vector bit[max]
while traversing original array, start setting bit in bit[] array
after finishing original array, iterate over bit[] array to find max increasing sequence.

you will perform one pass on original array (input)
and one pass over bit[] array

- Anonymous July 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess you need two passes over original array,
one to find max and min
and one to hash all elements.... my bad

- Anonymous July 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1) It was telephonic.
2) Regarding above solution, he told that we dont have any limit on numbers.

- Neo July 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is no one go solution. At most you need two go's. If the interviewer was looking for hash-table he was reffering to the number range being arbitarily large and unknown and hash should be used compared to array to tag numbers.

solution is O(n) + O(max-min). If max-mix is less than the number range then solution is O(n).

- Anonymous July 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

max-min cannot be less than n as we dont have repititions. It is atleast equal to n

- sag February 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

max-min cannot be less than n as we dont have repititions. It is atleast equal to n

- sag February 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

isn't finding the max of an array require to travel once ? and then we also need to traverse through array to add elements to the bitmap ?

- orhancanceylan June 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can do it in single go. My algorithm is:
take an array(bit array/chars) of suitable size and scan the input sequence. For each input number , set the corresponding flag/bit on.
Now the single go:
initially take low1_index=0,low2_index=0 ,high_index=0 ,count_prev=0,count_new=0;
for(int i=0;i<=MAX;i++)
{
while(!array[i])i++;
low2_index=i;
while( i<=MAX && array[i++])
count_new++;
if(count_new > count_prev)
{high_index=i;low1_index=low2_index;}
}

for(int i=low1_index;i<high_index;i++)
printf("%d ",array[i]);

- mrn July 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ohh..it takes to scan. one for input and one for count.

- mrn July 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mrn
I am trying to find how my algo is different than yours..
"take an array(bit array/chars) of suitable size "
how do you define suitable size?

in my algo you need to go once in the original array to get this value.. am I missing something here? please help me understand

I guess rest is similar

- Anonymous July 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for pointing it out.One possible solution is dynamic array.
But we can use link list. The algorithm needs to be changed.First store value of current node then increase counter i and compare i with next node value.If they at all match then simply proceed and if not then readjust the temp_head and temp_tail pointers.I think u got me what and how i am talking about.Any improvements?

- mrn July 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As Neo mentioned "we dont have any limit on numbers" , how about taking the bit array of size MAX range?

- mrn July 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think this is a viable solution.

What if the MAX range greatly exceeds the size of the original array and the max and min elements of the array are very far apart? Then the work required to do the final scan could be well in excess of n.

- magritte128 July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

it was discussed earlier
id=7695669

- Anonymous July 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why dont you just post the link directly..

- Anonymous July 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Neo: Did u answer this question? Whats the interview outcome?

- Anonymous July 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I was able to give answer by sorting and by using a bit array. But he was looking for a answer in O(n) in one go

- Neo July 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Following approach is possible:
We can use extended binary search tree. Each node stores continious Interval (start - end) and amount of numbers inside the interval (if numbers can repeat). Nodes are compared by Start of the Interval.
Then we scan array from the beginning to end and for each number NUM update tree by following rules:
1. If tree doesn't contain intervals with NUM-1 and NUM+1 => add new node
2. If tree contains only interval with NUM-1 => add update this interval
3. If tree contains only interval with NUM+1 => add update this interval
4. If tree contains both intervals => merge them in one node and delete another

During update of tree, store Node with biggest range.

No collisions are possible because of mentioned update rules
For better performance extended RB tree can be used (support balance)

Performance characteristics:
- Original array passed only once
- Worst case (no consequtive sequences) - update of binary tree takes O(n*log(n))
- If there are a lot of consequtive sequences, performance of algorithm can be much better as tree will contain much less then n elements

Critisism please?

- Zerg July 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi all,
I think the question is not framed correctly, if it is what I think it is then, there is no need to break your head so much it is a standard problem in Dynamic Programming, just Google on "Longest increasing subsequence"

- Dr.Sai July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

longest increasing sequence is from start->end...
here the consecutive elements and can be any where in array

- Anonymous July 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We could use this code:

public List<Integer> longestConsSeq(int[] arr){
		BitSet set = new BitSet();
		for( int value : arr ){
			set.set(value);
		}
		
		int index = 0;
		int maxSequenceLength = 0;
		
		List<Integer> res = new ArrayList<Integer>();
		
		while( index < set.length() ){
			int startIndex = set.nextSetBit(index);
			int endIndex = set.nextClearBit(index+1)-1;
			
			int sequenceLength = endIndex - startIndex;
			
			if( sequenceLength > maxSequenceLength ){
				res.clear();
				maxSequenceLength = sequenceLength;
				for( int i = startIndex; i < endIndex+1; i++ ){
					res.add( i );
				}
			}
			
			index = endIndex+1;
		}
		
		return res;

}

- m@}{ July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Who care's your code without a single line of explanation? Can't you explain idea only? Who can't code such simple solution if can grasped the idea at first place.

Needless to talk about your so-called performance measurement. I never heard that a job-seeker calculates complexity in such bizarre manner for such a simple problem!

- anonymous July 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I've measured time in java:
1 000 000 => 85 ms
2 000 000 => 175 ms
4 000 000 => 653 ms
8 000 000 => 1 656 ms
16 000 000 => 3 614 ms
So we have linear time here: O(N).

- m@}{ July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have a different approach
For each element in A[i], draw an edge between A[i]-1, A[i]+1 if they exist.
For this, we ll need to hash each element in A.
Then run a DFS to compute the size of components in the graph.
Total Time = O(n) + O(V+E)
V = O(n), E = O(n).
So time = O(n)
Space = O(n) for hash , O(n) to maintain adjacency list for each element.

- Sriram S July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Sriram: Interesting approach. But, I think it can't be done in O(n). You need to start a DFS from every starting point. Then it'd be O(n^2) indeed. Correct me, if wrong.

- anon July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it's O(n). It's same as finding longest path in a DAG. You need not consider every node as starting point. Only consider node that has no predecessor.

- lol July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Construct an auxiliary hash table K => V. The keys K will represent the ending (maximum) values of continuous sequences, and the values V will hold the lengths of those sequences. For example, for the sequence 10, 11, 12, 13 the table should contain a key-value pair 13 => 4.

So, iterate over the random array. For each element E, see if key E is in the hash table. If not, add a new key-value pair to the table: E+1 => 1. If it is, replace E => oldV with E+1 => oldV+1.

Every time you add something to the table, update some variable that stores the key with the maximum value.

- Netspirit July 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not 13 => 4, sorry - 14 => 4. Once we've seen 13, we're looking for 14.

- Netspirit July 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ah, scratch that, it's more involved than that. One would have to construct quite a special hash table, with ranges instead of scalar keys.

- Anonymous July 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done with one pass over the array, and keeping 2 hash tables.

Say your numbers are: 10, 5, 2, 3, 1, 4, 20

Now run over the array like this:

10 doesn't exist so enter 10->10 in to the table, and 10->1 to the other table to mark that the continuous array that has 10 in it has a run of 1

Now for 5: 5 doesn't exist neither does 3 or 4, so enter 5->5 into one table and 5->1 into the other
For 2: same, 2 is not there and neither are 1 or 3, so we enter 3->3 and 3->1
for 3: 3's neighbor 2 exists, so enter 3->2, and update 2's count on the other table 2->2
for 1: 2 exists, so enter 1->2, ans update 2's count again 2->3
for 4: 3 exists and points to 2, so enter 4->2, and update 2->4, but 5 also exists, so update 5->5 to 5->2 and update 2->4 to 2->5
etc.

You can keep track of the max length as you do this.

Only one run over the original array...

- memo July 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem with this approach is that as chains grow you have to repeatedly go over each element in the chain updating, so it is no longer O(n)

- juando.martin July 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, no. Because you are only keeping track of the very first occurrence in any chain, and updating only Ak, (Ak)-1, and (Ak)+1 for any kth element. It is O(n).

- memo July 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@memo: I strongly think it won't work. Work with this example:
3, 5, 7, 2, 6, 8, 4, 9, 1

When you reach 4, which connects to continuous range [2,3] and [5,8]; it has no idea that the later range is of size 4. The reason is when you reach 8, you updated 7's run-length (not 6 or 5).

- anonymous August 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maintain a HashTable h(with default val 0 for each key) and update h as you traverse forward through the array A

For each element a (in A) 
 if h(a) == 0, then h(a) = h(a+1) + h(a-1) + 1
 If h(a) > eleWithMax
  max = h(a)
  eleWithMax = a

Sequence containing eleWithMax is the max sequence. To get this range/sequence, do this.

min=eleWithMax
max=eleWithMax
while(h(--min) > 0 || h(++max) > 0){}; 
--min; ++max;

Time complexity - O(n), since for each element a, you're only checking h(a+1) and h(a-1).
Space - O(n) I guess, depending on how the hash table is implemented. Any thoughts?

- Jagat July 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple idea:
Use a hashmap to build a double linked list:
1. Create a Map of linked nodes
2. for each number create a linked node in the map. Check if its previous value is there, if is link then. Do the same for the next value.
3. scan the map to check the longest linked list build

Complexity:
Space: O(n) (The linked lists and the map)
Time: O(n) (One iteration in the input, and one iteration in the hashmap, each using a value at most once)
Code:

public class LongestSequence {
	public static class NodeList {
		public NodeList prev;
		public NodeList next;
		public int value;
	}
	public static NodeList findLongestConsecutives(int[] values) {
		Map<Integer, NodeList> nodeMap = new HashMap<Integer, NodeList>();
		buildLinkedLists(values, nodeMap);
		return findLongestLinkedList(nodeMap);
	}
	private static void buildLinkedLists(int[] values,
			Map<Integer, NodeList> nodeMap) {
		for (int val :  values) {
			if (!nodeMap.containsKey(val)) {
				NodeList cur = new NodeList();
				cur.value = val;
				nodeMap.put(val, cur);
				NodeList prev = nodeMap.get(val-1);
				if (prev != null) {
					prev.next = cur;
					cur.prev = prev;
				}
				NodeList next = nodeMap.get(val+1);
				if (next != null) {
					next.prev = cur;
					cur.next = next;
				}
			}
		}
	}
	private static NodeList findLongestLinkedList(Map<Integer, NodeList> nodeMap) {
		NodeList list = null;
		int maxSize = 0;
		while (!nodeMap.isEmpty()) {
			NodeList tail = nodeMap.entrySet().iterator().next().getValue();
			nodeMap.remove(tail.value);
			int size = 1;
			NodeList head = tail;
			while (head.prev != null) {
				++size;
				head = head.prev;
				nodeMap.remove(head.value);
			}
			while (tail.next != null) {
				++size;
				tail = tail.next;
				nodeMap.remove(tail.value);
			}
			if (size > maxSize) {
				maxSize = size;
				list = head;
			}
		}
		return list;
	}
}

- lucas.eustaquio August 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

find the largest subset of it which form a sequence.
can u explain in detail the meaning of the above sentence.

- Anonymous October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

By subset i mean any number of elements from the array not necessarily contiguous.
By Sequence i mean if sorted they will be consecutive on the number line.

- learner October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if we follow above statements then your initial example is wrong

in your example according to you
Eg. {1,6,10,4,7,9,5}
then ans is 4,5,6,7

if you are not considering the order then why not 1,4,5,6,7 or
1,4,5,6,7,9,10 ?

- Random October 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it should be consecutive elements

- Anonymous October 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry but i dont understand C#.
It would be great if you provide the algo in simple words

- learner October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1: find the max element in the array
Step 2: create a boolean array one element larger than the value of max element
Step 3: set all the elements in the boolean array to false
Step 3: set to true the indices in the boolean array that match the values in the initial array
Step 4: traverse the boolean array; keep track of where sequences start/stop and check if sequence is larger than previous max sequence
Hope this helped

- Anonymous October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,

Wouldnt the algorithm become O(n*k) in this case . Here k is the size of the boolean array , and that would depend on the largest element in the given array

- aniket October 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ankiet

Why O(n*k). It will be simply (max_element).

- swap October 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

By this method - You can do any soring in in finite time....which is not right way...see how much space you are cosuming. It might be some time like 2^32 bits...

- Anonymous November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@anonymous
I answered the same thing, but he said this can be done better. Here the size of the boolean array is O(max_size) which can be even 2 raise to power 32. Can we reduce the space complexity

- learner October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This bit-array method wonr work. Say at position 198 i am having 30 duplicates .....then?

- Anonymous October 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Hey asshole! What's ur prob dude! Why the fuck u only repost old problems. All these appeared here in Google/Amazon section not in remote past? If u can't grasp a solution, just post it to Stackoverflow rather spamming CC for no good reasons!

- anonymous October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Stop abusing guys. Just post the link to that thread and close the discussion

- Anonymous October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would say use hash here and while scanning the original array just check if currentElement-1 is part of hash , if yes then follow union set DS to set the minimum value as a root for currentElement hash Value. This way it will be O(N) and you need only O(N) extra memory.

- Anonymous October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What implementation of hash (you mean map, right?) do you know with O(n) space complexity and O(1) time complexity for lookup and insert ?

- Anonymous October 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess you mean Union-Find. But good solution !

- Anonymous January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess you mean Union-Find. But good solution !

- Anonymous January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess you mean Union-Find. But good solution !

- Anonymous January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the use of union DS here? we will be inserting all elements into hash, when we find X for which X-1 already exists we recursively find the next X-1 to find the minimum(length of subset), and store the corresponding length in new array, when we further traverse the original array we can use previous stored length to find bigger set if exists. !

- Guest September 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Important thing is array may contain duplicates, in such case this hash based solution may lead to 0(n^2). Any idea of linear time algorithm for this problem ?

- Guest September 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@learner
The only thing I can think of is also keeping track of min value in your array. That way the size of the boolean array is sizeof(max-min). Space complexity is still O(max_size) if min=0, and max=2^32.

- Anonymous October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time O(1) space solution doesn't exist!

- anonymous October 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using counting sort?? And you need extra space.

- appscan October 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do this one with Hash table with o(n)

- N.M October 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Radix sort. As the numbers are interger, Radix sort is the best choice and can be done in O(n).

- bylike October 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time and O(1) solution exists. We need two passes over the numbers. In the first pass calculate minimum and maximum numbers. Then allocate a bit vector and in the second pass mark the elements found. If all 1s in the vector congregate together then there is a sequence.

- Ashish Kaila October 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What type of idiots are you? You wanna use bit vector, and claim it's O(1) space sol...... LMAO !!!

- anonymous October 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ashish your soln is not O(1) space but O(n)

- learner October 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

rather than "Laughing your *** off " you can give the right solution... dont you think... you anonymous....

- aragorn November 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given array 'Array', this

-> can be done in O(n) time and O(max(Array)) space using a naive solution:

1. Create an array 'TempArray' of O(max(Array)) initialized with 0's
2. Pass through the 'Array' and element 'i' set TempArray[Array[i]] = 1
3. Pass through the 'Array' again and for each element 'i' check if neighbours are set

-> Can be done with lesser space using a hashmap. O(n) time and O(n+k) space

-> Is there a solution with O(n) time and O(lessthan n) space ?

- WallStreetCup October 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Radix sort is O(n) time...

- Anonymous October 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

is O(N * x) x is the smallest power of 2 that is larger or equal to the largest number.

- Anonymous January 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Radix sort is O(n) time...

- Anonymous October 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "stdio.h"

int main()
{

unsigned int arr[8]={1,4,5,6,7,9,11,17};
unsigned int index=0,current_index=0,max_matches=1,i=0;

for(i=0;i<7;i++)
{
if(arr[i]+1 == arr[i + 1])
{
current_index++;
}
else
{
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
current_index = 1;
}

}

for(i=index ; i < (max_matches + index); i++)
printf("%d\n",arr[i]);
}

- x October 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include "stdio.h"

int main()
{

unsigned int arr[14]={1,4,5,6,7,9,11,17,21,22,23,24,25,26};
unsigned int index=0,current_index=0,max_matches=1,i=0;

for(i=0;i<13;i++)
{
if(arr[i]+1 == arr[i + 1])
{
current_index++;
printf("%d %d %d\n",arr[i ],arr[i + 1],current_index);
}
else
{
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
current_index = 1;
printf("%d %d %d %d\n",index,max_matches,current_index,i);

}

}

index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;

printf("%d %d\n",max_matches,index);
printf("%d\n",current_index);
for(i=index ; i < (max_matches + index); i++)
printf("%d\n",arr[i]);
}

- Anonymous October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include "stdio.h"

int main()
{

unsigned int arr[14]={1,4,5,6,7,9,11,17,21,22,23,24,25,26};
unsigned int index=0,current_index=0,max_matches=1,i=0;

for(i=0;i<13;i++)
{
if(arr[i]+1 == arr[i + 1])
{
current_index++;
}
else
{
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
current_index = 1;

}

}

index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;


for(i=index ; i < (max_matches + index); i++)
printf("%d\n",arr[i]);
}

- Anonymous October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include "stdio.h"

int main()
{

unsigned int arr[14]={1,4,5,6,7,9,11,17,21,22,23,24,25,26};
unsigned int index=0,current_index=0,max_matches=1,i=0;

for(i=0;i<13;i++)
{
if(arr[i]+1 == arr[i + 1])
{
current_index++;
}
else
{
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
current_index = 1;

}

}

index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;


for(i=index ; i < (max_matches + index); i++)
printf("%d\n",arr[i]);
}

- Anonymous October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about constructing a binary tree for the given array and then traverse it in-order form to find the largest sequence of numbers.

- Anonymous October 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Creating a BST is an implicit sorting.

- Anonymous October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is also equivalent to sorting ...
but we are asking about the liner time coplexity.

- Anonymous November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. add all elements into a hash set s
2. for each element e in s, if s contains e - 1, then add e - 1 into another hash set s'
3. if s' has only 1 element, say e*, then e* is the start of the longest sequence; else, s = s', go to 2.

- Anonymous October 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. add all elements into a hash set s
2. for each element e in s, if s contains e - 1, then add e - 1 into another hash set s'
3. if s' has only 1 element, say e*, then e* is the start of the longest sequence; else, s = s', go to 2.

- Anonymous October 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this seems to be divide and conquer , break set into two, get the largest from left, largest from right. Merging will take O(1) time if needed.

T(n) = 2 * T(n/2) + o(1)

T(n) = O(n)

- Anonymous October 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@anonymous
how come merging is O(1)??

- Swap October 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Try RadixSort it (Since they are all integers) and find the max sequence by moving start and end marker. It is O(n) time and O(1) space solution for sure.

- Julian November 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Radix sort is not O(1) in terms of memory. It copies array for each iteration of counting sort, so memory usage would be O(n).

- Ivan July 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey12013" class="run-this">/**
*
*/
package array;

import java.util.HashMap;

import LinkList.LinkList;
import LinkList.LinkListNode;

;

/**
* @author envio
*
*/
public class FindMaximumSequence {

public static int find_maximum_sequence(int[] array) {
HashMap<Integer, LinkList> hash = new HashMap<Integer, LinkList>();
int maximum_size = 0;
LinkList sequence = null;
for (int i = 0; i < array.length; i++) {
int value = array[i];
LinkList node = new LinkList(value);
LinkList front = null;
LinkList end = null;
if ((end = hash.get(value + 1)) != null) {
node.union(end);
int end_key = node.end.get_value();
hash.remove(end_key);
hash.put(end_key, node);
hash.put(value, node);
if (maximum_size < node.size) {
maximum_size = node.size;
sequence = node;
}
}

if ((front = hash.get(value - 1)) != null) {
front.union(node);
int end_key = node.end.get_value();
hash.remove(end_key);
hash.put(end_key, front);
if (maximum_size < front.size) {
maximum_size = front.size;
sequence = front;
}
}
if(end == null && front==null){
hash.put(value, node);
}

}
sequence.print();
return maximum_size;
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(FindMaximumSequence.find_maximum_sequence(new int[] {
1, 6, 10, 4, 7, 9, 5,8 ,112,144,113,114}));
}

}
</pre><pre title="CodeMonkey12013" input="yes">
</pre>

- Anonymous November 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this would works and the time complexity is O(n);

- Anonymous November 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yea, It works

- sichang@skyweaver.com November 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

please explain the algorithm

- learner November 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If it is sequence, it's sum should be n * (2 * min + n - 1) /2. We can also have predetermined product in place. Re-scan the array to prove the validation. (Some technique requires for interger overflow).

- Anonymous November 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use the bit array

{

typedef struct{
unsigned int bit:1
}Bit;

typedef struct{
Bit bitvalues[max_size];
}Bitarray;

int main(){
Bitarray ba;
int input[]={1,16,3,4,5, .....};
int max = maximum(input);
set all ba bit to null;
for(i =0;i<sizeof(input);i++){
ba[i].bit = 1;
}

now count the number of continuous bit inside this bit array
}

}

- skg January 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about using the mathematical property that says, 1+2+3+...+(n-1)+n = n*(n+1)/2

1. Calculate the sum of all numbers in the array.
2. Meanwhile find out the min and max elements in the array. Call it arrSum
3. Find
a. maxSum = 1+2+3+...+(max-1)+max
b. minSum = 1+2+3+...+(min-1)
4. Check if arrSum == maxSum - minSum
5. If true, it's a sequence. If not, it's not a sequence.

Here's some working code.

#include<iostream>
#include<vector>
#define MIN -1
#define MAX 100

using namespace std;

int main()
{
        int a[] = {45, 50, 47, 46, 49, 48};
        vector<int> input (a, a + sizeof(a) / sizeof(int) );
        vector<int>::iterator it;

        int min = MAX;
        int max = MIN;
        int arrSum = 0;

        for(it = input.begin(); it != input.end(); it++)
        {
                arrSum += *it;
                if(*it < min)
                        min = *it;
                else if(*it > max)
                        max = *it;
        }

        int maxSum = max*(max+1)/2;
        int minSum = (min*(min+1)/2) - min;

        if(maxSum - minSum == arrSum)
                cout<<"Yes! They're a sequence!"<<endl;
        else
                cout<<"No! They're not a sequence!"<<endl;

        return 0;
}

- Ashwin January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't handle duplicates.

What if the numbers are 1,2,3,4,4? They are in sequence, if you eliminate duplicates.

- Prash September 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about this? make sure it works.
public static int[] NoDuplication(int[] input)
{
int i = 0, j = 1, m = 0, k=0;
int count = 0;
int[] nonReptArr;
while(i+1< input.Length)
{
if (input[i] != input[i + 1])
j++;

}
nonReptArr = new int[j];


while (m+1< input.Length)
{
if (input[m] != input[m + 1])
{
nonReptArr[k] = input[m];
//count[k] = cnt;
count=1;
k++;
}
else
{
count++;
}
m++;
}

nonReptArr[k] = input[m];
return nonReptArr;
}
}
}

- Amy February 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

I think i have a O(n) time and O(1) space solution -

Iterate through the array and subtract adjacent elements like -
A[1] - A[0]
A[2] - A[1]
...
A[n] - A[n-1]
& A[0] - A[n]

Calculate the sum of these numbers and it will always be 0. Eg -
For the sequence - {45,50,47,46,49,48}
If you subtract the adjacent elements : 50 -45 , 47 -50 , 46 -47 , 49 - 46 , 48 - 49 & 45 - 48
==>5 , -3 , -1 , 3, -1 & -3
If you add these numbers : 5 -3 -3 +3 -1 -3 = 0

So the numbers form a sequence. Here is another example with duplicates -
{49,45,48,47,47,46,50}
If you subtract adjacent elements and add them :
-4 + 3 -1 +0 -1 +4 -1 = 0
So these numbers form a sequence too.

To do this in O(1) space, have a variable which is initialized to 0. Keep adding the differences as you iterate through the array.]
eg-

int diff=0;
for(int i=1;i<n;i++){
diff+=A[i]-A[i-1]
}
diff+=A[0]-A[n]

- Pushkar Gopalakrishna February 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is true for any array regardless the array is a sequence or not.
(A[1] - A[0]) + (A[2] - A[1]) + ... + (A[n] - A[n - 1]) + (A[0] - A[n]) = (A[1] - A[1]) + (A[2] - A[2]) + ... + (-A[0] + A[0]) + (A[n] - A[n]) = 0.

- Art. February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is true for any array regardless the array is a sequence or not.
(A[1] - A[0]) + (A[2] - A[1]) + ... + (A[n] - A[n - 1]) + (A[0] - A[n]) = (A[1] - A[1]) + (A[2] - A[2]) + ... + (-A[0] + A[0]) + (A[n] - A[n]) = 0.

- Art. February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is true for any array regardless the array is a sequence or not.
(A[1] - A[0]) + (A[2] - A[1]) + ... + (A[n] - A[n - 1]) + (A[0] - A[n]) = (A[1] - A[1]) + (A[2] - A[2]) + ... + (-A[0] + A[0]) + (A[n] - A[n]) = 0.

- Art. February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is true for any array regardless the array is a sequence or not.
(A[1] - A[0]) + (A[2] - A[1]) + ... + (A[n] - A[n - 1]) + (A[0] - A[n]) = (A[1] - A[1]) + (A[2] - A[2]) + ... + (-A[0] + A[0]) + (A[n] - A[n]) = 0.

- Art. February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What an idiot

- Anonymous March 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getConsequetiveNumbers(int[] array)
	{
		int min, max;
		min = max = array[0];
		for(int i = 1;  i < array.length; i++)
		{
			if(array[i] < min)
			{
				min= array[i];
			}
			if(array[i] > max)
			{
				max = array[i];
			}
		}
		BitSet bitSet = new BitSet(max-min);
		for(int i = 0; i < array.length; i++)
		{
			bitSet.set(array[i] - min, true);
		}
		int maxLength = 0, currentLength = 0;
		for(int i = 0; i < bitSet.length(); i++)
		{
			if(bitSet.get(i))
			{
				currentLength++;
			}
			else
			{
				if(currentLength > maxLength)
				{
					maxLength = currentLength;
				}
				currentLength = 0;
			}
		}
		return maxLength;
	}

- hello world February 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// took from karmaandcoding.blogspot.in/2012/01/given-int-array-which-might-contain.html
public class ArraySeq {
 public static void main(String[] args) {
//  int [] A = {4, 1, 3, 3, 2};
  //int [] A = {3, 1, 4, 3, 2};
  //int [] A = {45,50,47,46,49,48};
  int [] A =  {45,50,47,45,50,46,49,48,49};
  System.out.println("Printing Original Array ...");
  printArr(A);
  System.out.println("Is Sequence: " + isSequence(A));
   
 }
  
 public static boolean isSequence(int [] A) {
  int len = A.length;
  int MIN = Integer.MAX_VALUE;
  int MAX = Integer.MIN_VALUE;
  boolean result = false;
  for (int i=0; i<len; i++) {
   if (A[i] < MIN) {
    MIN = A[i];
   }
   if (A[i] > MAX) {
    MAX = A[i];
   }
  }
  System.out.println("MIN:" + MIN + "  " + "MAX:" + MAX);
  //printArr(A);
  if ((MAX-MIN) >= len) {
   return result;
  }
  int i=0;
  while (i<len) {
   while ((i < len) && (i != (A[i] - MIN))) {
    if (A[A[i] - MIN] == A[i]) {
     A[i] = A[len-1]; A[len-1] = Integer.MAX_VALUE;
     len = len-1;
    } else {
     int k = A[i] - MIN;
     int temp = A[i]; A[i] = A[k]; A[k] = temp;
    }
   }
   ++i;
  }
  System.out.println("Final Array ... ");
  printArr(A);
  for (i=1; i<len; i++) {
   if ((A[i]-A[i-1]) != 1) {
    return false;
   }
  }
   
  return true;
 }
  
 public static void printArr(int [] A) {
  int len = A.length;
  for (int i=0; i<len; i++) {
   System.out.print(A[i] + " ");
  }
  System.out.println();
 }
}

- googlebhai February 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

come on guys, there is a very simple way to do it

go through it once, and find out the max and the min

then return max - min == array size

- FZD March 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

come on dude its not this simple either ..(45,46,46,47,49)

- vivek September 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isSequenceArray(int[] array)
    {
	int min = Integer.MAX_VALUE;
	int max = Integer.MIN_VALUE;
	
	for (int i:array)
	{
	    min = (i<min)? i:min;
	    max = (i>max)? i:max;
	}
	
	if (max-min > array.length)
	{
	    return false;
	}

	for (int index = 0 ;index<array.length;index++)
	{
	    boolean done = false;
	    
	    while(!done)
	    {
		int offset = array[index] - min;
		
		if (offset == index) // right place
		{
		    done = true;
		}
		else if (array[index] == array[offset]) // duplicate
		{
		    break;
		}
		else	// wrong place, swap
		{
		    // swap 
		    array[index] += array[offset];
		    array[offset] = array[index] - array[offset];
		    array[index] -= array[offset];
		}
	    }
	}
	
	for (int i=0;i<=max-min;i++)
	{
	    if (array[i] != min+i)
	    {
		return false;
	    }
	}
	
	return true;
    }

- Anonymous April 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//note: the question is asking for largest subset instead of longest sequence

class Sequence{
   private int start;
   private int end;
   private int count;
}

public Sequence findMaxSequence(int[] array){
   Set<Integer> set = new HashSet<Integer>(Arrays.asList(array));
   Map<Integer,Sequence) map = new HashMap<Integer,Sequence>();
   Sequence out = null;
   int maxSequenceCnt = 0;

   for (int n:set){
       Sequence s = map.get(n);
       if (s==null){
           s = new Sequence();
           map.put(n,s);
           s.start = n;
           s.end = n;
           while (set.contains(s.start-1)) {
               s.start--;
               map.put(s.start,s);
           }
           while (set.contains(s.end+1)) {
               s.end++;
               map.put(s.end,s);
           }
       }
       s.count++;
       if (s.count > maxSequenceCnt){
           maxSequenceCnt = s.count;
           out=s;
       }
   }
   return out;
}

- Hei May 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the basic algorithm to unshuffle an array, also prints the permutation cycles
O(n) solution, O(1) space
well you can map the given problem to this generic problem by subtracting min from all elements in the array

import sys, pdb
from random import shuffle

def unshuffle(arr):
    n=len(arr)
    if n==0: return
    
    s=0
    while s<n:
        p=s   
        ini=arr[p]
        while True:
            print p,
            p=ini
            buf=arr[p]
            arr[p]=ini
            ini=buf
            if p==s: break
        while s<n and arr[s]==s: s+=1
        print

if __name__=='__main__':
    arr=range(10)
    shuffle(arr)
    print arr
    unshuffle(arr)
    print arr

- light May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;

public class Test
{
	public static void main(String[] args)
	{
		int[] array = new int[] {5,7,1,2,3,4,8,9,10,12,13,16,18 };
		findLongestSeq(array);
//		Original
//		==================
//		5 7 1 2 3 4 8 9 10 12 13 16 18 
//
//		Longest Consecutive Seq
//		==================
//		1 2 3 4 5 

	}

	public static void findLongestSeq(int[] array)
	{
		HashSet<Integer> set = new HashSet<Integer>();
		//This takes O(n). Adding all element in array into set.
		//Set doesn't allow duplicate element.
		System.out.println("Original");
		System.out.println("==================");
		for(int element : array)
		{
			set.add(element);
			System.out.print(element + " ");
		}
		System.out.println("\n");
		
		int min = -1;
		int max = -1;
		int range = -1;
		
		//This takes O(n). Iterate until every element is removed.
		while(set.size() > 0)
		{
			//Pop one element.
			int element = set.iterator().next();
			set.remove(element);
			
			int temp_min = element;
			//Try to find the minimal consecutive number 
			while(set.contains(temp_min-1))
			{
				temp_min = temp_min -1;
				set.remove(temp_min);
			}
			
			//Try to find the maximal consecutive number 
			int temp_max = element;
			while(set.contains(temp_max+1))
			{
				temp_max= temp_max+1;
				set.remove(temp_max);
			}
			
			//Check range
			if(range < temp_max - temp_min)
			{
				min = temp_min;
				max = temp_max;
				range = temp_max - temp_min;
			}
		}
		
		//Print result
		System.out.println("Longest Consecutive Seq");
		System.out.println("==================");
		for(int i=min; i<= max; i++)
		{
			System.out.print(i + " ");
		}
		System.out.println();
		
		//Since O(n) + O(n) = O(n). This algorithm runs in O(n).
		//I utilized the characteristic of consecutive number with hashing.
	}
}

- Ted June 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The correct algorithm for a one-pass O(n) solution solution has already been posted a couple of times (for example see juando.martin), just posting the java implementation here.

The gist of the algorithm is to keep a hash map where the key is an integer value from the array, and the value indicates the min/max of the consecutive range that this integer is in. On reading each new value, check for +1/-1 neighbors, get the new min/max, and update the two ends as needed.

There are a couple comments that indicate that this is not O(n) because you need to update the hash map for all the intermediate values in the range as well. You DO NOT need to update the intermediate values. Assuming that the input array does not contain any repeated elements, the intermediate values will never come up as a neighbor for a new array value (since the +1/-1 neighbors have already occurred by definition), so they don't need to change. The only hash map elements you need to insert/update on every turn are the min/max values of the current range. Therefore the number of ops needed for each array iteration is a constant and it runs in O(n).

The implementation below just uses a 2 element array for tracking the min/max of each range, where range[0] is the min and range[1] is the max.

public static Integer[] findLongestConsecutive(Integer[] input) {
        Map<Integer, Integer[]> ranges = new HashMap<Integer, Integer[]>(input.length);

        int maxLength = 0;
        Integer[] maxRange = null;

        for (int element : input) {
            Integer[] prevRange = ranges.get(element - 1);
            Integer[] nextRange = ranges.get(element + 1);

            int min = (prevRange == null) ? element : prevRange[0];
            int max = (nextRange == null) ? element : nextRange[1];

            if (prevRange != null) {
                ranges.get(min)[1] = max;
            }
            if (nextRange != null) {
                ranges.get(max)[0] = min;
            }
            if (prevRange == null || nextRange == null) {
                ranges.put(element, new Integer[]{min, max});
            }

            if (max - min + 1 > maxLength) {
                maxLength = max - min + 1;
                maxRange = new Integer[]{min, max};
            }
        }

        return maxRange;
    }

- vertigo July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems that there is some misconceptions.
1) the original question did not ask for time complexity of O(n) at all. It just asked going through once.
2) the bit vector way is not O(n) (n is the number of array element). Instead, it is O(m) where m is max-min. m has nothing to do with n and maybe m>>n.

- jiangok2006 July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can use set of ranges to sort numbers

Pseudo code:

struct el{
int val;
int range;
}
set<struct el, is_low()> S
bool is_low(){
return lhs->val<rhs->val;
}
for every value in array(x), 
	if(x>low_bound->val-low_bound->range) continue;//duplicate
	else if(x==low_bound->val-low_bound->range) {
		low-bound->range++;
		tmp=low_bound;
		if((--tmp)->val+1==x){
			low_bound->range+=tmp->range;
			S.erase(tmp);
		}
		if(max<lower-bound->range) 
			max=lower-bound->range;
	} else if(x==(--lower_bound)->val+1){
		lower_bound->val++;
		lower_bound->range++;
		if(max<lower-bound->range) 
			max=lower-bound->range;
	} else { 
		t= new struct el;
		t.val=x;
		t.range=1;
		S.insert(t);
	}

What it does is,
Set contains ordered pairs of continues ranges.
Each element consists of its maximum value and range.
ie, at some point if sorted array looks {4,5,6,7,11,12,13,45,46,50,51,52,53,178}
Set contains {(7,4),(13,3),(46,2),(53,4),(178,1)}
lower bound() gives us iterator to value greater than equal to x,
so if x is 53, S.lower_bound(x) gives iterator to 53 and since 53>53-4, we continue(ignore)
if x is 49, S.lower_bound(x) gives iterator to 53 and since 53-4 is 49, we make (53,4) to (53,5)
If x is 47, it will pass second check and we make (46,2) to (47,3)
If x is 48, it will add a new element in the set to make it {(7,4),(13,3),(46,2),(48,1),(53,4),(178,1)}
"if((--tmp)->val+1==x){" checks if adding new element clubbed 2 ranges into one, like adding 4 to {(3,2) ,(7,3)} and makes {(7,6)}

and we maintain a max to keep track of maximum.
I think it takes O(nlogn)

- sLeviN063 August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I propose the following algorithm with a HashMap<Integer, Integer>:

When inserting a number, x, into the hashmap (the key is the array element and the value is the number pointing to its farthest existing sequence), we first check that the hashmap has no entries for x-1 or x+1. Then we insert (x,x) into the hashmap.

When there are entries for x-1 or x+1, we could be extending a sequence by one to the right, by one to the left, or joining two sequences with a gap of 1 space. We update the values for the hashmap accordingly such that the end entry of a sequence has for its value the opposite end of that sequence. For example, if we have seen 1,2,3,4 then we would like the hashmap entry for 1 to be 4, and the entry for 4 to be 1.

The following is the code:

HashMap<Integer, Integer> map = new HashMap<Integer,Integer> ();

public void doSomething()
    {
        int[] arr = {100,3,200,1,2,4};
      
        int longestSequenceLength = -1;
        int longestSequence1 = Integer.MIN_VALUE;
        int longestSequence2 = Integer.MAX_VALUE;
        
        for (int i=0;i<arr.length;i++)
        {
            //check whether number is already in hashmap
            if (!map.containsKey(arr[i]))
            {
                //check left and right values
                if (!(map.containsKey(arr[i]-1)) && !(map.containsKey(arr[i]+1)))
                {
                    map.put(arr[i], arr[i]);
                }
                else
                {
                    int x,y;
                    if (map.containsKey(arr[i]-1) && !(map.containsKey(arr[i]+1)))
                    {
                        x = map.get(arr[i]-1);
                        y = arr[i];
                        
                        map.put(arr[i], x);
                        map.put(x, arr[i]);
                        
                    }else if (!map.containsKey(arr[i]-1) && (map.containsKey(arr[i]+1)))
                    {
                        x = arr[i];
                        y = map.get(arr[i]+1);
                        
                        map.put(arr[i], y);
                        map.put(y, arr[i]);
                        
                    }
                    else
                    {
                        x = map.get(arr[i]-1);
                        y = map.get(arr[i]+1);
                        
                        map.put(arr[i],arr[i]);
                        map.put(x,y);
                        map.put(y, x);
                    }
                    
                    if ((y - x) > longestSequenceLength)
                    {
                        longestSequenceLength = y - x;
                        longestSequence1 = x;
                        longestSequence2 = y;
                    }
                }
            }
        }
        
        System.out.println(longestSequenceLength);
        System.out.println(longestSequence1);
        System.out.println(longestSequence2);
        
        
        
    }

whether there is a value for that x-1 or x+1. This means we are extending a sequence by 1 so that the length is at least 2.

- bk August 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oops disregard the last few sentences, "whether there is a value... at least 2."

- bk August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just few lines of code.

17 bool hasSequence(vector<int> &A)
18 {
19 int minVal, maxVal;
20 minVal = *std::min_element(A.begin(), A.end());
21 maxVal = *std::max_element(A.begin(), A.end());
22
23 if ( maxVal - minVal >= A.size() ) return false;
24
25 for ( size_t i = 0; i < A.size(); i++ )
26 {
27 if ( A[i] == i + minVal ) continue;
28 if ( A[A[i] - minVal] == A[i] ) A[i] = INT_MIN;
29 else swap(A[i], A[A[i] - minVal]);
30 //display(A);
31 }
32
33 return true;
34 }

- Cheergo September 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1: Find min
Step 2: Subtract min from all elements
Step 3: Check whether the numbers are from 0 - k, where k < n
Step 4: Have a temporary variable, sum = 0
Step 5: Start with the first element in the array; let it be a
Step 6: Check whether Arr[ mod(a) ] is negative.
Step 7: If it is positive, sum = sum + a
Step 8: If it is negative (implying it is already counted), go to the next element
Step 9: Go to step 5
Step 10: (Optional) Go through the contents of the array and change them back to their original values

At the end of the loop, if your sum = k*(k+1)/2, then the numbers are a sequence, else not. This approach uses O(2n) traversal and O(1) space.

- Prash September 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1: Find min
Step 2: Subtract min from all elements
Step 3: Check whether the numbers are from 0 - k, where k < n
Step 4: Have a temporary variable, sum = 0
Step 5: Start with the first element in the array; let it be a
Step 6: Check whether Arr[ mod(a) ] is negative.
Step 7: If it is positive, sum = sum + a; set Arr[ mod(a) ] = -Arr[ mod(a) ]
Step 8: If it is negative (implying it is already counted), go to the next element
Step 9: Go to step 5
Step 10: (Optional) Go through the contents of the array and change them back to their original values

At the end of the loop, if your sum = k*(k+1)/2, then the numbers are a sequence, else not. This approach uses O(2n) traversal and O(1) space.

- Prash September 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;


public class LargestSeq {
static String largestSeq(int a[]){
String largestSeq = "";

HashSet<Integer> hash = new HashSet<Integer>();
for(int n : a){
hash.add(n);
}
for(int n : a){
StringBuffer sb = new StringBuffer(n+"");
int n1 = n+1;
int n2 = n-1;
while(hash.contains(n1)){
sb.append(n1);
hash.remove(n1);
n1++;
}
while(hash.contains(n2)){
sb.insert(0, n2);
hash.remove(n2);
n2--;
}
if(largestSeq.length() < sb.length()){
largestSeq = sb.toString();
}
}
return largestSeq;
}

public static void main(String args[]){
System.out.println(largestSeq(new int[] {1,3,5,7,9}));
}
}

- Anonymous November 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In addition to the numerous hash table based approaches described in this problem comments, it seems the solution can also be expressed through using auxiliary Disjoint Set structure to perform the actual merge of the nodes in the node set. That is:
* Use hash table to store the nodes where each node contains information about its parent node in the disjoint set, as well as min and max value.
* When iterating over numbers, add a node for this number into the set if it is not there yet and join the node with x+1 and x-1 nodes.
* Once done, scan over the root nodes in the disjoint set forest and find the one with maximum set size.

All steps are amortized O(n).

Code:

# Given an array of random numbers. Find the longest consecutive sequence.
# For ex
# Array 100 3 200 1 2 4
# Ans 1 2 3 4
# Array 101 2 3 104 5 103 9 102
# Ans 101 102 103 104
# 
# Can we do it in one go on array using extra space??

import random

data = [int(5000*random.random()) for i in xrange(1000000)]

class Node:
    def __init__(self, num):
        self.parent = None
        self.rank = 0
        self.set_size = 1
        self.min_num = num
        self.max_num = num

class DisjointSet:
    def __init__(self):
        self.nodes = {}

    def add(self, num):
        if num not in self.nodes:
            self.nodes[num] = Node(num)

    def find(self, num, add=False):
        x = self.nodes.get(num)
        if x is None:
            return None
        if x.parent is None:
            return num
        else:
            return self.find(x.parent)


    def join(self, num1, num2):
        p1 = self.find(num1)
        if p1 is None: return
        p2 = self.find(num2)
        if p2 is None: return
        if p1 != p2:
            # different sets - join now
            n1 = self.nodes[p1]
            n2 = self.nodes[p2]
            assert n1.parent == None
            assert n2.parent == None
            if n1.rank == n2.rank:
                n1.rank += 1
            if n1.rank < n2.rank:
                (p1, p2) = (p2, p1)
                (n1, n2) = (n2, n1)
            n2.parent = p1
            n1.set_size += n2.set_size
            n1.min_num = min(n1.min_num, n2.min_num)
            n1.max_num = max(n1.max_num, n2.max_num)


#data = [6, 100, 3,200,1,2,4]
ds = DisjointSet()
for i in data:
    ds.add(i)
    ds.join(i, i+1)
    ds.join(i, i-1)

max_size = 0
max_start_num = None
for i in ds.nodes.values():
    size = i.max_num - i.min_num + 1
    if size > max_size:
        max_size = size
        max_start_num = i.min_num

print "start=%d, finish=%d" % (max_start_num, max_start_num+max_size-1)

- Nightingale November 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef map<int,bool> mapType;
typedef mapType::iterator mapIt;

void findConSeq(int* arr,int len){
if(arr==NULL||len<=0)return;
mapType hash;
for(int i=0;i<len;++i){
hash[arr[i]]=true;
}
int maxLen=0;
int begI=-1;
for(int i=0;i<len;++i){
if(hash[arr[i]]==false)continue;
int posStep=1;
while(true){
if(hash.find(posStep+arr[i])!=hash.end()){
hash[posStep+arr[i]]=false;
++posStep;
}else break;
}
int negStep=-1;
while(true){
if(hash.find(negStep+arr[i])!=hash.end()){
hash[negStep+arr[i]]=false;
--negStep;
}else break;
}
if(posStep-negStep-1>maxLen){
maxLen=posStep-negStep-1;
begI=arr[i]+negStep+1;
}
}
for(int i=0;i<maxLen;++i){
printf("%d ",begI+i);
}
}

- YuG January 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Slightly modified version.
1. Find min and max
2. if max - min + 1 > length of arry => return false
3. Place each integer in the right position index = value - min
4. Loop through array up to val == max and verify that each value in its right position.

public class FindIfSubsequenceWithDupicates {
	public static void main(String[] args) {
		int[] arr =  {45,50,47,46,49,48,48,48,48,46,46,46,46,51};
		System.out.println(isSequence(arr));
	}
	
	private static boolean isSequence(int[] arr) {
		if (arr == null || arr.length == 0) return false;
		if (arr.length == 1) return true;
		int[] minAndMax = findMinAndMax(arr);
		int min = minAndMax[0];
		int max = minAndMax[1];
		
		if (max - min + 1 > arr.length) return false;
		
		for (int i = 0; i < arr.length; i++) {
			int val = arr[i];
			int valIndex;
			
			int currenIndex = i;
			while ( (valIndex = val - min) != currenIndex) {
				int tmp = arr[valIndex];
				arr[valIndex] = val;
				val = tmp;
				currenIndex = valIndex;
			}
		}
		
		//now every element up to max should be consecutive
		for (int i = 0; i < arr.length; i++) {
			int val = arr[i];
			if (i + min > max) break;
			if (i + min != val) return false;
		}
		return true;
	}
	
	private static int[] findMinAndMax(int[] arr) {
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int i: arr) {
			if (i > max) max = i;
			if (i < min) min = i;
		}
		return new int[]{min, max};
	}
}

- sshlyk July 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void findSequence(int[] is) {
		int min = Integer.MAX_VALUE;
		int max = Integer.MAX_VALUE+1;
		
		HashMap<Integer, Integer> hashmap = new HashMap<Integer,Integer>();
		for(int i : is){
			if(!hashmap.containsKey(i)){
				hashmap.put(i, i);
				if(i < min)
					min = i;
				if(i > max)
					max = i;
			}
		}
		
		String output = (max-min + 1) == hashmap.size() ? "Sequence" : "Not Sequece";
	}

- brucyy December 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

On a slightly tangential note, if sorting is required as stated in the question then there is no sorting algorithm which has a running time complexity equivalent to O(n). So the problem cannot be solved.

- Galileo July 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#define MAX 100

using namespace std;

void getLgst(int * arr, int n){
int i = 0;
int mark[MAX] = {0};
int max = 0, max_temp = 0, start = 0, start_temp=0, end = 0;
while (i<n) mark[*(arr+i++)] = 1;
i = 0;
while (i<MAX){
if (mark[i] and mark[i+1])
max_temp += i++;
else if (mark[i] and !mark[i+1]){
if(max<max_temp+i){
max = max_temp+i;
end = i++;
start = start_temp;
}
else
i++;
}
else{
max_temp = 0;
i++;
if(mark[i])
start_temp = i;
}
}

cout<<start << " "<< end<<" "<<max<<endl;
}

int main()
{
cout << "Hello World" << endl;
int array[7] = {1,6,10,4,7,9,5};
getLgst(array, 7);
return 0;
}

Space can me further limited by using map.

- ltcshuai91 September 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- Anonymous October 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] findMaxSubSet(int[] array){
		int max = 0;
		int startKey = 0;
		int tempCnt = 0;
		int[] maxSub = null;
		for(int i=1; i<array.length; i++){
			if(array[i]-array[i-1] == 1) {
				tempCnt++;
				
			} else {
				if(max <= tempCnt) {
					max = tempCnt;
					maxSub = Arrays.copyOfRange(array, startKey, i);
				}
				startKey = i;
				tempCnt = 0;
			}
		}
		
		return maxSub;
	}
	
	public static int[] removeDuplication(int[] array){
		int[] maxSub = new int[array.length];
		int temp = -1;
		int tempKey = 0;
		for(int a:array) {
			if(temp != a) {
				maxSub[tempKey] = a;
				tempKey++;
			}
		}
		
		return maxSub;
	}

	public static void main(String[] args) {
		//Sort (O(logn))
		int[] array = {1, 6, 10, 4, 7, 7, 9, 5};
		QuickSort qsort = new QuickSort(array.length);
		qsort.setArray(array);
		qsort.quickSort(0, array.length-1);
		array = qsort.getArray();
		//find subset (O(n))
		int[] maxSub = findMaxSubSet(array);
		maxSub = removeDuplication(maxSub);
		System.out.println(maxSub);
	}

- Julie October 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my python code

example=[9,9,9,9]
index=len(example)-1
res=0
long(res)
for e in example:

res=res+e*10**index

index-=1

res_list=str(res+1)
final=[]
for r in res_list:

final.append(int(r))

print final

- LFT1988 November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my python code

example=[9,9,9,9]
index=len(example)-1
res=0
long(res)
for e in example:

res=res+e*10**index

index-=1

res_list=str(res+1)
final=[]
for r in res_list:

final.append(int(r))

print final

- LFT1988 November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my python code

example=[9,9,9,9]
index=len(example)-1
res=0
long(res)
for e in example:

res=res+e*10**index

index-=1

res_list=str(res+1)
final=[]
for r in res_list:

final.append(int(r))

print final

- LFT1988 November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.company;

import java.util.HashMap;

public class Main {

    public static void main(String[] args) {
        int a[] = {1,6,10,4,7,9,5, 8};
        int max = 0;
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        for(int i = 0; i< a.length; i++){
            hash.put(a[i], 1);
        }

        for(int i = 0; i<a.length; i++){
            int max1 = isThisPartOfSubSequence(a[i], hash);
            if(max1 > max){
                max = max1;
            }
        }
        System.out.println(max);
    }

    public static int isThisPartOfSubSequence(int a, HashMap<Integer, Integer> hash){
        int i = 0;
        while(hash.containsKey(a--)){
        }
        a = a + 2;

        while(hash.containsKey(a++)){
            i++;
        }
        while(hash.containsKey(--a)){
            hash.put(a, i);
        }
        return  i;

    }
}

- Daljeet Virdi December 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python O(n) time using a dictionary for constant time access to numbers.

mapping = {}
max_sequence = (None, 0)

arr = [1,6,10,4,7,9,5]


# throw into map n time
for i in arr:
	mapping[i] = [i]

# go through keys 2n time
for k in mapping.keys():
	if mapping[k] == None:
		continue
	n = 1
	while mapping.get(k+n) != None:
		mapping[k] = mapping[k] + mapping[k+n]
		n += 1
	while n > 0:
		mapping[k+n] = None
		n -= 1

# get sequence with max length n time
for k in mapping:
	if mapping[k] == None:
		continue
	seq_len = len(mapping[k])
	if seq_len > max_sequence[1]:
		max_sequence = (k, seq_len)

#print max_sequence
print mapping[max_sequence[0]]

- saaqibz May 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class StringSubset {

	public static void main(String[] args) {
		Integer[] result = find_subset(new int[] { 1, 6, 10, 4, 7, 9, 5 });
		for (int i = 0; i < result.length; i++) {
			System.out.print(result[i] + " ");
		}
	}

	public static Integer[] find_subset(int[] arr) {

		Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();

		for (int i = 0; i < arr.length; i++) {
			map.put(arr[i], new ArrayList<Integer>());
		}

		for (Entry<Integer, List<Integer>> entry : map.entrySet()) {
			List<Integer> previousValue = map.get(entry.getKey() - 1);
			int previousKey = entry.getKey() - 1;

			if (previousValue != null) {
				if (previousValue.size() > 0) {
					map.put(entry.getKey(), previousValue);
				} else if (previousValue.size() == 0) {
					List<Integer> list = new ArrayList<Integer>();
					list.add(previousKey);
					list.add(entry.getKey());
					map.put(entry.getKey(), list);
				}
			}

			List<Integer> nextValue = map.get(entry.getKey() + 1);
			int nextKey = entry.getKey() + 1;

			if (nextValue != null) {
				if (nextValue.size() > 0) {
					map.put(entry.getKey(), nextValue);
				} else if (nextValue.size() == 0) {
					List<Integer> list = entry.getValue();
					if (list.size() == 0) {
						list.add(entry.getKey());
					}
					list.add(nextKey);
					map.put(entry.getKey(), list);
				}
			}

		}

		List<Integer> maxArray = new ArrayList<>();
		for (List<Integer> list : map.values()) {
			if (list.size() > maxArray.size()) {
				maxArray = list;
			}
		}

		return maxArray.toArray(new Integer[maxArray.size()]);
	}

}

- Hawk November 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] findLongestCommonSubsequense(int[] a){

Set<Integer> seen = new HashSet<Integer>();
Map<Integer, Integer> intervals = new HashMap<Integer, Integer>();


for(int j: a){
if(seen.contains(j)){

continue;

}
seen.add(j);
Int lo=j; hi=j;

for(int i=0; i<a.length; i++){
  if(intervals.contains(i+1)){
     hi = intervals.remove(i+1);
 }

if(intervals.contains(i-1)){
     lo = intervals.remove(i-1);
 }

intervals.put(hi, lo);
intervals.put(lo,hi);

}
}

int hi=0, lo=0;
for(Entry<Integer, Integer> pair : intervals.entrySet()){
if(hi - lo < pair.getKey() - pair.getValue()){
     lo = pair.getValue();
     hi = pair.getPair();
}

}
Int ret[] = new int[hi-lo+1];

for(int i=0; i<ret.length; i++){

ret[i] = i + lo;

} 

return ret;

}

- sunny July 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] findLongestCommonSubsequense(int[] a){

Set<Integer> seen = new HashSet<Integer>();
Map<Integer, Integer> intervals = new HashMap<Integer, Integer>();


for(int j: a){
if(seen.contains(j)){

continue;

}
seen.add(j);
Int lo=j; hi=j;

for(int i=0; i<a.length; i++){
  if(intervals.contains(i+1)){
     hi = intervals.remove(i+1);
 }

if(intervals.contains(i-1)){
     lo = intervals.remove(i-1);
 }

intervals.put(hi, lo);
intervals.put(lo,hi);

}
}

int hi=0, lo=0;
for(Entry<Integer, Integer> pair : intervals.entrySet()){
if(hi - lo < pair.getKey() - pair.getValue()){
     lo = pair.getValue();
     hi = pair.getPair();
}

}
Int ret[] = new int[hi-lo+1];

for(int i=0; i<ret.length; i++){

ret[i] = i + lo;

} 

return ret;

}

- sunny July 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

On the one hand, using a hash table, we can dfs/bfs and find connected components on the path graph (add an edge for each adjacent elements) to solve the problem in Θ(n) expected time.

On the other hand, on the algebraic decision tree model, your problem cannot be solved in O(n) time. To see this, take an instance of the set disjointness problem (A, B) and transform it to [3A1, ..., 3An, 3B1 + 1, ..., 3Bn + 1]. Because the set disjointness problem has lower bound [1], your problem has the same bound.

[1] Ben-Or, Michael. Lower bounds for algebraic computation trees.

- harrypotter0 September 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>


int largest_subset(int * a,int len)
{
    int h[10000];
    int i,max,curr_max;
    for(i=0;i<len;i++)
    {
        h[a[i]]=1;
    }
    max = 0;
    i = 0;
    while(i < 10000)
    {
        if(h[i] == 1)
            {
                curr_max = 0;
                while(h[i] == 1)
                {
                    curr_max++;
                    i++;
                }
                if(curr_max > max)
                    max = curr_max;
            }
            i++;
    }
    return max;
}


int main()
{
    int a[10] = {11,4,3,2,1,7,10,8,9};
    int i = 9;
    int j;
    j = largest_subset(a,i);
    printf("Largest subset = %d",j);

    return 0;
}

- Engineer1111 June 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hp help, hp laptop support, hp laptop support number, contact hp customer support, hp support phone number, hp desktop support, hp pavilion tech support phone number, hp laptop technical support number, hp pavilion support number, l

- helptechhp June 12, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findLargetSeq(arr) {
  const arrMap = {};
  let max = -Infinity;
  let min = Infinity;
  const sequences = [];
  let seqRunning = false;
  let currentIndex = -1;
  let maxIndex = -1;
  let maxLen = -Infinity;
  for (let i = 0; i < arr.length; i++) {
    const currentNum = arr[i];
    arrMap[currentNum] = true;
    max = Math.max(currentNum, max);
    min = Math.min(currentNum, min);
  }
  for (let i = min; i <= max; i++) {
    if (i in arrMap) {
      if (seqRunning) {
        sequences[currentIndex].push(i);
      } else {
        currentIndex += 1;
        seqRunning = true;
        sequences[currentIndex] = [];
        sequences[currentIndex].push(i);
      }
    } else {
      seqRunning = false;
      if (sequences[currentIndex].length > maxLen) {
        maxLen = sequences[currentIndex].length;
        maxIndex = currentIndex;
      }
    }
  }
  if (maxIndex > -1) return sequences[maxIndex];

}

- Anonymous December 12, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

let say the array is a[]= 5 7 1 2 3 4 8 9 10 12 13 16 18


algo:

1) declare 3 set of variables int cnt1,cnt2,index[2],val[2]
2) start traversing the array and update the initial array ..--->>follow step 3
3)while traversing the array starting from index 0..store the diff of a[i+1] - a[i] in a[i]

so now the array becomes...-->> arr[] = 2 -6 1 1 1 4 1 1 2 1 3 2 18(leave the last number as it is (18) in here..
4) while traversing...if we get two values same like in here 1 and 1 a[i] == a[i-1]
then store the index of a[i-1] in index[0] and value of a[i-1] in val[0] and increase the cnt1 from 0 to 1..and increase it..unless we get any diff in values of a[i] and a[i-1]
so in here cnt1 will have 3 and val[0]=1 and index[0]=2

from now.on follow step 4 and use cnt2 instead of cnt1 to count the sequence and compare value of cnt2 with cnt1. if cnt2> cnt1 replace value of ant1 with cnt2 and arr[0] with arr[1] and index[0] with index[1] and..initialise cnt2,index[1] and val[1] to 0 each.

so go on doing this..and at last in cnt 1 we will be having the cnt of the longest sequence and in index[0] the index from which the sequence start and at val[0] ..the starting value of this sequence..

so we now know the starting value ..the diff and the index..and the count of such sequence.... now we can print the sequence..

- asetech February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

<pre lang="java" line="1" title="CodeMonkey91450" class="run-this">import java.util.HashMap;
import java.util.Map;


class Main {

public static void printLongestSeq(Integer[] inp)
{
//Check if input is empty or null
if ((inp == null) || (inp.length == 0))
{
return;
}

Map<Integer, Integer> lens = new HashMap<Integer, Integer>();

Integer resElem; //Result element
Integer resElemLen; //Result element len
resElem = inp[0]; //By default take first element
resElemLen = 1; //By default set max len 1
for (Integer currElemKey : inp)
{
//For current element in array find longest increasing sequence
//by jumping in hash table
Integer nextElemKey = currElemKey+1;
//In each key we are storing element of input array
//In each value we are storing longest increasing seq starting from integer (key)
Integer nextElemLen = lens.get(nextElemKey);
Integer totalLenToAdd = 0;
while (nextElemLen != null)
{
//Add total len of subseqences
totalLenToAdd += nextElemLen;
if (nextElemLen > 1)
{
//If nextElemLen > 1 then subsequence starting with this element
//is already calculated so exit from this loop
break;
}
else
{
//We have found increasing sequence
//just update total len
nextElemKey++;
nextElemLen = lens.get(nextElemKey);
}
}
//If current element is not in the hash put it in hash table along with
//total length of increasing elements
Integer currElemLen = lens.get(currElemKey);
if (currElemLen == null)
{
currElemLen = 1;
}
currElemLen += totalLenToAdd;
lens.put(currElemKey, currElemLen);
if (currElemLen > resElemLen)
{
resElem = currElemKey;
resElemLen = currElemLen;
}

//If current element is in the middle of increasing sequence
//then update previous elements of this sequence
//by adding +currElemLen
Integer prevElemKey = currElemKey - 1;
Integer prevElemLen = lens.get(prevElemKey);

while ( prevElemLen != null )
{
lens.put(prevElemKey, prevElemLen + currElemLen);
if ((prevElemLen + currElemLen) > resElemLen)
{
resElem = prevElemKey;
resElemLen = prevElemLen + currElemLen;
}
prevElemKey--;
prevElemLen = lens.get(prevElemKey);
}
}

//Dump the sequence starting from element resElem with
//total resElemLen elements count
for (int i = 0; i < resElemLen; i++)
{
Integer currElement = resElem + i;
System.out.print(currElement + " ");
}
System.out.println();
}

public static void main(String[] args)
{
Integer[] test1 = new Integer[]{100, 3, 200, 1, 2, 4};
printLongestSeq(test1);
Integer[] test2 = new Integer[]{101, 2, 3, 104, 5, 103, 9, 102};
printLongestSeq(test2);
Integer[] test3 = new Integer[]{5, 4, 3, 2, 1};
printLongestSeq(test3);
}

}
</pre><pre title="CodeMonkey91450" input="yes">
</pre>

- Anonymous July 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Fuck off stupid nonsense! Why post code here without explanation? Who asked for it?

- anonymous July 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

One go hashtable solution:

For each cell, calculate the hashvalue first, for example for Array 101 2 3 104 5 103 9 102
we insert 101 on the 101th cell of the hastable. Then for each number we will check the value in the hastable for the cell value minus and plus one.
for our example, we check the hashtable at index 100 and 102 and both are empty. we proceed to the second cell

void largestConsecutiveSequence(int[] Array)
{
int maxLength=0; //indicates the length of the longest consequtive sequence
for (int cell: Array)
{
hashtable(cell)=cell;
int i=cell;
int LengthofCurrentSequence=0;
while ( !hastable(i))
{
LengthofCurrentSequence++;
i--;
}
i=cell+1;
while ( !hastable(i))
{
LengthofCurrentSequence++;
i++;
}
if LengthofCurrentSequence>maxLength
maxLength= LengthofCurrentSequence;
}

Systems.out.println("Length of the largest consecutive sequence=" + maxLength;
}

Complexity: O(n)
One go

- Anonymous July 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

it's wrong. Work with : 3, 5, 7, 2, 6, 8, 4, 9, 1

- anon August 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't think the approach is wrong, yes it requires some modification. Correct me if I am wrong.

Focusing on this line of submitter - 'for our example, we check the hashtable at index 100 and 102 and both are empty. we proceed to the second cell'
If we set the values to zero after checking it in hashtable , then the order analysis will definitely improve, means it will become O(n).

- Skataria December 01, 2011 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More