CareerCup

Look at connected component labeling problem
en.wikipedia.org/wiki/Connected-component_labeling

I did, this was long time ago..
so deleted my post

subsequences if the array is sorted??
if so, why not 2 4 5, 2 4 6....etc..??
if no, then why is 1 2 6 an answer?

Yep, this is good

I believe internally the compiler would still be passing n references for the complete recursion cycle. anyways, the solution by S is the best one I think.

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

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

Look at Animation of NN searching with a KD Tree in 2D on wiki
that might help visualize. thanks

If you unroll the recursion what's happening is the algo is creating a 'n' additional pointers by passing head->link.
so basically all the algo is doing is constructing an array of additional pointers to each element and is visiting them in the reverse order and simultaneously comparing by to element at 'h1' in the forward order.
i.e. using an additional space of O(n) {array of n pointers}
Also a small suggestion on the terminology, people usually refer to next element as "head->next" rather than "head->link"
thanks

ya, as @gekko says; thats not a good answer.

Here's a O(n) without any extra space and without multiplication or addition (because factorial requires special datatype/datastructure)

// since we know there are n numbers in an array of size n all we want is to swap the numbers to their corresponding positions i.e. move '1' to 0th position, move '2' to 1st position ...etc.
if the number already exists in its position then its a duplicate and we set it to (n+1) or -1 i.e. something we can identify. Basically 2 traversals will give u the missing spot.

-> for(i=0;i<n;++i){
       if(array[i]<0) //is less than zero only when we set the duplicate to -1, look below
            continue;
       if array[i]==i+1   //in the right position
            continue;
       else{
            if(array[i]==array[array[i]-1]) //then its a duplicate, set it to -1
                 array[i] = -1
            else
                 swap(array[i],array[array[i]-1]) 
           }
    }
    //by the end of the above loop we have all elements in their corresponding positions and -1 in the place of the missing number
-> traverse the array and print out the position+1 of the the element with value == -1
//complexity analysis: no matter what the for loop will run 'n' times --> (n)
//traversal for finding the missing spot --> (n)
total complexity: O(n)

@Sathya, yep as gekko pointed out this solution can have cycles and one way to avoid cycles is by using extra space. This question is a duplicate and I posted a similar solution which had the same issue, can't find the duplicate question using CC's search

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.

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)

find 1st minimum O(n)
find 2nd minimum O(n)
total = O(n)
you could also do these together in one loop which is again O(2n) ==> O(n)
space = O(1)
thanks.

what kind of tree is it? and how is the tree stored?

well.. if we modify the binary search algo we can make it O(logn) i.e. the worst case happens only when num1 is repeated till the starting and num2 is repeated till the end.
so once we find num1 using binary search we can still do binary search to the left of num1 to find the first occurence of num1, which is again log(n) complexity
so on the whole the worst complextiy would be O(2(logn+logn)) ==> O(logn). Ex:

//The worst case scenario is as shown below
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
num1 = 4, num2 = 8
First binary search and find num1 at array[15]
Second binary search to left the of num1 to find first occurrence of num1, we find num1 at positions  7, 3, 1, 0

so two binary searches to find the first occurrence of num1, similarly for num2. 
And we get O(4logn) == O(logn)

If we do a linear search most cases tend to O(n).

Feel free to make suggestions. Thanks

Given num1&num2 , num1<num2. Array A
Do a binary search for num1
If found then move towards A[0] until A[i]==num1 because there can be dups
Else get lower bound (STL has lower bound for binary search)

Repeat for num2 
Return values between these indices

Complexity worst case O(n) best case O(logn)
Worst case example : num1: 4 num2: 8
Array: 4,4,4,4,4,4,4,4,4,4,4,4,8,8,8,8,8,8,8,8,8,8,8

