CareerCup

1 is the root node. Not able to get it in the right place in the question. Basically, 5 covers 1 in the bottom view.

When a customer selects for a delivery to be made-

1) They should be assigned a locker number closest to his zip code.
2) They should be allowed to cancel a locker delivery until the order has been shipped.
3) You can assume that you have several concurrent requests coming in. When I asked for the hourly/monthly requests we should expectedly be processing, I was told to assume it is tight but not extraordinary. However, the design should allow to scale up.
4) Service should be highly available.

I was also asked to think about how an update would be made to make a locker available when an order is picked up.

A fairly simple question. I proposed 3 approaches:

1) Brute Force: For each element in the array search all the remaining elements for (Sum - the chosen element). O(N^2) is the Time Complexity.

2) (a) Sort the array and use 2 references one from the start and the other from the end.
(b) If sum of both the referenced element is less than given sum then increment the position of the smaller reference.
(c) If sum of both the referenced element is greater than given sum then decrement the position of the larger reference.
(d) Repeat (b) & (c) until both references cross each other.
O(N*Log N) - For Sorting + O(N) searching with references = Total (N*Log N)

3) Use a HashTable (assume a HashMap). In the first pass, put each element into the HashTable. In the second pass, for each element, search for the element (Sum - current element). At the end of the two passes we will have our solution.
Time Complexity is O(N)

I was asked to assume memory is a constraint, so ended up writing code for the proposal (2) using Sorting.

This was a very open ended question and I'm guessing they are looking to see what kind of assumptions the candidate makes and whether all possible base cases have been covered.
I did not make it through this test despite having submitted a working solution. I am pretty sure that means there were either test cases that I missed handling or that I made incorrect assumptions.
Following are the assumptions I made:
1) Delimiters or separators between words are only one or more spaces.
2) The given input could be a bad string, meaning there could be trailing or leading spaces (OR) words could be separated by one or more than one spaces.
3) If the string cannot be justified perfectly, justify as much as possible.
4) If the string cannot be justified perfectly, after as much justification as possible leave the additional buffer empty at the trail.
5) If the buffer is insufficient or the input string is invalid, return the input string itself.
6) If there is no justification necessary (ex - if the input string is just one word and the buffer size is large), leave the rest of the buffer empty (leave spaces)

Following is code that goes along with all my assumptions:

