Google Interview Question
Software Engineer in Tests Software Engineer / DevelopersCountry: -
Interview Type: Phone Interview
dunt you think ; n means number of element;
what could be your space complexity for having only 2 number {1,100}??
+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.
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;
}
And here is the c# implementation of the same thing
{{public static void LongestContiguousSubArr(int[] arr)
{
Dictionary<int, int> map = new Dictionary<int, int>();
int f = 0;
int l = 0;
for (int i = 0; i < arr.Length; i++)
{
int num = arr[i];
int beg = num;
int end = num;
if (map.ContainsKey(num))
continue;//already processed
map[num] = num;
int numm1 = num - 1;
int nump1 = num + 1;
if (map.ContainsKey(numm1))
beg = map[numm1];
if (map.ContainsKey(nump1))
end = map[nump1];
int temp = map[beg];
map[beg] = map[end];
map[end] = temp;
if (f - l <= end - beg)
{
f = beg;
l = end;
}
}
for (int i = f; i < l; i++)
{
Console.WriteLine(i);
}
}}}
Reposting with formatting
public static void LongestContiguousSubArr(int[] arr)
{
Dictionary<int, int> map = new Dictionary<int, int>();
int f = 0;
int l = 0;
for (int i = 0; i < arr.Length; i++)
{
int num = arr[i];
int beg = num;
int end = num;
if (map.ContainsKey(num))
continue;//already processed
map[num] = num;
int numm1 = num - 1;
int nump1 = num + 1;
if (map.ContainsKey(numm1))
beg = map[numm1];
if (map.ContainsKey(nump1))
end = map[nump1];
int temp = map[beg];
map[beg] = map[end];
map[end] = temp;
if (f - l <= end - beg)
{
f = beg;
l = end;
}
}
for (int i = f; i < l; i++)
{
Console.WriteLine(i);
}
}
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}
Here's a in-place algorithm with O(n) time and O(1) extra-space
Given array 'A' of size 'n', the goal is to reorder elements in the given array so that they are in their correct positions i.e. A[i]-min(A) is at A[0] when A[i]==min(A)
and A[j]-min(A) is at A[1] if A[j] = min(A)+1
and A[k]-min(A) is at A[2] if A[k] = min(A)+2 ..... so on....
1. Pass1: Find max(A) and min(A)
if ( max(A)-min(A) > n ) then return false //i.e. you cannot have a sequence greater than n
2. Pass2: For every element 'i',
a. if A[i] == A[A[i]-min(A)] //already at the right position
if i != arr[i]-minArr then set A[i]=-Inf //this is a duplicate
else continue next iteration
b. else //swap to move it to the right position
swap A[i] with A[A[i]-min(A)]
after swapping if A[i] != min(A)+i repeat from step 'a'
3. Pass3: For every element 'i', check if next element == A[i]+1,
if not then return false.
An example with duplicates: {45,50,47,45,50,46,49,48,49}
Pass1: max(A) = 50, min(A) = 45
Pass2: modified Array:
[45,50,47,45,50,46,49,48,49] //45 already at A[A[0]-min(A)]
[45,46,47,45,50,50,49,48,49] //swap 50 & 46
[45,46,47,45,50,50,49,48,49] //47 already at A[47-45]
[45,46,47,-Inf,50,50,49,48,49] //A[3] = -Inf since it is a duplicate
[45,46,47,-Inf,-Inf,50,49,48,49]
[45,46,47,-Inf,-Inf,50,49,48,49]
[45,46,47,-Inf,49,50,-Inf,48,49]
[45,46,47,48,49,50,-Inf,-Inf,49]
[45,46,47,48,49,50,-Inf,-Inf,-Inf]
Pass3: return true
//Note : instead of -Inf you can use some other marker such as min(A)-2
ok, since many of you are disagreeing, I've posted the code below
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.
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.
//ideone.com/Sa2Xz
#include <vector>
#include <iostream>
#include <algorithm>
#include <limits>
using std::vector;
using std::cout;
bool HasSequence (vector <int>& arr)
{
int maxArr, minArr;
bool success = true;
if (arr.empty())
{
return !success;
}
//Step-1:
maxArr = *std::max_element (arr.begin(), arr.end());
minArr = *std::min_element (arr.begin(), arr.end());
if (maxArr - minArr >= arr.size())
{
return false;
}
//Step 2:
//For every element
for ( int i = 0; i < arr.size() ; ++i)
{
bool swappedProperly = false;
while (!swappedProperly) //DONT GET DECIEVED BY THIS WHILE LOOP FOR O(N^2) complexity.// This algo is stil O(n)
{
if (minArr > arr[i]) //Duplicate
{
break;
}
// a. if A[i] == A[A[i]-min(A)]
if (arr[i] == arr[arr[i]-minArr]) //already at the right position
{
if (i != arr[i]-minArr) //this is a duplicate
{
arr[i] = minArr - arr[i]; //mark it less than min(A) so that it can be identified as dup
}
swappedProperly = true; //next iteration
}
// b. swap to move it to the right position
else
{
// swap A[i] with A[A[i]-min(A)]
std::swap (arr[i], arr[arr[i]-minArr]);
// after swapping if A[i] != min(A)+i repeat from step 'a'
if (arr[i] == minArr+i)
{
swappedProperly = true;
}
}
}
}
//Step 3: //For every element 'i',
vector<int>::iterator itr = arr.begin();
++itr;
for ( ; arr.end() != itr ; ++itr)
{
if (*itr < minArr)
{
//traverse until the end to see that there are no gaps in the sequence
for ( ; arr.end() != itr; ++itr)
{
if (*itr >= minArr)
{
success = false;
continue;
}
*itr = minArr + *itr; //revert change done for marking as dup
}
break;
}
if ((*(itr-1))!= (*itr)-1) //check if current element == previous element - 1,
{
success = false;
break;
}
}
return success;
}
int main()
{
int arr[] = {45,50,47,45,50,46,49,48,49};
std::vector<int> inputArray (arr, arr + sizeof(arr)/sizeof(int));
if (!inputArray.empty() && HasSequence (inputArray) )
{
std::cout << "Contains a Sequence :\t [" ;
int prevVal = inputArray[0];
for (std::vector<int>::const_iterator itr = inputArray.begin();
inputArray.end() != itr; ++itr)
{
if (*itr < prevVal)
{
break;
}
std::cout << *itr << "'";
prevVal = *itr;
}
std::cout << "]" << std::endl;
}
else
{
std::cout << "Doesn't contain a sequence" << std::endl;
}
}
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.
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.
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.
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.
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?
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.
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.
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);
}
}
Well that is not exactly my idea. Than does not run in O(n) as you update nodes in the table that need not. Take into account that once a node is stored it will never be checked again unless a neighbor is checked in too for the first time, so you only need to keep updated the extremes of a chain.
The code would be for the node class just the same:
import java.util.HashMap;
class Node {
Integer first;
Integer last;
Node(Integer first_int, Integer last_int) {
this.first = first_int;
this.last = last_int;
}
}
But for the Consecutive string class:
import java.util.HashMap;
public class ConsecutiveString {
public static void main(String[] args) {
Integer max_length = 0;
Node max_chain = null;
HashMap<Integer, Node> table = new HashMap<Integer, Node>();
Integer[] numbers = { 101, 2, 3, 104, 5, 103, 9, 102 };
for (Integer number : numbers) {
if (table.containsKey(number)) {
continue;
} else {
Node here;
if (table.containsKey(number - 1)) {
Node left = table.get(number - 1);
if (table.containsKey(number + 1)) {
Node right = table.get(number + 1);
// We have both left and right. Link them and
// store in both sides
left.last = right.last;
right.first = left.first;
here = left; // Or right, it's the same
} else {
// there is a node at our left, but not at the right.
left.last = number;
table.put(number, left);
here = left;
}
} else if (table.containsKey(number + 1)) {
// We have only a node at our right
Node right = table.get(number + 1);
right.first = number;
here = right;
} else {
// No other node around
here = new Node(number, number);
}
table.put(number, here);
int length = here.last - here.first + 1;
if (length > max_length) {
max_length = length;
max_chain = here;
}
}
}
System.out.println(max_chain.first.toString() + " - " +
max_chain.last.toString());
}
}
@juando.martin Yes. I think you are right :-) Good idea. Thank you so much. What I implemented is what alphayoung suggests.
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
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());
}
}
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.
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);
}
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)
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.
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++)+" ");
}
@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)
1. Put the elements into a hash list = 0(n) (I am assuming 0(1) insertion here, which can be done at the expense of memory).
2. Maintain 2 variables say longestSeqLength = curSeqLength;
3. Run the following loop,
longestSeqLength = curSeqLength = 0;
for ( iterator itr = list.begin(); itr != list.end(); ++itr) {
curSeqLength++;
//Find all consecutive numbers greater than the current element
int offset = 1;
for (iteator j = list.find(*itr) + offset); j != list.end();
++offset, ++curSeqLength) {
list.erase(j);
}
//Find all consecutive numbers less than the current element
offset = -1;
for (iteator j = list.find(*itr) + offset); j != list.end();
--offset, ++curSeqLength) {
list.erase(j);
}
if (curSeqLength > longestSeqLength)
longestSeqLength = curSeqLength;
curSesLenght = 0;
}
caveat: I am assuming its safe to erase elements from a hash list while iterating over it. In some implementations (eg C++ stl) you have to take special precutions for this. In the interest of clarity I have not added the code to cater to iterator invalidation.
4. Note that for each number we find the longest sequence that this number could be a part of in the input. We do this by progressively finding the numbers greater than and less than the current number such that the combined result is part of a sequence. When we find such a number we erase it from the list so we will never visit this again. If we don't find any such numbers we move onto the next number.
5. In the loop above we only hit a number once, making this a O(n) loop.
Total time = n (hashing) + n (loop in step 3) = 2n = O(n)
Jasmeet
@Jasmeet: a hashtable is not sorted so 3,4,5 need not be in a consecutive order. So if you insert 3,1,6,2,8,9,10, into hashtable and traverse the table. you could get some order depending on the hash function n definitely not sorted
@Anonymous
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.
Here is a solution in c#. The java solution should not be much different
private static String MaxConsecutiveSequence(int[] data)
{
if (data == null)
{
return null;
}
if (data.Length < 2)
{
return data[0].ToString();
}
// find the largest value in the array - O(n)
int maxValue = Int32.MinValue;
for (int idx = 0; idx < data.Length; idx++)
{
if(data[idx] > maxValue)
{
maxValue = data[idx];
}
}
bool[] markers = new bool[maxValue+1];
// Set a marker for where the value occurs - O(k)
for (int idx = 0; idx < data.Length; idx++)
{
markers[data[idx]] = true;
}
markers[maxValue] = false;
// Traverse the marker array looking for max sequence - O(k)
int sequence = 0;
int start = 0;
int maxSequenceStart = 0;
int maxSequence = 0;
bool inSeq = false;
int j = 0;
while(j < markers.Length)
{
if(markers[j])
{
if (!inSeq)
{
start = j;
}
sequence++;
inSeq = true;
}
else
{
if (sequence > maxSequence)
{
maxSequence = sequence;
maxSequenceStart = start;
}
sequence = 0;
inSeq = false;
}
j++;
}
StringBuilder sb = new StringBuilder();
for (int i = maxSequenceStart; i <= maxSequenceStart + maxSequence; i++)
{
sb.Append(i);
sb.Append(" ");
}
return sb.ToString();
}
I'm pasting my code here for this problem.
The idea is to use merging small consecutive pieces:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Sequence {
public:
int start;
int end;
Sequence(int _start, int _end) {
start = _start;
end = _end;
}
};
class Solution {
public:
int longestConsecutive(vector<int> &num) {
unordered_map<int, Sequence*> map;
for (int t = 0 ; t < num.size() ; t++) {
int i = num[t];
if (map.find(i) != map.end()) {
//found, ignore
} else {
//not found
bool f1 = (map.find(i - 1) != map.end());
bool f2 = (map.find(i + 1) != map.end());
if (f1 && f2) {
map[map[i - 1]->start]->end = map[i + 1]->end;
map[map[i + 1]->end]->start = map[i - 1]->start;
map[i] = map[map[i - 1]->start];
} else if (f1 && !f2) {
map[map[i - 1]->start]->end = i;
map[i] = new Sequence(map[i - 1]->start, i);
} else if (!f1 && f2) {
map[i] = new Sequence(i, map[i + 1]->end);
map[map[i + 1]->end]->start = i;
} else {
//!f1 && !f2
map[i] = new Sequence(i, i);
}
}
}
int max = 0;
for (auto it = map.begin() ; it != map.end() ; it++) {
if (it->second->end - it->second->start + 1 > max) {
max = it->second->end - it->second->start + 1;
}
}
return max;
}
};
/*
int main(int argc, const char* argv[]) {
Solution s;
vector<int> num;
num.push_back(100);
num.push_back(4);
num.push_back(200);
num.push_back(1);
num.push_back(3);
num.push_back(2);
cout << s.longestConsecutive(num) << endl;
return 0;
}//*/
Here is the solution c++...!!!
#include<iostream>
#include<vector>
#include<unordered_map>
void getMaxSequence(vector<int>& vec){
unordered_map<int, int> hash;
unordered_map<int, int>::iterator it, prev, next;
for (int i = 0; i < vec.size(); ++i){
it = hash.find(vec[i]);
if (it == hash.end()){
prev = hash.find(vec[i] - 1);
next = hash.find(vec[i] + 1);
if (prev != hash.end() && next != hash.end()){
int temp = prev->second;
hash[prev->second] = next->second;
hash[next->second] = temp;
hash[vec[i]] = prev->first;
}
else if (prev != hash.end()){
int temp = prev->second;
hash[temp] = vec[i];
hash[vec[i]] = temp;
}
else if (next != hash.end()){
int temp = next->second;
hash[temp] = vec[i];
hash[vec[i]] = temp;
}
else{
hash[vec[i]] = vec[i];
}
}
}
int max = 0;
int start = 0, end = 0;
for (it = hash.begin(); it != hash.end(); it++){
int result = it->first - it->second;
if (result > max)
{
start = it->second;
end = it->first;
max = result;
}
}
for (int i = start; i <= end; i++)
cout << i << " ";
cout << endl;
}
int main(){
int arr[9] = { 1, 12, 10, 4, 7, 9, 5, 5, 8 };
vector<int> vec(arr, arr + 9);
getMaxSequence(vec);
return 0;
}
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.
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.
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.
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;
}
it is longest consecutive elements sequence..
in 3 1 4 2 5... 4 and 2 r not consecutive..neither do 1 ans 4 dn how it is 1 2 3 4 5
and in 5,12,3,13,10,9,4,6,23,8,7 .. 3,13 r not consecutive..
the answer should be 10,9 or 8,7.. not 3,4,5,6,7,8,9,10
@asetech: 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
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.
#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;
}
#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;
}
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
#include <vector>
using namespace std;
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
vector<int> p(a.size());
int u, v;
if (a.empty()) return;
b.push_back(0);
for (size_t i = 1; i < a.size(); i++)
{
// If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
if ((a[b.back()] < a[i])&&(a[i]-a[b.back()]==1))
{
p[i] = b.back();
b.push_back(i);
continue;
}
// Binary search to find the smallest element referenced by b which is just bigger than a[i]
// Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.
for (u = 0, v = b.size()-1; u < v;)
{
int c = (u + v) / 2;
if (a[b[c]] < a[i]) u=c+1; else v=c;
}
// Update b if new value is smaller then previously referenced value
if (a[i] < a[b[u]])
{
if (u > 0) p[i] = b[u-1];
b[u] = i;
}
}
for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
/* Example of usage: */
#include <cstdio>
int main()
{
int a[] = { 10, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
vector<int> seq(a, a+sizeof(a)/sizeof(a[0])); // seq : Input Vector
vector<int> lis; // lis : Vector containing indexes of longest subsequence
find_lis(seq, lis);
//Printing actual output
for (size_t i = 0; i < lis.size(); i++)
printf("%d ", seq[lis[i]]);
printf("\n");
return 0;
}
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
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.
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?
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
I guess you need two passes over original array,
one to find max and min
and one to hash all elements.... my bad
1) It was telephonic.
2) Regarding above solution, he told that we dont have any limit on numbers.
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).
I think we can do it in single go. My algorithm is:
take an array(bit array/chars) of suitable size and scan the input sequence. For each input number , set the corresponding flag/bit on.
Now the single go:
initially take low1_index=0,low2_index=0 ,high_index=0 ,count_prev=0,count_new=0;
for(int i=0;i<=MAX;i++)
{
while(!array[i])i++;
low2_index=i;
while( i<=MAX && array[i++])
count_new++;
if(count_new > count_prev)
{high_index=i;low1_index=low2_index;}
}
for(int i=low1_index;i<high_index;i++)
printf("%d ",array[i]);
@mrn
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
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?
As Neo mentioned "we dont have any limit on numbers" , how about taking the bit array of size MAX range?
Following approach is possible:
We can use extended binary search tree. Each node stores continious Interval (start - end) and amount of numbers inside the interval (if numbers can repeat). Nodes are compared by Start of the Interval.
Then we scan array from the beginning to end and for each number NUM update tree by following rules:
1. If tree doesn't contain intervals with NUM-1 and NUM+1 => add new node
2. If tree contains only interval with NUM-1 => add update this interval
3. If tree contains only interval with NUM+1 => add update this interval
4. If tree contains both intervals => merge them in one node and delete another
During update of tree, store Node with biggest range.
No collisions are possible because of mentioned update rules
For better performance extended RB tree can be used (support balance)
Performance characteristics:
- Original array passed only once
- Worst case (no consequtive sequences) - update of binary tree takes O(n*log(n))
- If there are a lot of consequtive sequences, performance of algorithm can be much better as tree will contain much less then n elements
Critisism please?
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"
We could use this code:
public List<Integer> longestConsSeq(int[] arr){
BitSet set = new BitSet();
for( int value : arr ){
set.set(value);
}
int index = 0;
int maxSequenceLength = 0;
List<Integer> res = new ArrayList<Integer>();
while( index < set.length() ){
int startIndex = set.nextSetBit(index);
int endIndex = set.nextClearBit(index+1)-1;
int sequenceLength = endIndex - startIndex;
if( sequenceLength > maxSequenceLength ){
res.clear();
maxSequenceLength = sequenceLength;
for( int i = startIndex; i < endIndex+1; i++ ){
res.add( i );
}
}
index = endIndex+1;
}
return res;
}
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!
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).
I have a different approach
For each element in A[i], draw an edge between A[i]-1, A[i]+1 if they exist.
For this, we ll need to hash each element in A.
Then run a DFS to compute the size of components in the graph.
Total Time = O(n) + O(V+E)
V = O(n), E = O(n).
So time = O(n)
Space = O(n) for hash , O(n) to maintain adjacency list for each element.
@Sriram: 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.
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.
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...
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)
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).
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?
Simple idea:
Use a hashmap to build a double linked list:
1. Create a Map of linked nodes
2. for each number create a linked node in the map. Check if its previous value is there, if is link then. Do the same for the next value.
3. scan the map to check the longest linked list build
Complexity:
Space: O(n) (The linked lists and the map)
Time: O(n) (One iteration in the input, and one iteration in the hashmap, each using a value at most once)
Code:
public class LongestSequence {
public static class NodeList {
public NodeList prev;
public NodeList next;
public int value;
}
public static NodeList findLongestConsecutives(int[] values) {
Map<Integer, NodeList> nodeMap = new HashMap<Integer, NodeList>();
buildLinkedLists(values, nodeMap);
return findLongestLinkedList(nodeMap);
}
private static void buildLinkedLists(int[] values,
Map<Integer, NodeList> nodeMap) {
for (int val : values) {
if (!nodeMap.containsKey(val)) {
NodeList cur = new NodeList();
cur.value = val;
nodeMap.put(val, cur);
NodeList prev = nodeMap.get(val-1);
if (prev != null) {
prev.next = cur;
cur.prev = prev;
}
NodeList next = nodeMap.get(val+1);
if (next != null) {
next.prev = cur;
cur.next = next;
}
}
}
}
private static NodeList findLongestLinkedList(Map<Integer, NodeList> nodeMap) {
NodeList list = null;
int maxSize = 0;
while (!nodeMap.isEmpty()) {
NodeList tail = nodeMap.entrySet().iterator().next().getValue();
nodeMap.remove(tail.value);
int size = 1;
NodeList head = tail;
while (head.prev != null) {
++size;
head = head.prev;
nodeMap.remove(head.value);
}
while (tail.next != null) {
++size;
tail = tail.next;
nodeMap.remove(tail.value);
}
if (size > maxSize) {
maxSize = size;
list = head;
}
}
return list;
}
}
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.
if we follow above statements then your initial example is wrong
in your example according to you
Eg. {1,6,10,4,7,9,5}
then ans is 4,5,6,7
if you are not considering the order then why not 1,4,5,6,7 or
1,4,5,6,7,9,10 ?
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
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
@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
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.
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 ?
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. !
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.
What type of idiots are you? You wanna use bit vector, and claim it's O(1) space sol...... LMAO !!!
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 ?
#include "stdio.h"
int main()
{
unsigned int arr[8]={1,4,5,6,7,9,11,17};
unsigned int index=0,current_index=0,max_matches=1,i=0;
for(i=0;i<7;i++)
{
if(arr[i]+1 == arr[i + 1])
{
current_index++;
}
else
{
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
current_index = 1;
}
}
for(i=index ; i < (max_matches + index); i++)
printf("%d\n",arr[i]);
}
#include "stdio.h"
int main()
{
unsigned int arr[14]={1,4,5,6,7,9,11,17,21,22,23,24,25,26};
unsigned int index=0,current_index=0,max_matches=1,i=0;
for(i=0;i<13;i++)
{
if(arr[i]+1 == arr[i + 1])
{
current_index++;
printf("%d %d %d\n",arr[i ],arr[i + 1],current_index);
}
else
{
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
current_index = 1;
printf("%d %d %d %d\n",index,max_matches,current_index,i);
}
}
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
printf("%d %d\n",max_matches,index);
printf("%d\n",current_index);
for(i=index ; i < (max_matches + index); i++)
printf("%d\n",arr[i]);
}
#include "stdio.h"
int main()
{
unsigned int arr[14]={1,4,5,6,7,9,11,17,21,22,23,24,25,26};
unsigned int index=0,current_index=0,max_matches=1,i=0;
for(i=0;i<13;i++)
{
if(arr[i]+1 == arr[i + 1])
{
current_index++;
}
else
{
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
current_index = 1;
}
}
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
for(i=index ; i < (max_matches + index); i++)
printf("%d\n",arr[i]);
}
#include "stdio.h"
int main()
{
unsigned int arr[14]={1,4,5,6,7,9,11,17,21,22,23,24,25,26};
unsigned int index=0,current_index=0,max_matches=1,i=0;
for(i=0;i<13;i++)
{
if(arr[i]+1 == arr[i + 1])
{
current_index++;
}
else
{
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
current_index = 1;
}
}
index = (current_index > max_matches)? ((i + 1) - current_index) : index;
max_matches = (current_index > max_matches)? current_index:max_matches;
for(i=index ; i < (max_matches + index); i++)
printf("%d\n",arr[i]);
}
How about constructing a binary tree for the given array and then traverse it in-order form to find the largest sequence of numbers.
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)
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.
<pre lang="" line="1" title="CodeMonkey12013" class="run-this">/**
*
*/
package array;
import java.util.HashMap;
import LinkList.LinkList;
import LinkList.LinkListNode;
;
/**
* @author envio
*
*/
public class FindMaximumSequence {
public static int find_maximum_sequence(int[] array) {
HashMap<Integer, LinkList> hash = new HashMap<Integer, LinkList>();
int maximum_size = 0;
LinkList sequence = null;
for (int i = 0; i < array.length; i++) {
int value = array[i];
LinkList node = new LinkList(value);
LinkList front = null;
LinkList end = null;
if ((end = hash.get(value + 1)) != null) {
node.union(end);
int end_key = node.end.get_value();
hash.remove(end_key);
hash.put(end_key, node);
hash.put(value, node);
if (maximum_size < node.size) {
maximum_size = node.size;
sequence = node;
}
}
if ((front = hash.get(value - 1)) != null) {
front.union(node);
int end_key = node.end.get_value();
hash.remove(end_key);
hash.put(end_key, front);
if (maximum_size < front.size) {
maximum_size = front.size;
sequence = front;
}
}
if(end == null && front==null){
hash.put(value, node);
}
}
sequence.print();
return maximum_size;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(FindMaximumSequence.find_maximum_sequence(new int[] {
1, 6, 10, 4, 7, 9, 5,8 ,112,144,113,114}));
}
}
</pre><pre title="CodeMonkey12013" input="yes">
</pre>
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
}
}
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;
}
what about this? make sure it works.
public static int[] NoDuplication(int[] input)
{
int i = 0, j = 1, m = 0, k=0;
int count = 0;
int[] nonReptArr;
while(i+1< input.Length)
{
if (input[i] != input[i + 1])
j++;
}
nonReptArr = new int[j];
while (m+1< input.Length)
{
if (input[m] != input[m + 1])
{
nonReptArr[k] = input[m];
//count[k] = cnt;
count=1;
k++;
}
else
{
count++;
}
m++;
}
nonReptArr[k] = input[m];
return nonReptArr;
}
}
}
I think i have a O(n) time and O(1) space solution -
Iterate through the array and subtract adjacent elements like -
A[1] - A[0]
A[2] - A[1]
...
A[n] - A[n-1]
& A[0] - A[n]
Calculate the sum of these numbers and it will always be 0. Eg -
For the sequence - {45,50,47,46,49,48}
If you subtract the adjacent elements : 50 -45 , 47 -50 , 46 -47 , 49 - 46 , 48 - 49 & 45 - 48
==>5 , -3 , -1 , 3, -1 & -3
If you add these numbers : 5 -3 -3 +3 -1 -3 = 0
So the numbers form a sequence. Here is another example with duplicates -
{49,45,48,47,47,46,50}
If you subtract adjacent elements and add them :
-4 + 3 -1 +0 -1 +4 -1 = 0
So these numbers form a sequence too.
To do this in O(1) space, have a variable which is initialized to 0. Keep adding the differences as you iterate through the array.]
eg-
int diff=0;
for(int i=1;i<n;i++){
diff+=A[i]-A[i-1]
}
diff+=A[0]-A[n]
This is true for any array regardless the array is a sequence or not.
(A[1] - A[0]) + (A[2] - A[1]) + ... + (A[n] - A[n - 1]) + (A[0] - A[n]) = (A[1] - A[1]) + (A[2] - A[2]) + ... + (-A[0] + A[0]) + (A[n] - A[n]) = 0.
This is true for any array regardless the array is a sequence or not.
(A[1] - A[0]) + (A[2] - A[1]) + ... + (A[n] - A[n - 1]) + (A[0] - A[n]) = (A[1] - A[1]) + (A[2] - A[2]) + ... + (-A[0] + A[0]) + (A[n] - A[n]) = 0.
This is true for any array regardless the array is a sequence or not.
(A[1] - A[0]) + (A[2] - A[1]) + ... + (A[n] - A[n - 1]) + (A[0] - A[n]) = (A[1] - A[1]) + (A[2] - A[2]) + ... + (-A[0] + A[0]) + (A[n] - A[n]) = 0.
This is true for any array regardless the array is a sequence or not.
(A[1] - A[0]) + (A[2] - A[1]) + ... + (A[n] - A[n - 1]) + (A[0] - A[n]) = (A[1] - A[1]) + (A[2] - A[2]) + ... + (-A[0] + A[0]) + (A[n] - A[n]) = 0.
public int getConsequetiveNumbers(int[] array)
{
int min, max;
min = max = array[0];
for(int i = 1; i < array.length; i++)
{
if(array[i] < min)
{
min= array[i];
}
if(array[i] > max)
{
max = array[i];
}
}
BitSet bitSet = new BitSet(max-min);
for(int i = 0; i < array.length; i++)
{
bitSet.set(array[i] - min, true);
}
int maxLength = 0, currentLength = 0;
for(int i = 0; i < bitSet.length(); i++)
{
if(bitSet.get(i))
{
currentLength++;
}
else
{
if(currentLength > maxLength)
{
maxLength = currentLength;
}
currentLength = 0;
}
}
return maxLength;
}
// 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();
}
}
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
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;
}
//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;
}
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
import java.util.HashSet;
public class Test
{
public static void main(String[] args)
{
int[] array = new int[] {5,7,1,2,3,4,8,9,10,12,13,16,18 };
findLongestSeq(array);
// Original
// ==================
// 5 7 1 2 3 4 8 9 10 12 13 16 18
//
// Longest Consecutive Seq
// ==================
// 1 2 3 4 5
}
public static void findLongestSeq(int[] array)
{
HashSet<Integer> set = new HashSet<Integer>();
//This takes O(n). Adding all element in array into set.
//Set doesn't allow duplicate element.
System.out.println("Original");
System.out.println("==================");
for(int element : array)
{
set.add(element);
System.out.print(element + " ");
}
System.out.println("\n");
int min = -1;
int max = -1;
int range = -1;
//This takes O(n). Iterate until every element is removed.
while(set.size() > 0)
{
//Pop one element.
int element = set.iterator().next();
set.remove(element);
int temp_min = element;
//Try to find the minimal consecutive number
while(set.contains(temp_min-1))
{
temp_min = temp_min -1;
set.remove(temp_min);
}
//Try to find the maximal consecutive number
int temp_max = element;
while(set.contains(temp_max+1))
{
temp_max= temp_max+1;
set.remove(temp_max);
}
//Check range
if(range < temp_max - temp_min)
{
min = temp_min;
max = temp_max;
range = temp_max - temp_min;
}
}
//Print result
System.out.println("Longest Consecutive Seq");
System.out.println("==================");
for(int i=min; i<= max; i++)
{
System.out.print(i + " ");
}
System.out.println();
//Since O(n) + O(n) = O(n). This algorithm runs in O(n).
//I utilized the characteristic of consecutive number with hashing.
}
}
The correct algorithm for a one-pass O(n) solution solution has already been posted a couple of times (for example see juando.martin), just posting the java implementation here.
The gist of the algorithm is to keep a hash map where the key is an integer value from the array, and the value indicates the min/max of the consecutive range that this integer is in. On reading each new value, check for +1/-1 neighbors, get the new min/max, and update the two ends as needed.
There are a couple comments that indicate that this is not O(n) because you need to update the hash map for all the intermediate values in the range as well. You DO NOT need to update the intermediate values. Assuming that the input array does not contain any repeated elements, the intermediate values will never come up as a neighbor for a new array value (since the +1/-1 neighbors have already occurred by definition), so they don't need to change. The only hash map elements you need to insert/update on every turn are the min/max values of the current range. Therefore the number of ops needed for each array iteration is a constant and it runs in O(n).
The implementation below just uses a 2 element array for tracking the min/max of each range, where range[0] is the min and range[1] is the max.
public static Integer[] findLongestConsecutive(Integer[] input) {
Map<Integer, Integer[]> ranges = new HashMap<Integer, Integer[]>(input.length);
int maxLength = 0;
Integer[] maxRange = null;
for (int element : input) {
Integer[] prevRange = ranges.get(element - 1);
Integer[] nextRange = ranges.get(element + 1);
int min = (prevRange == null) ? element : prevRange[0];
int max = (nextRange == null) ? element : nextRange[1];
if (prevRange != null) {
ranges.get(min)[1] = max;
}
if (nextRange != null) {
ranges.get(max)[0] = min;
}
if (prevRange == null || nextRange == null) {
ranges.put(element, new Integer[]{min, max});
}
if (max - min + 1 > maxLength) {
maxLength = max - min + 1;
maxRange = new Integer[]{min, max};
}
}
return maxRange;
}
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.
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)
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.
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 }
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.
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.
import java.util.HashSet;
public class LargestSeq {
static String largestSeq(int a[]){
String largestSeq = "";
HashSet<Integer> hash = new HashSet<Integer>();
for(int n : a){
hash.add(n);
}
for(int n : a){
StringBuffer sb = new StringBuffer(n+"");
int n1 = n+1;
int n2 = n-1;
while(hash.contains(n1)){
sb.append(n1);
hash.remove(n1);
n1++;
}
while(hash.contains(n2)){
sb.insert(0, n2);
hash.remove(n2);
n2--;
}
if(largestSeq.length() < sb.length()){
largestSeq = sb.toString();
}
}
return largestSeq;
}
public static void main(String args[]){
System.out.println(largestSeq(new int[] {1,3,5,7,9}));
}
}
In addition to the numerous hash table based approaches described in this problem comments, it seems the solution can also be expressed through using auxiliary Disjoint Set structure to perform the actual merge of the nodes in the node set. That is:
* Use hash table to store the nodes where each node contains information about its parent node in the disjoint set, as well as min and max value.
* When iterating over numbers, add a node for this number into the set if it is not there yet and join the node with x+1 and x-1 nodes.
* Once done, scan over the root nodes in the disjoint set forest and find the one with maximum set size.
All steps are amortized O(n).
Code:
# Given an array of random numbers. Find the longest consecutive sequence.
# For ex
# Array 100 3 200 1 2 4
# Ans 1 2 3 4
# Array 101 2 3 104 5 103 9 102
# Ans 101 102 103 104
#
# Can we do it in one go on array using extra space??
import random
data = [int(5000*random.random()) for i in xrange(1000000)]
class Node:
def __init__(self, num):
self.parent = None
self.rank = 0
self.set_size = 1
self.min_num = num
self.max_num = num
class DisjointSet:
def __init__(self):
self.nodes = {}
def add(self, num):
if num not in self.nodes:
self.nodes[num] = Node(num)
def find(self, num, add=False):
x = self.nodes.get(num)
if x is None:
return None
if x.parent is None:
return num
else:
return self.find(x.parent)
def join(self, num1, num2):
p1 = self.find(num1)
if p1 is None: return
p2 = self.find(num2)
if p2 is None: return
if p1 != p2:
# different sets - join now
n1 = self.nodes[p1]
n2 = self.nodes[p2]
assert n1.parent == None
assert n2.parent == None
if n1.rank == n2.rank:
n1.rank += 1
if n1.rank < n2.rank:
(p1, p2) = (p2, p1)
(n1, n2) = (n2, n1)
n2.parent = p1
n1.set_size += n2.set_size
n1.min_num = min(n1.min_num, n2.min_num)
n1.max_num = max(n1.max_num, n2.max_num)
#data = [6, 100, 3,200,1,2,4]
ds = DisjointSet()
for i in data:
ds.add(i)
ds.join(i, i+1)
ds.join(i, i-1)
max_size = 0
max_start_num = None
for i in ds.nodes.values():
size = i.max_num - i.min_num + 1
if size > max_size:
max_size = size
max_start_num = i.min_num
print "start=%d, finish=%d" % (max_start_num, max_start_num+max_size-1)
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);
}
}
Slightly modified version.
1. Find min and max
2. if max - min + 1 > length of arry => return false
3. Place each integer in the right position index = value - min
4. Loop through array up to val == max and verify that each value in its right position.
public class FindIfSubsequenceWithDupicates {
public static void main(String[] args) {
int[] arr = {45,50,47,46,49,48,48,48,48,46,46,46,46,51};
System.out.println(isSequence(arr));
}
private static boolean isSequence(int[] arr) {
if (arr == null || arr.length == 0) return false;
if (arr.length == 1) return true;
int[] minAndMax = findMinAndMax(arr);
int min = minAndMax[0];
int max = minAndMax[1];
if (max - min + 1 > arr.length) return false;
for (int i = 0; i < arr.length; i++) {
int val = arr[i];
int valIndex;
int currenIndex = i;
while ( (valIndex = val - min) != currenIndex) {
int tmp = arr[valIndex];
arr[valIndex] = val;
val = tmp;
currenIndex = valIndex;
}
}
//now every element up to max should be consecutive
for (int i = 0; i < arr.length; i++) {
int val = arr[i];
if (i + min > max) break;
if (i + min != val) return false;
}
return true;
}
private static int[] findMinAndMax(int[] arr) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i: arr) {
if (i > max) max = i;
if (i < min) min = i;
}
return new int[]{min, max};
}
}
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";
}
#include <iostream>
#define MAX 100
using namespace std;
void getLgst(int * arr, int n){
int i = 0;
int mark[MAX] = {0};
int max = 0, max_temp = 0, start = 0, start_temp=0, end = 0;
while (i<n) mark[*(arr+i++)] = 1;
i = 0;
while (i<MAX){
if (mark[i] and mark[i+1])
max_temp += i++;
else if (mark[i] and !mark[i+1]){
if(max<max_temp+i){
max = max_temp+i;
end = i++;
start = start_temp;
}
else
i++;
}
else{
max_temp = 0;
i++;
if(mark[i])
start_temp = i;
}
}
cout<<start << " "<< end<<" "<<max<<endl;
}
int main()
{
cout << "Hello World" << endl;
int array[7] = {1,6,10,4,7,9,5};
getLgst(array, 7);
return 0;
}
Space can me further limited by using map.
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);
}
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;
}
}
Python O(n) time using a dictionary for constant time access to numbers.
mapping = {}
max_sequence = (None, 0)
arr = [1,6,10,4,7,9,5]
# throw into map n time
for i in arr:
mapping[i] = [i]
# go through keys 2n time
for k in mapping.keys():
if mapping[k] == None:
continue
n = 1
while mapping.get(k+n) != None:
mapping[k] = mapping[k] + mapping[k+n]
n += 1
while n > 0:
mapping[k+n] = None
n -= 1
# get sequence with max length n time
for k in mapping:
if mapping[k] == None:
continue
seq_len = len(mapping[k])
if seq_len > max_sequence[1]:
max_sequence = (k, seq_len)
#print max_sequence
print mapping[max_sequence[0]]
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class StringSubset {
public static void main(String[] args) {
Integer[] result = find_subset(new int[] { 1, 6, 10, 4, 7, 9, 5 });
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
public static Integer[] find_subset(int[] arr) {
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], new ArrayList<Integer>());
}
for (Entry<Integer, List<Integer>> entry : map.entrySet()) {
List<Integer> previousValue = map.get(entry.getKey() - 1);
int previousKey = entry.getKey() - 1;
if (previousValue != null) {
if (previousValue.size() > 0) {
map.put(entry.getKey(), previousValue);
} else if (previousValue.size() == 0) {
List<Integer> list = new ArrayList<Integer>();
list.add(previousKey);
list.add(entry.getKey());
map.put(entry.getKey(), list);
}
}
List<Integer> nextValue = map.get(entry.getKey() + 1);
int nextKey = entry.getKey() + 1;
if (nextValue != null) {
if (nextValue.size() > 0) {
map.put(entry.getKey(), nextValue);
} else if (nextValue.size() == 0) {
List<Integer> list = entry.getValue();
if (list.size() == 0) {
list.add(entry.getKey());
}
list.add(nextKey);
map.put(entry.getKey(), list);
}
}
}
List<Integer> maxArray = new ArrayList<>();
for (List<Integer> list : map.values()) {
if (list.size() > maxArray.size()) {
maxArray = list;
}
}
return maxArray.toArray(new Integer[maxArray.size()]);
}
}
int[] findLongestCommonSubsequense(int[] a){
Set<Integer> seen = new HashSet<Integer>();
Map<Integer, Integer> intervals = new HashMap<Integer, Integer>();
for(int j: a){
if(seen.contains(j)){
continue;
}
seen.add(j);
Int lo=j; hi=j;
for(int i=0; i<a.length; i++){
if(intervals.contains(i+1)){
hi = intervals.remove(i+1);
}
if(intervals.contains(i-1)){
lo = intervals.remove(i-1);
}
intervals.put(hi, lo);
intervals.put(lo,hi);
}
}
int hi=0, lo=0;
for(Entry<Integer, Integer> pair : intervals.entrySet()){
if(hi - lo < pair.getKey() - pair.getValue()){
lo = pair.getValue();
hi = pair.getPair();
}
}
Int ret[] = new int[hi-lo+1];
for(int i=0; i<ret.length; i++){
ret[i] = i + lo;
}
return ret;
}
int[] findLongestCommonSubsequense(int[] a){
Set<Integer> seen = new HashSet<Integer>();
Map<Integer, Integer> intervals = new HashMap<Integer, Integer>();
for(int j: a){
if(seen.contains(j)){
continue;
}
seen.add(j);
Int lo=j; hi=j;
for(int i=0; i<a.length; i++){
if(intervals.contains(i+1)){
hi = intervals.remove(i+1);
}
if(intervals.contains(i-1)){
lo = intervals.remove(i-1);
}
intervals.put(hi, lo);
intervals.put(lo,hi);
}
}
int hi=0, lo=0;
for(Entry<Integer, Integer> pair : intervals.entrySet()){
if(hi - lo < pair.getKey() - pair.getValue()){
lo = pair.getValue();
hi = pair.getPair();
}
}
Int ret[] = new int[hi-lo+1];
for(int i=0; i<ret.length; i++){
ret[i] = i + lo;
}
return ret;
}
On the one hand, using a hash table, we can dfs/bfs and find connected components on the path graph (add an edge for each adjacent elements) to solve the problem in Θ(n) expected time.
On the other hand, on the algebraic decision tree model, your problem cannot be solved in O(n) time. To see this, take an instance of the set disjointness problem (A, B) and transform it to [3A1, ..., 3An, 3B1 + 1, ..., 3Bn + 1]. Because the set disjointness problem has lower bound [1], your problem has the same bound.
[1] Ben-Or, Michael. Lower bounds for algebraic computation trees.
#include <stdio.h>
int largest_subset(int * a,int len)
{
int h[10000];
int i,max,curr_max;
for(i=0;i<len;i++)
{
h[a[i]]=1;
}
max = 0;
i = 0;
while(i < 10000)
{
if(h[i] == 1)
{
curr_max = 0;
while(h[i] == 1)
{
curr_max++;
i++;
}
if(curr_max > max)
max = curr_max;
}
i++;
}
return max;
}
int main()
{
int a[10] = {11,4,3,2,1,7,10,8,9};
int i = 9;
int j;
j = largest_subset(a,i);
printf("Largest subset = %d",j);
return 0;
}
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];
}
let say the array is a[]= 5 7 1 2 3 4 8 9 10 12 13 16 18
algo:
1) declare 3 set of variables int cnt1,cnt2,index[2],val[2]
2) start traversing the array and update the initial array ..--->>follow step 3
3)while traversing the array starting from index 0..store the diff of a[i+1] - a[i] in a[i]
so now the array becomes...-->> arr[] = 2 -6 1 1 1 4 1 1 2 1 3 2 18(leave the last number as it is (18) in here..
4) while traversing...if we get two values same like in here 1 and 1 a[i] == a[i-1]
then store the index of a[i-1] in index[0] and value of a[i-1] in val[0] and increase the cnt1 from 0 to 1..and increase it..unless we get any diff in values of a[i] and a[i-1]
so in here cnt1 will have 3 and val[0]=1 and index[0]=2
from now.on follow step 4 and use cnt2 instead of cnt1 to count the sequence and compare value of cnt2 with cnt1. if cnt2> cnt1 replace value of ant1 with cnt2 and arr[0] with arr[1] and index[0] with index[1] and..initialise cnt2,index[1] and val[1] to 0 each.
so go on doing this..and at last in cnt 1 we will be having the cnt of the longest sequence and in index[0] the index from which the sequence start and at val[0] ..the starting value of this sequence..
so we now know the starting value ..the diff and the index..and the count of such sequence.... now we can print the sequence..
<pre lang="java" line="1" title="CodeMonkey91450" class="run-this">import java.util.HashMap;
import java.util.Map;
class Main {
public static void printLongestSeq(Integer[] inp)
{
//Check if input is empty or null
if ((inp == null) || (inp.length == 0))
{
return;
}
Map<Integer, Integer> lens = new HashMap<Integer, Integer>();
Integer resElem; //Result element
Integer resElemLen; //Result element len
resElem = inp[0]; //By default take first element
resElemLen = 1; //By default set max len 1
for (Integer currElemKey : inp)
{
//For current element in array find longest increasing sequence
//by jumping in hash table
Integer nextElemKey = currElemKey+1;
//In each key we are storing element of input array
//In each value we are storing longest increasing seq starting from integer (key)
Integer nextElemLen = lens.get(nextElemKey);
Integer totalLenToAdd = 0;
while (nextElemLen != null)
{
//Add total len of subseqences
totalLenToAdd += nextElemLen;
if (nextElemLen > 1)
{
//If nextElemLen > 1 then subsequence starting with this element
//is already calculated so exit from this loop
break;
}
else
{
//We have found increasing sequence
//just update total len
nextElemKey++;
nextElemLen = lens.get(nextElemKey);
}
}
//If current element is not in the hash put it in hash table along with
//total length of increasing elements
Integer currElemLen = lens.get(currElemKey);
if (currElemLen == null)
{
currElemLen = 1;
}
currElemLen += totalLenToAdd;
lens.put(currElemKey, currElemLen);
if (currElemLen > resElemLen)
{
resElem = currElemKey;
resElemLen = currElemLen;
}
//If current element is in the middle of increasing sequence
//then update previous elements of this sequence
//by adding +currElemLen
Integer prevElemKey = currElemKey - 1;
Integer prevElemLen = lens.get(prevElemKey);
while ( prevElemLen != null )
{
lens.put(prevElemKey, prevElemLen + currElemLen);
if ((prevElemLen + currElemLen) > resElemLen)
{
resElem = prevElemKey;
resElemLen = prevElemLen + currElemLen;
}
prevElemKey--;
prevElemLen = lens.get(prevElemKey);
}
}
//Dump the sequence starting from element resElem with
//total resElemLen elements count
for (int i = 0; i < resElemLen; i++)
{
Integer currElement = resElem + i;
System.out.print(currElement + " ");
}
System.out.println();
}
public static void main(String[] args)
{
Integer[] test1 = new Integer[]{100, 3, 200, 1, 2, 4};
printLongestSeq(test1);
Integer[] test2 = new Integer[]{101, 2, 3, 104, 5, 103, 9, 102};
printLongestSeq(test2);
Integer[] test3 = new Integer[]{5, 4, 3, 2, 1};
printLongestSeq(test3);
}
}
</pre><pre title="CodeMonkey91450" input="yes">
</pre>
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
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).
O(n) time and space
- Anonymous October 26, 2011In Python, dict is a hash with O(1) time to retrieve an item.