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

• 11

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

+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.

Comment hidden because of low score. Click to expand.
6

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;
}``````

Comment hidden because of low score. Click to expand.
0

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))

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);
}
}}}

Comment hidden because of low score. Click to expand.
2

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))

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);
}``````

}

Comment hidden because of low score. Click to expand.
0

Can someone post an explanation?

Comment hidden because of low score. Click to expand.
4

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}``````

Comment hidden because of low score. Click to expand.
0

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}

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 when A[i]==min(A)
and A[j]-min(A) is at A if A[j] = min(A)+1
and A[k]-min(A) is at A 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,46,47,45,50,50,49,48,49] //swap 50 & 46
[45,46,47,-Inf,50,50,49,48,49] //A = -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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

it will not handle duplicate elements....

Comment hidden because of low score. Click to expand.
0

it wont work

Comment hidden because of low score. Click to expand.
0

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.

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;
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;
}

}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

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?

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.

Comment hidden because of low score. Click to expand.
0

seems good..

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Like

Comment hidden because of low score. Click to expand.
0

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);

}
}``````

Comment hidden because of low score. Click to expand.
0

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());

}
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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());

}
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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);
}``````

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)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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 ?

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++)+" ");
}``````

Comment hidden because of low score. Click to expand.
0

@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)

Comment hidden because of low score. Click to expand.
0

Awesome solution dude.. It works!

Comment hidden because of low score. Click to expand.
0

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

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

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

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

I think this solution works fine..good work.

Comment hidden because of low score. Click to expand.
0

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

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.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();
}``````

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 {
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;
}//*/``````

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 = { 1, 12, 10, 4, 7, 9, 5, 5, 8 };
vector<int> vec(arr, arr + 9);

getMaxSequence(vec);
return 0;
}``````

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Use a treeMap

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

where have you had the interview?

Comment hidden because of low score. Click to expand.
0

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.

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

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

it is in O(n) time complexity.

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

@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

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.. :)

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.

Comment hidden because of low score. Click to expand.
0

Epic fail ...

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;
}

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;
}``````

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.

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``````

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)); // 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;
}

Comment hidden because of low score. Click to expand.
0

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

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

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.

Comment hidden because of low score. Click to expand.
0

Aren't insertions into a Red Black Tree

``O(log n)``

?

Comment hidden because of low score. Click to expand.
0

Yes they are

``O(log n)``

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

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?

Comment hidden because of low score. Click to expand.
0

where did u attend this interview?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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 ?

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]);

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

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

it was discussed earlier
id=7695669

Comment hidden because of low score. Click to expand.
0

why dont you just post the link directly..

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

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

Comment hidden because of low score. Click to expand.
0

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

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

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"

Comment hidden because of low score. Click to expand.
0

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

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++ ){
}
}

index = endIndex+1;
}

return res;``````

}

Comment hidden because of low score. Click to expand.
0

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!

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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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.

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

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...

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

@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).

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?

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>();
}
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;
++size;
}
while (tail.next != null) {
++size;
tail = tail.next;
nodeMap.remove(tail.value);
}
if (size > maxSize) {
maxSize = size;
}
}
return list;
}
}``````

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.

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.

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0

it should be consecutive elements

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@ankiet

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

Comment hidden because of low score. Click to expand.
0

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...

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

Comment hidden because of low score. Click to expand.
0

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

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!

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

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.

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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. !

Comment hidden because of low score. Click to expand.
0

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 ?

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.

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

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

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

Using counting sort?? And you need extra space.

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

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

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).

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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 ?

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

Comment hidden because of low score. Click to expand.
0

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

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

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

#include "stdio.h"

int main()
{

unsigned int arr={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]);
}

Comment hidden because of low score. Click to expand.
0

#include "stdio.h"

int main()
{

unsigned int arr={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]);
}

Comment hidden because of low score. Click to expand.
0

#include "stdio.h"

int main()
{

unsigned int arr={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]);
}

Comment hidden because of low score. Click to expand.
0

#include "stdio.h"

int main()
{

unsigned int arr={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]);
}

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.

Comment hidden because of low score. Click to expand.
0

Creating a BST is an implicit sorting.

Comment hidden because of low score. Click to expand.
0

This is also equivalent to sorting ...

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.

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.

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)

Comment hidden because of low score. Click to expand.
0

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

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.

Comment hidden because of low score. Click to expand.
0

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).

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;

;

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

public static int find_maximum_sequence(int[] array) {
int maximum_size = 0;
for (int i = 0; i < array.length; i++) {
int value = array[i];
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>

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Yea, It works

Comment hidden because of low score. Click to expand.
0

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).

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
}

}

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;
}``````

Comment hidden because of low score. Click to expand.
0

This doesn't handle duplicates.

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

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

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;
}
}
}

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 - A
A - A
...
A[n] - A[n-1]
& A - 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}
-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-A[n]

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

What an idiot

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

``````public int getConsequetiveNumbers(int[] array)
{
int min, max;
min = max = array;
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;
}``````

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();
}
}``````

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

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

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;
}``````

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``````

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)
{
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.
}
}``````

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 is the min and range 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;
int max = (nextRange == null) ? element : nextRange;

if (prevRange != null) {
ranges.get(min) = max;
}
if (nextRange != null) {
ranges.get(max) = 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;
}``````

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.

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)

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.

Comment hidden because of low score. Click to expand.
0

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

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 }

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.

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.

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){
}
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}));
}
}

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 = {}

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

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:
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.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)``````

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);
}
}

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;
int max = minAndMax;

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};
}
}``````

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";
}``````

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.

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 = {1,6,10,4,7,9,5};
getLgst(array, 7);
return 0;
}

Space can me further limited by using map.

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

test

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);
}``````

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

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

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

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;

}
}``````

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:
max_sequence = (k, seq_len)

#print max_sequence
print mapping[max_sequence]``````

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>();
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) {
}
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()]);
}

}``````

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;

}
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;

}``````

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;

}
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;

}``````

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 , your problem has the same bound.

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

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;
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 = {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;
}``````

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

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];``````

}

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,val
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 and value of a[i-1] in val 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=1 and index=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 with arr and index with index and..initialise cnt2,index and val 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 the index from which the sequence start and at val ..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..

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; //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);
while (nextElemLen != null)
{
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;
}
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
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>

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?

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

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

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).

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.

### 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.