/*
	 * This is the method that will justify the line.
	 * It will return a justified result as a string of the given buffer length.
	 * If the input does not allow to justify the line, then the line itself is returned.
	 */
	public String justify(String inputLine, int bufferLength)
	{
		//If the inputLine happens to be invalid we return the given line itself.
		if(inputLine==null)
			return inputLine;
		
		int inputStringLength = inputLine.length();
		
		//If the inputLine happens to be invalid we return the given line itself.
		if(inputStringLength<=0)
			return inputLine;
		
		int numberOfWords = 0;
		int effectiveInputStringLength = 0;
		
		//There may be trailing spaces leading to the first word in given line.
	    int indexOfFirstWord = getCharIndexOfNextWord(inputLine,inputStringLength,0);
		
		/*Counting the number of words assuming the following about the input: 
		 * 1) two words may be separated by more than one space characters
		 * 2) the first word in input need not start from the first character (could be a trail of spaces)
		 * 3) the only possible delimiter between 2 words is one or more spaces
		 * 4) The last word may be followed by one or more spaces
		 */
		for(int charIndex = indexOfFirstWord; charIndex<inputStringLength; charIndex++)
		{
			if(inputLine.charAt(charIndex) == ' ')
			{
				numberOfWords++;
				charIndex = getCharIndexOfNextWord(inputLine,inputStringLength,charIndex);
				if(charIndex==-1)
				{
					numberOfWords--;
					break;
				}
					
			}
			effectiveInputStringLength++;
		}
		
		numberOfWords++;
		int numberOfSpacesNeeded = numberOfWords - 1;
		
		//effectiveInputStringLength is the length of the line as it would be if there was only one space between 2 words and no trailing spaces.
		effectiveInputStringLength = effectiveInputStringLength + numberOfSpacesNeeded;
		
		//If the provided buffer length is too small or just equal.
		if(bufferLength<=effectiveInputStringLength)
		{
			System.out.println("Buffer Length is too small to justify the input line.");
			return inputLine; // returning input line itself
		}
		
		int extraBufferAvailable = bufferLength - effectiveInputStringLength;
		int numberOfExtraPossibleSpaces = 0;
		int numOfSpacesAtTheEndOfBuffer = 0;
		
		if(numberOfSpacesNeeded!=0)
		{
			//We can justify perfectly
			if(extraBufferAvailable % numberOfSpacesNeeded == 0)
			{
				System.out.println("We will be able to justify this line accurately");
				numberOfExtraPossibleSpaces = extraBufferAvailable/numberOfSpacesNeeded;
			}
			
			//We can justify only as much as possible. Last word ends before last available buffer index.
			else
			{
				System.out.println("We will NOT be able to justify this line accurately. But"
						+ " we will justfiy as much as possible such that the first word starts"
						+ "from the first character but the last word ends before the last available buffer index.");
				numberOfExtraPossibleSpaces = extraBufferAvailable/numberOfSpacesNeeded;
				numOfSpacesAtTheEndOfBuffer = extraBufferAvailable % numberOfSpacesNeeded;
			}
			numberOfExtraPossibleSpaces = numberOfExtraPossibleSpaces+1;
		}
		
		else
		{
			numOfSpacesAtTheEndOfBuffer = extraBufferAvailable;
		}
		
		StringBuilder justifiedStringBuilder = new StringBuilder(bufferLength);
		char currentChar;
		
		for(int charIndex = indexOfFirstWord; charIndex<inputStringLength; charIndex++)
		{
			currentChar = inputLine.charAt(charIndex);
			
			if(currentChar != ' ')
			{
				justifiedStringBuilder.append(currentChar);
			}
			else
			{
				charIndex = getCharIndexOfNextWord(inputLine,inputStringLength,charIndex);
				if(charIndex==-1)
				{
					break;
				}
				
				addSpacesToResult(justifiedStringBuilder,numberOfExtraPossibleSpaces);
				currentChar = inputLine.charAt(charIndex);
				justifiedStringBuilder.append(currentChar);
			}
		 }
		
		if(numOfSpacesAtTheEndOfBuffer>0)
		{
			addSpacesToResult(justifiedStringBuilder,numOfSpacesAtTheEndOfBuffer);
		}
		
		return justifiedStringBuilder.toString();
	}
	
	

	private void addSpacesToResult(StringBuilder justifiedStringBuilder,
			int numberOfExtraPossibleSpaces) {
		for(int noOfSpaces = numberOfExtraPossibleSpaces; noOfSpaces>0; noOfSpaces--)
		{
			justifiedStringBuilder.append(' ');
		}
		
	}



	private int getCharIndexOfNextWord(String inputLine, int inputStringLength,
			int currentIndex) {
		for(int charIndex = currentIndex; charIndex<inputStringLength; charIndex++)
		{
			if(inputLine.charAt(charIndex)!=' ')
			{
				return charIndex;
			}
		}
		
		return -1;
	}
	public static void main(String[] args) {
		CodingChallenge mycodeChallenge = new CodingChallenge();
		String[] input = {"The quick brown fox jumps over the lazy dog.",
				"The", "     The     ", null, "     The quick brown fox jumps over the lazy dog.",
				"The quick brown fox        jumps over the lazy dog.     ", 
				"The quick      brown      fox jumps over the      lazy dog."
		};
		String res;
		for(String s:input)
		{
			res = mycodeChallenge.justify(s,52);
			System.out.println(res);
		}
	}

It would be very helpful if anyone had suggestions about where I may have faltered in my code or test cases or any of the assumptions made.

This question is really straight forward if more than one passes are allowed. The following are the approaches for more than one passes:

