teli.vaibhav
 0of 2 votes
AnswersHow would you design Amazon Lockers?
 teli.vaibhav in United States
Amazon Lockers  Customers can use these lockers to have their products delivered. These lockers are physically available to customers at the same or several nearby zip codes. Report Duplicate  Flag
Amazon SDE2 design  0of 0 votes
AnswersThe amazon site was working just fine until yesterday. But in the past 24 hours processing the customer orders is taking a really long time.
 teli.vaibhav in United States
How would you debug and fix the issue?
When I asked if anything had changed in the past 24 hours, I was told several new products had been added after which the performance issues were noticed. Report Duplicate  Flag
Amazon SDE2 Debugging  3of 3 votes
AnswersGiven the root of a Binary Tree along with two integer values. Assume that both integers are present in the tree.
 teli.vaibhav in United States
Find the LCA (Least Common Ancestor) of the two nodes with values of the given integers.
2 pass solution is easy. You must solve this in a single pass. Report Duplicate  Flag
Amazon SDE2 Algorithm  1of 1 vote
AnswersYou are given 2 lists 
List 1: List<Demand> is a list of Demand objects.
List 2: List<Supply> is a list of Supply objects.
Return a result fulfillment List<Demand,List<Supply>>.
This means each demand could be satisfied by more than one supplies.class Demand { Date startDate; Date expirationDate; int quantity; } class Supply { Date startDate; Date expirationDate; int quantity; }
The Demand and Supply refers to that of groceries. You must map supplies to a demand only if the supply still has at least 3 days remaining to its expiration before the demand can be fulfilled.
 teli.vaibhav in United States
A demand is said to be fulfilled 24 hours after all demands have been mapped to correspondingly available supplies. Report Duplicate  Flag
Amazon SDE2 Algorithm  2of 2 votes
AnswersGiven a string with only parenthesis. Check if the string is balanced.
 teli.vaibhav in United States
ex 
1) "<({()})[]> is balanced
2) "<({([)})[]> is not balanced Report Duplicate  Flag
Amazon SDE2 Algorithm  1of 1 vote
AnswerWrite code for the partition subroutine in Quicksort.
 teli.vaibhav in United States Report Duplicate  Flag
Amazon SDE2 Algorithm  1of 1 vote
AnswerHow would you Design a HashTable?
 teli.vaibhav in United States
In what ways would you attempt to address collisions? Report Duplicate  Flag
Amazon SDE2 design  0of 0 votes
AnswersFor this problem, we would like you to think of a single line of text, and justify that text into a buﬀer,where the ﬁrst character of the line of text is in the ﬁrst spot in the buﬀer and the last character of textis in the speciﬁed slot in the buffer.
In ruby, you might deﬁne this function as follows:def justify(line, length)
It might be called like this:
puts justify("The quick brown fox jumps over the lazy dog.", 52)
It produces a string that looks like this:
 teli.vaibhav in United StatesThe quick brown fox jumps over the lazy dog. 1234567890123456789012345678901234567890123456789012 (You have 7 characters remaining in the buffer)
 Report Duplicate  Flag
RealSelf Software Engineer / Developer Algorithm  0of 0 votes
AnswersWhat is indexing in a database?
 teli.vaibhav in United States
What are the underlying data structures you think are involved in indexing of a database?
What are some upsides and downsides of using indexing? Report Duplicate  Flag
Yahoo Software Engineer / Developer Algorithm  0of 0 votes
AnswersGiven an array of integers. Find the surpasser count of each element of the array.
 teli.vaibhav in United States
"A surpasser of an element of an array is a greater element to its right"
ex 
Input: [2, 7, 5, 3, 0, 8, 1]
Output: [4, 1, 1, 1, 2, 0, 0] Report Duplicate  Flag
Yahoo Software Engineer / Developer Algorithm  1of 1 vote
AnswersGiven an array of integers and a sum 'S'. Find 2 integers in the array that add up to S.
 teli.vaibhav in United States Report Duplicate  Flag
Yahoo Software Engineer / Developer Algorithm  0of 0 votes
AnswersFind the first unrepeated character in a given string. Solve this in a single pass.
 teli.vaibhav in United States Report Duplicate  Flag
Yahoo Software Engineer / Developer Algorithm  0of 0 votes
AnswersGiven a list of sorted arrays, like List<int[]>. Prepare and return a single sorted list.
 teli.vaibhav in United States Report Duplicate  Flag
Amazon SDE2 Algorithm  0of 0 votes
AnswersGiven two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.
 teli.vaibhav in United States
ex
Tree1:
5
1 6
5 4 3 6
Tree2:
1
3 4
6 5
have identical integers. Report Duplicate  Flag
Amazon SDE2 Algorithm  1of 1 vote
AnswersGiven a string which may contain parenthesis. We must verify the validity of the string.
 teli.vaibhav in United States
