CareerCup

changed the question..

This is nice solution but you are using space for stack as recursive calls. Below program is written as iterative approach.

public int sumFibo(int n){
int n0=0;
int n1=1;
int n2;
int sum=1;
int i=0;
while(i<=n){

n2=n0+n1;
sum+=n2;
n0=n1;
n1=n2;
i++;
}

return sum;

}

How you gonna check A or B on same side?.. since it doesn't have data to compare.

int getHeight(Node root){

if(root==null) return 0;

int L=0;
int R=0;

if(root.L!=null) L=1+getHeight(root.L);

if(root.R!=null) R=1+getHeight(root.R);

return max(L,R);
}

Thats nice solution, But there are many case where this approach can break your solution.
1> if 1st element is 0 than the whole multiplication will be zero. Also this apply to the last element.
2> Your multiplication can overflow if large input is provided. Large in terms of array size or element it self: In this case you have to use BigInteger in java

oops! forgot to return prev Node at the end of the code

You are right . This method is not thread safe, since two thread can pass same object and do the changes which will produce unwanted result.

I would use Max heap data structure key for this data structure would be Balance of the Person
So when max balance is query is requested you will get at O(1). But when the persons balances changes based on the heap DS it will chnage its position in the tree which will be O(lgn)..

So building heap will be O(n)..I would represent class:

class Person{
String name;
String location;
float balance;
int day;

float credit(float amount);
boolean debit(float amount);
int getDay();
String getName();
String getLocation();
}

@ Miguel Oliveira for your 4th point its actually O(n+k) space where k is range

Solution:-
-Not problem
-Its ok
-Thats fine
-It's okay.
-Don't worry about it.
-Not a big deal.
-Don't be

Last but not least :- "You better be"
.. :-)

HashSet<String> permutaion(String s){
	  HashSet<String> set=new HashSet<String>();
	  permutation(" ", s,set);

  } 

 void permutation(String prefix,String s,HashSet<String> set){
	  
	  if(s.length()==0){
		  set.add(prefix);
		  System.out.println( prefix);
	  }
	  
	  for(int i=0;i<s.length();i++){
		  
		  permutation(prefix+s.charAt(i),s.substring(0, i)+s.substring(i+1, s.length()),set);
		  
	  }
  }

Unique words will be = n!/ (number of Repeated Characters);

How is it O(n) for the space ? since you are not using any extra space other than input array.

Your solution works for the common friends list not the connected friend list. This is the problem of graph. Using shortest path Algorithm can be solved this problem.

For eg: Suppose Alphabets represent person.
|A| - F-G-H-U-I
|U| - W-G-H-N-J-K-A
|k| - I-A-J-P-B-U
|P| - Q-G-J-K-B
|B| - K-O-L-M-Y


Answer should be U,K
Since A-U-K-B

1. Do Binary Search on that input number -- O(lgn)
2. find successor than that's the least difference and if successor is not found than find predecessor - O(lgn)

because least difference has to be elements besides it. --- O(1)

Total - O(lgn)

static char printUniquechar(char a[]){
		char unique='\u0000';
		int count=0,i=0;
		while(i<a.length){
			if(unique!=a[i]){
				if(count==1)break;
				unique=a[i];
				count=0;
				count++;
			}else{
				  count++;	
			}
		i++;
		}
		
		if(count!=1) 
			{unique='\u0000';}
		
		return unique;
	}
	
	
}

Time=O(N)

All operations on Hashtable or Hashmap are O(1) assuming the uniform distribution of the key in the table and avoiding the collision of the key. Avoiding collision and uniform distribution is all depends how hash function is well implemented which is very critical implementation. But the aim of this data structure is providing operations at O(1).
So if the hash function is really bad than the worst case will be O(N).

static void printUniqueList(int list1[],int list2[]){

int i=0,j=0;

while(i<list1.length || j<list2.length  )
{
		if(i<list1.length){
			
			if(list1[i]<list2[j]){
				System.out.println( list1[i++]);
				}else if(list1[i]!=list2[j]){
				System.out.println( list2[j++]);	
			}else{
				i++;
				j++;
			}
		}else{
		System.out.println( list2[j++]);
		}

	
 }
}
	
}

}

Time= O(N)
Space= O(1)

int findFirstOne(int array[]){
	  
	  int length=array.length;
	  
	  int head=0,tail=length-1;
	  
	  while(head<tail){
		  
		  int middle=head+(tail-head)/2;
		  
		  if(array[middle]==0)
		  head=middle+1;
		  else 
	      tail=middle;
		  	  
	  }
	  
	  if(head==tail && array[head]==1)
		return head;  
	  
	  
	  
	  
	  return -1;
  }
  
  
}

int a1[]={0,0,0,0,0,0,0,0,0,0,0};
		int a2[]={0,0,1,1,1,1,1,1};
		int a3[]={1,1,1,1,1,1,1,1,1};
		int a4[]={0,0,0,0,0,0,0,0,0,0,1};
		
		System.out.println(" a1 ="+findFirstOne(a1)+" a2 ="+findFirstOne(a2)+" a3="+findFirstOne(a3)+" a4= "+findFirstOne(a4));

OUTPUT------------------------------------
a1 = -1 a2 =2 a3 =0 a4= 10


time complexity = O(lgn)

correction in previous code int n=1;