1) Brute Force: Simple O(N^2) solution, compare each character with all the remaining characters.
2) Using a Hashtable: O(N) solution, populate the Hashtable (lets say HashMap) in the first pass. The HashMap contains the character and the count of the character occurrences.
In the second pass, we can look at the count in the HashMap and figure out the the first unrepeated.

Single Pass Solution:
Use a combination of HashMap<Character, DoublyLinkedList> and Doubly Linked List.
1) If the character is not present in the HashMap, we add the a node to the doubly linked list and to the HashMap.
2) If the character is already present in the HashMap and has occurred only one time before (count of occurrences of character maintained in a different HashMap), we delete the node from the doubly linked list.
3) If the character is already present in the HashMap and has occurred more than one time before simply update the count in the HashMap that maintains the count.

Maintain the head of the doubly linked list in a separate reference throughout the pass, the value of this node will be the first unrepeated character.

Solution for the single pass HashMap and Doubly Linked List proposal:

public Character getFirstUnrepeatedCharacter(String inputString)
	{
		if(inputString==null)
			return null;
		
		int inputLength = inputString.length();
		
		if(inputLength<=0)
			return null;
		
		Map<Character,DoublyListNode> charHash = new HashMap<Character,DoublyListNode>();
		Map<Character,Integer> charCountHash = new HashMap<Character,Integer>();
		
		DoublyListNode firstUnrepeatedChar = null;
		DoublyListNode lastUnrepeatedChar = null;
		Character currentChar;
		DoublyListNode refCharNode;
		Integer currentCharCount;
		
		for(int charIndex=0; charIndex<inputLength; charIndex++)
		{
			currentChar = inputString.charAt(charIndex);
			refCharNode = charHash.get(currentChar);
			
			if(refCharNode==null)
			{
				DoublyListNode nodeToBeAdded = new DoublyListNode(currentChar);
				firstUnrepeatedChar = addDoublyNodeToList(firstUnrepeatedChar, lastUnrepeatedChar, nodeToBeAdded);
				lastUnrepeatedChar = nodeToBeAdded;
				charHash.put(currentChar, nodeToBeAdded);
				charCountHash.put(currentChar, 1);
			}
			
			else
			{
				currentCharCount = charCountHash.get(currentChar);
				if(currentCharCount==1)
				{
					firstUnrepeatedChar = removeDoublyNodeFromList(firstUnrepeatedChar, lastUnrepeatedChar, refCharNode);
					if(lastUnrepeatedChar == refCharNode)
					{
						lastUnrepeatedChar = lastUnrepeatedChar.prev;
					}
				}
				
				charCountHash.put(currentChar, currentCharCount+1);
			}
			
			DoublyListNode current = firstUnrepeatedChar;
			
			while(current!=null)
			{
				current = current.next;
			}
		}
		
		if(firstUnrepeatedChar==null)
			return null;
		
		return firstUnrepeatedChar.element;
	}



	private DoublyListNode removeDoublyNodeFromList(DoublyListNode firstUnrepeatedChar,
			DoublyListNode lastUnrepeatedChar, DoublyListNode refCharNode) {
		if(firstUnrepeatedChar == refCharNode)
		{
			if(firstUnrepeatedChar.next==null)
			{
				firstUnrepeatedChar=null;
				lastUnrepeatedChar=null;
			}
			else
			{
				firstUnrepeatedChar = firstUnrepeatedChar.next;
			}
		}
		
		else
		{
			if(lastUnrepeatedChar != refCharNode)
			{
				refCharNode.next.prev = refCharNode.prev;
			}
			refCharNode.prev.next = refCharNode.next;	
		}
		
		return firstUnrepeatedChar;	
	}

	private DoublyListNode addDoublyNodeToList(DoublyListNode firstUnrepeatedChar,
			DoublyListNode lastUnrepeatedChar, DoublyListNode nodeToBeAdded) {
		
		if(firstUnrepeatedChar==null)
		{
			firstUnrepeatedChar = nodeToBeAdded;
		}
		
		else
		{
			lastUnrepeatedChar.next = nodeToBeAdded;
			nodeToBeAdded.prev = lastUnrepeatedChar;
		}
		
		return firstUnrepeatedChar;
	}