ex
1) "<ad675+fkmfd>" is a valid string
2) "<[((kskfhdbh7)" is invalid
3) "[<<((shfs8))>>]" is valid
Extension to the question 
Suppose you had a hash table that told you how a parenthesis starts and how it ends as a key value pair, how would you then validate the string.
ex  <key,value> = < '(' , ')' > indicates '(' is a start parenthesis and ')' should be the end of that paranthesis.
<'A','&'> indicates that 'A' is a start parenthesis and '&' is the end parenthesis.
Note: Validity means a parenthesis that starts, must end. Report Duplicate  Flag
Amazon SDE2 Algorithm

1 Answer
Printing all permutations of a String with repeated characters
I wanna print all permutations of lets say a char[] array for simplicity. This array contains a few repeated characters.
 teli.vaibhav December 17, 2013
I need to get the result without going into any previous results.
ex say we have ['a','c','a','b']
I will print "aacb" when I encounter is the first time and I must not print it the second time, neither can I look into the previous result. Flag 
0 Answers
Time and Space complexity
Could someone tell me what the time and space complexity of an iterative + recursive algorithm would be?
 teli.vaibhav December 15, 2013
ex:
The following code snippet prints binary sequences. i.e if n=2,
The output is
00
01
10
11
public static void printBinarySequence(int n)
{
if(n<0)
return;
int[] temp = new int[n];
printBinarySequenceAux(n,0,temp);
}
private static void printBinarySequenceAux(int n, int d, int[] temp) {
if(d==n)
{
printArray(temp);
return;
}
for(int i=0;i<=1;++i)
{
temp[d]=i;
printBinarySequenceAux(n,d+1,temp);
}
} Flag 
7 Answers
Space complexity for Recursive Binary Search
Space complexity for Iterative Binary Search would obviously be O(1) but with the recursive algorithm I believe the stack would use O(log n) space. However, everywhere I read I see the worst case complexity for BS O(1). Could someone please help me understand.
 teli.vaibhav November 07, 2013 Flag
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.
 teli.vaibhav October 30, 2016This 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;
}
}

teli.vaibhav
October 30, 2016 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.
 teli.vaibhav July 06, 2016The heap solution would make sense if k closest stars to the earth are asked.
 teli.vaibhav January 07, 2016Assume 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.
 teli.vaibhav October 05, 2015Well.. 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 :)
 teli.vaibhav October 02, 2015Clean code. Accurately solves the first part of the question.
 teli.vaibhav October 02, 2015It 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.
 teli.vaibhav October 02, 2015Step 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> :)
 teli.vaibhav September 01, 2015We 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.length1;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, numberOfDigits1);
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;
}

teli.vaibhav
September 01, 2015 Which is exactly what the solution smarthbehi proposed does. It picks one element randomly where all the elements have equal probability to be picked.
 teli.vaibhav August 29, 2015Since 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.
 teli.vaibhav August 25, 2015Parse 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)
@genxs 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
 teli.vaibhav May 05, 2015I 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 n1.
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 n1, which will ensure there is one duplicate. So, the above solution is only for 1 to n1.
However, 0 can be simply handled with a flag I suppose.
@dhakkad13 absolutely! Thanks for pointing that out! :)
 teli.vaibhav February 13, 2015Counting Sort would fit perfectly here.
Steps:
1) Create an array 'result[]' of size 10. So now, our index will range from 09.
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[individualElement1]+=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;
}

teli.vaibhav
February 12, 2015 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 spaceaccuracy 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.length1;
int m;
while(l<=r)
{
m=(rl)/2+l;
/*
* This condition is super tricky, all base cases must be covered.
*/
if((m==0 && a[m]>a[m+1])  (m==a.length1 && a[m1]<a[m])  (a[m]>a[m1] && a[m]>a[m+1]))
return a[m];
if(a[m]<a[m+1])
l=m+1;
else
r=m1;
}
return Integer.MIN_VALUE;
}

teli.vaibhav
February 09, 2015 @erikihr: seriously! I was amazed to see a bunch of sorting solutions for this question!
 teli.vaibhav February 01, 20151) 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;
}
}
}

teli.vaibhav
January 29, 2015 the question says the immediate right neighbor, not the rightmost.
 teli.vaibhav January 08, 2015Relax 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 :(
 teli.vaibhav January 05, 2015Saying 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.
 teli.vaibhav December 30, 2014Yeah, 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.
 teli.vaibhav December 18, 2014Rubbish..
 teli.vaibhav August 06, 2014@diegum, thanks for pointing it out. My bad.
 teli.vaibhav June 06, 2014Simply 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, n1);
}

teli.vaibhav
June 06, 2014 Although as mentioned by several others the best and easiest way to ensure singleton behaviour would be by instantiating the class into the variable declaration, sometimes when the Singleton object has a lot of overhead and may or may not be used in your application, you should use lazy load and the best way to do it is by exploiting the 'volatile' keyword which ensures that the JVM supplies the latest version of Singleton within the Synchronized code.
public class Singleton {
private static volatile Singleton s;
private Singleton()
{
}
public static Singleton getInstance()
{
if(s == null)
{
synchronized(Singleton.class)
{
if(s==null)
{
s = new Singleton();
}
}
}
return s;
}
}

teli.vaibhav
May 04, 2014 Open Chat in New Window
When a customer selects for a delivery to be made
 teli.vaibhav October 30, 20161) 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.