@Kannan: I prefer your solution but interviewers wont accept it because the solution has to be successful in all cases when compared to a worser complexity algorithm. Sort and compare for this problem will work for a case like below
a1 = [ (2^128−1) , 2^127 , 4, 1, 2, 10]
a2 = [ 2 , 4, 1, 10, (2^128−1), (2^128−1)]
If you sort both and compare then it would definitely work.
But your code would fail. The algo you wrote is a really good approach. But as blue_skin points out, there are constraints to your solution as >0 and datatype range
Thanks

@shashi: Well, merge sort can be done inplace but complicated. thomas baudel has a variant of inplace merge sort.
But if there's a simpler inplace sort for merging k sorted arrays then please suggest. Thanks

I think you got confused.
There are n/k sorted arrays of length k. (you are thinking the other way i.e. there are k arrays of length n/k. thats wrong understanding)
So merging two arrays of length k is O(k), it's basically merge sort. For example, in merge sort you start of with k=1, so complexity is O(n/1 log (n/1)) ==> O(n logn). Thanks.

I'll try a heuristic,
the middle boxes are surrounded with more number boxes, our goal is to not to have neighbors. so lets take a number from 1 to 8 that has less neighbors which is either 1 or 8.
place it in the middle 4 boxes then alternatively place continuous elements

- 1 - -        - 1 - 2            - 1 - 2          - 1 - 2
- - - -        - - - -            - 3 - -          - 3 - 4

and then

5 1 - 2        5 1 6 2            5 1 6 2          5 1 6 2        
- 3 - 4        - 3 - 4            7 3 - 4          7 3 8 4

you could try selecting different box for 1 as below:

- - - -        - - - -            - - 3 -          4 - 3 -
- - 1 -        2 - 1 -            2 - 1 -          2 - 1 -

and then

4 - 3 -        4 - 3 -            4 - 3 7          4 8 3 7 
2 - 1 5        2 6 1 5            2 6 1 5          2 6 1 5

feel free to suggest advanced heuristics. thanks

so The question is find and delete duplicates in an array of size N with a max value N in time complexity O(N), and space O(1).
I wrote the right solution, there's no 'n'. There's only N which is the size of the array and max of the array.
damn it.. someone got me confused somewhere

buddy..you are not getting the point. the point is not about n or N. The point is whatever may be the size of array, the algorithm doesn't use any extra space.
For example: consider n = n1, if the program takes n1+k bytes of memory. then for n = n2, the program takes n2+k bytes of memory, the algorithm takes k bytes of memory irrespective of value of n. so the space complexity = O(k) ==> O(1). I hope this helps

Hash tables have high insertion complexity but other operations are constant time depending on the hash function. hashmaps or unordered are implemented using this.
RBTrees is the widely used balanced binary tree which has logn for all operations. and not so easy to implement. Maps are implemented using this structure
So it depends on the application, if you know approx. what the size of your data would be then hashmaps are the best if not you need to choose.
An easier alternative to RBTrees are skip lists which are much easier to implement but same performance.
anyways, please reply your perspective on this problem. Thanks

From a perspective this is a sorting problem and whose solution is nlogn
5log5 = 7 or 8, it depends on the input order. correct me if wrong. Thanks

A hash table is an associative container that maps a key to a value. a key can be a string or anything that has a operator==() and hash() function defined.
In addition, to ensure maximum performance, the hash function should be designed in such a way that if x != y
Very useful when insertion is done once and primarily used for searching using a key.

For implementing a hash table, things to keep in mind:
Choosing a hash function.
Data structure which can dynamically resize, [vectors or array lists]
Taking care of collisions

A possible solution but maybe not the best would be using a hashmap.
Time: O(n)
Space: O(n)
if only computational complexity is important then this would be the best. Thanks

what??/ how ??

yep.. as Anon pointed out, the question is incomplete without the measurement mechanism,
if measured using a balance i.e. comparison of weights then it would take lesser measurements in some cases
if measured using a digital scale then its different again.
Thanks