class DoublyListNode
{
	char element;
	DoublyListNode next;
	DoublyListNode prev;
	
	DoublyListNode(char element)
	{
		this.element=element;
	}
}

We could create an object let us call it a 'Cab' object that looks something like this -

class Cab
{
int x;
int y;
double distance; //distance between (p,q) and (x,y)
}

Now create a MaxHeap (based on distance) of size 5 by adding the first 5 Cab objects. For each object after the 5th Cab object follow the algorithm below:

if(distance(new object) < distance (root))
  delete root (max object) and add new object.

else
   ignore new object

After traversing all the Cab objects, the 5 objects left in the heap are 5 closest cabs.

The heap solution would make sense if k closest stars to the earth are asked.

Assume the number of arrays in the given list are 'k'.
1) Create an array of size k so that each index in the array maintains the individual indices from the k arrays index[].
2) Create another array of size 'k' and this array should contain the max number of elements possible in each of the given arrays.
3) Create a MinHeap of size k, with first elements from each array. The MinHeap would be a heap of Objects that contain the (element value, array number that the element came from)
4) Delete the root element from the heap (it would be the minimum element) and add its to the result list.
5) If the array that the deleted element came from is not entirely visited increment the index of this array in the index[] and add this new element at the incremented index to the MinHeap.
6) Repeat steps 4 & 5, until all arrays are not completely visited and then return the result list.

No. That is invalid. (<str>) would be valid.

Well.. the Sets sure should have same identical integers.
But I don't see you comparing the Sets, you converted the 2 sets into 2 arrays and compared the 2 arrays element by element sequentially.. It will fail there as the integers in both arrays though the same, wouldn't be the same sequentially.

Yes. The validation in step 3 should be customized accordingly. Which is why I called it tricky :)

Clean code. Accurately solves the first part of the question.

It is not a BST, its only a BT. The above solution would work correctly for a BST only if you had done an Indorder traversal instead of a preorder because it looks like you are expecting both arrays to be sorted.

Step 1: Do a simple Inorder traversal of the first tree & save each integer in a Map1<Integer value, number of occurrences>

Step 3: Do a simple Inorder traversal of the second tree & save each integer in Map2, also, check whether each integer is present in the Map1 or not.

If not present, we return false right away.
If present, if the number of occurrences is only 1 (value in Map1), we delete the element else we simply decrement the count.

Step 4:
If your Map1 is empty, it means all the elements are present, return true.

If Map1 is not empty, validate the remaining elements are present in Map2. If yes, return true, else false.

Time complexity: O(m+n)
Space Complexity: O(m+n)

The idea here is to use a stack. Since the parenthesis that opens last must close first, last in first out.

Step 1: Begin iterating over the given string character by character.

Step 2: If your current character is an opening parenthesis then push onto the stack.

Step 3: If your current character is a closing parenthesis then pop from the stack and validate if the current character matches appropriately with the popped element.

ex - if currentChar=']' then popped element should be '['. If they don't match or your stack is empty and there is nothing to pop then return false right away.

Step 4: By the end of the string your stack is empty then your string is valid and we return true.

Extension:

Most of the steps would remain the same, except that we could initially save all the values (NOT Keys) of the Map into a Set.

Now we could perform the earlier steps and to identify if the current character is an opening of a parenthesis we simply query the key in the given map & to identify the current character represents the closure of a parenthesis we query from our Set.
I felt the validation in Step 3 was a little tricky.

Time complexity is O(n)
Space complexity is O(m+n)
n - size of the string
m - number of elements in the given map

He couldn't have been. HashMap would take up unnecessary space and not give a resolve to the question at hand.
We use a HashMap when we want a key value pair and the requirement is something like, how will you find out how many tweets a particular movie got.
Here what is asked is not the number of tweets a movie got, but the movie which got the max number of tweets, a Heap generally solves questions like find the maximum or minimum number in a lot of data (maybe a stream) or questions like find the 10 or 20 or 'k' movies with the maximum tweets.
Hope this helps!

Oh you meant we should create a hashtag when you said Hashing. I would just ask the interviewer how a tweet is identified to be that of so n so movie.
He may suggest hashtag or an id associated with the tweet or the movie name. All work for us. We construct our Tweet object accordingly.

How would hashing benefit in any way? We are looking for a max count here.
A Hashtable could possibly be useful if you intend to query the number of tweets for a given movie as input, which is not the case here.

Use a Max Heap of something called 'Tweet' objects.

Each of these Tweet objects will have attributes like 'Movie Hashtag' which would be a unique identifier, another attribute called 'Number of Tweets' which would be used to decide the position of an object in the Max Heap.

At any given time the root element would be the most tweeted movie.

Solution is O(1) time.

However, the O(1) time is only for the query of the most tweeted movie. This comes with a space cost of O(n) and the additional O(log n) time each time a new movie is tweeted about to maintain & rearrange the heap.

Yep. Counting solution was what I meant to say. <edited> :)

We could simultaneously calculate the given number as the question states it must be interpreted. At the same time we can add one to the least significant digit to return the same result array.
This will be a clean O(d) time & O(1) space solution, the only catch is when the number has all 9s, this is when the result array must have an extra element.

public static int[] getIncrementedArray(int[] a)
	{
		if(a==null || a.length==0)
			return null;
		
		int resultNumber = 0;
		int givenNumber = 0;
		int factor = 1;
		int carry=1;
		
		for(int i=a.length-1;i>=0;i--)
		{
			givenNumber += a[i]*factor;
			resultNumber = a[i] + carry;
			
			if(resultNumber==10)
			{
				a[i]=0;
				carry=1;
			}
			
			else
			{
				a[i]=resultNumber;
				carry=0;
			}
			factor*=10;
		}
		
		int[] res = null;
		
		if(carry == 1)
		{
			res = new int[a.length+1];
			res[0]=1;
		}
		System.out.println("Given Number is: " + givenNumber);
		
		if(carry==0)
		   return a;
		else
			return res;
	}

The solution has time complexity O(n) & space complexity of O(1) when all digits are not 9.
The solution has O(n) time complexity & O(n) space complexity when all digits are 9.

We basically need to perform a sort here, the result should be our greatest number.
Counting sort is a fit here.
The only additional space we need here is a bucket of size 10, which is technically still O(1) space. The time complexity will be O(n) where n is the number of digits.

public static int getGreatestNumber(int a)
	{
		if(a<=0)
			return Integer.MIN_VALUE;
		
		int[] bucket = new int[10];
		int currentNumber = a;
		int modNumber = 0;
		int numberOfDigits = 0;
		
		while(currentNumber>0)
		{
			modNumber = currentNumber % 10;
			bucket[modNumber]++;
			currentNumber=currentNumber/10;
			numberOfDigits++;
		}
		
		int multiplier = (int) Math.pow(10, numberOfDigits-1);
		int res = 0;
		int temp = 0;
		
		for(int i=9;i>=0;i--)
		{
			temp = bucket[i];
			while(temp>0)
			{
				res += i*multiplier;
				multiplier /=10;
				temp--;
			}
		}
		return res;
	}

Which is exactly what the solution smarthbehi proposed does. It picks one element randomly where all the elements have equal probability to be picked.

Since it says the 100 tasks are to be done sequentially, I don't see the need to use threads at all. Simply sequentially executing the tasks from the same thread would do.

Parse the given string from the end, character by character.
Here's a small snippet:

int res = 0;
int factor = 1;

for(int i = givenString.length()-1; i>=0; i--)
{
res = res + givenString.charAt(i)*factor;
factor = factor*10;
}

We have our integer we need.

The time complexity would be O(n).
'n' being the number of characters in the string.

1) Sort the smaller array O(m*log m)
2) Binary search each element in the larger array in the sorted array. O(log n)

Total Time complexity : O(m*log m + log n)

@gen-x-s A sign bit is present in all integer data types. A sign bit is the very first bit (MSB) i.e the leftmost.
There is no way one can introduce an extra bit in a given integer. Negation implies only making the sign bit which is 0 for positive numbers to 1 indicating a negative number. So, this algorithm is definitely O(1) when we talk of space :-)