ashpiy: thats not totally true. I changed the solution a little bit but anyways, as Anon commmented, the problem is given 10 coin stacks, 9 of them are 100gms and 1 is 90 gms,
if stack 6 is 90gms then (5500-5440)/(100-90) = 6
if stack 1 is 90gms then (5500-5490)/(100-90) = 1
thanks

Sieve of eratosthenes is a really simple implementation. A person asking this question should be aware of this solution. i explained this in my interview and the interview got it right away because it doesn't make sense if you dont know the optimal solutions

yep.. I gave the same solution today. One is a fast pointer and the other is a slow one

2. Take 1 coin from the first, 2 from second, 3 from third..., and weigh them all together
if total weight = x grams, then (5500-x)/10 is the stack number.
All assuming a digital scale. If we have a weighing balance then I believe its much easier problem

1. Reverse

//!Function reverses an input list
void reverseList(Node*& head){
	Node* curr = head;
	Node* nxt  = head->next;
	curr->next = NULL;
	while(true){
			head	   = nxt;
			if(head->next==NULL){
				head->next = curr;
				break;
			}
			nxt	   = nxt->next;
			head->next = curr;
			curr	   = head;
	}
}

2. Check if the current value is less for every node and insert

/*Solution Code to algorithm suggested by lanse.cse
		1. reverse the lists. 
		2. add them digit by digit and construct the result list. 
		3. reverse the result list.
	NOTE: This code demonstrates the solution. The code will fail for invalid or no input and maybe other cases. Output for the following code : 9,1,3,1,3,8
*/
#include <iostream>
using namespace std;
//! Node to store digits
struct Node{
	short digit;	//doesn't make a difference if I use short or int
	Node* next;
};
//!Function reverses an input list
void reverseList(Node*& head){
	Node* curr = head;
	Node* nxt  = head->next;
	curr->next = NULL;
	while(true){
			head	   = nxt;
			if(head->next==NULL){
				head->next = curr;
				break;
			}
			nxt	   = nxt->next;
			head->next = curr;
			curr	   = head;
	}
}
//! Function to compute the sum of two input lists. Complexity: O(m+n), sizes of lists m,n
void sumOfLists(Node*& list1, Node*& list2, Node*& result){
	// Reverse lists: Time: O( m + n). operating on input lists to save space complexity
	reverseList(list1);
	reverseList(list2);
	Node* ptr;
	ptr = new Node();
	result = ptr;
	int n1=0,n2=0,sum=0,carry=0;
	bool n1flag=true,n2flag=true;
	while(n1flag || n2flag){
		n1= n1flag?list1->digit:0;
		n2 = n2flag?list2->digit:0;
		sum = n1+n2+carry;
		carry = (sum>=10)?1:0;
		ptr->digit = (sum-10*carry);
		if(n1flag)
			if(list1->next==NULL)
				n1flag = false;
			else
				list1 = list1->next;
 		if(n2flag)
			if(list2->next==NULL)
		 		n2flag = false;
			else
				list2 = list2->next;
		if(n1flag || n2flag){
			ptr->next = new Node();
			ptr = ptr->next;
		}else
			ptr->next = NULL;
	}
	reverseList(result);
}
void printListValues(Node*& list){
	Node* ptr=list;
	do{
		cout<<ptr->digit<<",";
		ptr = ptr->next;
	}while(ptr->next!=NULL);
	cout<<ptr->digit<<endl;
}
int main(){
	
	//construct two lists, replace the below digits to test your values
	int myNum1[] = {9,1,2,3,2,9};//First list 912329,
	int myNum2[] = {0,8,0,9};  //second list 0809
	Node *newNd1, *num1, *num2, *result;
	newNd1=new Node;num1 = newNd1;
	int sz = sizeof(myNum1) / sizeof(int);
	for(int i=0;i<sz;++i){
		newNd1->next = (i==sz-1)?NULL:(new Node);
		newNd1->digit = myNum1[i];
		newNd1=newNd1->next;
	}
	newNd1 = new Node;num2 = newNd1;
	sz = sizeof(myNum2) / sizeof(int);
	for(int i=0;i<sz;++i){
		newNd1->digit = myNum2[i];
		newNd1->next = (i==sz-1)?NULL:(new Node);
		newNd1=newNd1->next;
	}
	//Find sum
	sumOfLists(num1,num2,result);	//. Result should be 913138
 	printListValues(result);
}