If the tree is a complete binary tree. We can suggest a Heap solution.
Now talking about a general case where it may or may not be a complete BT:
1) Find the smallest element in the tree
2) Delete the smallest element you found & print the same
3) Rebalance the tree to ensure it still remains a BST.
Repeat steps 1 to 3 until you are done with all elements.
The algorithm is inefficient with O(n^2) time complexity but the desired O(1) space

Your solution would be valid only if it is a complete binary tree

I guess what the interviewer means by first repeating element should be clarified during the course of the interview as technically 3 is the one that gets repeated first and 1 is the first of the elements that is repeated.
So I guess that's perception based, in any case I think the same solution could be extended to cover both requirements with a few changes.

Use Negation.

Since the range is from 0 to n-1.
1) Iterate over the given array and go to the corresponding index of each value and change its sign to negative.
ex- For {1,2,3,0,3} since a[0]=1, we make a[a[0]] = -2 i.e a[1]=-2;
then a[a[1]] = -3
and so on.
2) When you encounter a value that is already negative after step 1 then that index is the repeated value.

public static int getRepeatedNumber(int[] a)
	{
		if(a==null || a.length==0)
			return -1;
		int currentIndex;
		
		for(int i=0;i<a.length;i++)
		{
			currentIndex=Math.abs(a[i]);
			
			if(a[currentIndex]<0)
				return currentIndex;
			else
				a[currentIndex]*=-1;
		}
		
		return -1;
	}

I have a feeling the question should be for numbers from 1 to n-1, which will ensure there is one duplicate. So, the above solution is only for 1 to n-1.
However, 0 can be simply handled with a flag I suppose.

@dhakkad13 absolutely! Thanks for pointing that out! :-)

Counting Sort would fit perfectly here.

Steps:
1) Create an array 'result[]' of size 10. So now, our index will range from 0-9.
2) Simply iterate over the given array of 10000 elements and maintain a count in the result[] array for each element.
3) Once step 2 is complete, iterate over the result[] array and enter the encountered values in the given array.
ex- If res[0] = 78 then enter 78 1s in the given array.
If res[9] = 345 then enter 345 10s into the given array
4) After step 3 we have our sorted array.

The time complexity here would O(n) and space complexity is O(1) as an extra array of 10 elements is used.

Code would be as follows:

public int[] sortGivenArrayOf1To10Range(int[] givenArray)
	{
		if(givenArray==null || givenArray.length==0)
			return null;
		
		int[] res = new int[10];
		
		for(int individualElement:givenArray)
		{
			res[individualElement-1]+=1;
		}
		
		int count=0;
		int j=0;
		
		for(int i=0;i<res.length;i++)
		{
			count=res[i];
			
			while(count>0)
			{
				givenArray[j++]=i+1;
				count--;
			}
				
		}
		
		return givenArray;
	}

First I think it would be best to clarify with the interviewer how we should compare users to establish uniqueness. Since the fields you mentioned are date, user and name he would most likely tell you that user is something like a userId that would be unique.

Now since the files are large in number and each have a considerable size, Hashtable is not an option and Sorting is definitely not!

Bitmaps or an array of bits would definitely be a good suggestion. This would mean we should enquire the range of the userId from the interviewer.

If a probabilistic estimate of the count would suffice then there are several cardinality estimation algorithms (extremely complicated) out there which give a space-accuracy tradeoff, that would be worth suggesting. Its certainly an open ended question.

Bitmaps seems to be the only possibility though, if the count required must be exact.

It appears to be a modified binary search question. I am assuming the question is to find the maximum element.
Solution would be to perform binary search with a modified condition to check the element adjacent to the middle element. The base cases get a little tricky.