Code based on comment from Anonymous' comment 
//dp[i][j] = max(dp[i-1][j],dp[i][j-1])+a[i][j]; 
/*	//! Complexity for a nxn matrix is O(nxn) i.e. Linear (since nxn elements)
*/
#include <iostream>
#include <vector>
using namespace std;
int main(){
	int arr[4][4] =
              {  { 1,7,5,2 },
                 { 5,12,3,6 },
                 { 100,9,23,16 },
                 { 16,4,5,9 },
              };
	int n=4;
	vector<vector<int> > maxRoute(n,vector<int> (n,0)); //initialize vector	
	//dp[i][j] = max(dp[i-1][j],dp[i][j-1])+a[i][j]; //Dynamic programming //from Anonymous
	for(int i=0;i<n;++i){ //move right
		for(int j=0;j<n;++j){ //move down
			if(i==0 && j==0)
				maxRoute[i][j] = arr[i][j];
			else if(i==0 && j!=0)
				maxRoute[i][j] = arr[i][j]+maxRoute[i][j-1];
			else if(i!=0 && j==0)
				maxRoute[i][j] = arr[i][j]+maxRoute[i-1][j];
			else
				maxRoute[i][j] = max(maxRoute[i-1][j],maxRoute[i][j-1])+arr[i][j];
		}
	}
	cout<<"Max grass ::"<<maxRoute[n-1][n-1]<<endl;
}

please suggest if any thing's wrong,Thanks.

Okay. so my bad.. i was assuming a binary matrix, thought the goat traverses only connected components in a binary matrix. Thanks Ankur

I've edited the comment to change complexity analysis, it didnt change. Complexity would be
==> O(n/k * (k+log(n/k) ) )
Best case would be O(n/k * log(n/k))

Hey, just saw your comment.
Ya. It would make a difference. If the length of sequences are 'k' then there are n/k subsets which monotonically increase and then decrease. So once we find where the shift happens for a subset, now we can split this into two sorted arrays and merge. total: operations for every subset would be 2k (worst case)
In this way, we get all n/k subsets sorted in (n/k)*2k => 2n operations, now we merge n/k sorted arrays which should take (n/k)log(n/k). So total complexity would be O(2n + (n/k)log(n/k))
==> O(n/k * (2k+log(n/k) ) )
Best case would be O(n/k * log(n/k))
All of this with the condition that every k subset increases to a point and then decrease once. (Ex: the whole array can be a sine curve)
Correct me if am wrong. Thanks

@extinct: I was just lazy to write the deletion code, but anyways, added the code for moving duplicates to the end of the array, now, you can delete or truncate or .... anything.
again the complexity remains the same O(n) or O(4n), space complexity O(1).

papaya says, "the problem says numbers are in range of 1...N, but not necessary contain all number from 1 to N."
Yes, I know that. I am not assuming that.
what am saying is if there are numbers between 1 to N in an array and complexity is O(N) that means the size of array cannot be greater than N and no element is greater than N, right?
Now, if no duplicates exist then the array has to be of size N right?
Now if duplicates exist then after moving the elements to their correct positions you should be left with duplicates. If you try the following array
{3,3,3,3,3,2,2,2,2,2,2,4};
The algorithm will give,
Final Array :15,2,3,4,15,15,14,14,14,14,14,15,
Duplicates are :: 3,3,3,2,2,2,2,2,3,
Correct me if am wrong.