/*
	 * Given a bitonic array in which there is an increasing
	 * sequence of ints followed by a decreasing sequence. We 
	 * are to find the largest value in such an array. The solution
	 * has O(log n) Time Complexity & O(1) Space Complexity.
	 */
	public int getMaxValueInBitonicArray(int[] a)
	{
		if(a==null)
			return Integer.MIN_VALUE;//returns negative infinity
		
		int l=0;
		int r=a.length-1;
		int m;
		
		while(l<=r)
		{
			m=(r-l)/2+l;
			
			/*
			 * This condition is super tricky, all base cases must be covered.
			 */
			if((m==0 && a[m]>a[m+1]) || (m==a.length-1 && a[m-1]<a[m]) || (a[m]>a[m-1] && a[m]>a[m+1]))
			  return a[m];
			
			if(a[m]<a[m+1])
				l=m+1;
			else
				r=m-1;
		}
		
		return Integer.MIN_VALUE;
	}

@erikihr: seriously! I was amazed to see a bunch of sorting solutions for this question!

1) I am assuming this is a Binary Tree to begin with

A simple non recursive (Iterative) approach is possible by trying to replace the recursion stack by our own stack, sort of a behavioral replication. Here are the steps:

a) Keep adding all the left nodes to the stack.
b) Once done with step 'a', pop the element from the stack and print it.
c) Once done with step 'b', add the node on the right of the popped element to the stack.
d) Repeat 'a','b','c' until the stack is empty & there are no elements left on the right.

The maximum size of the stack in the worst case would be O(n) as the height of the BT could be 'n' in the worst case.

Here's the java code:

/*
	 * Given the root of a BT. We must print the
	 * Inorder of this tree without recursion.
	 * The solution is O(n) time and O(n) space
	 * solution
	 */
	public void printInorderIterative(TreeNode root)
	{
		
		if(root==null)
			return;
		
		Stack<TreeNode> s= new Stack<TreeNode>();
		
		TreeNode current= root;
		
		while(!s.isEmpty() || current!=null)
		{
			while(current!=null)
			{
				s.push(current);
				current=current.left;
			}
			
			if(!s.isEmpty())
			{
				current=s.pop();
				System.out.print(current.element + " ");
				current=current.right;
			}
		}
	}

the question says the immediate right neighbor, not the rightmost.

Relax dude.. I wasn't saying it was you. But a possible BST in this scenario has worst case O(n) is correct and is what I stand by.
If you have your implementation to include rebalancing then you are right in you own way :)

some idiot down voted my generous and very correct explanation :(

Saying O(something) itself means worst case complexity.

You can argue that your approach has a better average complexity than O(n^2), but average complexity is not denoted by 'O'.

How do you figure that the tree behaves like a linked list and is infact a degenerate tree?
Consider a scenario where Array B is a sorted array in the increasing order. This would lead us to a completely unbalanced BST.
In such a situation the height of the tree = the number of nodes and add and search operations would both be O(n).
Your solution would no doubt be a good one to discuss with the interviewer, but the worst case time complexity would still be O(n^2)

For the operations other than max, a hashtable seems like the best fit like you assessed.

Yeah, the presence of the delete operation wouldn't allow things to be as simple as saving the max value in an extra variable.
Appears that the interviewer may have been looking for the same argument.

Adding an element to a BST is O(n) complexity and not O(log n).

Consider a binary tree with 3 elements {6,7,9). Now imagine you add 10 to it, starting from the root you will need to iterate through all the elements, in other words the height of the tree would also happen to be 'n' in case you have sorted elements in your array.

So, even for the BST solution you proposed the complexity would be O(n^2)

Thanks for your time & walk out of the interview.

Rubbish..

@diegum, thanks for pointing it out. My bad.

Simply iterate over the array with duplicates and add each element to a HashSet. If the add() method of the HashSet returns true we add the element to the new array, if it returns false we ignore the element.

Time Complexity: O(n)
Space Complexity: O(n)

public double getProductOfGroups(int[] inputArray)
	{
		if(inputArray == null)
			return Integer.MIN_VALUE;
		
		int n= inputArray.length;
		
		if(n==0)
			return Integer.MIN_VALUE; 
		
		double res = 1;
		
		for(int eachNumber : inputArray)
			res*= eachNumber; 
		
		return Math.pow(res, n-1);
		
	}