I have a feeling that the question is not complete. because here's a bruteforce O(n) solution.

Assume 'n' elements in each linked list, 
  construct an array from each linked list, 
  start from the end of the arrays and keep adding elements and storing into another array with carry. The max size of the second array can be 2n.
  Build another linked list from the result array.
  Time complexity: O(n + n + 2n + 2n) => O(6n) => O(n)
  Space complexity: O(n + n + 2n) => O(4n) => O(n)

so what are we trying to optimize? space , time ? or something else?

To make it n^2, you have to construct hashfunction that can compute a unique index for every unique input string. And then you can do direct indexing because every unique string would have a unique index in the hashmap. which should give you O(1) for finding/inserting in a hashmap

Not n^3 but O(N^2*(logN))
Explanation:

The elements in a map are sorted and any operation for map takes logarithmic time. 
Construction of Map:
   Find operation takes logn because there are n strings.
   But for finding, we need to match strings so matching operation takes n (because n elements in each row) total complexity of find operation = nlogn and for inserting = nlogn.
   The first for loop runs n times and its inner loop runs n times, then find and insertion takes 2nlogn
   total computations for constructing map=> n * (n + 2nlogn)

Searching if column matches any key in the map:
   The same way computations => n * (n + nlogn)

Total complexity => O( (n*(n+2nlogn)) + (n*(n+nlogn)) ==> O(2n^2 + 3n^2(logn)) ==> O(n^2*(logn))

Pseudo Code:
  Create a map that takes a string as key and vector<int> as data

  For every row construct a string using the values. (for ex: "4:5:10:9:2:"
       Check if your map already contains the key, 
            if yes then retrieve and add the row index
            else insert a new item with this key and data as rowIndex
 For every column construct a string using the values. 
       Check if your map contains the key
            if yes then this column matches with all the indices in the 'data' for this key
            else no rows exist that are same as this column

///Complexity: O(N^2 + N^2) => O(N^2)

#include <map>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
int main()
{
  map<string, vector<int> > valStrings;
  map<string,vector<int> >::iterator it;
  string str;
  int n = 4;
  int matrix[][4] = {   {2,2,2,15},
			{2,2,5,5},
			{15,5,2,2},
			{15,5,2,2}};

	vector<int> indxs;
	for(int i=0;i<n;++i)	//for every row
	{
		char bfr[4];
		str="";
		for(int j=0;j<n;++j){
			sprintf(bfr,"%d",matrix[i][j]);
			str.append(bfr);str.append(":");
		}
		it=valStrings.find(str);
		if(it!=valStrings.end())
			indxs = (*it).second;
		indxs.push_back(i);
		valStrings[str] = indxs;
		indxs.clear();
	}
	for(int i=0;i<n;++i)	//for every column find if there's a key already inserted
	{
		char bfr[4];
		str="";
		for(int j=0;j<n;++j){
			sprintf(bfr,"%d",matrix[j][i]);
			str.append(bfr);str.append(":");
		}
		it=valStrings.find(str);
		if(it!=valStrings.end()){ //if key already exists then obtain row values
			cout<<endl<<"Column "<<i<<" matches row(s) : ";
			indxs = (*it).second;
			for(int k=0;k<indxs.size();++k)
				cout<<indxs[k]<<",";
			indxs.clear();
		}
	}
}
//Column 1 matches row(s) : 1,
//Column 3 matches row(s) : 2,3,

got me .. :D
I didnt think about same values...

my bad... I didnt rebuild before running.. sorry :D
it is 1

Actually, it doesn't make sense. any random set of numbers can be said as increasing and decreasing. For example, I just pressed numbers randomly on the keyboard and,
2 8 0 5 4 2 3 8 0 4 8
If you observe then, it increases to 8 then decreases to 0 then increases to 5 then decreases to 2..so on
any set of random numbers will have the behavior described in this problem. So its just a sort problem?

wrong